# The basics of pathfinding – animated example

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();
fieldSetup();
drawGrid();
findPath();
}
// 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.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
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.

Get the first Phaser 3 book
Through 202 pages, 32 source code examples and an Android Studio project I will teach you how to build cross platform HTML5 games and build a game with you along the way.Then you can turn your game into a native mobile App.

Never miss an update!

Email:

← Quick Switch Flash game prototype made with Box2DBox2D for Flash Games book is on the shelves! →

Get the most popular Phaser 3 book

Through 202 pages, 32 source code examples and an Android Studio project you will learn how to build cross platform HTML5 games and create a complete game along the way.

215 GAME PROTOTYPES EXPLAINED WITH SOURCE CODE

// 1+2=3// 100 rounds// 10000000// 2 Cars// 2048// A Blocky Christmas// A Jumping Block// A Life of Logic// Angry Birds// Angry Birds Space// Artillery// Astro-PANIC!// Avoider// Back to Square One// Ball Game// Ball vs Ball// Ball: Revamped// Balloon Invasion// BallPusher// Ballz// Bar Balance// Bejeweled// Biggification// Block it// Blockage// Bloons// Boids// Bombuzal// Boom Dots// Bouncing Ball// Bouncing Ball 2// Bouncy Light// BoxHead// Breakout// Bricks// Bubble Chaos// Bubbles 2// Card Game// Castle Ramble// Chronotron// Circle Chain// Circle Path// Circle Race// Circular endless runner// Cirplosion// CLOCKS - The Game// Color Hit// Color Jump// ColorFill// Columns// Concentration// Crossy Road// Crush the Castle// Cube Jump// CubesOut// Dash N Blast// Dashy Panda// Deflection// Diamond Digger Saga// Don't touch the spikes// Dots// Down The Mountain// Drag and Match// Draw Game// Drop Wizard// DROP'd// Dudeski// Dungeon Raid// Educational Game// Elasticity// Endless Runner// Erase Box// Eskiv// Farm Heroes Saga// Filler// Flappy Bird// Fling// Flipping Legend// Floaty Light// Fuse Ballz// GearTaker// Gem Sweeper// Globe// Goat Rider// Gold Miner// Grindstone// GuessNext// Helicopter// Hero Emblems// Hero Slide// Hexagonal Tiles// HookPod// Hop Hop Hop Underwater// Horizontal Endless Runner// Hundreds// Hungry Hero// Hurry it's Christmas// InkTd// Iromeku// Jet Set Willy// Jigsaw Game// Knife Hit// Knightfall// Legends of Runeterra// Lep's World// Line Rider// Lumines// Magick// MagOrMin// Mass Attack// Math Game// Maze// Meeblings// Memdot// Metro Siberia Underground// Mike Dangers// Mikey Hooks// Nano War// Nodes// o:anquan// One Button Game// One Tap RPG// Ononmin// Pacco// Perfect Square!// Perfectionism// Phyballs// Pixel Purge// PixelField// Planet Revenge// Plants Vs Zombies// Platform// Platform game// Plus+Plus// Pocket Snap// Poker// Pool// Pop the Lock// Pop to Save// Poux// Pudi// Pumpkin Story// Puppet Bird// Pyramids of Ra// qomp// Quick Switch// Racing// Radical// Rebuild Chile// Renju// Rise Above// Risky Road// Roguelike// Roly Poly// Run Around// Rush Hour// SameGame// SamePhysics// Save the Totem// Security// Serious Scramblers// Shrink it// Sling// Slingy// Snowflakes// Sokoban// Space Checkers// Space is Key// Spellfall// Spinny Gun// Splitter// Spring Ninja// Sproing// Stabilize!// Stack// Stairs// Stick Hero// String Avoider// Stringy// Sudoku// Super Mario Bros// Surfingers// Survival Horror// Talesworth Adventure// Tetris// The Impossible Line// The Moops - Combos of Joy// The Next Arrow// Threes// Tic Tac Toe// Timberman// Tiny Wings// Tipsy Tower// Toony// Totem Destroyer// Tower Defense// Trick Shot// Tunnelball// Turn// Turnellio// TwinSpin// vvvvvv// Warp Shift// Way of an Idea// Whack a Creep// Wheel of Fortune// Where's my Water// Wish Upon a Star// Word Game// Wordle// Worms// Yanga// Yeah Bunny// Zhed// zNumbers

© 2006 - 2022 Emanuele Feronato

var deviceAgent = navigator.userAgent.toLowerCase();
}
if (navigator.userAgent.search("MSIE") >= 0) {
}
else if (navigator.userAgent.search("Chrome") >= 0) {
}
else if (navigator.userAgent.search("Firefox") >= 0) {
}
else if (navigator.userAgent.search("Safari") >= 0 && navigator.userAgent.search("Chrome") < 0) {
}
else if (navigator.userAgent.search("Opera") >= 0) {
}
});

/* <![CDATA[ */
var countVars = {"disqusShortname":"emanuele-feronato"};
/* ]]> */

/* <![CDATA[ */
var embedVars = {"disqusConfig":{"integration":"wordpress 3.0.22"},"disqusIdentifier":"6007 http:\/\/www.emanueleferonato.com\/?p=6007","disqusShortname":"emanuele-feronato","disqusTitle":"The basics of pathfinding \u2013 animated example","disqusUrl":"https:\/\/www.emanueleferonato.com\/2012\/11\/26\/the-basics-of-pathfinding-animated-example\/","postId":"6007"};
/* ]]> */

```