destroyfinder.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;
using System.Collections;

namespace Lines.Core
{
	/// <summary>
	/// Encloses algorithm to find all balls that compose lines (vertical, horizontal 
	/// and diagonal) of <c>n</c> and more balls of the same color in a row.
	/// </summary>
	/// <remarks>
	/// <p>This class is used to determine balls that should be removed from a board
	/// at current step.</p>
	/// <p style="color:red"><i>The algorithms to find lines appearance are kind of clumsy by now, especially for
	/// diagonal lines, but they seem <b>to be working</b>. Probably I'll come back latter with 
	/// better implementation.</i></p>
	/// </remarks>
	public class DestroyFinder
	{
		/// <summary>
		/// Describes balls distributed over the board.
		/// </summary>
		private int[,] matrix;
		/// <summary>
		/// Defines the minimum amount of balls of the same color in a line which is enough
		/// to remove this line from a board.
		/// </summary>
		private int ballsInLine;

		/// <summary>
		/// Creates an instance of <c>DestroyFinder</c> class.
		/// </summary>
		/// <param name="matrix">describes balls distributed over the board. Each color is represented by 
		/// a number greater then <c>0</c>. <c>0</c> indicates an empty field of a board.</param>
		/// <param name="ballsInLine">defines the minimum amount of balls of the same color in a line,
		/// which is enough to remove this line from a board.</param>
		public DestroyFinder(int[,] matrix, int ballsInLine)
		{
			this.matrix = matrix;
			this.ballsInLine = ballsInLine;
		}
		
		/// <summary>
		/// Read-only property that returns the width of a board (matrix).
		/// </summary>
		public int Width
		{
			get {return matrix.GetLength(0);}
		}

		/// <summary>
		/// Read-only property that returns the height of a board (matrix).
		/// </summary>
		public int Height
		{
			get {return matrix.GetLength(1);}
		}

		/// <summary>
		/// Looks for the appearance of ball lines of the same color with length greater
		/// or equal to <see cref="ballsInLine"/> which is defined by the constructor of this 
		/// class.
		/// <seealso cref="DestroyFinder(int[,], int)"/>
		/// </summary>
		/// <returns>An array of locations on the board where the balls are placed that are 
		/// supposed to be removed.</returns>
		/// <remarks>
		/// This is the search for lines method itself. It consistently executes search over horizontal,
		/// vertical and both side diagonal lines to an appearance of balls of the same color with length
		/// greater or equal to defined one.
		/// </remarks>
		public Point[] FindLocations()
		{
			ArrayList locations = new ArrayList();
			
			// Horizontal lines
			AddUnique(locations, FindHorizontal());
			// Vertical lines
			AddUnique(locations, FindVertical());
			// NW-to-SE lines
			AddUnique(locations, FindDiagonal());
			// NE-to-SW lines
			AddUnique(locations, FindDiagonalBackward());
			
			Point[] result = new Point[locations.Count];
			for (int i = 0; i < locations.Count; i++)
			{
				result[i] = (Point)locations[i];
			}

			return result;
		}

		/// <summary>
		/// Helps to fill an array list with only positions (<see cref="System.Drawing.Point"/>) that
		/// are unique to this array.
		/// </summary>
		/// <param name="addTo">the array list where new positions supposed to be add to.</param>
		/// <param name="addFrom">the array list that encloses new positions.</param>
		/// <remarks>
		/// This method will add to array list <c>addTo</c> only those positions from array list
		/// <c>addFrom</c>, which are not yet enclosed by this array. This method is used to avoid
		/// duplicates in output.
		/// </remarks>
		private void AddUnique(ArrayList addTo, ArrayList addFrom)
		{
			for (int i = 0; i < addFrom.Count; i++)
			{
				Point pos = (Point)addFrom[i];
				bool unique = true;
				for (int j = 0; j < addTo.Count; j++)
				{
					if (((Point)addTo[j]) == pos)
					{
						unique = false;
						break;
					}
				}
				if (unique)
				{
					addTo.Add(pos);
				}
			}
		}

		/// <summary>
		/// Looks up for <b>horizontal</b> lines of balls of the same color.
		/// </summary>
		/// <returns>An array list of positions (<see cref="System.Drawing.Point"/>) of balls that supposed 
		/// to be removed from the board at current step.</returns>
		private ArrayList FindHorizontal()
		{
			ArrayList locations = new ArrayList();

			for (int y = 0; y < Height; y++)
			{
				// Each horizontal line
				int length = 0;
				int x = 0;
				int color = -1;
				while (x < Width)
				{
					int newColor = matrix[x, y];
					if ((newColor > 0) && (newColor == color))
					{
						length++;
					} 
					else 
					{
						if (length >= ballsInLine)
						{
							for (int i = 0; i < length; i++)
							{
								locations.Add(new Point(x - i - 1, y));
							}
						}

						if (newColor > 0)
						{
							length = 1;
							color = newColor;
						}
						else
						{
							length = 0;
							color = -1;
						}
					}
					x++;
				}
				if (length >= ballsInLine)
				{
					for (int i = 0; i < length; i++)
					{
						locations.Add(new Point(x - i - 1, y));
					}
				}
			}

			return locations;
		}

