A* Pathfinder tutorial

Performance Tuning
#1

Hi all,

I’ve recently had the pleasure of debugging a friends A* pathfinder routine, and decided to write a tutorial on the subject.

For those that don’t know A* is able to find the shortest path between two points avoiding objects in the way.

Which can be located : http://RealmDesigns.Russki.net/?command=tutor&t=3

It is broken down into easy to follow steps, so its relatively painless to follow.

It also covers some of the common pitfalls that will be encountered and performance problems like how to deal with heuristic failure (which is why I’ve posted it in this forum - moderator shoot me if I’m wrong!)

There is no code, so Cut & Paste Queens will be disappointed…

Anyone implementing it in a real-time enironment is going to have to work on their optimization in order to get lots of objects moving!

I’d certainly like to hear from peoples experience!!
Data structure is definately the key, in order to eliminate the sort per move.

All the best.

Woz.

P.S.
Tutorial 2 (Garbage Collection, and how to avoid it) keeps getting bigger and bigger so it isn’t finished (probably wont for some time).
But it should at least be interesting!

#2

i think this belongs to the AI section (http://www.java-gaming.org/cgi-bin/JGOForums/YaBB.cgi?board=AI)

#3

Yes, it should go in the AI section.

And it’s a nice tutorial!

For some other A* tips, I’ve found the AI Game Programming Wisdom book which was just released to be very good as well. Although a lot of the A* stuff deals with C++ optimizations that are not applicable to Java.

#4

My A* tip would be start by adding the target(s) to the open list rather than the starting position. This lets you solve problems like ‘Find the path to the nearest exit.’ where there are several exits more easily.

My question is does any one have any links/code/ideas on the best way to write an efficient priority queue for the open list.

Luke

#5

forgot to mention that the tutorial was very nice indeed.

#6

A typical link list will allow you to insert nodes anywhere in the list.

If you order your link list correctly (not difficult) the nearest node (to the target) will always be at the top, first in the list.

This looks clean in an implementation, but the memory distribution of (the link list) Objects is not contiguous, in that they could located be anywhere in ram. This will generate cache misses (a bad thing).

Although modern Generation Garbage Collection suggests that objects are grouped by age, unfortunately the cache is so small that it will not cover each generations collection of objects (several meg each, or even bigger), the objects are not guaranteed to be localised enough to be in the cache all at the same time.

This is always a major draw back of Object Orientated Languages, which is FAR MORE serious for Java because it does not support structures, which could be used to greater effect in this situation. Although you are not going to get linear memory access (it’s a link list after all) at least each link will be very close to the next.

It does, however, eliminate the need for sort the open list each iteration as you can just insert your nodes (typically only 3, 5 if moving diagonally).

I would strongly suggest using a pool of object, to remove any GC activity that WILL occur.

It soon turns into quite a heavy piece of code, simply because it has to be fast (unless your not using it in a real-time situation).

Of course you could always just call it every other frame (or even less). For those that like using Threads it could be possible to stick everything in a round-robin style list and stick it on a low priority and have it running in the back ground, refeshing targets when possible.

Woz.

#7

Thanks for the reply.

If I use a linked list, is there a smart way to find the right place to insert an entry, or is it best just to start at the bottom and work up until the correct place is found? Another complication seems to be that before an entry is added, you need to check whether it is already on the open list, and this will involve checking every entry in the list unless a more sophisticated data structure is used. Is there a standard way of solving this problem? (Btw, I haven’t done a CS degree, so apologies if I’m missing something that seems obvious).

Luke

#8

Luke,

A linear search will suffice, as the list is ordered always start at the end nearest to the target location (I assume bottom in your case, but I have a tendency to visualise it at the top - just like the stack in the example).

Because A* always tries to move closer to the target each iteration, it makes sense that each node will either be equal to or grater than the value on the top of the stack (if not very close to it). So you will usually only have to search the first few nodes.

(When I say value I mean the distance value from the current location to the target location).

Unless your map has lots of obstacles, and so may make several wrong decisions, a link list will be fine.

On a map with lots of obstacles you will need to start using a different data structure, like a binary tree, so that you can find the location to insert at quicker (as it could be anywhere in the list). A binary tree will accelerate the search into a binary search, which divides the data set in halve repeatedly until it has found the appropriate location.

In order to simplify and accelerate the check to see if the node is already on the open list, you can use a 2 dimensional array for each location on the map, true for already on the open list, false for available to use.

Most people will reduce this down to a single large array, or use a bitmap to save some space.

Woz.

P.S.
Don’t worry about the CS degree, you don’t need one to be able to write good code.