A* Super Slow slow slow? (Optimizing Javascript?)

Unity Engine
1

Hi,

So I am trying to get A* pathfinding working in my project. I know there are some solutions out there but I am trying to go for a Javascript solution that I kinda know a little of whats going on behind the scenes. I found this script partially on here (ported a bit to Unity) and a site that had this script for flash. Most implementations ive seen for flash usually return a solution within 8ms. Well when I use this on Update or Awake depending on the size of my grid that Im using it can cause Unity to hang (little color circle thingy) before it comes to the solution. I would hope I could solve a 64x64 grid rather quickly(honesty id like to solve up to 1024x1024) but thats not the case. Anyone have any pointers for profiling this? Or can anyone see anything in my code that I can do better? Im sorry its a bit of a mess. :slight_smile: (oh and I do have another function that sets some of the grid to unpassable (-1)… I just left it out.

class MapPathFinder
{
	private var finalPosition : Vector2;
	private var startPosition : Vector2;
	
	// Storing Arrays That Handle All Nodes
	private var openList : Array;
	private var closedList : Array;
	
	// 2D Array For Grid Of Environment
	private var _array : Array;
	
	// If To Use Euclidean Instead Of Manhattan
	private var allowDiagonal : boolean = false;
	
	private var _gridSize : int;
	
	// Constructor
	function MapPathFinder(ar : Array, gr : int){
			this.instantiate(ar , gr);
	}
	
	// Reset / Instantiate Arrays
	// Expects: Array of Map points
	// Returns: NULL
	function instantiate(ar : Array, gr : int){
		
		this._array = ar;
		this._gridSize = gr;
		this.openList = new Array();
		this.closedList = new Array();
	}
	
		function init(startPos : Vector2, finalPos : Vector2){
		
		var startX : int = startPos.x;
		var startY : int = startPos.y;
		
		var finalX : int = finalPos.x;
		var finalY : int = finalPos.y;
		
		// CHECK IF START  END POINTS ARE VALID
		if (this._array[startX][startY] >= 0  this._array[finalX][finalY] >= 0){
		
			// Store for reference
			this.startPosition = startPos;
			this.finalPosition = finalPos;
		    
			// Create Node And Add to OpenList
			var startingNode : StructNode = new StructNode(startPosition, 0, 0, 0);
			this.openList.Push(startingNode);
			
			//Debug.Log(finalPosition);
		
		}
	}


// ** Find the successors ** //
function getSuccessorsFlash(pos : Vector2){
		var r : int = pos.x;
		var c : int = pos.y;
        // put all the successors in this array...
        var ret = new Array ();
        if (this._array[r - 1][c] == 0) {
                ret.push ([r - 1, c]);
        }
        if (this._array[r][c + 1] == 0) {
                ret.push ([r, c + 1]);
        }
        if (this._array[r + 1][c] == 0) {
                ret.push ([r + 1, c]);
        }
        if (this._array[r][c - 1] == 0) {
                ret.push ([r, c - 1]);
        }
        
        // ** disabling the diagonal movement ** //
        /*
        if (this._array[r + 1][c + 1] == 0  this._array[r][c + 1] == 0  this._array[r + 1][c] == 0) {
                ret.push([r + 1, c + 1]);
        }
        if (this._array[r + 1][c - 1] == 0  this._array[r][c - 1] == 0  this._array[r + 1][c] == 0) {
                ret.push([r + 1, c - 1]);
        }
        if (this._array[r - 1][c - 1] == 0  this._array[r][c - 1] == 0  this._array[r - 1][c] == 0) {
                ret.push([r - 1, c - 1]);
        }
        if (this._array[r - 1][c + 1] == 0  this._array[r][c + 1] == 0  this._array[r - 1][c] == 0) {
                ret.push([r - 1, c + 1]);
        }
        */
        return ret;
};

	// Looks Up All Directions From Current Node
	// Expects: Vector2
	// Returns: List of Vector2 items
	function getSuccessors(pos : Vector2){
		
		// Split X and Y into Int based R and C
		var r : int = pos.x;
		var c : int = pos.y;
		
		//Debug.Log(r);
		
		// Build Base Direction List
		var ret : Array = new Array();
		if (r-1 > -1)
		{
        	if (this._array[r - 1][c] >= 0) {
        		ret.Push (new Array(Vector2(r - 1, c), this._array[r - 1][c]));
        	}
		}
		
		if (c+1 < _gridSize)
		{
        	if (this._array[r][c + 1] >= 0) {
        		ret.Push (new Array(Vector2(r, c + 1), this._array[r][c + 1]));
        	}
		}
		
		if (r + 1 < _gridSize){
        	if (this._array[r + 1][c] >= 0) {
        		ret.Push (new Array(Vector2(r + 1, c), this._array[r + 1][c]));
        	}
        }
        
        if (c-1 > -1)
       {
        	if (this._array[r][c - 1] >= 0) {
        		ret.Push (new Array(Vector2(r, c - 1), this._array[r][c - 1]));
        	}
       }
        return (ret);
	}

	// Gets Distsance between points specified
	// Expects: Vector2 for each of the two points
	// Returns: Integer distance between points
	function getDistance(pos1 : Vector2, pos2 : Vector2){
	
		var d1 : int = Mathf.Abs(pos2.x - pos1.x);
		var d2 : int = Mathf.Abs(pos2.y - pos1.y);
		
		return (d1 + d2);
	}

		
	function findPath(startPos : Vector2, finalPos : Vector2){
		init(startPos, finalPos);
		// Iterate OpenList And Find Lowest Cost
		while (this.openList.length > 0){
		
			var _max : int = 5000;
			var _selected : int = -1;
			
			for (var o=0;o<this.openList.length;o++){
			
				if (this.openList[o].f < _max){
					_max = this.openList[o].f;
					_selected = o;
				}
			}
			
			// Remove Node From List And Check If Final Node Required
			var node : StructNode = this.openList[_selected];
			this.openList.RemoveAt(_selected);
			
			if (node.pos == this.finalPosition){
				this.closedList.Push(node);
				
				// Get Last Node And Work Backwards
				var cur : StructNode = this.closedList[this.closedList.length - 1];
				var ret : Array = new Array();
				if(cur.parent != "") {
				}
				
				// Build Path
				while (cur.parent !== null){
					ret.Push(cur);
					cur = cur.parent;
				}
				
				// Return To Initial Caller
				return (ret);				
				
			}
			
			//Debug.LogError("foo");
			
			// Get Other Directions And Iterate To Find Best Path
			//var successors : Array = this.getSuccessors(node.pos);
			var successors : Array = this.getSuccessors(node.pos);
            for (var a=0;a<successors.length;a++) {
            	
            	// Set Skip Default
            	var _skip : boolean = false;
            	
            	// Build Struct Properties
            	var g : int = node.g + this.getDistance(successors[a][0], node.pos);
            	//var h : int = this.getHeuristic(successors[a][0], this.finalPosition) + successors[a][1];
            	var h : int = this.getDistance(successors[a][0], this.finalPosition);
            	var f : int = g + h;
            	            	
            	// Create New Node, Apply Parent And Iterate On
                var struct : StructNode = new StructNode(successors[a][0], g, h, f);
                struct.parent = node;
                
                // Check Lowest Cost In Open List
                for (var bo in openList) {
                	if (bo.pos == struct.pos  bo.f < struct.f) {
                    	_skip = true;
                        break;
                    }
               	}
                
                // Check Lowest Cost In Closed List
                for (var bc in this.closedList) {
                	if (bc.pos == struct.pos  bc.f < struct.f) {
                    	_skip = true;
                        break;
                    }
                }
                
                // If Not Found
                if (_skip == false) {
                	
                	// Check Same Position And Remove If Exists
                	var coCount : int = -1;
                	for (var co in this.openList) {
                		
                		coCount++;
                		
                		if (co.pos == struct.pos) {
                			this.openList.RemoveAt(coCount);
                        }
                    }
                    
                	// Check Same Position And Remove If Exists
                    var ccCount : int = -1;
                    for (var cc in this.closedList) {
                    	
                    	ccCount++;
                    	
                    	if (cc.pos == struct.pos) {
                    		this.closedList.RemoveAt(ccCount);
                    	}
                    }
                    
                    // Add Node To Open List
                    this.openList.Push(struct);
                }
            }
            
            	
			// Add Node To Closed List
            this.closedList.Push(node);
			
		} // end while
		
		Debug.Log("IMPOSSIBLE TO FIND A PATH");		
		return (new Array());
	
	}
	
	function Update () {
	}

}

here is how im calling it. If you need a project please let me know too. And sorry if my math is off on the world to grid conversions :smile:.

var gridSize = 10;
var castHeight = 10;
var floorGeo : Transform;
var startGeo : Transform;
var endGeo : Transform;
private var grid : Object[];
//private var mypath : Object[];
private var layerMask = 1 << 8;

private	var cellSize;
private	var mapMoveXToMap;
private	var mapMoveYToMap;
private	var mapMoveXToWorld;
private	var mapMoveYToWorld;


function Array2D(rows : int, columns : int)
{
	var array = new Object[rows];
	for (i = 0; i < array.length; i++) 
	{
		array[i] = new int[columns];
	}
	return array;
}

function buildMap (grid : Object[])
{
	for (x = 0; x < grid.length; x++) 
	{
		for (z = 0; z < grid.length; z++) 
		{
			grid[x][z] = hasWorldGeo(x,z);
		}
	}
}


function convertToMapSystem(point : Vector2){
	//DIVIDE BY S AND FLOOR RESULT
	var movedX = (point.x + mapMoveXToMap);
	var movedY = (point.y + mapMoveYToMap);
	var xInt : int = Mathf.Floor(Mathf.Abs(movedX/cellSize));
	var yInt : int = Mathf.Floor(Mathf.Abs(movedY/cellSize));
	return (Vector2(xInt, yInt));
}


function convertToWorldSystem(point : Vector2){
	//MULT BY S
	//var bounds = floorGeo.renderer.bounds;
	//var cellSize = bounds.size.x/gridSize;    
	var xInt : float = (point.x * cellSize) + (cellSize/2) + mapMoveXToWorld;
	var zInt : float = (point.y * -cellSize) - (cellSize/2) - mapMoveYToWorld;
	return (Vector3(xInt, 0, zInt));	
}

function searchPath(start : Vector2, end : Vector2){
	
	//Debug.Log("ST: " + start + "  EN: " + end);
	//Debug.Log("ST2: " + convertToMapSystem(start) + "  EN2: " + convertToMapSystem(end));
	//testLoc(convertToMapSystem(start), convertToMapSystem(end));
	var pf = new MapPathFinder(grid,gridSize);
	var path = pf.findPath(convertToMapSystem(start), convertToMapSystem(end));
	
	if (path.length > 0){
	
		var userPath : Array = new Array();
		for (i=0;i<path.length;i++){
			userPath.Push(convertToWorldSystem(path[i].pos));
		}
	
		return (userPath);
	
	}
	
	return (path);	
}

function Awake () {
	grid = new Array2D(gridSize, gridSize);
	buildMap(grid);
	
	var bounds = floorGeo.renderer.bounds;
	cellSize = bounds.size.x/gridSize;
	mapMoveXToMap = -((bounds.center.x)-(bounds.size.x*0.5));
	mapMoveYToMap = -((bounds.center.z)+(bounds.size.z*0.5));
	mapMoveXToWorld = bounds.center.x-(bounds.size.x*0.5);
	mapMoveYToWorld = bounds.center.z-(bounds.size.z*0.5);
}

//then finally somewhere call this
	var start = Vector2(startGeo.position.x,startGeo.position.z);
	var end = Vector2(endGeo.position.x,endGeo.position.z);
	mypath = searchPath(start, end);

[/code]

2

I only glanced at the code so I don’t know how important this is overall or how problematic it would be to fix, but one thing I noticed is that it’s using dynamic Javascript arrays (“private var _array : Array;”), which are at least 20X slower than built-in arrays (“private var _array : int[ ];” and so on).

–Eric

3

The main problem is that you are using simple linear searches for both the open and closed lists. You are more or less looking at every element in both arrays every time a new position is tested. This gets really bad because both the open and closed lists inevitably get longer as the search progresses.

The standard way to handle this issue is to use some kind of priority queue for the open list and a hashtable for the closed list. The queue basically just keeps the elements in sorted order, so the next search position will always be at the end of the array. The hashtable lets you retrieve an element by a “key” (which can be any data you like) and only needs to search through a few items each time, rather than the whole list. Using these techniques, I would expect a 1024x1024 map to be well within reach.

You might be interested in the first issue of Unity Developer mag, actually. This explores A* in detail for a similar situation to yours and covers the priority queue and hashtable along with some source code.

4

Built-in arrays and a non-linear search system are an absolute must. From first hand experience, this will take your A* from beach-ball to being able to do 100’s of searches per second.

I haven’t looked through your code in detail, but another thing to consider is that A* implementations often either work perfectly or they work horrendously. If you are still having trouble after implementing the above changes, try adding some step-by-step debugging code. For example, when I was testing my code, I would have it spawn a marker at every node checked. This usually made it easy to see when it wasn’t performing a strictly A* operation.

5

Cool! Thank you guys tons!

Actualy when I was researching about A* I saw that the Unity mag had the article. Its hard for me to order it though since I move/travel too much. Ill take a look at the hashtable/priority queue.

Ill also take a look at builtin arrays and how to re-stucture what I have not to use pushs/pops, etc. The code I saw floating around several places were using dynamic arrays so I figured it was ok.

6

“In the worst case, the number of nodes expanded is exponential in the length of the solution (the shortest path)”

and

“More problematic than its time complexity is A*’s memory usage. In the worst case, it must also remember an exponential number of nodes.”

I think you might want to do something other than implement A* for 1024x1024 nodes.

7

Update:

I found a binary heap for Javascript. It seems to work in my case. I can now solve grids of 64(128 is sluggy and 1024 kills unity with my code). :slight_smile: Im going to keep on trying to optimize it. I found some articles in game programming gems on A* optimizing. Im not really that into the CS/heavier coding side of things(im an artist) so it takes me longer to do something like this. Im happy ive gotten things this far. :smile:

Podperson:
I dont mind trading memory for speed to get it working on a 1024 grid. The design of the game doesnt lend itself to other pathfinding methods well(well not that I know of). Its an open area (there are some walls but its rather open) and the user can put down objects onto the field. So its easy just to tick off an area on the grid as being unpassable where the player has dropped a new item. (Kind of open sandbox sims type).

Anyways here is a BinaryHeap in Unity Javscript if anyone wants it(I hope its not borked ^_^). Its the implementation from:

http://eloquentjavascript.net/

class BinaryHeap extends System.Object
{
//class State extends UnityEngine.MonoBehaviour
	var content;
	var scoreFunction;
	
	function BinaryHeap(scoreFunction){
	//this.content = [];
	this.content = new Array();
	this.scoreFunction = scoreFunction;	
	}


		
	function push(element)
	{
		this.content.Push(element);	
	}

  function pop() {
    // Store the first element so we can return it later.
    var result = this.content[0];
    // Get the element at the end of the array.
    var end = this.content.Pop();
    // If there are any elements left, put the end element at the
    // start, and let it bubble up.
    if (this.content.length > 0) {
      this.content[0] = end;
      this.bubbleUp(0);
    }
    return result;
  }

  function remove(node) {
    var leng = this.content.length;
    // To remove a value, we must search through the array to find
    // it.
    for (var i = 0; i < leng; i++) {
      if (this.content[i] == node) {
        // When it is found, the process seen in 'pop' is repeated
        // to fill up the hole.
        var end = this.content.pop();
        if (i != this.content.length - 1) {
          this.content[i] = end;
          this.bubbleUp(i);
        }
        return;
      }
    }
    Debug.Log("Node not found.");
  }

  function size() {
    return this.content.length;
  }
  
  
  function   sinkDown(n) {
    // Fetch the element that has to be sunk.
    var element = this.content[n];
    // When at 0, an element can not sink any further.
    while (n > 0) {
      // Compute the parent element's index, and fetch it.
      var parentN = Mathf.Floor((n + 1) / 2) - 1;
      var parent = this.content[parentN];
      // Swap the elements if the parent is greater.
      if (this.scoreFunction(element) < this.scoreFunction(parent)) {
        this.content[parentN] = element;
        this.content[n] = parent;
        // Update 'n' to continue at the new position.
        n = parentN;
      }
      // Found a parent that is less, no need to sink any further.
      else {
        break;
      }
    }
  }

  function bubbleUp(n)  {
    // Look up the target element and its score.
    var length = this.content.length;
    var element = this.content[n];
    var elemScore = this.scoreFunction(element);

    while(true) {
      // Compute the indices of the child elements.
      var child2N = (n + 1) * 2;
      var child1N = child2N - 1;
      // This is used to store the new position of the element,
      // if any.
      var swap;
      // If the first child exists (is inside the array)...
      if (child1N < length) {
        // Look it up and compute its score.
        var child1 = this.content[child1N];
        var child1Score = this.scoreFunction(child1);
        // If the score is less than our element's, we need to swap.
        if (child1Score < elemScore)
          swap = child1N;
      }
      // Do the same checks for the other child.
      if (child2N < length) {
        var child2 = this.content[child2N];
        var child2Score = this.scoreFunction(child2);
        if (child2Score < (swap == null ? elemScore : child1Score))
          swap = child2N;
      }

      // If the element needs to be moved, swap it, and continue.
      if (swap != null) {
        this.content[n] = this.content[swap];
        this.content[swap] = element;
        n = swap;
      }
      // Otherwise, we are done.
      else {
        break;
      }
    }
  }
}

[/code]

8

Unfortunately, podperson missed out the second half of the sentence from the Wikipedia article that essentially says A* complexity is polynomial (ie, good) when the heuristic works perfectly. In practice, the heuristic works imperfectly but mostly very well in a situation like the one you have here (open area with a few walls). The likelihood of getting worst case performance from A* is very low except in rather contrived and avoidable situations.

Looking again at your code, there are still a few things you could try:-

  • I notice you have disabled diagonal moves, but they will tend to improve performance considerably. You will need to change the Manhattan heuristic so that it accounts for the diagonal part of the move, but this is fairly straightforward.

  • You can probably reduce the position marker from a Vector2 to just an integer. This saves quite a lot of memory overall and will make better use of the CPU cache. (This probably isn’t a major optimisation, but it should help a bit.)

  • With the binary heap, you won’t help performance by removing suboptimal nodes from the queue, although you will save some memory. Your “remove” routine is another linear search which will negate much of the advantage of using a heap in the first place. You can either ignore the redundant elements (the priority queue takes care of them from the algorithm’s point of view) or you could try “opportunistic” removal - you only throw out a suboptimal node if you happen to encounter it while adjusting the heap after insertion/removal.

Any one of these things should help, but you should also be sure to use the hashtable for the closed list if you are not already doing so.

9

I didn’t quote that sentence, you’re right.

Polynomial isn’t “good”. This means that the time taken goes up as the square, cube, or some other power of the size of the number of nodes. The number of nodes is going up with area already. So if you double the grid size you quadruple the number of nodes, and then maybe increase execution time by a factor of 16 or 64… This is NOT good.

To go from 64x64 to 1024x1024 you’re looking at, conservatively, a 2^16 (65536)x slower – 256x as many nodes with O(n^2) search. You’ll need to have a wicked fast algorithm.

Order n is good, log(n) is very good, i is GREAT.

10

Yes, some other power - actually, n^1 is also a polynomial and A* does tend toward linear time when the heuristic works well. When the shortest path is unobstructed, it will check a small, bounded number of candidate positions (probably eight in the case of a grid layout) for each step of progress. The hash table and even the priority queue operations can be made close to o(1), so the time is roughly linear in the length of the path for the straightforward parts of the search. Obstacles are negotiated by “flooding” the local area until a detour is discovered. This is the really time-consuming part of the search, but only gets truly pathological in large spaces that also happen to be dead ends. Most dead ends can easily be detected at the design stage and can usually be turned to advantage by allowing an efficient multi-stage search (this is effectively just an easy way of having a cleverer heuristic). A dense maze is the obvious counter-example, but in this case, a large part of the search space will likely be used up by walls and also the number of alternative paths at any particular point will be very limited. A* might not be ideal for this situation but you wouldn’t expect it to do too badly even here.

Almost every heuristic has “killer” cases (eg, caches, compression, Boyer-Moore, quicksort…) but in practice, you can often just design and code so as to avoid them rather than regarding them as showstoppers.