# Center for Analysis and Design of Intelligent Agents

### Site Tools

public:t-622-arti-11-1:lab_4_materials

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:
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/ailab/WWW/wiki/data/pages/public/t-622-arti-11-1/lab_4_materials.txt · Last modified: 2011/02/03 11:31 by angelo

### Page Tools 