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!

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

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:

    forgot to ask:
    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).
        Thanks for your reply.
        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..

  6. Nick says:

    Either I’m missing a lot, or some info is left out of this tutorial. Don’t find anything explaining where to loop through nodes, what path is and when it is declared, what pObj is and when it’s created, how getPathNeighbors functions differently than in the previous tutorial, etc. I’m sure most of it is simply a semantic change from the recent tutorial, but I can’t seem to get it to present anything useful for me.

    • kegogrog says:

      Yes, it is crappy code. And I am deeply sorry for that.

      That said, you would loop through the nodes initially and once a tower is placed. path, from what it looks, is an overlaying sprite where the arrows are drawn, but it’s not further used in this code. So, just delete it. pObj is declared in for each ( var pObj in pArray ) though it doesn’t look good. getPathNeighbors seems to be the same as getNeighbors.

      Hmm, maybe I should do a reload of that. It can also be easily optimized using a FSM.

      • Nick says:

        Makes more sense now. I took a look at some different a* methods and got a working version, but yours seems to run far faster. I’ve tried several different heuristics, but I’m not really satisfied with either the accuracy of the quick ones or the speed of the best ones. Mind posting the source code for this so I can disect it in a little more detail?

      • Nick says:

        Figured out how to modify your code a bit to make it work with mine. The key was figuring out that the source node was actually used as the next node in series for a creep to travel to. If anybody is wondering, this pathfinding algorithm runs far faster than an a*/dijkstra algorithm on large grids, and is a much more viable solution as you can update creep movements easily as you don’t have to iterate through all enemies on screen finding a path for each of them. (My grid has a path found for it at a max time of 55 ms and decreases as obstacles/towers are added, whereas my a* algorithm takes 3 ms per creep and increases to around 300-350 ms per creep as the grid becomes filled with towers.)

  7. Siro says:

    Hi kegogrog You are very kind and helpful and I thank you very much for that!

    Give me youe email so we can talk more exhaustively.

    Regards siro
    siro13_AT_hotmail.it

Leave a Reply

Your email address will not be published.