The basics of pathfinding – animated example

Talking about Actionscript 3, Flash and Game development.

This is the first step of a tutorial series which will guide you through the creation of pathfinding algorithms.

Pathfinding is the “art” of finding the shortest route between two points, and you can use it in several situations, such as when moving non-playing characters or when moving player controlled charachter if you use a “click to set destination” way to control it.

Before we start, let me clarify one thing: pathfinding works when the destination point is known. Also, being this just the first of a series of tutorials, I am going to show you a very basic and unefficent algorithm (but all in all, it works!), which will be improved and optimized until we’ll make the famous A* algorithm (and beyond!) in a very intuitive way.

I don’t want to publish “just another A* algorithm”, so following this series you will master the art of pathfinding rather than just copying some code. That’s why I built an animated example.

So, let’s examine the basics of this simple pathfinding algorithm:

* Given a start tile and a known end tile, I examine all tiles adjacent to start tile (no diagonals at the moment) which aren’t part of the path yet, and for each one I determine three values:

G: the cost of moving from start tile to examined tile. At the moment, I always leave it to 1.

H: the presumable distance from the examined to the end tile. I say “presumable” because I can only suppose the distance from current to end tile, as it may vary due to walls or movement cost. The easiest way to calculate the presumable distance is the Manhattan distance, which I’ll use in this example. If you need more information about Manhattan distance, check the blog post the fastest way to find the distance between two points.

F: simply G+H

* Once I examined all adjacent tiles, I pick the one with the lowest F value and set it as visited

* I restart the process from scratch using the picked tile as start tile

After some steps, I can have one of these two situations:

* I found the end tile. Achievement unlocked.

* I don’t have legal moves. In this case I must backtrack until I found a legal move, and continue the process, or I will backtrack until start tile, meaning the end tile cannot be reached.

This first, unoptimized algorithm can be written in AS3 this way:

