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

git-svn-id: https://bd85.net/svn/cs3505_group@160 92bb83a3-7c8f-8a45-bc97-515c4e399668

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.Linq;\r
 using System.Text;\r
 using System.Diagnostics;\r

+using System.Threading;\r

 using Microsoft.Xna.Framework;\r
 \r
 namespace CarFire\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
         /// <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
         #endregion\r
 \r
 \r


@@ -175,6 +233,81 @@ namespace CarFire
         }\r
 \r
 \r
         }\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
         /// <summary>\r
         /// Get the manhattan distance between two points.  This is a simple but\r
         /// effective and commonly-used heuristic.\r

diff --git a/CarFire/CarFire/CarFire/SaberMonster.cs b/CarFire/CarFire/CarFire/SaberMonster.cs
index a2b5aae9f327ee0f6762e544ebb582d882b673c1..8d66efd1a64b12affd3fa48d2e5907a75b332b97 100644 (file)
--- a/CarFire/CarFire/CarFire/SaberMonster.cs
+++ b/CarFire/CarFire/CarFire/SaberMonster.cs
@@ -43,7 +43,7 @@ namespace CarFire
         {\r
             mId = identifier;\r
             mMotion = new MovementManager(position);\r
         {\r
             mId = identifier;\r
             mMotion = new MovementManager(position);\r

-            mRetryInterval = 20 + (position.X * 25789 + position.Y * 259) % 30;\r
+            mRetryInterval = 2 + (position.X * 25789 + position.Y * 259) % 30;\r

 \r
             // We need to keep the game reference in order to get the grid when we\r
             // need to find paths.\r
 \r
             // We need to keep the game reference in order to get the grid when we\r
             // need to find paths.\r


@@ -69,6 +69,7 @@ namespace CarFire
                     if (point != null) mWaypoints.Add(point.Value);\r
                 }\r
             }\r
                     if (point != null) mWaypoints.Add(point.Value);\r
                 }\r
             }\r

+            mPath = new List<Point>();\r

 \r
             // Start doing something...\r
             StartPacing();\r
 \r
             // Start doing something...\r
             StartPacing();\r


@@ -113,38 +114,49 @@ namespace CarFire
 \r
         Direction GetDirectionToNextCell()\r
         {\r
 \r
         Direction GetDirectionToNextCell()\r
         {\r

-            if (mPathIndex >= mPath.Count)\r
+            if (mPath != null)\r

             {\r
             {\r

-                // We're done with the current path, so find the path to\r
-                // the next waypoint... forever.\r
-                mWaypointIndex++;\r
-                ChartPath();\r
-            }\r
+                if (mPathIndex >= mPath.Count)\r
+                {\r
+                    // We're done with the current path, so find the path to\r
+                    // the next waypoint... forever.\r
+                    mWaypointIndex++;\r
+                    ChartPath();\r
+                }\r

 \r
 \r

-            // We need to make sure our direction is set to the next cell\r
-            // we want to be.  If our current coordinates match that, we need\r
-            // to change our direction to get to the next cell.\r
-            if (mPathIndex < mPath.Count && mPath[mPathIndex] == mMotion.Coordinates)\r
-            {\r
-                mPathIndex++;\r
-                mPathDirection = MovementManager.GetDirection(mMotion.Coordinates, mPath[mPathIndex % mPath.Count]);\r
-            }\r
+                // We need to make sure our direction is set to the next cell\r
+                // we want to be.  If our current coordinates match that, we need\r
+                // to change our direction to get to the next cell.\r
+                else if (mPath[mPathIndex] == mMotion.Coordinates)\r
+                {\r
+                    mPathIndex++;\r
+                    mPathDirection = MovementManager.GetDirection(mMotion.Coordinates, mPath[mPathIndex % mPath.Count]);\r
+                }\r

 \r
 \r

-            return mPathDirection;\r
+                return mPathDirection;\r
+            }\r
+            else return Direction.None;\r

         }\r
 \r
         void ChartPath()\r
         {\r
         }\r
 \r
         void ChartPath()\r
         {\r

-            mPath = new List<Point>(32);\r
+            if (mPathSearch == null)\r
+            {\r
+                Point waypoint = mWaypoints[mWaypointIndex % mWaypoints.Count];\r
+                PathFinder pathFinder = new PathFinder(mGame.Grid);\r
+                Point? nearby = pathFinder.GetNearbyOpenCell(waypoint);\r
+                if (nearby != null) mPathSearch = pathFinder.GetPathAsync(mMotion.Coordinates, nearby.Value);\r

 \r
 \r

-            Point waypoint = mWaypoints[mWaypointIndex % mWaypoints.Count];\r
-            PathFinder pathFinder = new PathFinder(mGame.Grid);\r
-            List<Point> path = pathFinder.GetPath(mMotion.Coordinates, waypoint);\r
-            if (path != null) mPath.AddRange(path);\r
+                mPathIndex = 0;\r
+                mPath = null;\r
+            }\r
+            else if (mPathSearch.IsCompleted)\r
+            {\r
+                mPath = (List<Point>)mPathSearch.Path;\r
+                mPathSearch = null;\r

 \r
 \r

-            mPathIndex = 0;\r
-            if (mPathIndex < mPath.Count) mPathDirection = MovementManager.GetDirection(mMotion.Coordinates, mPath[mPathIndex]);\r
-            else mPathDirection = Direction.None;\r
+                if (mPath != null) mPathDirection = MovementManager.GetDirection(mMotion.Coordinates, mPath[0]);\r
+            }\r

         }\r
 \r
 \r
         }\r
 \r
 \r


