pathfinder.cs

C#开发的运行于windows mobile ＰＤＡ上的游戏

////////////////////////////////////////////////
// 
// Project: Lines.NET
// Version: 1.1
// Author:  Vladimir L.
// 
// homepage: http://www.boomsoft.org
// e-mail:   [e-mail]
// 
// Copyright (c) 2003-2004, Boomsoft.org
// 

using System;
using System.Drawing;

namespace Lines.Core
{
	/// <summary>
	/// Finds the shortest path from one point to another.
	/// </summary>
	/// <remarks>
	/// <p>This class uses wave algorithm to find the shortest path between two positions
	/// on a 2-D map with obstacles. It assumes that ball can be moved only in vertical or 
	/// horizontal directions (no diagonal movement allowed).</p>
	/// <p>Based upon algorithm described in the article <a href="http://www.gotai.net/documents/doc-imp-003.aspx">http://www.gotai.net/documents/doc-imp-003.aspx</a></p>
	/// </remarks>
	/// <example>
	/// <code>
	/// X - an obstacle.
	/// S - start position.
	/// D - destination.
	/// * - path.
	///      - - - - - - - - - 
	///     | | | | | | | | | |
	///      - - - - - - - - - 
	///     | | | | | | | | | |
	///      - - - - - - - - - 
	///     | | | |*|*|*|D| | |
	///      - - - - - - - - - 
	///     | |X| |*|X| | | | |
	///      - - - - - - - - - 
	///     | | | |*| |X| | | |
	///      - - - - - - - - - 
	///     | | |X|*| | |X| | |
	///      - - - - - - - - - 
	///     | | | |*|*|S| |X| |
	///      - - - - - - - - - 
	///     | | | | | | | | | |
	///      - - - - - - - - - 
	///     | | | | | | | | | |
	///      - - - - - - - - - 
	/// </code>
	/// </example>
	public class PathFinder
	{
		/// <summary>
		/// Constant that indicates a free position on the map.
		/// </summary>
		public static readonly int POS_FREE     = 0;
		/// <summary>
		/// Constant that indicates an obstacle on the map.
		/// </summary>
		public static readonly int POS_OCCUPIED = -1;
		/// <summary>
		/// Constant that indicates a start position on the map.
		/// </summary>
		public static readonly int POS_START    = -2;
		/// <summary>
		/// Constant that indicates a destination position on the map.
		/// </summary>
		public static readonly int POS_END      = 1;

		/// <summary>
		/// The 2-D matrix that describes a map.
		/// </summary>
		private int[,] matrix;
		/// <summary>
		/// Holds the upper limit of path length for wave algorithm.
		/// </summary>
		private int maxPathLength;

		/// <summary>
		/// Creates an instance of PathFinder class for given map.
		/// </summary>
		/// <remarks>
		/// The upper limit of path lenght <see cref="MaxPathLength"/> in this case is caculated 
		/// as a double sum of matrix dimensions.
		/// </remarks>
		/// <param name="matrix">The map.</param>
		public PathFinder(int[,] matrix)
		{
			this.matrix = matrix;
			this.maxPathLength = (Width + Height) * 2;
		}

		/// <summary>
		/// Gets or sets the upper limit of path length for wave algorithm.
		/// </summary>
		public int MaxPathLength
		{
			set {maxPathLength = value;}
			get {return maxPathLength;}
		}

		/// <summary>
		/// Gets the width of map (size of dimention X).
		/// </summary>
		public int Width
		{
			get {return matrix.GetLength(0);}
		}

		/// <summary>
		/// Gets the height of map (size of dimention Y).
		/// </summary>
		public int Height
		{
			get {return matrix.GetLength(1);}
		}

		/// <summary>
		/// Sets a value for a certain posion on the map.
		/// </summary>
		/// <param name="x">The x coordinate of position.</param>
		/// <param name="y">The y coordinate of position.</param>
		/// <param name="val">The new value to be set.</param>
		public void SetPosValue(int x, int y, int val)
		{
			matrix[x, y] = val;
		}

		/// <summary>
		/// Sets a start position on the map.
		/// </summary>
		/// <param name="x">The x coordinate of start position.</param>
		/// <param name="y">The y coordinate of start position.</param>
		protected void SetStartPos(int x, int y)
		{
			SetPosValue(x, y, POS_START);
		}
		
		/// <summary>
		/// Sets an end position on the map.
		/// </summary>
		/// <param name="x">The x coordinate of end position.</param>
		/// <param name="y">The y coordinate of end position.</param>
		protected void SetEndPos(int x, int y)
		{
			SetPosValue(x, y, POS_END);
		}
		
