Archive for the ‘geometry’ Tag

Snapping a Point to a Line Segment

Following up yesterday’s post on hit-testing a point within a polygon, there’s one other key geometric function that the Lassie engine’s motion grid would required in order to support polygonal motion areas: that’s the ability to snap stray (out-of-grid) clicks onto grid lines.

This took a bit of digging around to get working correctly… specifically, I wanted the point to snap to a line segment, therefore the snapped point’s position needs to be limited by the extent of the segment’s two end points. Ultimately, the operation turned out to be pretty compact:

// Snaps point P to the nearest position along line segment AB.
// @param p: The point to snap.
// @param a: First point of the line segment.
// @param b: Second point of the line segment.
// @return: A new point object with "x" and "y" coordinates.
function snapPointToLine(p, a, b) {
    var ap1 = p.x-a.x,
        ap2 = p.y-a.y,
        ab1 = b.x-a.x,
        ab2 = b.y-a.y,
        mag = ab1*ab1 + ab2*ab2,
        dot = ap1*ab1 + ap2*ab2,
        t = dot/mag;

    if (t < 0) {
        return {x: a.x, y: a.y};
    } else if (t > 1) {
        return {x: b.x, y: b.y};
    } else {
        return {x: a.x+ab1*t, y: a.y+ab2*t};
    }
}

Give it a try:

var a = {x:0, y:0};
var b = {x:50, y:50};
snapPointToLine({x:0, y:50}, a, b); // {x: 25, y: 25}
snapPointToLine({x:100, y:100}, a, b); // {x: 50, y: 50}
Advertisements

Polygon Hit Test with Ray Casting

Another old project that I’ve been digging back into with JavaScript recently has been the Lassie engine’s geometry system. Now, first and foremost, that’s NOT to say that the Lassie engine is in production for HTML5 (coding in my free time is not among my current priorities!). However, I’ve always found Lassie’s point-and-rectangle grid system to be archaic, and in all honesty, the only reason for that is because I’ve never taken the time to figure out polygon math. So, I’ve been tinkering with this…

The first thing that Lassie’s grid system would need to support polygons is a way to hit-test points against a polygonal area. A quick Google search on this led to an old (and shockingly simple) technique called ray casting.

The premise of ray casting involves extending a ray in one direction from the target point, and then counting how many times that ray intersects sides of the polygon in question. If the intersection count is an even number, then we can assume that the ray has both entered and exited the polygon’s boundaries an equal number of times, therefore placing the point outside of the polygon. However, if the intersection count is an odd number, then the point has entered but never left the bounds of the polygon and is therefore inside. Amazing that such a simple test holds up.

In JavaScript:

// Tests for counter-clockwise winding among three points.
// Specifically written for an intersection test:
// Uses ">=" (rather than ">") to cast equal points as valid CCW components.
function ccw(x, y, z) {
    return (z.y-x.y) * (y.x-x.x) >= (y.y-x.y) * (z.x-x.x);
}

// Tests for intersection between line segments AB and CD.
function intersection(a, b, c, d) {
    return ccw(a, c, d) !== ccw(b, c, d) && ccw(a, b, c) !== ccw(a, b, d);
}

// Performs ray casting, testing if point P falls within a polygonal region.
// @param p: The point to test.
// @param poly: An array of points forming a polygonal shape.
// @return: true if point falls within polygon.
function hitTestPolygon(p, poly) {
    var sides = poly.length,
        origin = {x:0, y:p.y},
        hits = 0,
        s1,
        s2,
        i;

    // Test intersection of an external ray against each polygon side.
    for (i = 0; i < sides; i++) {
        s1 = poly[i];
        s2 = poly[(i+1) % sides];
        origin.x = Math.min(origin.x, Math.min(s1.x, s2.x)-1);
        hits += (intersection(origin, p, s1, s2) ? 1 : 0);
    }

    // Return true if an odd number of hits were found.
    return hits % 2 > 0;
}

