X-Git-Url: https://git.dogcows.com/gitweb?a=blobdiff_plain;f=CarFire%2FCarFire%2FCarFire%2FPathFinder.cs;h=b6a5fc855638e87694112f0fc254c75828db7aff;hb=2079dadac9b317d61015a9e37eefc9aca761c1ad;hp=8b627ace0bed4f8500132ee33da9b6540615940b;hpb=8bd8893e7f7516c76558ad7262e9f9350f5192b9;p=chaz%2Fcarfire
diff --git a/CarFire/CarFire/CarFire/PathFinder.cs b/CarFire/CarFire/CarFire/PathFinder.cs
index 8b627ac..b6a5fc8 100644
--- a/CarFire/CarFire/CarFire/PathFinder.cs
+++ b/CarFire/CarFire/CarFire/PathFinder.cs
@@ -1,8 +1,13 @@
-using System;
+
+// Uncomment this to disable diagonal movemet.
+//#define ALLOW_DIAGONAL_MOVEMENT
+
+using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
+using System.Threading;
using Microsoft.Xna.Framework;
namespace CarFire
@@ -35,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
@@ -64,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);
@@ -78,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);
@@ -92,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);
@@ -106,13 +168,13 @@ 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();
mCells = new Cell[mGridWidth, mGridHeight];
- Cell startCell = new Cell(start, 0, GetManhattanDistance(start, finish));
+ Cell startCell = new Cell(start, 0, heuristic(start, finish));
mFringe.Add(startCell);
mCells[start.X, start.Y] = startCell;
while (mFringe.Count > 0)
@@ -123,39 +185,37 @@ namespace CarFire
if (cell.Point == finish)
{
List list = new List();
+ list.Add(cell.Point);
cell = cell.Parent;
- while (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;
}
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));
+#if ALLOW_DIAGONAL_MOVEMENT
neighbors.Add(new Point(cell.Point.X - 1, cell.Point.Y - 1));
- neighbors.Add(new Point(cell.Point.X + 0, 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 + 0));
- neighbors.Add(new Point(cell.Point.X + 1, cell.Point.Y + 0));
neighbors.Add(new Point(cell.Point.X - 1, cell.Point.Y + 1));
- neighbors.Add(new Point(cell.Point.X + 0, cell.Point.Y + 1));
neighbors.Add(new Point(cell.Point.X + 1, cell.Point.Y + 1));
+#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 + GetCost(cell.Point, point);
+ int cost = cell.G + costFunction(cell.Point, point);
+ Cell inQueue = mCells[point.X, point.Y];
if (inQueue == null)
{
- Cell neighbor = new Cell(point, cost, GetManhattanDistance(point, finish), cell);
+ Cell neighbor = new Cell(point, cost, heuristic(point, finish), cell);
mFringe.Add(neighbor);
mCells[point.X, point.Y] = neighbor;
}
@@ -173,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.
| |