===== Lab 4: A* Pathfinding Search =====

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.

==== Material for Pathfinding ====

  *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:
    * [[http://www.policyalmanac.org/games/aStarTutorial.htm|A* Tutorial Page]];
    * [[http://www.gamasutra.com/features/19990212/sm_01.htm|Intelligent Pathfinding Article]] (with a Delphi Example for Win32);
    * More information on [[http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html| pathfinding A* heuristics]];
    * Another [[http://www.turtlezero.com/models/view.php?model=a-star_2009|Java Applet]] implementing the A* Pathfinding Search.

==== Examining Heuristics for the A* Pathfinding Search ====

  - Download and decompress the {{:public:t-622-arti-09-1:pathfinder.zip|Java Pathfinder Tool}} (developed by Árni Arent at RU).
  - Test launching it with:\\
    - **Windows**: <code>
java -Xmx128m -classpath ./pathfinder;. -Djava.library.path=./pathfinder  pathfinder/demo/AStarDemo maps/32x32TestMap01.raw 32 32</code>
    - **GNU/Linux**: <code>
java -Xmx128m -classpath ./pathfinder:. -Djava.library.path=./pathfinder  pathfinder/demo/AStarDemo maps/32x32TestMap01.raw 32 32</code>
    * You may have to resize the application window before you see the environment.
    * Some important keys:<code>

           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

</code>
  - Now test running the **A* search** on different **maps**, using different **heuristics**. You can choose maps from the "maps" folder (I recommend using the ''32x32TestMap0**X**.raw'' files, where **X** is the **number**) simply by passing the map name to the program when you launch it.
    * Available Heuristics ([[http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html|More information on pathfinding A* heuristics]]) :
      * **Manhattan** heuristics:<code>
h(n) = D * (abs(n.x-goal.x) + abs(n.y-goal.y))</code>
      * **Euclidean** heuristics:<code>
h(n) = D * sqrt((n.x-goal.x)^2 + (n.y-goal.y)^2)</code>
      * **Diagonal** heuristics:<code>
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)))
</code>
      * **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.
  - Imagine that you are developing a computer game with characters that need to traverse a variety of terrains. 
    - Which A* heuristic would you pick?
    - What is your argument for picking that heuristic?
    - Are there any trade-offs?