You’ll see our test uses three methods. First, ccw() tests for counter-clockwise winding among three points. Using that, we can test intersection() between two line segments by testing if the points of either segment wind into one another. Finally, we can perform ray casting by testing a target point’s line to an exterior point against each line segment in the polygon, and counting the number of intersections that are registered. Keep in mind that point order of your polygon array does matter (although the hit test still seems to work for oddly-wound polygons with intersecting sides). To see the hit test in action, try this:

var poly = [
    {x:10, y:10},
    {x:100, y:25},
    {x:125, y:125},
    {x:25, y:100}
];
hitTestPolygon({x:50, y:50}, poly); // true
hitTestPolygon({x:15, y:50}, poly); // false

A* Pathfinding With AS3

When I earned my degree as a designer, I never thought I’d end up writing a blog post about AI. However, I took a crack at writing an A* (A-star) pathfinding algorithm about five years ago for the avatar movement system in the first generation of the Lassie Engine (built using Macromedia Director and Lingo). My entire source of reference for that first implementation was The Beginner’s Guide to Pathfinding Algorithms. If you’re interested in pathfinding theory, that article is an absolute gold mine. I won’t even pretend that I could do a better job of explaining the algorithm’s nuts and bolts, so I’ll just stick to what an AS3 implementation looks like.

First, we need a data structure of a grid to run searches across. I’m generally drawn to XML for raw data structures like this since it’s easy to compose and maintain by hand. Here’s a simple XML grid of points:

Save as: grid.xml

<nodes>
    <node id="n1" x="25" y="25" join="n2,n3"/>
    <node id="n2" x="110" y="110" join="n1,n3,n4"/>
    <node id="n3" x="50" y="180" join="n1,n2,n5,n6"/>
    <node id="n4" x="225" y="90" join="n2,n5,n6"/>
    <node id="n5" x="190" y="160" join="n3,n4"/>
    <node id="n6" x="230" y="170" join="n3,n4"/>
</nodes>

The above XML creates a grid that looks like this:

demo grid of points

That XML structure is extremely simple. Each node is given an ID, an X and Y coordinate, and has a comma-separated list of other node ID’s that it connects to.

Next, we move on to the simple geometry structures that we’ll feed into our pathfinder. First is the Node object. While we’ll load our grid data as XML, we’ll want to parse that into typed Objects to give our implementation compile-time validation. So, we’d load our XML and then parse the nodes into this structure:

Save as: com/lassie/player/geom/Node.as

package com.lassie.player.geom
{
    import flash.geom.Point;

    public final class Node extends Point
    {
        // public
        public var id:String = "";

        // private
        private var _neighbors:Array;

        public function Node(key:String="", x:int=0, y:int=0):void
        {
            super(x, y);
            id = key;
            _neighbors = new Array();
        }

        /*
        * Returns all current data as a new Node object.
        */
        public function cloneNode():Node
        {
            var node:Node = new Node(id, x, y);
            node.parseNeighbors(_neighbors.join(","));
            return node;
        }

        /*
        * Parses a list of comma-seperated node id's into the array of neighbors.
        */
        public function parseNeighbors(csv:String):void
        {
            for each (var j:String in csv.split(",")) addNeighbor(j);
        }

        /*
        * Adds a new neighbor Id.
        */
        public function addNeighbor(id:String):void
        {
            if (!containsNeighbor(id) && id != "") _neighbors.push(id);
        }

        /*
        * Gets a neightbor Id by numeric index.
        */
        public function getNeighbor(index:int):String
        {
            if (index >= 0 && index < _neighbors.length) return _neighbors[index];
            return null;
        }

        /*
        * Gets the number of neighbors assigned to this node.
        */
        public function get numNeighbors():int
        {
            return _neighbors.length;
        }

        /*
        * Tests if the specified node id is among this node's neighbors.
        */
        public function containsNeighbor(id:String):Boolean
        {
            return _neighbors.indexOf(id) > -1;
        }

        /*
        * Appends an additional namespace key onto all Node references. Avoids conflicts during Grid unions.
        */
        public function expandNamespace(key:String):void
        {
            id += key;
            for each (var j:String in _neighbors) j += key;
        }

        /*
        * Trace object to string.
        */
        public override function toString():String
        {
            return "[Node] id:"+ id +", x:" + x + ", y:" + y + ", neighbors:(" + _neighbors + ")";
        }
    }
}

