Hi
I am trying to learn A* pathfinding.
But I am having a few problems. If you paste this code into an empty Game Object JS behav you can see it work.
The problems are:
This is noted out in the script but when it is enabled it causes problems in the Neighbor array - not sure why … a g value of 10 should be a “wall” and not added to the OpenList.
(neighbor.g==10){continue;}
Also my OpenList array become massive. How do I limit it?
thanks
var c = new Array ();
var openList = new Array ();
var closedList = new Array ();
var startnode : Vector2;
var endnode : Vector2;
class node {
var f : int;
var g : int;
var pos : Vector2;
var cube : GameObject;
}
function Start(){
for (x=0; x<7; x++) {
c[x] = new Array();
for(y=0;y<7;y++){
c[x][y] = new node();
c[x][y].f = 0;
c[x][y].g = 0;
c[x][y].pos = Vector2(x,y);
c[x][y].cube=GameObject.CreatePrimitive(PrimitiveType.Cube);
c[x][y].cube.transform.position = Vector3(x,1,y);
c[x][y].cube.transform.localScale *= 0.5;
c[x][y].cube.name = "cube" + x + y; }
}
startnode = c[0][0].pos;
endnode = c[6][6].pos;
c[4][4].g=10;
c[startnode.x][startnode.y].cube.renderer.material.color = Color.green;
c[endnode.x][endnode.y].cube.renderer.material.color = Color.red;
var traceit = search (startnode,endnode);
for (var xx=0;xx<traceit.length;xx++){
traceit[xx].cube.renderer.material.color = Color.green;}
}
function Update () {
}
function search (snode,enode) {
openList.Push(c[snode.x][snode.y]);
var currentNode = snode;
var lowInd = 0;
while(currentNode != enode ) {
var neighbors = neighbors(currentNode);
for(var n=0; n<neighbors.length;n++) {
var neighbor = neighbors[n];
for(var ccl=0; ccl<closedList.length;ccl++) {
if (neighbor.cube.name == closedList[ccl.cube.name]){
continue;}
}
for(var opl=0; opl<closedList.length;opl++) {
if (neighbor.cube.name == openList[opl].cube.name){
continue;}
}
//if (neighbor.g==10){
//continue;}
neighbor.f = 10 + heuristic(neighbor.pos, enode);
openList.Push(neighbor);
}
for(var i=0; i<openList.length; i++) {
if(openList[i].f <openList[lowInd].f) { lowInd = i; }
}
currentNode = openList[lowInd];
closedList.Push(currentNode);
currentNode = openList[lowInd].pos;
openList.RemoveAt(lowInd);
}
return closedList;
}
function neighbors (noder) {
var dir = new Array(0,-1,10,1,-1,14,1,0,10,1,1,14,0,1,10,-1,1,14,-1,0,10,-1,-1,14,0,-1,10,1,-1,14,1,0,10);
var ret = new Array();
var x = noder.x;
var y = noder.y;
var sd = 0;
var ed = 21;
if (x==0){
sd=6;
ed=18;}
if(y==0){
sd=0;
ed=12;}
if(x==7){
sd=12;
ed=24;}
if(y==7){
sd=18;
ed=30;}
if(x==0 y==0){
sd=6; ed=12;}
if(x==7 y==7){
sd=18; ed=24;}
for (var d=sd; d<ed; d+=3) {
ret.Push(c[x+dir[d]][y+dir[d+1]]);}
return ret;
}
function heuristic (pos0, pos1) {
//This is the Manhattan distance
var d1 = Mathf.Abs(pos1.x - pos0.x);
var d2 = Mathf.Abs(pos1.y - pos0.y);
return d1 + d2;
}