## Grid based games – Part 5.3: Pathfinding

Alright, the most important part of that mazing type tower defence game must be the pathfinding. Completely different from the given path games, a constant ‘re-pathing’ is neccessary. What we’ll do here is the basic thing. A backwards pathfinding with all nodes to create a flowfield. Heuristics are included to later check if there is a possible path (using the shortest path). There is a number of end nodes taken into account but only one start node yet. Creeps will later use the given direction of the node they are on.

Here is what we are going to create, have a little test:

A bit of code:

```function findPath()
{
for each ( var member in nodeArray )
{
member.visited = false;
member.g = 0;
member.h = 0;
member.f = 0;
}
path.graphics.clear();
var openList:Array = new Array();
var closedList:Array = new Array();
var wayPoint:Object = null;
openList.push(stringToNode("9.27"));
```

First thing here is the resetting of all assignments that will be set later. We need to reset the values whenever a new run of the findPath has to be done, though for optimization purposes some values could be left alone here. The endNode we push onto the open list here is one of positions we did set before.

```	while ( openList.length > 0 )
{
```

If in here was an argument like ‘wayPoint == startNode’, the algorithm would be equal to an A* and thus be faster. But one path is not what we are looking for.

```		openList.sortOn("f", Array.NUMERIC|Array.DESCENDING);
```

‘f’ is the combined value for the distance to the start (endNode here) and estimated distance to the end (startNode here).

```		wayPoint = openList.pop();
closedList.push(wayPoint);
```

Once we took the node with the smallest ‘f’ from the openList, we need its neighbors. The getPathNeighbors function is nearly equal to the getNeighbors function we used in the previous post.

```		var pArray = getPathNeighbors(wayPoint);

for each ( var pObj in pArray )
{
if ( closedList.indexOf(pObj) == -1 )
{
var travelValue:int = 0;
if ( pObj.u !== wayPoint.u && pObj.v !== wayPoint.v )
{
travelValue = 14;
}
else
{
travelValue = 10;
}
pObj.endNode ? travelValue = 0 : void;
```

For each neighboring node we set a travel value to the actual wayPoint. The distance is bigger if the direction is diagonal. If the neighbor is an endnode the travelValue is set to zero, because we want all endnodes to be treated the same.

```				if ( !pObj.visited )
{
pObj.endNode ? pObj.sourceNode = pObj : pObj.sourceNode = wayPoint;
pObj.g = travelValue + wayPoint.g;
pObj.h = Math.abs( pObj.u - startNode.u ) * 10 + Math.abs( pObj.v - startNode.v ) * 10;
pObj.f = pObj.g + pObj.h;
openList.push(pObj);
pObj.visited = true;
}
```

If we have not seen that node before, we calculate its f value and push it to the openList.

```				else
{
pObj.newG = travelValue + wayPoint.g;
if ( pObj.newG < pObj.g )
{
pObj.g = pObj.newG;
pObj.h = Math.abs( pObj.u - startNode.u ) * 10 + Math.abs( pObj.v - startNode.v ) * 10;
pObj.f = pObj.g + pObj.h;
pObj.sourceNode = wayPoint;
}
}
```

If we have it seen before we calculate g with the new wayPoint and if it is smaller set the new wayPoint as sourceNode.

```			}
}
}
}
findPath();
```

Right now the heuristics do not take diagonal travelling into account, but after all it basically works. You can still completely block the path with obstacles and the program would not hesitate to run. But these are topics for the next posts. Yoho!

### More articles in grid based games:

This entry was posted in as3, flash, Grid Based Games, grids, mochiads and tagged , , , , , . Bookmark the permalink.

### 17 Responses to Grid based games – Part 5.3: Pathfinding

1. JJ says:

keg does a marvelous job here, (he assumes you know the basics of path-finding) but in case some of you don’t, here is a good article that might get you started

“A* Pathfinding for Beginners”
http://www.policyalmanac.org/games/aStarTutorial.htm

Thanks again keg

2. OP says:

Will this tutorial series continue?

• kegogrog says:

If you have something, that you think should be next just tell me. I’d be happy to continue on this.

• OP says:

Right now the heuristics do not take diagonal travelling into account, but after all it basically works. You can still completely block the path with obstacles and the program would not hesitate to run. But these are topics for the next posts. Yoho!

3. OP says:

How can I trace out the direction of a specific node?

• Siro says:

Also I’m interested to know about directions and I ask you: How can I use the Heuristic after loop “for each ( var pObj in pArray )”?? (I mean during playing the game)

Regards

• kegogrog says:

Hmm, from how I understand the question: Once the path (or field if we talk about the whole grid) is set, you’d just recall that routine when the grid is changed (e.g. by placing an object). With the set field you can determine the angle between two node (a node and its parent) with a simple `Math.atan2`. You can then apply this as rotation to the ‘wandering’ object. So, if I (the wandering object) am on node X, I have a look at its parent node, calculate the angle between them and set this angle (in degrees then) as my rotation (in one step or more). Thus, the direction I am facing after reaching a new node would always be the direction of my next target node.

Is that anywhere near to where you’ve aimed your question?

• Siro says:

Ok, for the angles, but can you explain to me how would you use the heuristic? In your article you wrote:”Heuristics are included to later check if there is a possible path (using the shortest path)”. Now I’m blocked at this point.
I’ve made the flowfield with f,g,h for every node, but I can’t figure out how to use it to find a shortest path from every single node to the goal.
At the end I must have the nodes in flowfield with x,y pointing to the the neighbor shortest node (node or cell).
Regards

• kegogrog says:

At the end I must have the nodes in flowfield with x,y pointing to the the neighbor shortest node (node or cell).

In that approach it would be the ‘sourceNode’ property (sorry for the naming). Since we went backwards the ‘sourceNode’ is actually the neighbor on the shortest path. So, basically you have the shortest path from each node to the goal (in nodewise steps of course) once the routine is finished.
The shortest path is just needed when you later place towers to have a quick check if you are blocking the way from the start to the goal. Then it would be a while loop and a check `if ( wayPoint.startNode ) break;`
I hope that helps a bit, if you want to be more specific just write me a mail. I’d really like to help you on that if I can.

4. OP says:

Nevermind, I figured it out.

But a little info on how to prevent blocking would be nice.

• kegogrog says:

Hmm, pretty simple. I’ll put something on here as soon as I can. As a hint: Build the shortest path when moving the mouse in ‘build’-mode. If there is no complete path, disable building. I have done it, just need to find it on my harddrive.

5. OP says:

Thanks!
Will fiddle around with the “build”-mode..