Now we need a Path object. Paths will be the actual search routes that our A* algorithm will create, branch, prioritize, and purge as it works. Here’s the Path class:

Save as: com/lassie/player/geom/Path.as

package com.lassie.player.geom
{
    public final class Path
    {
        // public
        public var length:int = -1;
        public var bestCase:int = -1;
        public var nodes:Array;

        // private
        private var _path:Array;

        public function Path($length:Number=-1, $bestCase:Number=-1, $path:Array=null):void
        {
            length = $length;
            bestCase = $bestCase;
            _path = ($path != null) ? $path : new Array();
        }

        public function destroy():void
        {
            _path = null;
            nodes = null;
        }

        /*
        * Returns all current data as a new Path object.
        */
        public function clone():Path
        {
            return new Path(length, bestCase, _path.slice());
        }

        /*
        * Tests if path has been initialized with actual pathing data.
        */
        public function get hasLength():Boolean
        {
            return length + bestCase >= 0;
        }

        /*
        * Returns the last node id contained within the path.
        */
        public function get lastElement():String
        {
            return _path.slice(-1)[0];
        }

        /*
        * Tests if this path contains a node Id.
        */
        public function containsNode($id:String):Boolean
        {
            return _path.indexOf($id) > -1;
        }

        /*
        * Adds a node to the path if not already present.
        */
        public function addNode($id:String):void
        {
            if (!containsNode($id)) _path.push($id);
        }

        /*
        * Trace object to string.
        */
        public function toString():String
        {
            return "[Path] length:"+ length +", nodes:("+ _path +")";
        }
    }
}

And finally we need a grid class. A Grid will hold Nodes, keyed by their respective Id’s, and will have the actual A* implementation within it to do the heavy lifting of grid searches.

Save as: com/lassie/player/geom/Grid.as

