NorthStar is my new pathfinder for use with arbitrary, irregular polygons. CHECK IT OUT. Drag around the green and red circles. The green one is used as the start point and the red is the end

A couple months ago I decided I would begin working toward my long time dream of producing a real-time strategy game. I actually finished NorthStar and had this written a few weeks later, but I’m only posting now because I’ve been hard at work with the rest of the game! Now working on unit logic along with a new Sokay project (more on that later) and editing a new film (later still), so I been a little busy. Expect Demos.

I planned on basing the RTS engine on some of my previous work with physics (perhaps that sounds strange, but it makes sense). Step one was coming up with a pathfinder.

Demands:

  1. Irregular Polygons: I dislike tile-based systems and I already had groundwork in my physics engine for handling irregular polygons. I decided the RTS should implement the same ideas and therefore it cannot use traditional, tile-based pathfinding techniques.
  2. The Illusion of Intelligence: Paths must appear to have resulted from intelligent decision-making. I didn’t want to see units going on crazy birdwalks for no apparent reason like they often do in popular RTSes. I’m disgusted by the presence of such awful pathfinding in blockbusters like Blizzard’s Warcraft and Starcraft series. I want my units to use paths that make them appear intelligent.
  3. Forethought in Navigation: The path must be relatively efficient, demonstrating a knowledge of the overall terrain unless I specify otherwise.  If I want a unit to appear ignorant or lost, letting it wander is fine, otherwise it should not bother with any path that will not eventually lead it to the goal.
  4. Efficiency: I can’t have units lagging every time they decide to move somewhere and ideally I can have lots of units deciding to move to different places all at the same time. That means it’s gotta be quick.

A* Logic

I didn’t have any background in pathfinder’s, but Bryson had used the popular A* (“A star”) for his Liquid Generation puzzle game a while back and it seemed to work well for him.

The essence of A* is decision-making. It navigates a network of nodes by rating each one available and selecting the node with the best rating (making it a “best-first” algorithm). The rating function can be customized for a given project, but generally it is an optimistic estimation of the cost (in distance) of a path through a given node.

So imagine you have to walk around a car. The car may have one node on the left and another node on the right. If walking through the left node costs at least 15 steps, but walking on the right costs at least 10 steps, A* chooses to go right. It is “optimistic” in that walking to the right may eventually cost more than 10 steps, but walking to the left will cost at least 15 steps.

A*’s simplicity and effectiveness made it a good model from which to build NorthStar. But the reason A* is so easy to implement in so many games is because its nodes directly translate into tiles in a tile-based engine. I needed a way to describe a field of arbitrary polygons as nodes before I could apply any of that logic. This proved to be the real challenge.

Creating a Node Network from Arbitrary Polygons

Polygon Data

Using my old physics engine systems, I constructed polygons from movieClip points organized into groups. I drop the point movieClips onto the stage and convert groups of them into new movieClip instances, then the points automatically arrange their data into arrays at run-time. The result is a single array (_root.PolygonArray) indexing each individual polygon (_root.PolygonArray[p]) which are represented as arrays indexing vertices (_root.PolygonArray[p][v]) which are also arrays containing x and y values of the points (_root.PolygonArray[p][v].x , _root.PolygonArray[p][v].y). This is the polygon data I’m converting into nodes.

Some pathfinder’s handle this process by identifying all vertices as nodes and creating links between all of them that have no walls between them. That works, but it creates a very wasteful network. A pathfinder has to scan through all the options available before it can make a decision, therefore the pathfinder works most quickly with the least number of options. So yes, you can simply convert all polygon corners into nodes and link them all, but your pathfinder will be much more effective if you only create the most useful links. Plus, having extra links lying around may occasionally put pointless Sunday strolls in your path instead of keeping it nice and tight.

If a link is unnecessary, don’t create it! Having extra links around will just bog down your pathfinder while it scans the entire network for the best path.

Identifying a Good Link

I came up with this set of steps for determining whether or not a pair of nodes (A and B) should be linked to one another (read Filtering Links for a Lean Network for justification):

  1. Draw a line connecting vertex A to vertex B. Call this “lineAB”
  2. Find the two vertices neighboring vertex A and make sure they are both on the same side of lineAB.
  3. Find the two vertices neighboring vertex B and make sure they are both on the same side of lineAB. (They do not need to be on the same side as vertex A’s neighbors)
  4. Check for polygon walls blocking lineAB.

If each node’s neighbors are to one side of the link and no polygon walls are penetrated by it, the link is worth having.

The Math

