A* Demonstration

Applet by James Macgill

Instructions

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

To test:

• Hit the go button.
• Watch as the algorithm tries to find a route from the green dot to the red one.

To load predefined maps:

• Choose a .grd file from the Load Map : menu.
• Hit the go button.

To test with your own map:

• Hit the clear button. (Some junk may be left on the screen for now but it really has been cleared!)
• Select the set start option and choose a location on the grid. (it should turn green)
• Select the set finish option and chose a location on the grid. (it should turn red)
• Hit the go button.

To set up obstacles/paths:

• Select the set blocks option.
• Choose a level for the blocks from the menu underneath
  • Impossible : No route can pass through this cell. (might be water in a game)
  • Very Tough : Going through this cell is hard going (might represent mountains in a game)
  • Tough : Going through this cell is quite hard (might represent a hill or forest in a game)
  • Easy : Going through this cell is easier than a normal square (might be a road in a game)
• Click on the grid to set blocks (click on a block again to clear it)
• Set the start and end points as above.
• Hit the go button.

To try different methods

• Pick a method from the method box
  • Classic A* : An implementation of A*
  • Old : My first attempt, actually its more like Dijkstra’s algorithm.
  • Fudge : Like classic A* except that this one uses a modified heuristic to find a more direct route, suggested by Amit Patel.

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.

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.

Take a look at the Influence Mapping applet.