A* Pathing Algorythm
Posted: Fri Apr 28, 2017 7:11 am
I couldn't find a decent pathing algorythm on the internet the last time I wrote one it took me days I don't know if it's just the way I think or if I'm dyslexic or what. But I have the code I figured I would share it and also I'm probably going to improve it a bit and make it a little more flexible for people to use in their games.
I"ve never seen an A* algorythm that was concide and easy to read... To me this is close. I'm not the best coder in the world though and I think this is one of the more complex snippets of my game.
This code paths on a grid that looks like this
(pseudocode) in my game it's actually path = Array(49) not 7 arrays of 7
Here's the code:
this is made for a player standing in the middle of a 7x7 grid so there are some numbers hard coded in. It's designed for a server based game so it assumes the player can't access the entire map and players and AI will use the area they can see
I'm also going to change the function so you input a start and a finish this assumes you start in the center of the 49 tiles which is the 25th tile "path.node[24]"
I wrote it so it's really easy to make a plugin since it just outputs the id of a tile that can easily my converted into data for any tile based game.
The code still has debugging lines in it too it's 2am and I started coding it at 7 this morning while stopping to watch my infant daughter.
I"ve never seen an A* algorythm that was concide and easy to read... To me this is close. I'm not the best coder in the world though and I think this is one of the more complex snippets of my game.
This code paths on a grid that looks like this
(pseudocode) in my game it's actually path = Array(49) not 7 arrays of 7
Code: Select all
[00,01,02,03,04,05,06]
[07,08,09,10,11,12,13]
[14,15,16,17,18,19,20]
[21,22,23,24,25,26,27]
[28,29,30,31,32,33,34]
[35,36,37,38,39,40,41]
[42,43,44,45,46,47,48]
Here's the code:
Code: Select all
<script>
var z = 0;
function pathTo(goal){
var createPath = function (goal){
var createNode = function(i){
this.id = i;
this.g = Infinity;
this.f = Infinity;
this.parent = null;
this.open = null;
};
this.nodes = Array(49);
for(i=0;i<this.nodes.length;i++){
this.nodes[i] = new createNode(i);
}
this.start = this.nodes[24];
this.start.g = 0;
this.currentNodeId = 24;
this.goal = this.nodes[goal];
this.bestPath = null;
};//end createPath
var path = new createPath(goal);
var getBestNeighbor = function(nodeId){
var getG = function(parentG){
//here you can check the map for water, sand, and ruins penalties
/*
default = 1
path = .9
water = 3
*/
return (parentG + 1);
};
var closeNode = function (node){
node.open = false;
};//end closeNode
var getF = function(startId,endId,g){
var startX = startId % 7;
var startY = (startId - startX) / 7;
var endX = endId % 7;
var endY = (endId - endX) / 7;
var h = Math.sqrt( Math.pow((startX - endX) , 2 ) + Math.pow(( startY - endY ), 2 ) );
return (h + g);
};//end getF
var tracePath = function(tracedNode){
path.bestPath = [];
while(tracedNode != path.start){
path.bestPath.unshift(tracedNode.id);
tracedNode = tracedNode.parent;
}
return path.bestPath;
};//end tracePath
var getNeighborNodeId = function(x,y,currentId){return currentId + (y*7) + x;};//end getNeighborNodeId
debugger;
z++
if(z>50){throw z}
if(path.bestPath === null){
var neighborNode = {};
var bestNode = {f: Infinity};
if(nodeId == path.goal.id){//may need to pass path
return tracePath(path.nodes[nodeId]);
}else{
for(y=-1;y<=1;y++){
for(x=-1;x<=1;x++){
var nnId = getNeighborNodeId(x,y,nodeId);
if( ( !(x==0 && y==0) && ( nnId>=0 && nnId<=48))){
var neighborNode = path.nodes[nnId];
if(path.nodes[nodeId].parent!=neighborNode){
if(neighborNode.open === null){ neighborNode.open = true; }
if(neighborNode.open === true ){//don't check closed neighbors
if(typeof neighborNode === "object"){
neighborNode.parent = path.nodes[nodeId]
neighborNode.g = getG(neighborNode.parent.g);
neighborNode.f = getF(neighborNode.id , path.goal.id , neighborNode.g);
if( neighborNode.f < bestNode.f){
bestNode = neighborNode;
}//endif
}//endif
}
}//endif Note: if the node isn't null or true, it's false.
}
}//endfor
}//endfor - Note: Here we should have the best neighbor
if(bestNode.f >= 50){ //limit crazy pathing errors.
closeNode(path.nodes[nodeId]);//need escape for no possible path
return;
}else{
path.currentNodeId = bestNode.id;
getBestNeighbor(bestNode.id);
}//endelse
}//endelse
}//endif
};//end getBestNeighbor
while(path.bestPath === null){
getBestNeighbor(path.currentNodeId);
}//end while
return path.bestPath;
}//end pathTo
myPath = pathTo(41); //testing with 6
console.log("path2:"+myPath);
</script>
I'm also going to change the function so you input a start and a finish this assumes you start in the center of the 49 tiles which is the 25th tile "path.node[24]"
I wrote it so it's really easy to make a plugin since it just outputs the id of a tile that can easily my converted into data for any tile based game.
The code still has debugging lines in it too it's 2am and I started coding it at 7 this morning while stopping to watch my infant daughter.