You may be wondering how I applied those steps mathematically. To “Draw a line” between vertices A and B, I found the line in Slope-Intercept form that contains the two. To find out if their respective neighbors were on the same side of that line, I ran the x values for each neighboring vertex through the line’s equation. The result is the y value of a point (call it pointL) on the line with the same x value as the neighbor. If pointL has a y value that is greater than the a neighbor’s y value, it means that neighbor is below the line. If pointL has a smaller y value than the neighbor, the neighbor is above the line.

The only exception to this is when the slope of the line is Infinity (it points straight up and down when the 2 nodes being tested have the same x value and different y values). In this case, because the 2 nodes being tested have the same x values, you can detect which side each pair of neighbors is on by comparing their x values to the x value of either of the 2 nodes being tested.

Organizing Node and Link Data

I arranged link information in a new array called “nodeMap” which indexes each individual node. Each node is an array with point information in addition to being associated with a “link” array (nodeMap[n].link). The “link” array lists each of the nodes to which the current node is linked (nodeMap[n].link[m]). Each element in the “link” array is an array containing a reference to the linked node (at the zero position, [0]), and the distance between the two nodes (at [1]). A pair of linked nodes must have a reference to each other otherwise the link will only work in one direction.

The nodeMap grows as loops cycle through every vertex on every polygon, checking them against every other vertex in the field, converting polygon data into node data.

Pathfinding

Linking the Start and End Points to the Network

Now that the polygon map has been converted into a node map, the pathfinder must be given start and end points to represent the desired movement. These points can be anywhere on the field.

NorthStar uses logic just like the node linking process to link the start and end points to the node network. The start and end points are not vertices so they do not need to compliment any nodes to form a link and their linking process is a bit simpler than detecting links between nodes.

  1. Draw a line connecting startPoint to node A. Call this “lineSA”
  2. Find the two vertices neighboring node A and make sure they are both on the same side of lineSA.
  3. Check for polygon walls blocking lineSA.

(Run the same process with the endPoint in place of the startPoint.)

Finally, the network is ready to be analyzed.

Blazing the Path

Starting from the startPoint, a path is drawn from one node to the next, through link after link, until a node is reached that is linked to the endPoint. When the endpoint has been reached, the search is over. The path has been found.

NorthStar is continually updating a library of available options, starting with each of the links of the startPoint. Each time it moves from one node to another, it deletes the new node from its library of options and adds all of that node’s links to the library (except the one it came from).

When selecting the next node, it sorts the entire library by node rating. The one with the best rating is chosen to have its path grown until that path attains a worse rating than another option in the library. All available nodes are constantly checked against one-another so that NorthStar quickly abandon’s any paths that seem wasteful and returns to old paths with better ratings.

The Rating System

Breeding A* with a few other methods, I rated nodes according to an estimated cost in distance in addition to a few tie-breakers and special cases that would probably change from project to project.

I put rating data into arrays (you can probably tell I use arrays a lot). The first element in the rating array is the path distance required to get to the node. The second element is the estimated distance to the endPoint. These two are added together to get a rating value.

In most cases the estimated distance to the endPoint may simply be the distance of a straight path between the node and the endPoint (an optimistic estimation), however if possible, other information may be used to find an exact distance, like when the current node is indirectly linked to the endPoint. An indirect link is when a node can lead to the endPoint if at least one other node is used between the two.

Indirect Links

I implemented a check for indirect links into my rating system. It just scans to see if there are any links that a node has in common with the endPoint, then selects the one with the shortest path (if one or more exist). When this is used, the resulting rating is exact rather than an estimation.

Another way of taking advantage of indirect links is to create them between nodes as soon as a path is found between them. If the path has already been proven to be effective, you can indirectly link all the nodes within that path to each other and the path can be easily reused in the future without requiring a complete rescan of the network. I did this by adding a third element to any links between nodes that are indirect. This element is an array containing all nodes along the path between the two indirectly linked nodes, in order.

Finding Indirect Links Pre-emptively

I have a function for scanning a node network ahead of time to find all the shortest indirect links between all nodes on the field, but it’s a little buggy. With that implemented a ton of time can be saved because as soon as the start and end points have been linked to the network, you can instantly find a path between them by picking any of the nodes they’re linked to and finding the precalculated indirect link between those two nodes.

Why is the path so close to the obstacles?

Fair question. I haven’t bothered with checking unit thickness yet, so right now the path goes right up against walls and corners (offset by 1 pixel, just so it’s always clear when a unit is outside or inside a polygon).