		/// <summary>
		/// Looks up for <b>vertical</b> lines of balls of the same color.
		/// </summary>
		/// <returns>An array list of positions (<see cref="System.Drawing.Point"/>) of balls that supposed 
		/// to be removed from the board at current step.</returns>
		private ArrayList FindVertical()
		{
			ArrayList locations = new ArrayList();

			for (int x = 0; x < Width; x++)
			{
				// Each vertical line
				int length = 0;
				int y = 0;
				int color = -1;
				while (y < Height)
				{
					int newColor = matrix[x, y];
					if ((newColor > 0) && (newColor == color))
					{
						length++;
					} 
					else 
					{
						if (length >= ballsInLine)
						{
							for (int i = 0; i < length; i++)
							{
								locations.Add(new Point(x, y - i - 1));
							}
						}

						if (newColor > 0)
						{
							length = 1;
							color = newColor;
						}
						else
						{
							length = 0;
							color = -1;
						}
					}
					y++;
				}
				if (length >= ballsInLine)
				{
					for (int i = 0; i < length; i++)
					{
						locations.Add(new Point(x, y - i - 1));
					}
				}
			}

			return locations;
		}
		
		/// <summary>
		/// Looks up for <b>diagonal</b> (NW-to-SE oriented) lines of balls of the same color.
		/// </summary>
		/// <returns>An array list of positions (<see cref="System.Drawing.Point"/>) of balls that supposed 
		/// to be removed from the board at current step.</returns>
		private ArrayList FindDiagonal()
		{
			ArrayList locations = new ArrayList();

			for (int line = ballsInLine - 1; line < (Width + Height - 2); line++)
			{
				// Each diagonal line
				int length = 0;
				int color = -1;
				int x = 0, y = line - x;
				for (; x <= line; x++, y = line - x)
				{
					if ((x < Width) && (y < Height))
					{
						int newColor = matrix[x, y];
						if ((newColor > 0) && (newColor == color))
						{
							length++;
						} 
						else 
						{
							if (length >= ballsInLine)
							{
								for (int i = 0; i < length; i++)
								{
									locations.Add(new Point(x - i - 1, y + i + 1));
								}
							}

							if (newColor > 0)
							{
								length = 1;
								color = newColor;
							}
							else
							{
								length = 0;
								color = -1;
							}
						}
					}
					else if (y < Height)
					{
						if (length >= ballsInLine)
						{
							for (int i = 0; i < length; i++)
							{
								locations.Add(new Point(x - i - 1, y + i + 1));
							}
							length = 0;
						}
					}
				}
				if (length >= ballsInLine)
				{
					for (int i = 0; i < length; i++)
					{
						locations.Add(new Point(x - i - 1, y + i + 1));
					}
				}
			}

			return locations;
		}
		
		/// <summary>
		/// Looks up for <b>diagonal</b> (NE-to-SW oriented) lines of balls of the same color.
		/// </summary>
		/// <returns>An array list of positions (<see cref="System.Drawing.Point"/>) of balls that supposed 
		/// to be removed from the board at current step.</returns>
		private ArrayList FindDiagonalBackward()
		{
			ArrayList locations = new ArrayList();

			for (int line = ballsInLine - 1; line < (Width + Height - 2); line++)
			{
				// Each backward diagonal line
				int length = 0;
				int color = -1;
				int x = 0, y = Height - 1 - line + x;
				for (; x <= line; x++, y = Height - 1 - line + x)
				{
					if ((x < Width) && (y >= 0) && (y < Height))
					{
						int newColor = matrix[x, y];
						if ((newColor > 0) && (newColor == color))
						{
							length++;
						} 
						else 
						{
							if (length >= ballsInLine)
							{
								for (int i = 0; i < length; i++)
								{
									locations.Add(new Point(x - i - 1, y - i - 1));
								}
							}

							if (newColor > 0)
							{
								length = 1;
								color = newColor;
							}
							else
							{
								length = 0;
								color = -1;
							}
						}
					}
					else if ((y >= 0) && (y < Height))
					{
						if (length >= ballsInLine)
						{
							for (int i = 0; i < length; i++)
							{
								locations.Add(new Point(x - i - 1, y - i - 1));
							}
							length = 0;
						}
					}
				}
				if (length >= ballsInLine)
				{
					for (int i = 0; i < length; i++)
					{
						locations.Add(new Point(x - i - 1, y - i - 1));
					}
				}
			}

			return locations;
		}
	}
}