X-Git-Url: https://git.dogcows.com/gitweb?p=chaz%2Fcarfire;a=blobdiff_plain;f=CarFire%2FCarFire%2FCarFire%2FPathFinder.cs;h=ef41370ef4a3fc442b623d3a7d1d2be3c4748ab0;hp=8b627ace0bed4f8500132ee33da9b6540615940b;hb=122c062297acac44673e947b666c1d72cd23fb1b;hpb=8bd8893e7f7516c76558ad7262e9f9350f5192b9

diff --git a/CarFire/CarFire/CarFire/PathFinder.cs b/CarFire/CarFire/CarFire/PathFinder.cs
index 8b627ac..ef41370 100644
--- a/CarFire/CarFire/CarFire/PathFinder.cs
+++ b/CarFire/CarFire/CarFire/PathFinder.cs
@@ -1,4 +1,8 @@
-using System;
+
+// Uncomment this to disable diagonal movemet.
+//#define ALLOW_DIAGONAL_MOVEMENT
+
+using System;
 using System.Collections.Generic;
 using System.Linq;
 using System.Text;
@@ -64,7 +68,7 @@ namespace CarFire
         /// <param name="start">The cell to start at.</param>
         /// <param name="finish">The desired destination.</param>
         /// <returns>A list of points representing the path through the grid,
-        /// ends points not included, or null if no path could be found.</return>
+        /// starting point not included, or null if no path could be found.</return>
         public List<Point> GetPath(Point start, Point finish)
         {
             return GetPath(start, finish, GetManhattanDistance, GetCost);
@@ -78,7 +82,7 @@ namespace CarFire
         /// <param name="finish">The desired destination.</param>
         /// <param name="heuristic">The heuristic function.</param>
         /// <returns>A list of points representing the path through the grid,
-        /// ends points not included, or null if no path could be found.</return>
+        /// starting point not included, or null if no path could be found.</return>
         public List<Point> GetPath(Point start, Point finish, Heuristic heuristic)
         {
             return GetPath(start, finish, heuristic, GetCost);
@@ -92,7 +96,7 @@ namespace CarFire
         /// <param name="finish">The desired destination.</param>
         /// <param name="costFunction">The cost function</param>
         /// <returns>A list of points representing the path through the grid,
-        /// ends points not included, or null if no path could be found.</return>
+        /// starting point not included, or null if no path could be found.</return>
         public List<Point> GetPath(Point start, Point finish, CostFunction costFunction)
         {
             return GetPath(start, finish, GetManhattanDistance, costFunction);
@@ -106,13 +110,13 @@ namespace CarFire
         /// <param name="heuristic">The heuristic function.</param>
         /// <param name="costFunction">The cost function.</param>
         /// <returns>A list of points representing the path through the grid,
-        /// ends points not included, or null if no path could be found.</return>
+        /// starting point not included, or null if no path could be found.</return>
         public List<Point> GetPath(Point start, Point finish, Heuristic heuristic, CostFunction costFunction)
         {
             mFringe = new BinaryHeap<Cell>();
             mCells = new Cell[mGridWidth, mGridHeight];
 
-            Cell startCell = new Cell(start, 0, GetManhattanDistance(start, finish));
+            Cell startCell = new Cell(start, 0, heuristic(start, finish));
             mFringe.Add(startCell);
             mCells[start.X, start.Y] = startCell;
             while (mFringe.Count > 0)
@@ -123,39 +127,37 @@ namespace CarFire
                 if (cell.Point == finish)
                 {
                     List<Point> list = new List<Point>();
+                    list.Add(cell.Point);
 
                     cell = cell.Parent;
-                    while (cell.Point != start)
-                    {
-                        list.Add(cell.Point);
-                        cell = cell.Parent;
-                    }
+                    if (cell != null) for (; cell.Point != start; cell = cell.Parent) list.Add(cell.Point);
 
                     list.Reverse();
                     return list;
                 }
 
                 List<Point> neighbors = new List<Point>(8);
+                neighbors.Add(new Point(cell.Point.X, cell.Point.Y - 1));
+                neighbors.Add(new Point(cell.Point.X - 1, cell.Point.Y));
+                neighbors.Add(new Point(cell.Point.X + 1, cell.Point.Y));
+                neighbors.Add(new Point(cell.Point.X, cell.Point.Y + 1));
+#if ALLOW_DIAGONAL_MOVEMENT
                 neighbors.Add(new Point(cell.Point.X - 1, cell.Point.Y - 1));
-                neighbors.Add(new Point(cell.Point.X + 0, cell.Point.Y - 1));
                 neighbors.Add(new Point(cell.Point.X + 1, cell.Point.Y - 1));
-                neighbors.Add(new Point(cell.Point.X - 1, cell.Point.Y + 0));
-                neighbors.Add(new Point(cell.Point.X + 1, cell.Point.Y + 0));
                 neighbors.Add(new Point(cell.Point.X - 1, cell.Point.Y + 1));
-                neighbors.Add(new Point(cell.Point.X + 0, cell.Point.Y + 1));
                 neighbors.Add(new Point(cell.Point.X + 1, cell.Point.Y + 1));
+#endif
                 foreach (Point point in neighbors)
                 {
-                    Cell inQueue = mCells[point.X, point.Y];
-
                     if (0 <= point.X && point.X < mGridWidth && 0 <= point.Y && point.Y < mGridHeight &&
                         mGrid[point.X, point.Y])
                     {
-                        int cost = cell.G + GetCost(cell.Point, point);
+                        int cost = cell.G + costFunction(cell.Point, point);
 
+                        Cell inQueue = mCells[point.X, point.Y];
                         if (inQueue == null)
                         {
-                            Cell neighbor = new Cell(point, cost, GetManhattanDistance(point, finish), cell);
+                            Cell neighbor = new Cell(point, cost, heuristic(point, finish), cell);
                             mFringe.Add(neighbor);
                             mCells[point.X, point.Y] = neighbor;
                         }