There are 3 ways to solve this problem:

  1. The Ugly Way: Make the art for the obstacles smaller than the actual boundaries. Voila.
  2. The Bad Way: Add an outward extension to node locations by a given distance (equal to the radius of your unit). You may want to make that distance a value you can easily change so you can have units of different sizes.
  3. The Good Way: This requires that you do the same as in #2, but you also run checks to find out if the units have enough room to fit through all of the passages. Your pathfinder will have to ignore passages that are too thin to fit through. Do this and you never have to worry about units penetrating walls as they walk. (I’ve postponed this, using The Ugly Way in the meantime)

Result

As you can see in the demo, NorthStar’s workin quite well. It’s not 100% bug-free yet, but I’m very pleased with the results and it can easily be implemented into some games. After optimizing it some more, I’m confident I can have it running quick enough that it can be used for pathfinding in pretty huge settings. One method I haven’t seen in other pathfinders would involve generalizing start and end points so you don’t have to calculate linking them to the network so often.

More posts comin.

-Christopher J. Rock

Filtering Links for a Lean Network

The only way to clean up our network is to set up some rules for identifying a useful node link. Our pathfinder will work from the startPoint to the endPoint, but that order is not necessary. If we find a good path, it shouldn’t matter whether it started from the startPoint and worked to the endPoint or started at the endPoint and worked to the startPoint. Keep this in mind when I refer to “direct access” between points. If point A has direct access to point B, point B has direct access to point A.

  1. Links cannot penetrate polygon walls: Since you don’t want paths that lead directly through your polygons, you must check to see if a wall is blocking the path between a pair of nodes before declaring them linked.
  2. Nodes are only important as potential waypoints: Say you’re traveling from startPoint to endPoint. If an obstacle is blocking the way, you must find a waypoint with direct access to startPoint and endPoint. However, if startPoint has direct access to endPoint, it is unnecessary to use any waypoints when moving between them. Therefore, linking to a node is only useful if the node has direct access to a place that you currently do not. This rule describes finding links to your start and end points.
  3. All vertices must be recognized as nodes: Vertices are formed by walls. Walls block nodes from directly accessing areas of the field, but when two walls form a vertex, they do not block that vertex from accessing any point on the field. Therefore, a vertex formed by any two walls will be useful in providing access to spaces around those walls.
  4. Nodes must compliment each other: When the startPoint does not have access to the endPoint and linking to a single node achieves access, only 1 node is necessary. But if that node also has no access to the endPoint, it must use a 2nd node to achieve it. If the startPoint has direct access to this 2nd node, the 1st node can be skipped. In this case, the nodes do not compliment each other. On the other hand, if the startPoint does not have direct access to the 2nd node, it must use the 1st node to obtain it. Another way of looking at it is to say that the 1st node must have direct access to an area that the 2nd node does not (the startPoint) and the 2nd node must have direct access to an area the 1st node does not (the endPoint). The nodes must be linked to share their potential as waypoints. In this way, the pair of nodes compliment each other.
  5. Nodes will only form links on one side of their vertex: Every vertex forms a “V” shape pointing in some direction. As a result of rules 1 and 2, a node can only have links on the outside of the “V”. Therefore, vertices pointing into the polygon can be labeled “internal” because they will only link to other nodes within that polygon. External vertices, pointing out from the polygon, are only linked to nodes on the outside of the polygon.
