Center for Analysis and Design of Intelligent Agents

In lab 3 we will continue with lab 2 and also take a closer look at the A* Search algorithm using some testing tools.

There are many resources available for studying A* in the domain of pathfinding. Here are a few that you can take a quick look at now and then come back to them later when you want to implement something yourself.

• Simple implementation in Flash
• A* Tutorial Page
• Intelligent Pathfinding Article (with Delphi Example)

1. Download and decompress the Java Pathfinder Tool (developed by Árni Arent at RU).
2. Test launching it with:

   java -Xmx128m -classpath ./pathfinder;. -Djava.library.path=./pathfinder  pathfinder/demo/AStarDemo maps/32x32TestMap01.raw 32 32

   • You may have to resize the application window before you see the environment.
   • Some important keys:

                ENTER    Run the chosen algorithm
                SPACE    Show all generated search nodes
                C        Show the final cost
                1,2,3..  Pick a heuristic function
                +/-      Zoon in/out of map
     

3. Now test running the A* search on different maps, using different heuristics. You can choose maps from the “maps” folder (I recommend using the <pre>32x32TestMap0n.raw</pre> files) simply by passing the map name to the program when you launch it.
4. Imagine that you are developing a computer game with characters that need to traverse a variety of terrain. Which A* heuristic would you pick? What is your argument for picking that heuristic? Are there any trade offs?