From 8b6a959f18e80bc6fca70218e1749718ec2ac0b4 Mon Sep 17 00:00:00 2001 From: Charles Date: Tue, 27 Apr 2010 09:22:03 +0000 Subject: [PATCH] new PathFinder.GetPathAsync to push path finding onto the thread pool; new PathFinder.GetNearbyOpenCell; implemented async path finding in SaberMonster git-svn-id: https://bd85.net/svn/cs3505_group@160 92bb83a3-7c8f-8a45-bc97-515c4e399668 --- CarFire/CarFire/CarFire/PathFinder.cs | 133 ++++++++++++++++++++++++ CarFire/CarFire/CarFire/SaberMonster.cs | 91 ++++++++-------- 2 files changed, 178 insertions(+), 46 deletions(-) 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 /// The cost. public delegate int CostFunction(Point a, Point b); + + /// + /// An async task object to manage a search task that has been + /// put on the thread pool. + /// + public class AsyncTask + { + /// + /// Construct an async task object. + /// + /// A path finder. + /// The cell to start at. + /// The desired destination. + /// The heuristic function. + /// The cost function. + public AsyncTask(PathFinder finder, Point start, Point finish, Heuristic heuristic, CostFunction costFunction) + { + mPathFinder = finder; + mStart = start; + mFinish = finish; + mHeuristic = heuristic; + mCostFunction = costFunction; + } + + + /// + /// Determine whether or not the task has completed. + /// + public bool IsCompleted { get { return mIsDone; } } + + /// + /// Get the resulting path. + /// + public List 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 mPath; + bool mIsDone; + + #endregion + } + #endregion @@ -175,6 +233,81 @@ namespace CarFire } + /// + /// Get a shortest path by putting the task on the thread pool. + /// + /// The cell to start at. + /// The desired destination. + /// The async task object. + public AsyncTask GetPathAsync(Point start, Point finish) + { + AsyncTask task = new AsyncTask(this, start, finish, GetManhattanDistance, GetCost); + ThreadPool.QueueUserWorkItem(new WaitCallback(task.Run)); + return task; + } + + + /// + /// Find the closest open cell that is near another cell. + /// + /// The coordinates. + /// An open cell at or near the given coordinates, + /// or null if no open nearby cell could be found. + 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(); + 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 neighbors = new List(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; + } + + /// /// Get the manhattan distance between two points. This is a simple but /// effective and commonly-used heuristic. diff --git a/CarFire/CarFire/CarFire/SaberMonster.cs b/CarFire/CarFire/CarFire/SaberMonster.cs index a2b5aae..8d66efd 100644 --- a/CarFire/CarFire/CarFire/SaberMonster.cs +++ b/CarFire/CarFire/CarFire/SaberMonster.cs @@ -43,7 +43,7 @@ namespace CarFire { mId = identifier; mMotion = new MovementManager(position); - mRetryInterval = 20 + (position.X * 25789 + position.Y * 259) % 30; + mRetryInterval = 2 + (position.X * 25789 + position.Y * 259) % 30; // We need to keep the game reference in order to get the grid when we // need to find paths. @@ -69,6 +69,7 @@ namespace CarFire if (point != null) mWaypoints.Add(point.Value); } } + mPath = new List(); // Start doing something... StartPacing(); @@ -113,38 +114,49 @@ namespace CarFire Direction GetDirectionToNextCell() { - if (mPathIndex >= mPath.Count) + if (mPath != null) { - // We're done with the current path, so find the path to - // the next waypoint... forever. - mWaypointIndex++; - ChartPath(); - } + if (mPathIndex >= mPath.Count) + { + // We're done with the current path, so find the path to + // the next waypoint... forever. + mWaypointIndex++; + ChartPath(); + } - // We need to make sure our direction is set to the next cell - // we want to be. If our current coordinates match that, we need - // to change our direction to get to the next cell. - if (mPathIndex < mPath.Count && mPath[mPathIndex] == mMotion.Coordinates) - { - mPathIndex++; - mPathDirection = MovementManager.GetDirection(mMotion.Coordinates, mPath[mPathIndex % mPath.Count]); - } + // We need to make sure our direction is set to the next cell + // we want to be. If our current coordinates match that, we need + // to change our direction to get to the next cell. + else if (mPath[mPathIndex] == mMotion.Coordinates) + { + mPathIndex++; + mPathDirection = MovementManager.GetDirection(mMotion.Coordinates, mPath[mPathIndex % mPath.Count]); + } - return mPathDirection; + return mPathDirection; + } + else return Direction.None; } void ChartPath() { - mPath = new List(32); + if (mPathSearch == null) + { + Point waypoint = mWaypoints[mWaypointIndex % mWaypoints.Count]; + PathFinder pathFinder = new PathFinder(mGame.Grid); + Point? nearby = pathFinder.GetNearbyOpenCell(waypoint); + if (nearby != null) mPathSearch = pathFinder.GetPathAsync(mMotion.Coordinates, nearby.Value); - Point waypoint = mWaypoints[mWaypointIndex % mWaypoints.Count]; - PathFinder pathFinder = new PathFinder(mGame.Grid); - List path = pathFinder.GetPath(mMotion.Coordinates, waypoint); - if (path != null) mPath.AddRange(path); + mPathIndex = 0; + mPath = null; + } + else if (mPathSearch.IsCompleted) + { + mPath = (List)mPathSearch.Path; + mPathSearch = null; - mPathIndex = 0; - if (mPathIndex < mPath.Count) mPathDirection = MovementManager.GetDirection(mMotion.Coordinates, mPath[mPathIndex]); - else mPathDirection = Direction.None; + if (mPath != null) mPathDirection = MovementManager.GetDirection(mMotion.Coordinates, mPath[0]); + } } @@ -194,22 +206,8 @@ namespace CarFire } else { - if (mGame.CurrentFrameNumber % mRetryInterval == 0) - { - // Something is in our way, so let's chart a new course. - ChartPath(); - - direction = GetDirectionToNextCell(); - /*if (direction == Direction.None) - { - // If we still can't chart a course, just stand there - // and try to chart again later. - mState = AiState.Standing; - }*/ - - mMotion.Update(timeSpan, direction); - } - else mMotion.Update(timeSpan); + if (mGame.CurrentFrameNumber % mRetryInterval == 0) ChartPath(); + mMotion.Update(timeSpan); } break; @@ -283,15 +281,16 @@ namespace CarFire List mWaypoints = new List(); // List of waypoints that we got from the map. int mWaypointIndex; // Index to the waypoint we're heading for. - List mPath; // List of cells in the path between the position between where - // we started and the waypoint we're heading for. - int mPathIndex; // Index to the cell we're heading for. - Direction mPathDirection; // The direction between our current position and the place we're going. + List mPath; // List of cells in the path between the position between where + // we started and the waypoint we're heading for. + int mPathIndex; // Index to the cell we're heading for. + Direction mPathDirection; // The direction between our current position and the place we're going. int mRetryInterval; + PathFinder.AsyncTask mPathSearch; // If a path search is in progress, this is the task object. - AiState mState; // What is the monster doing? + AiState mState; // What is the monster doing? - Texture2D mTexture; // Obvious. + Texture2D mTexture; // Obvious. #endregion } -- 2.45.2