No Backtracking
canvasgamedevaipath-findingjavascriptarchivedPathing with no backtracking
This simple "pathfinding" method, which I call No Backtracking, is a method I previously developed for use in a game where an unintelligent NPC chases the player. As such, this method is not really pathfinding, but can appear to act in this way in many circumstances.
This method works as follows when the NPC is given a target coordinate:
- Each of the neighbouring tiles surrounding the NPC is valued based on:
- Can the tile be moved to? (ie; not a wall, outside map bounds, or otherwise impassable)
- Distance of the tile from the destination
- If the tile is in our movement history, and if so how far back in the list? (older tiles are scored less than newer tiles)
- The list of available tiles is then sorted, and the lowest scored tile is set as the current destination of the NPC
- The destination is put on the end of the history list
- If the history is longer than the maxHistory for the NPC, an entry is shifted (removed) from the beginning of the list
- The method repeats (indefinitely) until the target is reached
This also means the NPC may run madly backwards and forwards, unable to pass a confusing area of terrain. In some circumstances, this style of behaviour can be desireable.
To begin with, our Character needs some specific properties:
var character = {
from : [0, 0],
to : [0, 0],
target : [0, 0],
history : [],
maxHistory : 20,
update : function(timeElapsed) { ... }
};
When the Character has moved to a new map cell, it performs the following check to see if it needs to keep moving to reach its destination:
if(this.from[0]!=this.target[0] || this.from[1]!=this.target[1])
{We then create a temporary array, n, to which we add each of the neighbouring tiles if they fall within map bounds, and are a tile type we can move on:
var n = new Array();
if(this.from[0]>0 && map[((this.from[1]*mapW)+this.from[0]-1)]==1)
{ n.push([this.from[0]-1, this.from[1], 0]); }
if(this.from[0]<(mapW-1) && map[((this.from[1]*mapW)+this.from[0]+1)]==1)
{ n.push([this.from[0]+1, this.from[1], 0]); }
if(this.from[1]>0 && map[(((this.from[1]-1)*mapW)+this.from[0])]==1)
{ n.push([this.from[0], this.from[1]-1, 0]); }
if(this.from[1]<(mapH-1) && map[(((this.from[1]+1)*mapW)+this.from[0])]==1)
{ n.push([this.from[0], this.from[1]+1, 0]); }Along with the neighbouring tiles x, y coordinates, we add a third entry, which is currently just 0 (zero).
We then loop through all of the tiles in the n array, and find the distance of that tile from the target, which we assign to the third index of the entry:
for(i in n)
{
n[i][2] = getDistance(this.target[0], this.target[1], n[i][0], n[i][1]);We the loop through the history of traversed tiles, and if this tile is in the Characters history, we increase the distance of this tile by 10 plus 10 x [array index].
for(h in this.history)
{
if(n[i][0]==this.history[h][0] && n[i][1]==this.history[h][1])
{
n[i][2] = n[i][2] + 10 + (h*10);
}
}
}If the n is not empty, we first sort it with the lowest score first:
if(n.length)
{
n.sort(function(v1, v2) { return v1[2]-v2[2]; });
We then set our characters destination tile (to) to the first tile (the tile with the lowest score) in the neighbours list:
this.to[0] = n[0][0];
this.to[1] = n[0][1];
...and we add this new destination tile to the end of the history array...
this.history.push([n[0][0], n[0][1]]);If the history array is longer than maxHistory entries, we remove the first entry, and we're ready to go:
if(this.history.length > this.maxHistory) { this.history.shift(); }
}
Additionally, when we give the character a new target, we must remember to clear the history!
setTarget : function(px, py)
{
this.history.length = 0;
this.target = [px, py];
}
Example source code
<!DOCTYPE html>
<html>
<head>
<script type="text/javascript">
var ctx = null;
var gameCanvas = null;
var gameTime = 0;
var gameSpeed = 1;
var mapW = 20;
var mapH = 15;
var lastFrameTime = 0;
var map = [
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0,
0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0,
0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0,
0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0,
0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0,
0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0,
0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0,
0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0,
0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0,
0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0,
0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0,
0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0,
0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
];
var character = {
from : [0, 0],
to : [0, 0],
realPos : [0, 0],
departed : 0,
moveSpeed : 230,
target : [0, 0],
history : [],
maxHistory : 20,
update : function(t)
{
if(this.from[0]!=this.to[0] || this.from[1]!=this.to[1])
{
if((t - this.departed)>=this.moveSpeed) { this.setPos(this.to[0], this.to[1]); }
else
{
var amt = ((40/this.moveSpeed) * (t-this.departed));
var amtX = (this.from[0]==this.to[0] ? 0 : (this.to[0]<this.from[0] ? 0 - amt : amt));
var amtY = (this.from[1]==this.to[1] ? 0 : (this.to[1]<this.from[1] ? 0 - amt : amt));
this.realPos = [
(this.from[0]*40) + 5 + amtX,
(this.from[1]*40) + 5 + amtY
];
}
}
else
{
if(this.from[0]!=this.target[0] || this.from[1]!=this.target[1])
{
var n = new Array();
if(this.from[0]>0 && map[((this.from[1]*mapW)+this.from[0]-1)]==1) { n.push([this.from[0]-1, this.from[1], 0]); }
if(this.from[0]<(mapW-1) && map[((this.from[1]*mapW)+this.from[0]+1)]==1) { n.push([this.from[0]+1, this.from[1], 0]); }
if(this.from[1]>0 && map[(((this.from[1]-1)*mapW)+this.from[0])]==1) { n.push([this.from[0], this.from[1]-1, 0]); }
if(this.from[1]<(mapH-1) && map[(((this.from[1]+1)*mapW)+this.from[0])]==1) { n.push([this.from[0], this.from[1]+1, 0]); }
for(i in n)
{
n[i][2] = getDistance(this.target[0], this.target[1], n[i][0], n[i][1]);
for(h in this.history) { if(n[i][0]==this.history[h][0] && n[i][1]==this.history[h][1]) { n[i][2] = n[i][2] + 10 + (h*10); } }
}
if(n.length)
{
n.sort(function(v1, v2) { return v1[2]-v2[2]; });
this.to[0] = n[0][0];
this.to[1] = n[0][1];
this.departed = t;
this.history.push([n[0][0], n[0][1]]);
if(this.history.length > this.maxHistory) { this.history.shift(); }
}
}
}
},
setPos : function(px, py)
{
this.from = [px, py];
this.to = [px, py];
this.realPos = [(px*40)+5, (py*40)+5];
this.departed = 0;
},
setTarget : function(px, py)
{
this.history.length = 0;
this.target = [px, py];
}
};
function getDistance(x1, y1, x2, y2)
{
return (Math.abs(Math.sqrt(((x1-x2) * (x1-x2)) +
((y1-y2) * (y1-y2)))));
}
window.onload = function()
{
gameCanvas = document.getElementById('game');
ctx = document.getElementById('game').getContext('2d');
character.setPos(1,1);
character.setTarget(1, 1);
gameCanvas.addEventListener('mouseup', function(e) {
mouseX = e.pageX;
mouseY = e.pageY;
var p = game;
do
{
mouseX-= p.offsetLeft;
mouseY-= p.offsetTop;
p = p.offsetParent;
} while(p!=null);
var tileX = Math.floor(mouseX / 40);
var tileY = Math.floor(mouseY / 40);
if(tileX < mapW && tileY < mapH && map[((tileY*mapW)+tileX)]==1)
{
character.setTarget(tileX, tileY);
}
});
requestAnimationFrame(drawGame);
};
function drawGame()
{
if(ctx==null) { return; }
if(lastFrameTime==0)
{
lastFrameTime = Date.now();
requestAnimationFrame(
drawGame);
return;
}
var timeElapsed = Date.now()-lastFrameTime;
gameTime+= (timeElapsed * gameSpeed);
character.update(gameTime);
for(y = 0; y < mapH; ++y)
{
for(x = 0; x < mapW; ++x)
{
ctx.fillStyle = (map[((y*mapW)+x)]==0 ? "#000000" : "#ffffff");
ctx.fillRect((x*40), (y*40), 40, 40);
}
}
ctx.fillStyle = "#ff0000";
for(i in character.history)
{
var pos = character.history[i];
ctx.fillRect((pos[0] * 40)+15, (pos[1]*40)+15, 10, 10);
}
ctx.fillStyle = "#0000bb";
ctx.fillRect(character.realPos[0], character.realPos[1], 30, 30);
ctx.lineWidth = 2;
ctx.strokeStyle = "#00bb00";
ctx.setLineDash([5, 5]);
ctx.strokeRect(character.target[0]*40, character.target[1]*40, 40, 40);
lastFrameTime = Date.now();
requestAnimationFrame(drawGame);
}
</script>
</head>
<body>
<p>Click anywhere on the maps paths (white tiles) to set the characters destination.</p>
<canvas id="game" width="800" height="600"></canvas>
</body>
</html>