public:t-622-arti-09-1:lab_3_materials

In lab 3 we will continue with lab 2 and also take a closer look at the A* Search algorithm using some testing tools.

- 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.

- Download and decompress the Java Pathfinder Tool (developed by Árni Arent at RU).
- Test launching it with:
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

- 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) 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.

- 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?

/var/www/ailab/WWW/wiki/data/pages/public/t-622-arti-09-1/lab_3_materials.txt · Last modified: 2009/02/02 15:23 by hannes