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 for the Pathfinding problem.

• 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);
  • More information on pathfinding A* heuristics;
  • Another Java Applet implementing the A* Pathfinding Search.

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 32x32TestMap0X.raw files, where X is the number) 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 h(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 terrains.
   1. Which A* heuristic would you pick?
   2. What is your argument for picking that heuristic?
   3. Are there any trade-offs?