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

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