A* pathfinding gurus - help needed please!!!!!!!

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;
	}

This looks as though it should work. Are you sure the field is being assigned with a value of ten in the right cases?

Open lists generally do become massive. Typically, they are implemented as priority queues for the sake of efficiency. Similarly, you will improve the speed if you use a hashtable for the closed list. There are a few other tricks you can use to weed redundant items out of the open list but these will depend on the priority queue implementation. Although it is possible to search the list thoroughly to get rid of redundant items, this generally wastes much more time than it saves.

Thanks for your help.

Yeah the array element c[4][4] get assigned in the code.

c[4][4].g=10;

But for some reason it makes the the array of Neigbors go crazy.

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;
   }

The reason why I am concerned about the OpenList is that if I make my two dimensional array larger Unity freezes.

Is this bcos I am creating an array of objects (node) and it is therefore cumbersome?

var c = new Array (); 

class node  {
   var f : int;
   var g : int;
   var pos : Vector2;
   var cube : GameObject;
} 


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; }
   }

[/code]

If Unity freezes with that code, try putting a print statement in the inner loop to see where the freeze occurs. Another option is to comment lines out of the loop body to find out what causes the freeze. It is actually quite surprising that this code freezes and it may be due to a bug in Unity. There is no particular reason why you can’t have a large jagged array of object references.