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!