		/// <summary>
		/// Finds the shortest path from between two locations on the map.
		/// </summary>
		/// <param name="start">The start location.</param>
		/// <param name="end">The end location.</param>
		/// <returns>The path from start position to the end position as an array of locations on the map,
		/// or <c>null</c> if algorithm has failed to find a path.</returns>
		/// <remarks>
		/// <p>The implementation of wave algorithm itself.</p>
		/// <p>Theis algorithm will always find one of the shortest paths between <c>start</c> and <c>end</c>
		/// locations if such one exists. This algorithm may fail to find it due to the following reasons:
		/// <list type="number">
		///		<item>
		///			<description>There is no way to go from start point to end because of obstacles.</description>
		///		</item>
		///		<item>
		///			<description>The shortest way is longer then <see cref="MaxPathLength"/> property.</description>
		///		</item>
		/// </list>
		/// </p>
		/// </remarks>
		public Point[] FindPath(Point start, Point end)
		{
			SetStartPos(start.X, start.Y);
			SetEndPos(end.X, end.Y);

			bool found = false;
			int current = POS_END;
			while ((current < (maxPathLength + POS_END)) && (!found))
			{
				for (int i = 0; i < Width; i++)
				{
					for (int j = 0; j < Height; j++)
					{
						if (matrix[i, j] == current)
						{
							if (CheckNeighbour(i - 1, j, current + 1))
							{
								found = true;
							}
							if (CheckNeighbour(i + 1, j, current + 1))
							{
								found = true;
							}
							if (CheckNeighbour(i, j - 1, current + 1))
							{
								found = true;
							}
							if (CheckNeighbour(i, j + 1, current + 1))
							{
								found = true;
							}
						}
					}
				}
				current++;
			}

			Point[] result = null;
			if (found)
			{
				// Build the path
				result = new Point[current - POS_END];
				Point pos = start;
				int index = 0;
				while (pos != end)
				{
					pos = GetMinNearest(pos);
					result[index++] = pos;
				}
			} 
			else 
			{
				// There is no solution
			}

			return result;
		}
		
		/// <summary>
		/// Checks up a location for the appearence of start position.
		/// </summary>
		/// <param name="x">The x coordinate of location.</param>
		/// <param name="y">The y coordinate of location.</param>
		/// <param name="val">The current step of wave algorithm.</param>
		/// <returns><c>true</c> if location <c>[x, y]</c> is marked as a start position on the map, 
		/// <c>false</c> otherwise.</returns>
		/// <remarks>
		/// This method is internally used to verify whether location is a start position or not.
		/// In case the location remains as a free position it is updated with a current step of 
		/// wave algorithm.
		/// </remarks>
		private bool CheckNeighbour(int x, int y, int val)
		{
			if (IsInBounds(x, y))
			{
				if (matrix[x, y] == POS_START)
				{
					return true;
				}
				if (matrix[x, y] == POS_FREE)
				{
					matrix[x, y] = val;
				}
			}
			return false;
		}

		/// <summary>
		/// Verifies whether location coordinates are inside bounds of the map or not.
		/// </summary>
		/// <param name="x">The x coordinate of location.</param>
		/// <param name="y">The y coordinate of location.</param>
		/// <returns><c>true</c> if the location is placed on the map, <c>false</c> in case it is out of 
		/// map bounds</returns>
		private bool IsInBounds(int x, int y)
		{
			if ((x < 0) || (y < 0) || (x >= Width) || (y >= Height))
			{
				return false;
			}
			return true;
		}

		/// <summary>
		/// Gets the neighbour position to the provided location with a minimum value.
		/// </summary>
		/// <param name="pos">The position to find the minimum neighbour for.</param>
		/// <returns>The location of the neighbour position with a minimum value.</returns>
		private Point GetMinNearest(Point pos)
		{
			int min = matrix[pos.X, pos.Y];
			
			Point result = pos;
			int x, y;

			x = pos.X - 1;
			y = pos.Y;
			if (IsInBounds(x, y) && (matrix[x, y] > 0))
			{
				if ((min < 0) || (matrix[x, y] < min))
				{
					min = matrix[x, y];
					result = new Point(x, y);
				}
			}
			x = pos.X + 1;
			y = pos.Y;
			if (IsInBounds(x, y) && (matrix[x, y] > 0))
			{
				if ((min < 0) || (matrix[x, y] < min))
				{
					min = matrix[x, y];
					result = new Point(x, y);
				}
			}
			x = pos.X;
			y = pos.Y - 1;
			if (IsInBounds(x, y) && (matrix[x, y] > 0))
			{
				if ((min < 0) || (matrix[x, y] < min))
				{
					min = matrix[x, y];
					result = new Point(x, y);
				}
			}
			x = pos.X;
			y = pos.Y + 1;
			if (IsInBounds(x, y) && (matrix[x, y] > 0))
			{
				if ((min < 0) || (matrix[x, y] < min))
				{
					min = matrix[x, y];
					result = new Point(x, y);
				}
			}
			return result;
		}
	}
}