X-Git-Url: https://git.dogcows.com/gitweb?p=chaz%2Fcarfire;a=blobdiff_plain;f=CarFire%2FCarFire%2FCarFire%2FPathFinder.cs;h=ef41370ef4a3fc442b623d3a7d1d2be3c4748ab0;hp=91724384ab2ac4cccca98b2c830b66c0bff2c1e7;hb=122c062297acac44673e947b666c1d72cd23fb1b;hpb=681f16a95c1c67bdd40ed16842a70f8e10ba31e1
diff --git a/CarFire/CarFire/CarFire/PathFinder.cs b/CarFire/CarFire/CarFire/PathFinder.cs
index 9172438..ef41370 100644
--- a/CarFire/CarFire/CarFire/PathFinder.cs
+++ b/CarFire/CarFire/CarFire/PathFinder.cs
@@ -1,4 +1,8 @@
-using System;
+
+// Uncomment this to disable diagonal movemet.
+//#define ALLOW_DIAGONAL_MOVEMENT
+
+using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
@@ -64,7 +68,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 +82,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 +96,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,7 +110,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();
@@ -123,36 +127,34 @@ 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 + costFunction(cell.Point, point);
+ Cell inQueue = mCells[point.X, point.Y];
if (inQueue == null)
{
Cell neighbor = new Cell(point, cost, heuristic(point, finish), cell);
|