Faster A* Pathfinding

-

 

I know it doesn't answer your question, but have you seen this?:
http://www.arongranberg.com/unity/a-pathfinding/

 

I have looked at that but had way more trouble implementing it into my game. The setup uses a 2D grid system of cells which are either non-walkable or walkable. In addition to my first point creating my own system wasn't too hard and it's more customizable that way.

 

A few suggestions (I'm not sure which ones will be applicable to what you are doing)...

You appear to be using GameObjects in the scene to mark the positions of squares on the 2D grid. You will probably find it much easier to calculate the position of a grid square from its <X,Y> index in the grid. Also, it is easy to determine which squares are neighbours using this arrangement, and you can just use a 2D array of boolean to denote which squares in the grid are inaccessible. If you do prefer to use the GameObjects to implement the grid, you will find it much faster to calculate which squares are neighbours once at the start and then store this information in a graph structure. An implementation of a graph that is very suitable for this kind of thing is posted in this thread. This will save the overhead of searching the array repeatedly in GetNeighbours (ie, you simply look up which cells are neighbours of the current cell).

Rather than search for the current cell and target cell by distance on each update, simply store the array indices of these cells in variables. The search itself is time-consuming but it is especially bad when you use the expensive Distance operation so frequently. Also, if you are just comparing distances between positions to see which is closest then it is much quicker to compare squared distances instead:-

Code (csharp):

1. function SqrDistance(ptA: Vector3, ptB: Vector3) {
2.   return (ptA - ptB).sqrMagnitude;
3. }

The GameObject array or grid system is fine for defining the layout of the grid but you can do better as regards searching. Rather than recalculate the distance and heuristic information repeatedly, you can make your own class to store it once you've calculated it the first time:-

Code (csharp):

1. class CellInAction {
2.   var position: Vector3;  // ...or grid ref as <X, Y> coordinate.
3.   var f: float;
4.   var g: float;
5.   var originalGO: GameObject;
6.   // Other stuff as required.
7. }

With a class like this, you can use a priority queue to hold the open list and a hashtable/dictionary to hold the closed list. These structures perform their searches *much* faster than a simple linear search through an array. The priority queue can be used to keep items in the open list in order of their total cost values with much less overhead than sorting the array.

If the grid system only allows rectilinear and/or diagonal moves then you can make the path-so-far and heuristic values more accurate and avoid the expensive Vector3.Distance call. Check out this Wikipedia page for more information.

Anyway, just a few thoughts! Any of them will probably help performance quite a bit but I would say the first priority is to cut down on the repeated Vector3.Distance calculations if you can.

 

This package is one of the fastest ones, easier to understand and even easier to implement.

It uses a heap priority queue.

 

I'm new to hash tables and priority queues, I've looked them up a bit and found that hash tables are somewhat similar to arrays, however my attempts at replacing the arrays with hash tables didn't work. Most of the examples I found weren't in Java, some psuedo-code for some of the things I'm doing (for priority queues and hash tables) would help.

 

priority queue is; you add something to your arrays end, it automatically increases its queue down(to the head) until the comparing value is less or more than the one infront. Thus, it doesnt re-sort the whole array but a portion of it. And keeps the array sorted almost all the time, so whenever you grab the first in array, you always get the best value. Which is why its faster method.

Net 4.0 have some of this functionality already builtin but as far as i know its unavailable in unity 3.5(not sure though never tried and ive been working on my custom priorityqueue class for almost a year now, i think its better)

Java already has such a functionality builtin. But unity doesnt use java.
Hash table is not the same thing for the purpose of astar.

Finally, if you want to work with unity and do complex stuff. Work with C# unless you are a javascript guru or something.

 

Bump.