package com.lassie.player.geom
{
    import flash.geom.Point;

    public final class Grid extends Object
    {
        private var _nodes:Object;

        public function Grid():void
        {
            super();
            _nodes = new Object();
        }

        /*
        * Parses an XML structure into the grid object.
        */
        public function parseXML($xml:XML):void
        {
            // loop through all <node> XML items
            for each (var $nodeXML in $xml.children())
            {
                // create a new Node object for each XML item
                var $node:Node = new Node($nodeXML.@id, $nodeXML.@x, $nodeXML.@y);
                $node.parseNeighbors($nodeXML.@join);

                // register node by Id within the grid
                _nodes[$node.id] = $node;
            }
        }

        /*
        * Gets a node object by ID name
        */
        public function getNodeById($id:String):Node
        {
            if (_nodes[$id] != undefined) return _nodes[$id] as Node;
            return null;
        }

        /*
        * Finds the shortest path between two nodes.
        */
        public function findPath($startId:String, $goalId:String):Path
        {
            // queue of paths to search
            var $stack:Array = new Array(new Path(0, 0, [$startId]));
            // best path to goal
            var $best:Path = new Path();
            // shortest distance to each node reached thus far
            var $reachedNodes:Object = new Object();
            // cycle counter (for debug and optimization)
            var $cyc:int = 0;

            // UNTIL ALL SEARCH PATHS HAVE BEEN ELIMINATED
            while ($stack.length > 0)
            {
                // pull the first path out from the search stack
                var $searchPath:Path = $stack.shift() as Path;

                // pull the last node element from the path
                var $searchNode:Node = getNodeById($searchPath.lastElement);

                // EXTEND PATH ONE STEP TO ALL NEIGHBORS
                // creating X new paths
                for (var j:int=0; j < $searchNode.numNeighbors; j++)
                {
                    // Branch: duplicate current search path as a new branch
                    var $branch:Path = $searchPath.clone();

                    // Pull and expand upon each of searchNode's neighbor Id's.
                    var $expandNode:String = $searchNode.getNeighbor(j);

                    // REJECT PATHS WITH LOOPS
                    // if branch does NOT already contain next search node
                    if (!$branch.containsNode($expandNode))
                    {
                        // get coordinates of previous, current, and goal nodes
                        var $prevCoord:Node = getNodeById($branch.lastElement);
                        var $currentCoord:Node = getNodeById($expandNode);
                        var $goalCoord:Node = getNodeById($goalId);

                        // extend branch after having referenced last end-point.
                        $branch.addNode($expandNode);

                        // UPDATE BRANCH LENGTH AND UNDERESTIMATE
                        $branch.length += Point.distance($prevCoord, $currentCoord);
                        $branch.bestCase = $branch.length + Point.distance($currentCoord, $goalCoord);

                        // TRACK SHORTEST DISTANCE TO EACH NODE REACHED
                        // attempt to pull a distance-to-node from the register of reached nodes.
                        // if node has not yet been reached, register it with the current branch length.
                        var $shortest:Number = $reachedNodes[$expandNode];
                        if (isNaN($shortest)) $shortest = $branch.length;

                        // TEST IF PATH IS WORTH KEEPING (keep if:)
                        // - if branch is as short or shorter than the best distance to the current expansion node
                        // - and if a best-path has not been found yet, OR if this branch's best case scenario is still shorter than the best path.
                        if ($branch.length <= $shortest && (!$best.hasLength || $branch.bestCase < $best.length))
                        {
                            // log as best path to current search node
                            $reachedNodes[$expandNode] = $branch.length;

                            // If the expansion node is the goal, save branch as the parth to beat.
                            // Otherwise, add the branch back into the search stack.
                            if ($expandNode == $goalId) $best = $branch;
                            else $stack.push($branch);
                        }
                    }
                }

                // PRIORITIZE SEARCH PATHS
                // sort paths by best-case scenario so that most likely paths are searched first.
                var $priority:Function = function($a:Path, $b:Path):int
                {
                    if ($a.bestCase < $b.bestCase) return -1;
                    else if ($a.bestCase > $b.bestCase) return 1;
                    else return 0;
                }
                $stack.sort($priority);
                $cyc++;
            }
            return $best;
        }
    }
}

Now let’s put all that together. Create a new Flash document in the root of your class path and put that “grid.xml” file in with it. Then in frame-1 actions of the root timeline, just add the following:

import com.lassie.player.geom.Grid;
var $xmlLoader:URLLoader = new URLLoader();
$xmlLoader.addEventListener(Event.COMPLETE, this._onXMLLoaded);
$xmlLoader.load(new URLRequest("grid.xml"));

function _onXMLLoaded($event:Event):void
{
    // retrieve the loaded XML data
    var $xml:XML = new XML($event.target.data);

    // create a new grid and parse the loaded XML into it.
    var $grid:Grid = new Grid();
    $grid.parseXML($xml);

    // find a path between two node Id's
    trace($grid.findPath("n1", "n5"));
    trace($grid.findPath("n1", "n6"));
}

If you run that script as is, you should get the following output:

[Path] length:298, nodes:(n1,n3,n5)
[Path] length:316, nodes:(n1,n2,n4,n6)

Those are traces of two separate path searches run across the grid. The first search connected n1 and n5 to one another through their common neighbor of n3. The second search took a dramatically different route from n1 to n6 that branched through n2 and n4. Why? Because it was slightly shorter to run through two connections rather take the single connection through n3.