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.

Filed under: Actionscript, Everything, Sokay Development