Differences

This shows you the differences between two versions of the page.

--- public:t-622-arti-09-1:lab_3_materials [2009/02/02 14:57] – hannes
+++ public:t-622-arti-09-1:lab_3_materials [2024/04/29 13:33] (current) – external edit 127.0.0.1
@@ Line 26: / Line 26: @@
 </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 <pre>32x32TestMap0n.raw</pre> files) simply by passing the map name to the program when you launch it.
+  - 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 ([[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 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?