Problem with A star pathfinding. How to speed up?

Hi,
I have made an implementation of the A* algorithm as presented here: http://en.wikipedia.org/wiki/A*_search_algorithm#Pseudocode
I am making my grid of nodes like this:

	for(var i = 0; i < areaWidth; i++)
	{
		for(var j = 0; j < areaHeight; j++)
		{
			var newVector : Vector3 = new Vector3(startVector.x + i*2.0,
									 				2.5, startVector.z + j*2.0);
	    	
	    	newNode = Instantiate (node_prefab, newVector, Quaternion.identity);
	    	var component : AI_GraphNode = newNode.GetComponent(AI_GraphNode);
	    	component.SetNodeNumber(iteration);
	    	
	    	newNode.parent = nodesGameObject.transform;
	    	newNode.name = "GraphNode"+iteration;
	    	iteration++;
	    }
	}

It works pretty well on a grid of nodes 10x10 or 20x20.
If my grid is larger, then the whole calculation takes a while, more than a while and then the FPS goes down. Is there any way that could speed up my calculations, that you would like to hint out for me, what can speed up my calculations or operations?
For example, I have read somewhere that builtIn arrays are faster than javascript Array.

I saw a few implementations that works like a charm:

This gridGraph is huge:


11885-gridgraph.png


There are hundreds of nodes and it works pretty fast.

My implementation gives me a huuge lag for a player or his enemies, if I use so many nodes :wink:
It is really important for me and I don’t want to use mentioned above implementations in my project. How to handle so many nodes?
Thanks in advance.

I think it’s not a good idea to have a lot of getcomponent.

As others have pointed out, start by making sure that you have an efficient data structure to perform the algorithm on. Then, if an efficient implementation of A* still doesn’t work for you, you can speed it up using Jump Point Search: http://zerowidth.com/2013/05/05/jump-point-search-explained.html

The most common problem is incorrect tie-breaking behavior - you need to make sure to break ties towards the endpoint.

The other most common issue is running the pathfinder every frame; usually it only needs to be done once a second or less.

Also if you have many units moving to the same point, you can search outwards from the endpoint to every unit in one step, rather than from each unit to the end-point individually.


JPS (as mentioned in another answer) does not actually provide as great a speedup as the author’s claim if you are using correct tie-breaking criteria, and is only applicable to 4- and 8-connected grids. You could check out RSR by the same authors, or an incremental algorithm like D*-Lite, which would significantly decrease the speed of pathfinding… but use that only as a last resort. Typically, following the above advice will be more than fast enough, and you time will be better spent optimizing elsewhere.


[Edit] For your specific case, it looks like you are re-initializing the pathfinder every frame!? The initialization of the grid should only need to be done once…