new PathFinder.GetPathAsync to push path finding onto the thread pool; new PathFinder...

[chaz/carfire] / CarFire / CarFire / CarFire / PathFinder.cs

diff --git a/CarFire/CarFire/CarFire/PathFinder.cs b/CarFire/CarFire/CarFire/PathFinder.cs
index ef41370ef4a3fc442b623d3a7d1d2be3c4748ab0..b6a5fc855638e87694112f0fc254c75828db7aff 100644 (file)
--- a/CarFire/CarFire/CarFire/PathFinder.cs
+++ b/CarFire/CarFire/CarFire/PathFinder.cs
@@ -7,6 +7,7 @@ using System.Collections.Generic;
 using System.Linq;\r
 using System.Text;\r
 using System.Diagnostics;\r
+using System.Threading;\r
 using Microsoft.Xna.Framework;\r
 \r
 namespace CarFire\r
@@ -39,6 +40,63 @@ namespace CarFire
         /// <returns>The cost.</returns>\r
         public delegate int CostFunction(Point a, Point b);\r
 \r
+\r
+        /// <summary>\r
+        /// An async task object to manage a search task that has been\r
+        /// put on the thread pool.\r
+        /// </summary>\r
+        public class AsyncTask\r
+        {\r
+            /// <summary>\r
+            /// Construct an async task object.\r
+            /// </summary>\r
+            /// <param name="finder">A path finder.</param>\r
+            /// <param name="start">The cell to start at.</param>\r
+            /// <param name="finish">The desired destination.</param>\r
+            /// <param name="heuristic">The heuristic function.</param>\r
+            /// <param name="costFunction">The cost function.</param>\r
+            public AsyncTask(PathFinder finder, Point start, Point finish, Heuristic heuristic, CostFunction costFunction)\r
+            {\r
+                mPathFinder = finder;\r
+                mStart = start;\r
+                mFinish = finish;\r
+                mHeuristic = heuristic;\r
+                mCostFunction = costFunction;\r
+            }\r
+\r
+\r
+            /// <summary>\r
+            /// Determine whether or not the task has completed.\r
+            /// </summary>\r
+            public bool IsCompleted { get { return mIsDone; } }\r
+\r
+            /// <summary>\r
+            /// Get the resulting path.\r
+            /// </summary>\r
+            public List<Point> Path { get { return mPath; } }\r
+\r
+\r
+            #region Private Members\r
+\r
+            public void Run(object context)\r
+            {\r
+                mPath = mPathFinder.GetPath(mStart, mFinish, mHeuristic, mCostFunction);\r
+                mIsDone = true;\r
+            }\r
+\r
+\r
+            PathFinder mPathFinder;\r
+            Point mStart;\r
+            Point mFinish;\r
+            Heuristic mHeuristic;\r
+            CostFunction mCostFunction;\r
+\r
+            List<Point> mPath;\r
+            bool mIsDone;\r
+\r
+            #endregion\r
+        }\r
+\r
         #endregion\r
 \r
 \r
@@ -175,6 +233,81 @@ namespace CarFire
         }\r
 \r
 \r
+        /// <summary>\r
+        /// Get a shortest path by putting the task on the thread pool.\r
+        /// </summary>\r
+        /// <param name="start">The cell to start at.</param>\r
+        /// <param name="finish">The desired destination.</param>\r
+        /// <returns>The async task object.</returns>\r
+        public AsyncTask GetPathAsync(Point start, Point finish)\r
+        {\r
+            AsyncTask task = new AsyncTask(this, start, finish, GetManhattanDistance, GetCost);\r
+            ThreadPool.QueueUserWorkItem(new WaitCallback(task.Run));\r
+            return task;\r
+        }\r
+\r
+\r
+        /// <summary>\r
+        /// Find the closest open cell that is near another cell.\r
+        /// </summary>\r
+        /// <param name="coordinates">The coordinates.</param>\r
+        /// <returns>An open cell at or near the given coordinates,\r
+        /// or null if no open nearby cell could be found.</returns>\r
+        public Point? GetNearbyOpenCell(Point coordinates)\r
+        {\r
+            if (0 <= coordinates.X && coordinates.X < mGridWidth && 0 <= coordinates.Y && coordinates.Y < mGridHeight &&\r
+                mGrid[coordinates.X, coordinates.Y])\r
+            {\r
+                return coordinates;\r
+            }\r
+\r
+            mFringe = new BinaryHeap<Cell>();\r
+            mCells = new Cell[mGridWidth, mGridHeight];\r
+\r
+            Cell startCell = new Cell(coordinates, 0, 0);\r
+            mFringe.Add(startCell);\r
+            mCells[coordinates.X, coordinates.Y] = startCell;\r
+            while (mFringe.Count > 0)\r
+            {\r
+                Cell cell = mFringe.GetNext();\r
+\r
+                List<Point> neighbors = new List<Point>(8);\r
+                neighbors.Add(new Point(cell.Point.X, cell.Point.Y - 1));\r
+                neighbors.Add(new Point(cell.Point.X - 1, cell.Point.Y));\r
+                neighbors.Add(new Point(cell.Point.X + 1, cell.Point.Y));\r
+                neighbors.Add(new Point(cell.Point.X, cell.Point.Y + 1));\r
+                neighbors.Add(new Point(cell.Point.X - 1, cell.Point.Y - 1));\r
+                neighbors.Add(new Point(cell.Point.X + 1, cell.Point.Y - 1));\r
+                neighbors.Add(new Point(cell.Point.X - 1, cell.Point.Y + 1));\r
+                neighbors.Add(new Point(cell.Point.X + 1, cell.Point.Y + 1));\r
+                foreach (Point point in neighbors)\r
+                {\r
+                    if (0 <= point.X && point.X < mGridWidth && 0 <= point.Y && point.Y < mGridHeight)\r
+                    {\r
+                        if (mGrid[point.X, point.Y])\r
+                        {\r
+                            return point;\r
+                        }\r
+                        else\r
+                        {\r
+                            int cost = cell.G + GetCost(cell.Point, point);\r
+\r
+                            Cell inQueue = mCells[point.X, point.Y];\r
+                            if (inQueue == null)\r
+                            {\r
+                                Cell neighbor = new Cell(point, cost, 0);\r
+                                mFringe.Add(neighbor);\r
+                                mCells[point.X, point.Y] = neighbor;\r
+                            }\r
+                        }\r
+                    }\r
+                }\r
+            }\r
+\r
+            return null;\r
+        }\r
+\r
+\r
         /// <summary>\r
         /// Get the manhattan distance between two points.  This is a simple but\r
         /// effective and commonly-used heuristic.\r