@@ -194,22 +206,8 @@ namespace CarFire
                     }\r
                     else\r
                     {\r
                     }\r
                     else\r
                     {\r

-                        if (mGame.CurrentFrameNumber % mRetryInterval == 0)\r
-                        {\r
-                            // Something is in our way, so let's chart a new course.\r
-                            ChartPath();\r
-\r
-                            direction = GetDirectionToNextCell();\r
-                            /*if (direction == Direction.None)\r
-                            {\r
-                                // If we still can't chart a course, just stand there\r
-                                // and try to chart again later.\r
-                                mState = AiState.Standing;\r
-                            }*/\r
-\r
-                            mMotion.Update(timeSpan, direction);\r
-                        }\r
-                        else mMotion.Update(timeSpan);\r
+                        if (mGame.CurrentFrameNumber % mRetryInterval == 0) ChartPath();\r
+                        mMotion.Update(timeSpan);\r

                     }\r
 \r
                     break;\r
                     }\r
 \r
                     break;\r


@@ -283,15 +281,16 @@ namespace CarFire
         List<Point> mWaypoints = new List<Point>();      // List of waypoints that we got from the map.\r
         int mWaypointIndex;                              // Index to the waypoint we're heading for.\r
 \r
         List<Point> mWaypoints = new List<Point>();      // List of waypoints that we got from the map.\r
         int mWaypointIndex;                              // Index to the waypoint we're heading for.\r
 \r

-        List<Point> mPath;              // List of cells in the path between the position between where\r
-                                        // we started and the waypoint we're heading for.\r
-        int mPathIndex;                 // Index to the cell we're heading for.\r
-        Direction mPathDirection;       // The direction between our current position and the place we're going.\r
+        List<Point> mPath;                  // List of cells in the path between the position between where\r
+                                            // we started and the waypoint we're heading for.\r
+        int mPathIndex;                     // Index to the cell we're heading for.\r
+        Direction mPathDirection;           // The direction between our current position and the place we're going.\r

         int mRetryInterval;\r
         int mRetryInterval;\r

+        PathFinder.AsyncTask mPathSearch;   // If a path search is in progress, this is the task object.\r

 \r
 \r

-        AiState mState;                 // What is the monster doing?\r
+        AiState mState;                     // What is the monster doing?\r

 \r
 \r

-        Texture2D mTexture;             // Obvious.\r
+        Texture2D mTexture;                 // Obvious.\r

 \r
         #endregion\r
     }\r
 \r
         #endregion\r
     }\r