A* Demonstration

Applet by James Macgill

Opps! The number of user maps was too many for the drop down box to display (at least in my version of Netscape) I've had a little bit of a cleanup of older grids and I'm looking into a longer term solution. Those of you who have saved maps recently should now see them in the list.

[over 4000 users now and over 70 maps saved so far, thanks for the contributions, feel free to add new ones, if you try and fail then the servlet engine is probable down again, please send me an e.mail so that I can fix it, ]

If you like it
rate it.

Instructions

This is a simple interactive implementation of the A* path finding algorithm.

To test:

To load predefined maps:

To test with your own map:

To set up obstacles/paths:

To try different methods

To save maps so that others can look at them:

To install on your own system

astar.zip Is basically a zip of my development directory. It contains all the class and Java files you need as well as some example maps (And some other files you don't need!).
You can run AStarApplet.class both as an applet and as an application.
As an application you can save new maps.
(right click on the above link and choose 'save link as' if Netscape gets confused)

To make me happy (or sad)

Send me some feedback.

About the A* algorithm

(A quick overview for now, I'll go into more depth later)

The algorithm searches outwards from the start point adding up the cost of traversing each cell.
It stores the distance each cell is from the start point and moves on.
When it reaches the end point it searches back, looking for the cell with the shortest distance from the start each step.

For a more detailed introduction to A* take a look at this excellent online tutorial.

For other links to A* sites and all other things AI and Game related try these excellent sites - The GameAI page & Amit Patel's Game Programing Site.

Notes:

The applet has been deliberately slowed down so that you can see what is going on.
There are now three methods available: Classic A* which works properly and Old (my fist attempt) which doesn't.
Fudge is a recent addition that adds a tweak to the heuristic to find more direct routes in less time.(especially with diagonal cases)
Old may appear to operate faster than Classic but this is an artifact of the animation and not a result of the methods efficiency.

Improvements

Add additional path finder methods.
Add more predefined patterns.
[to do] A counter showing the number of tests made by each method.

Other Applets

Take a look at the Influence Mapping applet.

Or perhaps my main project, the GeoTools open source web mapping toolkit



Last Updated April 30 1999.
James Macgill - Center for Computational Geography.
Home Page