Differences

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

--- public:t-622-arti-11-1:lab_4_materials [2011/02/01 19:27] – angelo
+++ public:t-622-arti-11-1:lab_4_materials [2024/04/29 13:33] (current) – external edit 127.0.0.1
@@ Line 1: / Line 1: @@
-===== Lab 4: A* Pathfinding Search (WARNING: Work in Progress) =====
+===== 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.
@@ Line 7: / Line 7: @@
   *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).
+    * [[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 ====
@@ Line 29: / Line 31: @@
   - 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>
+      * **Manhattan** heuristics:<code>
 h(n) = D * (abs(n.x-goal.x) + abs(n.y-goal.y))</code>
-      * **Euclidean** heuristics<code>
+      * **Euclidean** heuristics:<code>
 h(n) = D * sqrt((n.x-goal.x)^2 + (n.y-goal.y)^2)</code>
-      * **Diagonal** heuristics<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**: 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.
+      * **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?
+  - 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?