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.