package {
	import flash.display.Sprite;
	import flash.geom.Point;
	import flash.events.MouseEvent;
	import flash.utils.Timer;
	import flash.events.TimerEvent;
	public class Main extends Sprite {
		private var canvas:Sprite;
		private var startPoint:Point;
		private var endPoint:Point;
		private var currPoint:Point;
		private var tileVector:Vector.;
		private var path:Vector.;
		private var timer:Timer;
		public function Main() {
			canvas=new Sprite();
			addChild(canvas);
			fieldSetup();
			drawGrid();
			findPath();
			stage.addEventListener(MouseEvent.CLICK,addWall);
		}
		// fieldSetup prepares the field. Each tile in the field is set to its default value:
		// * it's walkable
		// * it's not the start point
		// * it's not the end point
		// * it has not been visited
		private function fieldSetup():void {
			timer=new Timer(100);
			canvas.graphics.clear();
			tileVector=new Vector.();
			for (var i:Number=0; i<16; i++) {
				tileVector[i]=new Vector.();
				for (var j:Number=0; j<12; j++) {
					tileVector[i][j]=new Object();
					tileVector[i][j].walkable=true;
					tileVector[i][j].startPoint=false;
					tileVector[i][j].endPoint=false;
					tileVector[i][j].visited=false;
				}
			}
			// while the starting point is choosen absolutely random...
			startPoint=new Point(Math.floor(Math.random()*16),Math.floor(Math.random()*12));
			tileVector[startPoint.x][startPoint.y].startPoint=true;
			tileVector[startPoint.x][startPoint.y].visited=true;
			// ... we want the end point to be at least 10 tiles away from start point.
			// jsut to make things interesting
			do {
				endPoint=new Point(Math.floor(Math.random()*16),Math.floor(Math.random()*12));
			} while (manhattan(startPoint,endPoint)<10);
			tileVector[endPoint.x][endPoint.y].endPoint=true;
		}
		// findPath function initializes the field and sets the time listener to draw the path
		private function findPath():void {
			path=new Vector.();
			path.push(startPoint);
			for (var i:Number=0; i<16; i++) {
				for (var j:Number=0; j<12; j++) {
					tileVector[i][j].visited=false;
				}
			}
			currPoint=new Point(startPoint.x,startPoint.y);
			timer.addEventListener(TimerEvent.TIMER,step);
			timer.start();
		}
		// step is the core function. Let's explain it deeply
		private function step(e:TimerEvent):void {
			// f will be the variable which minimum value will decide which direction to take.
			// I created a minF variable with an high value to store the minimum f value found
			var minF:Number=10000;
			// initializing a temporary Point variable
			var savedPoint:Point;
			for (var i:Number=-1; i<=1; i++) {
				for (var j:Number=-1; j<=1; j++) {
					// these two for loops together with this if statement will scan for all four directions. No diagonals at the moment.
					if ((i!=0 && j==0)||(i==0 && j!=0)) {
						// we consider a tile only if:
						// * is inside the tile field 
						// * is walkable (not a wall)
						// * has not been already visited
						if (insideField(currPoint,i,j) && tileVector[currPoint.x+i][currPoint.y+j].walkable && !tileVector[currPoint.x+i][currPoint.y+j].visited) {
							// now, core of the loop: let's determine g, h and f
							// g represents the cost to move from the starting tile to the current tile. At the moment we aren't using this variable
							// so getG function will always return 1
							var g:Number=getG(i,j);
							// h is the presumable distance from the current tile and the ending tile. One of the quickest way to determine it is
							// using manhattan distance
							var h:Number=manhattan(new Point(currPoint.x+i,currPoint.y+j),endPoint);
							// f is just the sum of g and h
							var f:Number=g+h;
							// if the current f value is lower than the minimum f value found so far...
							if (f2) {
					drawTile(path[path.length-2].x,path[path.length-2].y,0xcccccc);
				}
				if (currPoint.x==endPoint.x&&currPoint.y==endPoint.y) {
					// solved
					timer.removeEventListener(TimerEvent.TIMER,step);
				}
			}
			else {
				// backtrack
				if (path.length>1) {
					currPoint=path[path.length-2];
					drawTile(path[path.length-1].x,path[path.length-1].y,0xffffff);
					path.pop();
				}
				else {
					// can't be solved
					drawTile(currPoint.x,currPoint.y,0xff00ff);
					timer.removeEventListener(TimerEvent.TIMER,step);
				}
			}
		}
		// getG function will become really important during next steps, but at the moment just returns 1
		private function getG(n1:Number,n2:Number) {
			return 1;
		}
		// function to find manhattan distance between two points
		private function manhattan(p1:Point,p2:Point):Number {
			return Math.abs(p1.x-p2.x)+Math.abs(p1.y-p2.y);
		}
		// insideField checks if a given point inside the field will remain inside the field after adding a x and y offset
		private function insideField(p:Point,n1:Number,n2:Number):Boolean {
			if (p.x+n1>15||p.x+n1<0||p.y+n2>11||p.y+n2<0) {
				return false;
			}
			return true;
		}
		// function to add/remove a wall or generate another random grid
		private function addWall(e:MouseEvent):void {
			var row:Number=Math.floor(mouseY/40);
			var col:Number=Math.floor(mouseX/40);
			if (! tileVector[col][row].startPoint&&! tileVector[col][row].endPoint) {
				tileVector[col][row].walkable=! tileVector[col][row].walkable;
			}
			else {
				timer.removeEventListener(TimerEvent.TIMER,step);
				fieldSetup();
			}
			drawGrid();
			findPath();
		}
		// drawTile function just draws a tile in a given position with a given color
		private function drawTile(pX:Number,pY:Number,color:Number):void {
			canvas.graphics.beginFill(color,1);
			canvas.graphics.drawRect(pX*40,pY*40,40,40);
			canvas.graphics.endFill();
		}
		// function to draw the entire grid;
		private function drawGrid() {
			canvas.graphics.clear();
			canvas.graphics.lineStyle(1,0x999999);
			for (var i:Number=0; i<16; i++) {
				for (var j:Number=0; j<12; j++) {
					drawTile(i,j,0xffffff);
					if (tileVector[i][j].walkable==false) {
						drawTile(i,j,0x000000);
					}
					if (tileVector[i][j].startPoint==true) {
						drawTile(i,j,0x00ff00);
					}
					if (tileVector[i][j].endPoint==true) {
						drawTile(i,j,0xff0000);
					}
				}
			}
		}
	}
}

And this is the result... sometimes the path is ridiculously longer than expected, but it works:




What these squares mean?


Green square: start point


Red square: end point


Black square: wall


Gray square: the path


Blue square: current position


Purple square: I give up. End point cannot be reached


Let's see how to interact with it


Click on empty/path tiles: add a wall


Click on black tiles: remove a wall


Click on start/end tiles: generate another random start-end points


And this is enough for today, during next step we'll see the first optimizations.


Download the source code.