Center for Analysis and Design of Intelligent Agents

In this lab we will take a closer look at the A* Search algorithm using some Testing Tools and different Heuristics.

• 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:
  • A* Tutorial Page;
  • Intelligent Pathfinding Article (with a Delphi Example for Win32).

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

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

   2. GNU/Linux:

      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 32x32TestMap0n.raw files, changing the n with the desired one) simply by passing the map name to the program when you launch it.
   • Available Heuristics (More information on pathfinding A* heuristics) :
     • Manhattan heuristics

       h(n) = D * (abs(n.x-goal.x) + abs(n.y-goal.y))

     • Euclidean heuristics

       h(n) = D * sqrt((n.x-goal.x)^2 + (n.y-goal.y)^2)

     • Diagonal heuristics

       h_diagonal(n) = min(abs(n.x-goal.x), abs(n.y-goal.y))
       h_straight(n) = (abs(n.x-goal.x) + abs(n.y-goal.y))
       h(n) = D2 * h_diagonal(n) + D * (h_straight(n) - 2*h_diagonal(n)))

     • Diagonal heuristics, with Tie-Breaker: Slight scaling of f(n) to avoid repeating the same f(n) value
     • Diagonal heuristics, with Tie-Breaker, and Cross-Product: Scaling of f(n) with the cross-product of the n→goal vector with the start→goal vector, resulting f(n) scaled higher if n lies further out from the direct goal line.
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?