About the author:
Christopher J. Rock (http://)
Film student at California State, Long Beach. I want to make the gaming world a better place.
  • I was just playing around with your pathfinder and wanted to know if you can expand it to take into account a certain shape or radius. Right now, the path will go directly along the contours of objects, and through thin gaps. If that was a character, it would be overlapping the environment — going through walls and such.

    If you added that in, I could think of a million things to use this for.

  • Near the end of the post there’s a small section titled “Why is the path so close to the obstacles?” which explains that issue.

    Like I said, at first the “ugly way” is good enough, but programming the good way is where I left off last. It’s been while since I got to work on NorthStar, but some of my latest work will apply to it very well. I’ll be building it from the ground up in AS3 for Flash10, which will bring huge performance gains (thanks to AVM2 as well as the new Flash 10 Vector class).
    I’ll be using some new equation classes that may allow me to implement curved paths as well. Those would be great for more organic and physics oriented movements. But curves introduce a bag of other issues that I won’t be bothering with for a while.

    I really need to post up some of my latest stuff. I think it has promise.

  • Nick

    Beautiful. Is there any way to allow it to handle the case in which no path exists? My attempts always lead to significant lag time when there is no solution.

  • NorthStar handles the “no path” situation very quickly because while it checks the nodes of a polygon, it also checks whether or not the start or endpoint is contained in that object. If one is contained in an object that the other is not, pathfinding stops.
    This test can be easily done in multiple ways.

    The essence of this to determine whether a point is contained by a polygon. You can do this with a hitTest on a DisplayObject, using a ray-cast method, or using the Rectangle Object’s “contains” function (for rectangular shapes only). The point is, you find out if the starting or ending points of a path are contained in a shape, and if so, you stop looking for a path around the shape.

    Northstar’s way is more complicated, but it comes for free with other functionality.

    Northstar
    Northstar checks containment by summing angle differences. For example, if you have a square and your path starts at the center of that square, the first corner checked might be at a -45 degree angle (A) from the center point. That would mean that (going clockwise) the next corner would be at 45 degrees (B), the next at 135 (C) degrees, and the last at -135 degrees (D).
    Now assume that we measure the distances between these angles only in a clockwise direction. The difference between -45 and 45 is then 90. The difference between 45 and 135 is 90, the difference between 135 and -135 is 90 (the measurement crosses over the -180/180 border) and the difference between -135 and -45 (returning to the start) is 90. Add up all the differences (90 + 90 + 90 + 90) and you get 360. (In flash the y axis points downward, so clockwise movement is an increase in angle; the opposite may be true elsewhere)
    A sum of 360 indicates that while measuring the angle of each corner, your “measuring stick” moved 360 degrees around the entire start point of the path. And that means that the start point is totally contained by the polygon. Therefore, there is no exit and no path to find.
    If the start point is outside of the square, the first corner of the point might be at 60 degrees, then the next at 30 degrees, the next at 150 and the last at 120. Measuring clockwise, angle differences are 30, -120, 30 and 60. Add them (30 + 30 + 60 – 120) and you get 0. 0 indicates that the starting point is outside of the polygon. The measuring stick moved half way right, moved all the way left, then moved all the way right, taking it back to the first corner, but without going 360 degrees around the point. Therefore, the point is not contained and there is a path around the polygon.
    This method also works if you measure counter-clockwise, but then your answer will be -360 for contained points.

    What’s Wrong with Other Methods
    I’m guessing your pathfinding system is tile-based. Tile-based pathfinding doesn’t involve any knowledge of barrier shapes, so you can’t calculate whether or not you can get through a shape without actually checking each tile that forms the shape’s edge. That’s why when there’s no way out of an object, the processing becomes intense.
    In this case, I suggest using a best-first system that doesn’t try to find an entire perfect path, it just guesses at the right direction and tries it. Your characters will move one step at a time, unaware of how they’ll ultimately get to their destination. Behavior won’t be as perfect, but it usually works very well, and you don’t have to worry about crashing. This is also a very popular method, used in games like the Warcraft series, so there’s no shame in it.

  • great stuff , i dont completely understand how it works but it shows really good results and performance i will have to take some free time to read carefully your method.

    thanks for sharing this information.

  • The pathfinder, although apparently very efficient, seems to have oversimplified some things. Place one endpoint deep in the left recess of the red shape, in the >-shaped area, and the other endpoint in the left concave nook in the cyan shape, above the green shape. You’ll notice that the path found goes along the red shape, brushes the dark blue’s corner, brushes the cyan’s corner, and – completely unnecesarily – bounces off the green’s corner, instead of going directly to the target. Why does it do that, I wonder…

  • … Odd, it no longer does that, after a reload. Must’ve been some leftover “convenient” shortcut link, misused…

  • Vemund

    Hey, your pathfinder seems to work pretty good! When i saw it i remembered this comprehensive library used for motion and behavior in games:
    library:http://opensteer.sourceforge.net/doc.html
    demos:http://www.red3d.com/cwr/steer/

  • Christopher J. Rock

    @Tentacled
    It’s not perfect. I was aware of one place I could break the pathfinder when I posted this, but I also figured it was good enough to demo. Since this was done in AS2, I haven’t been able to apply it to any current work in AS3, but I’ll post as soon as an update is complete!

  • Hi Chris,

    Do you publish NorthStar publically or is it a proprietary library? I’m an independent flash developer myself and I have a need for polygonal based boundary pathing for a game I’m working on and it seems you’ve already solved my problem. I’d love to try this library if you’re making it available.

    Nice work!

  • I’m ashamed to say I still haven’t brought NorthStar to as3 and I I stopped developing it after I made the transition myself…

    I’ll definitely put a post up when I get around to doing it, but there’s always a distraction.

  • Nothing to be ashamed of… I think many of us fall into the same boat frequently. 🙂

    You should set a milestone date for yourself and if you don’t get around to publishing it by then, you should open source it on google code or codeplex or something for the world to see and contribute to, rather than letting it rot. I know another developer who would be interested in using the API as well.

  • So, was this ever open sourced…?

  • So, was this ever open sourced…?

  • Pingback: Moncler()

  • Pingback: Pathing54 v0.2 « Code « Space Burger()