-using System;\r
+\r
+// Uncomment this to disable diagonal movemet.\r
+//#define ALLOW_DIAGONAL_MOVEMENT\r
+\r
+using System;\r
using System.Collections.Generic;\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
/// <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
/// <param name="start">The cell to start at.</param>\r
/// <param name="finish">The desired destination.</param>\r
/// <returns>A list of points representing the path through the grid,\r
- /// ends points not included, or null if no path could be found.</return>\r
+ /// starting point not included, or null if no path could be found.</return>\r
public List<Point> GetPath(Point start, Point finish)\r
{\r
return GetPath(start, finish, GetManhattanDistance, GetCost);\r
/// <param name="finish">The desired destination.</param>\r
/// <param name="heuristic">The heuristic function.</param>\r
/// <returns>A list of points representing the path through the grid,\r
- /// ends points not included, or null if no path could be found.</return>\r
+ /// starting point not included, or null if no path could be found.</return>\r
public List<Point> GetPath(Point start, Point finish, Heuristic heuristic)\r
{\r
return GetPath(start, finish, heuristic, GetCost);\r
/// <param name="finish">The desired destination.</param>\r
/// <param name="costFunction">The cost function</param>\r
/// <returns>A list of points representing the path through the grid,\r
- /// ends points not included, or null if no path could be found.</return>\r
+ /// starting point not included, or null if no path could be found.</return>\r
public List<Point> GetPath(Point start, Point finish, CostFunction costFunction)\r
{\r
return GetPath(start, finish, GetManhattanDistance, costFunction);\r
/// <param name="heuristic">The heuristic function.</param>\r
/// <param name="costFunction">The cost function.</param>\r
/// <returns>A list of points representing the path through the grid,\r
- /// ends points not included, or null if no path could be found.</return>\r
+ /// starting point not included, or null if no path could be found.</return>\r
public List<Point> GetPath(Point start, Point finish, Heuristic heuristic, CostFunction costFunction)\r
{\r
mFringe = new BinaryHeap<Cell>();\r
mCells = new Cell[mGridWidth, mGridHeight];\r
\r
- Cell startCell = new Cell(start, 0, GetManhattanDistance(start, finish));\r
+ Cell startCell = new Cell(start, 0, heuristic(start, finish));\r
mFringe.Add(startCell);\r
mCells[start.X, start.Y] = startCell;\r
while (mFringe.Count > 0)\r
if (cell.Point == finish)\r
{\r
List<Point> list = new List<Point>();\r
+ list.Add(cell.Point);\r
\r
cell = cell.Parent;\r
- while (cell.Point != start)\r
- {\r
- list.Add(cell.Point);\r
- cell = cell.Parent;\r
- }\r
+ if (cell != null) for (; cell.Point != start; cell = cell.Parent) list.Add(cell.Point);\r
\r
list.Reverse();\r
return list;\r
}\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
+#if ALLOW_DIAGONAL_MOVEMENT\r
neighbors.Add(new Point(cell.Point.X - 1, cell.Point.Y - 1));\r
- neighbors.Add(new Point(cell.Point.X + 0, 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 + 0));\r
- neighbors.Add(new Point(cell.Point.X + 1, cell.Point.Y + 0));\r
neighbors.Add(new Point(cell.Point.X - 1, cell.Point.Y + 1));\r
- neighbors.Add(new Point(cell.Point.X + 0, cell.Point.Y + 1));\r
neighbors.Add(new Point(cell.Point.X + 1, cell.Point.Y + 1));\r
+#endif\r
foreach (Point point in neighbors)\r
{\r
- Cell inQueue = mCells[point.X, point.Y];\r
-\r
if (0 <= point.X && point.X < mGridWidth && 0 <= point.Y && point.Y < mGridHeight &&\r
mGrid[point.X, point.Y])\r
{\r
- int cost = cell.G + GetCost(cell.Point, point);\r
+ int cost = cell.G + costFunction(cell.Point, point);\r
\r
+ Cell inQueue = mCells[point.X, point.Y];\r
if (inQueue == null)\r
{\r
- Cell neighbor = new Cell(point, cost, GetManhattanDistance(point, finish), cell);\r
+ Cell neighbor = new Cell(point, cost, heuristic(point, finish), cell);\r
mFringe.Add(neighbor);\r
mCells[point.X, point.Y] = neighbor;\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
projects / chaz / carfire / blobdiff