Sorry your browser is not supported!

A real pet-peeve of mine is A* implementations that are based on grids.

For anyone who understands the origins and applications of the algorithm, these implementations offer crippled functionality and restrict the user to the problem domain of path finding.

A-Star is a state based search algorithm. A state could describe anything from a state in a 15-puzzle problem to the current state of play in a game of chess - it is not restricted to path finding!

Anyway, rant out of the way...

I implemented a more general A* solution a few years ago, but never posted it on the TGC boards. So here it is (click code button).


Whilst this code demonstrates the algorithm as applied to path finding, it is general enough to be applied to other search problems without much modification (you only need to change the node UDT definition and the heuristic function).

To run the demo, you need to download this graph file and place it in the same directory as the compiled executable.

[edit: url tag doesn't like files without extensions!]
http://www.ecs.soton.ac.uk/~dg503/demo

If you want to try your own graphs, I also produced a simple editor to create them with (I'll attach this in the next post). If I've lost you with all this talk of graphs, take a quick peek at the attached screenshot to refresh your memory.

This implementation supports directed graphs out of the box. In other words, you can specify that you can travel from a node A to another node B, but not from B to A. This might be useful for, as an example, a path that travels over a cliff (you can drop down from the cliff, but you can't travel back up it!). However, I didn't include the functionality to specify edge direction in the example editor, so you'll have to add it yourself. The editor stores connectivity data in a standard connectivity matrix, so this is easy to add.

Additionally, this example code is already set for nodes specified in 3D space (although again you'll have to update the editor yourself as I only made it for 2D graphs).

You can of course use this implementation in a grid-based world. It will even be more efficient as the neighbours of each 'grid cell' would be stored in a node's internal list, hence removing the need to check all eight neighbours for connectivity.

Please note that the code is not optimised. When I wrote these, the built-in DBPro array functions were a bit buggy, so I made a few quick functions to manage the priority queue and closed list. I leave this as an exercise to the reader to optimise these functions if needed (if you really want a super-fast priority queue, I recommend implementing it using a Splay tree).

And the editor.

I haven't looked at the code, but... Nice.

The standard "A* for tiled pathfinding" is basically just an extension on the A* algorithm, like you said, it's a limited form of it.

It has all the same characteristics, it has nodes, their status and availability, their cost, etc, etc, it's just that they've been set to work just with a grid as that's the easiest way since all 2D games that used it were, infact, tile-based.

I wrote my own A* a few months ago... It's blisteringly fast, but it is only for 'grids' ( although, could easly be modified for other uses, and for entering only certain nodes ).

Did you use Binary Tree's for this?

Also, how'd you go about storing the adjacency Matrix's? Did you use DBP's internal vectors etc, or did you simply use arrays?

Thanks!

I use the graph-search form of the A* algorithm as general tree-based searches can not account for repeated states without cycle checking (and thus have the undesired side effect of turning a linear problem into an exponential one when many repeated states exist!)

I only use an adjacency matrix in the editor. The majority of an adjacency matrix is redundant data (i.e. which nodes don't connect) and they have a very high memory footprint for a large number of nodes (the space complexity is of the order O(n^2) for n nodes).

I store every node in a one dimensional array. For each node I store a list of indices to its connected nodes. This list is stored internal to each node as a pointer to dynamically allocated memory where the indices are stored. As such the space complexity of this implementation is never worse than O(n+nd) (where d is the maximum node degree that is present in the graph). In other words, it never allocates a byte of data more to connectivity information than it really needs to

Nice.

I remember going through all this in class last semester - Going to have to go through it all again as revision for this semester, so it's good to keep myself sharp

One VERY applicable use for it is an FPS way-point system ( you might be able to sell it to more newbs by calling it that ).

Have you stress tested it? I'd be interested to see how well it performs ( say, with a sample space of 1000 nodes, and 1000 path-finds ).

Anyway, It's 1am, so I've had enough hard thinking for the day

Looks like quality work there DSG. I have only thus far done grid based AStar using binary heaps to speed things up..I was wondering if you could recommend any resources for learning non grid based AStar.
(I am aware I can google but I am interested in a site recomended by you so I'm not fishing through potentialy weaker sites)

Anyhoo keep up the good work and thanks in advance for any sites you can point me at.

@JessTicular
I haven't stress tested it as I never got around to replacing the priority queue implementation (and the closed list, for that matter). When the need arises, I'll make the changes and post some results .


@Baggers
The best resource on the A* star search algorithm is the original paper ("A Formal Basis for the Heuristic Determination of Minimum Cost Paths"). It's available from the ACM library (acm.org), but only if you happen to have a subscription (for Uni students, this shouldn't be a problem).

I couldn't find a decent web-based resource for general A*. This article on Gamasutra gives a good practical overview of the algorithm (and several others) as it pertains to pathfinding.

If you've got some cash to burn, buy the book "Artificial Intelligence: A Modern Approach (second edition)" for the general perspective on the search algorithm, or get the book "Game Programming Gems: Volume 1" for a set of game (and pathfinding) specific articles on A* (as well as tons of other useful stuff!)

Thanks alot man,
Nope I'm not Uni yet...away on a gap year so I havnt got cash either! Will definately give the site a look though.
Thanks again