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:14] – 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.
-In lab 3 we will continue with [[public:t-622-arti-09-1:lab_2_materials|lab 2]] and also take a closer look at the A* Search algorithm using some testing tools.
 ==== 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.
+  *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.sephiroth.it/phpwiki/index.php?title=Path_finder|Simple implementation in Flash]]
+    * [[http://www.policyalmanac.org/games/aStarTutorial.htm|A* Tutorial Page]];
-    * [[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 Delphi Example)]]
+    * 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 ====
   - Download and decompress the {{:public:t-622-arti-09-1:pathfinder.zip|Java Pathfinder Tool}} (developed by Árni Arent at RU).
-  - Test launching it with:<code>
+  - Test launching it with:\\
+    - **Windows**: <code>
 java -Xmx128m -classpath ./pathfinder;. -Djava.library.path=./pathfinder  pathfinder/demo/AStarDemo maps/32x32TestMap01.raw 32 32</code>
+    - **GNU/Linux**: <code>
+java -Xmx128m -classpath ./pathfinder:. -Djava.library.path=./pathfinder  pathfinder/demo/AStarDemo maps/32x32TestMap01.raw 32 32</code>
     * You may have to resize the application window before you see the environment.
     * Some important keys:<code>
@@ Line 26: / Line 29: @@
 </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 ''32x32TestMap0n.raw'' 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 ''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?