User Tools

Site Tools


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

  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.
      • 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?
/var/www/ · Last modified: 2024/04/29 13:33 by

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki