X-Git-Url: https://git.dogcows.com/gitweb?a=blobdiff_plain;ds=sidebyside;f=CarFire%2FCarFire%2FCarFire%2FPathFinder.cs;h=b6a5fc855638e87694112f0fc254c75828db7aff;hb=692a2af57c7f1586b8513106acf47ddc0ac12748;hp=c37e51863d7ad4b4abe9b18c707de8a8126fcaf8;hpb=d167160264cd2c33de81a71039eddbb959c40bb2;p=chaz%2Fcarfire
diff --git a/CarFire/CarFire/CarFire/PathFinder.cs b/CarFire/CarFire/CarFire/PathFinder.cs
index c37e518..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
@@ -68,7 +126,7 @@ namespace CarFire
/// The cell to start at.
/// The desired destination.
/// A list of points representing the path through the grid,
- /// ends points not included, or null if no path could be found.
+ /// starting point not included, or null if no path could be found.
public List GetPath(Point start, Point finish)
{
return GetPath(start, finish, GetManhattanDistance, GetCost);
@@ -82,7 +140,7 @@ namespace CarFire
/// The desired destination.
/// The heuristic function.
/// A list of points representing the path through the grid,
- /// ends points not included, or null if no path could be found.
+ /// starting point not included, or null if no path could be found.
public List GetPath(Point start, Point finish, Heuristic heuristic)
{
return GetPath(start, finish, heuristic, GetCost);
@@ -96,7 +154,7 @@ namespace CarFire
/// The desired destination.
/// The cost function
/// A list of points representing the path through the grid,
- /// ends points not included, or null if no path could be found.
+ /// starting point not included, or null if no path could be found.
public List GetPath(Point start, Point finish, CostFunction costFunction)
{
return GetPath(start, finish, GetManhattanDistance, costFunction);
@@ -110,7 +168,7 @@ namespace CarFire
/// The heuristic function.
/// The cost function.
/// A list of points representing the path through the grid,
- /// ends points not included, or null if no path could be found.
+ /// starting point not included, or null if no path could be found.
public List GetPath(Point start, Point finish, Heuristic heuristic, CostFunction costFunction)
{
mFringe = new BinaryHeap();
@@ -127,13 +185,10 @@ namespace CarFire
if (cell.Point == finish)
{
List list = new List();
+ list.Add(cell.Point);
cell = cell.Parent;
- while (cell != null && cell.Point != start)
- {
- list.Add(cell.Point);
- cell = cell.Parent;
- }
+ if (cell != null) for (; cell.Point != start; cell = cell.Parent) list.Add(cell.Point);
list.Reverse();
return list;
@@ -152,13 +207,12 @@ namespace CarFire
#endif
foreach (Point point in neighbors)
{
- Cell inQueue = mCells[point.X, point.Y];
-
if (0 <= point.X && point.X < mGridWidth && 0 <= point.Y && point.Y < mGridHeight &&
mGrid[point.X, point.Y])
{
int cost = cell.G + costFunction(cell.Point, point);
+ Cell inQueue = mCells[point.X, point.Y];
if (inQueue == null)
{
Cell neighbor = new Cell(point, cost, heuristic(point, finish), cell);
@@ -179,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.
| |