This website uses cookies to improve user experience. By using our website you consent to all cookies in accordance with our Cookie Policy. X

Basics of tile-based engine part 2: path finding [advanced]

In the previous part I've talking a little about isometric view and how to achieve it a simplest way possible. This time around, just as promised, we will have a look at path finding in tile-based engine using one of the easiest methods available (but not the fastest). I am not really sure if the algorithm presented here has any specific name, but without a doubt it is the most direct way out of all possible solutions.
For all of you that are not interested in details I've prepared a class built around the whole algorithm, plus also a FLA file showing how to work with it: PathFind.zip
Running it will look like this:
(Pick a starting and an ending point but clicking any empty field. SPACE to create different map)

The idea behind the algorithm is quite simple and can be divided into two phases:
1. Target search. Starting for on of the chosen points we check, step by step, every tile in the neighborhood in search of the second specified point, while constantly saving current iteration step into the grid. These numbers are needed in the next phase.
Here is a code snippet from the example:

// ...
var vWrite:Vector.<Vector.<int>> = recreateTiles(tiles);
vWrite[startx][starty] = 1;
vWrite[endx][endy] = -1;
var vCheck:Vector.<Point>;
var vRead.<Point> = new Vector.<Point>();
			
var tile:Point;
var nStep:int = 2;
vRead.push( new Point(startx,starty) );
while(vRead.length != 0) {
				
	vCheck = vRead;
	vRead = new Vector.<Point>();
	for each(tile in vCheck) if(lookupTile(tile.x, tile.y, nStep, vRead,vWrite,vTile)) {
		return retracePath(tile.x,tile.y,nStep,vWrite);
	}
	nStep ++;
}
return null;
// ...
The lookupTile function looks for a next tile to be processed. If the end destination is anywhere in the 4 directions from the current tile, the loop ends and a found path is returned. In other cases vWrite is updated to hold new information, while any found tile is written into vRead to be processed in next iteration.
2. Path backtracking. Once we find our destination it is time to backtrack along the numbers saved in vWrite ,one by one to retrieve our path. Lets say the iteration stopped at 20 step - now we have start searching for the tile containing number 19, then 18, 17, and so on. Untill we reach number 1 which is the starting point (0 is used for tiles that were not checked).

Just a small note to finish this off: the algorithm can be speed up by executing it simultaneously on both starting and ending point, which means the path will be found when both of them meet each other half way through. This method was used in the attached example.
Next time we will have a look at the idea of "field of vision" in tile-based engines.