using System;
using System.Collections.Generic;
using System.Text;
namespace data.Game
{
public class Pather : Maze
{
//16*16 maps (room list) should be enough for all catacomb levels
public Pather()
: base(SizeX,SizeY)
{
base.AllowDiagonals = true;
}
public Pather(bool allowDiagonals)
: base(SizeX, SizeY)
{
//base.AllowDiagonals = allowDiagonals;
base.AllowDiagonals = true;
}
//fields
static int left = 0, top = 0, right = 0, bottom = 0; //bounds of the defined rooms inside the big _RoomList array
//methods
/// <summary>
/// used to convert world coordinates to coordinates used in our maze
/// </summary>
/// <param name="i"></param>
/// <param name="ConvertX"></param>
/// <returns></returns>
private uint ConvertToRelative(int i, bool ConvertX)
{
SetBounds();
int x = ((i - GameInfo.RoomOffsetX) / 5 - left * 12);
int y = ((i - GameInfo.RoomOffsetY) / 5 - top * 12);
if (ConvertX)
return (uint)x;
return (uint)y;
}
public List<System.Drawing.Point> GoTo(GameObject obj)
{
return GoTo(obj.X, obj.Y);
}
public List<System.Drawing.Point> GoTo(Warp warp)
{
if (warp == null)
return null;
return GoTo(warp.X, warp.Y);
}
public List<System.Drawing.Point> GoTo(int[] RoomIndex)
{
throw new ApplicationException("Method not implemented");
}
public List<System.Drawing.Point> GoTo(System.Drawing.Point WorldCoordinates)
{
return GoTo(WorldCoordinates.X, WorldCoordinates.Y);
}
public List<System.Drawing.Point> GoTo(int WorldX, int WorldY)
{
return GoTo(ConvertToRelative(WorldX, true), ConvertToRelative(WorldY, false));
}
public List<System.Drawing.Point> GoTo(System.Drawing.Point WorldFrom, System.Drawing.Point WorldTo)
{
if (!SetWalkableInfo())
throw new ApplicationException("Failed to set Walkable info from GoTo()");
int FromX = (int)ConvertToRelative(WorldFrom.X, true);
int FromY = (int)ConvertToRelative(WorldFrom.Y, false);
this[FromX, FromY] = 0;
base.fromx = FromX;
base.fromy = FromY;
base.tox = (int)ConvertToRelative(WorldTo.X, true);
base.toy = (int)ConvertToRelative(WorldTo.Y, false);
this[base.tox, base.toy] = 0;
base.FindPath((int)FromX, (int)FromY, base.tox, base.toy);
return base.PathPoints(left, top);
}
private List<System.Drawing.Point> GoTo(uint RelativeX, uint RelativeY)
{
if (!SetWalkableInfo())
throw new ApplicationException("Failed to set Walkable info from GoTo()") ;
int FromX = (int)ConvertToRelative(GameInfo.PlayerX, true);
int FromY = (int)ConvertToRelative(GameInfo.PlayerY, false);
this[FromX, FromY] = 0;
this[(int)RelativeX, (int)RelativeY] = 0;
base.fromx = FromX;
base.fromy = FromY;
base.tox = (int)RelativeX;
base.toy = (int)RelativeY;
base.FindPath((int)FromX, (int)FromY, (int)RelativeX,(int)RelativeY);
//Logger.Log(base.ToString((int)FromX, (int)FromY, (int)RelativeX, (int)RelativeY));
//Logger.Log(base.PathToString((int)FromX, (int)FromY, (int)RelativeX, (int)RelativeY));
return base.PathPoints(left, top);
}
/// <summary>
/// will set the base[x,y] walk info
/// </summary>
/// <returns>false if it fails to set bounds</returns>
private bool SetWalkableInfo()
{
if (!SetBounds())
return false;
base.m_iRows = (right - left + 1) * 12;
base.m_iCols = (bottom - top + 1) * 12;
base.m_iMaze = new int[base.m_iRows, base.m_iCols];
for (int x = left; x < right + 1; x++)
{
for (int y = top; y < bottom + 1; y++)
{
for (int xroom = 0; xroom < 12; xroom++)
{
for (int yroom = 0; yroom < 12; yroom++)
{
//to set values in maze, substract left and top from all values
int xMaze = 0, yMaze = 0;
//set the x and y index of the maze relative to current rooms/room indexes
// (( x - left) * 12) removes the unused rooms to the left and adds previous rooms
xMaze = ((x - left) * 12) + xroom;
yMaze = ((y - top) * 12) + yroom;
if (GameInfo._RoomList[x, y].Walkable != null &&
((xroom == 0 || yroom == 0 || xroom == 11 || yroom == 11)))
{
//set this to walkable because edges are buggy (need to fix in Walkable array to check for other Prop0 value)
base[xMaze, yMaze] = 0;
continue;
}
if (GameInfo._RoomList[x, y].Walkable != null
&& GameInfo._RoomList[x, y].Walkable[xroom, yroom] == true)
{
//this is walkable
base[xMaze, yMaze] = 0;
}
else
{
//this is not walkable
base[xMaze, yMaze] = 1;
}
}
}
}
}
return true;
}
/// <summary>
/// set the left, top, bottom and right bounds of the array to determine the size of the maze
/// (because we dont want to use a 16*12*16*12 array all the time)
/// </summary>
/// <returns>true if it finds the bounds, false otherwise</returns>
private static bool SetBounds()
{
for (int x = 0; x < 16; x++)
{
for (int y = 0; y < 16; y++)
{
if (GameInfo._RoomList[x, y].isDefined)
{
left = x;
goto done1;
}
}
}
return false;
done1:
for (int y = 0; y < 16; y++)
{
for (int x = 0; x < 16; x++)
{
if (GameInfo._RoomList[x, y].isDefined)
{
top = y;
goto done2;
}
}
}
return false;
done2:
for (int x = 15; x > -1; x--)
{
for (int y = 15; y > -1; y--)
{
if (GameInfo._RoomList[x, y].isDefined)
{
right = x;
goto done3;
}
}
}
return false;
done3:
for (int y = 15; y > -1; y--)
{
for (int x = 15; x > -1; x--)
{
if (GameInfo._RoomList[x, y].isDefined)
{
bottom = y;
goto finish;
}
}
}
return false;
finish:
return true;
}
private static int SizeX
{
get
{
if (right == 0 || left == 0)
SetBounds();
return right - left ;
}
}
private static int SizeY
{
get
{
if (bottom == 0 || top == 0)
SetBounds();
return bottom - top ;
}
}
}
/// <summary>
/// Summary description for MazeSolver.
/// Class name: MazeSolver
/// Developed by: Syed Mehroz Alam
/// Email: smehrozalam@yahoo.com
/// URL: Programming Home "http://www.geocities.com/smehrozalam/"
///
/// Constructors:
/// ( int[,] ): takes 2D integer array
/// ( int Rows, int Cols ) initializes the dimensions, indexers may be used
/// to set individual elements' values
///
/// Properties:
/// Rows: returns the no. of rows in the current maze
/// Cols: returns the no. of columns in the current maze
/// Maze: returns the current maze as a 2D array
/// PathCharacter: to get/set the value of path tracing character
/// AllowDiagonal: whether diagonal paths are allowed
///
/// Indexers:
/// [i,j] = used to set/get elements of maze
///
/// Public Methods (Description is given with respective methods' definitions)
/// int[,] FindPath(int iFromY, int iFromX, int iToY, int iToX)
///
/// Private Methods
/// void GetNodeContents(int[,] iMaze, int iNodeNo)
/// void ChangeNodeContents(int[,] iMaze, int iNodeNo, int iNewValue)
/// int[,] Search(int iBeginningNode, int iEndingNode)
///
/// </summary>
public delegate void MazeChangedHandler(int iChanged, int jChanged);
/// <summary>
/// base class for Pather
/// </summary>
public class Maze
{
protected int fromx, fromy, tox, toy;
public string ToString(int fromx, int fromy, int tox, int toy)
{
System.Text.StringBuilder sb = new System.Text.StringBuilder();
for (int y = 0; y < this.GetMaze.GetUpperBound(1); y++)
{
for (int x = 0; x < this.GetMaze.GetUpperBound(0); x++)
{
if (x == fromx && y == fromy)
{
sb.Append("S");
}
else if (x == tox && y == toy)
{
sb.Append("E");
}
else
{
sb.Append(this[x, y]);
}
}
sb.Append(Environment.NewLine);
}
return sb.ToString();
}
public string PathToString()
{
int[,] solved = this.iMazeSolved;
System.Text.StringBuilder sb = new System.Text.StringBuilder();
for (int y = 0; y < this.GetMaze.GetUpperBound(1); y++)
{
for (int x = 0; x < this.GetMaze.GetUpperBound(0); x++)
{
if (solved[x, y] == 100)
{
if (x == tox && y == toy)
sb.Append("E");
else if (x == fromx && y == fromy)
sb.Append('S');
else
sb.Append("+");
}
else
{
sb.Append(solved[x, y]);
}
}
sb.Append(Environment.NewLine);
}
return sb.ToString();
}
/// <summary>
/// Class attributes/members
/// </summary>
public int[,] m_iMaze;
public int m_iRows;
public int m_iCols;
int iPath = 100;
bool diagonal = false;
public event MazeChangedHandler OnMazeChangedEvent;
List<System.Drawing.Point> retList = new List<System.Drawing.Point>();
public List<System.Drawing.Point> PathPoints(int left, int top)
{
for (int i =0; i < retList.Count; i++)
{
System.Drawing.Point p = retList[i];
int x = p.X, y = p.Y;
p.X = 22500 + x * 5 + left * 60;
p.Y = GameInfo.RoomOffsetY + y * 5 + top * 60;
retList[i] = p;
}
retList.Reverse();
return retList;
}
/// <summary>
/// Constructor 1: takes a 2D integer array
/// </summary>
public Maze(int[,] iMaze)
{
m_iMaze = iMaze;
m_iRows = iMaze.GetLength(0);
m_iCols = iMaze.GetLength(1);
}
/// <summary>
/// Constructor 2: initializes the dimensions of maze,
/// later, indexers may be used to set individual elements' values
/// </summary>
public Maze(int iRows, int iCols)
{
m_iMaze = new int[iRows, iCols];
m_iRows = iRows;
m_iCols = iCols;
}
/// <summary>
/// Properites:
/// </summary>
public int Rows
{
get { return m_iRows; }
}
public int Cols
{
get { return m_iCols; }
}
public int[,] GetMaze
{
get { return m_iMaze; }
}
public int PathCharacter
{
get { return iPath; }
set
{
if (value == 0)
throw new Exception("Invalid path character specified");
else
iPath = value;
}
}
public bool AllowDiagonals
{
get { return diagonal; }
set { diagonal = value; }
}
int[,] iMazeSolved;
/// <summary>
/// Indexer
/// </summary>
public int this[int iRow, int iCol]
{
get { return m_iMaze[iRow, iCol]; }
set
{
m_iMaze[iRow, iCol] = value;
if (this.OnMazeChangedEvent != null) // trigger event
this.OnMazeChangedEvent(iRow, iCol);
}
}
/// <summary>
/// The function is used to get the contents of a given node in a given maze,
/// specified by its node no.
/// </summary>
private int GetNodeContents(int[,] iMaze, int iNodeNo)
{
int iCols = iMaze.GetLength(1);
return iMaze[iNodeNo / iCols, iNodeNo - iNodeNo / iCols * iCols];
}
/// <summary>
/// The function is used to change the contents of a given node in a given maze,
/// specified by its node no.
/// </summary>
private void ChangeNodeContents(int[,] iMaze, int iNodeNo, int iNewValue)
{
int iCols = iMaze.GetLength(1);
iMaze[iNodeNo / iCols, iNodeNo - iNodeNo / iCols * iCols] = iNewValue;
}
/// <summary>
/// This public function finds the shortest path between two points
/// in the maze and return the solution as an array with the path traced
/// by "iPath" (can be changed using property "PathCharacter")
/// if no path exists, the function returns null
/// </summary>
public int[,] FindPath(int iFromY, int iFromX, int iToY, int iToX)
{
int iBeginningNode = iFromY * this.Cols + iFromX;
int iEndingNode = iToY * this.Cols + iToX;
return (Search(iBeginningNode, iEndingNode));
}
/// <summary>
/// internal function for that finds the shortest path using a technique
/// similar to breadth-first search.
/// It assigns a node no. to each node(2D array element) and applies the algorithm
/// </summary>
private enum Status
{ Ready, Waiting, Processed }
private int[,] Search(int iStart, int iStop)
{
const int empty = 0;
int iRows = m_iRows;
int iCols = m_iCols;
int iMax = iRows * iCols;
int[] Queue = new int[iMax];
int[] Origin = new int[iMax];
int iFront = 0, iRear = 0;
//check if starting and ending points are valid (open)
if (GetNodeContents(m_iMaze, iStart) != empty || GetNodeContents(m_iMaze, iStop) != empty)
{
return null;
}
//create dummy array for storing status
int[,] iMazeStatus = new int[iRows, iCols];
//initially all nodes are ready
for (int i = 0; i < iRows; i++)
for (int j = 0; j < iCols; j++)
iMazeStatus[i, j] = (int)Status.Ready;
//add starting node to Q
Queue[iRear] = iStart;
Origin[iRear] = -1;
iRear++;
int iCurrent, iLeft, iRight, iTop, iDown, iRightUp, iRightDown, iLeftUp, iLeftDown;
while (iFront != iRear) // while Q not empty
{
if (Queue[iFront] == iStop) // maze is solved
break;
iCurrent = Queue[iFront];
iLeft = iCurrent - 1;
if (iLeft >= 0 && iLeft / iCols == iCurrent / iCols) //if left node exists
if (GetNodeContents(m_iMaze, iLeft) == empty) //if left node is open(a path exists)
if (GetNodeContents(iMazeStatus, iLeft) == (int)Status.Ready) //if left node is ready
{
Queue[iRear] = iLeft; //add to Q
Origin[iRear] = iCurrent;
ChangeNodeContents(iMazeStatus, iLeft, (int)Status.Waiting); //change status to waiting
iRear++;
}
iRight = iCurrent + 1;
if (iRight < iMax && iRight / iCols == iCurrent / iCols) //if right node exists
if (GetNodeContents(m_iMaze, iRight) == empty) //if right node is open(a path exists)
if (GetNodeContents(iMazeStatus, iRight) == (int)Status.Ready) //if right node is ready
{
Queue[iRear] = iRight; //add to Q
Origin[iRear] = iCurrent;
ChangeNodeContents(iMazeStatus, iRight, (int)Status.Waiting); //change status to waiting
iRear++;
}
iTop = iCurrent - iCols;
if (iTop >= 0) //if top node exists
if (GetNodeContents(m_iMaze, iTop) == empty) //if top node is open(a path exists)
if (GetNodeContents(iMazeStatus, iTop) == (int)Status.Ready) //if top node is ready
{
Queue[iRear] = iTop; //add to Q
Origin[iRear] = iCurrent;
ChangeNodeContents(iMazeStatus, iTop, (int)Status.Waiting); //change status to waiting
iRear++;
}
iDown = iCurrent + iCols;
if (iDown < iMax) //if bottom node exists
if (GetNodeContents(m_iMaze, iDown) == empty) //if bottom node is open(a path exists)
if (GetNodeContents(iMazeStatus, iDown) == (int)Status.Ready) //if bottom node is ready
{
Queue[iRear] = iDown; //add to Q
Origin[iRear] = iCurrent;
ChangeNodeContents(iMazeStatus, iDown, (int)Status.Waiting); //change status to waiting
iRear++;
}
if (diagonal == true)
{
iRightDown = iCurrent + iCols + 1;
if (iRightDown < iMax && iRightDown >= 0 && iRightDown / iCols == iCurrent / iCols + 1) //if bottom-right node exists
if (GetNodeContents(m_iMaze, iRightDown) == empty) //if this node is open(a path exists)
if (GetNodeContents(iMazeStatus, iRightDown) == (int)Status.Ready) //if this node is ready
{
Queue[iRear] = iRightDown; //add to Q
Origin[iRear] = iCurrent;
ChangeNodeContents(iMazeStatus, iRightDown, (int)Status.Waiting); //change status to waiting
iRear++;
}
iRightUp = iCurrent - iCols + 1;
if (iRightUp >= 0 && iRightUp < iMax && iRightUp / iCols == iCurrent / iCols - 1) //if upper-right node exists
if (GetNodeContents(m_iMaze, iRightUp) == empty) //if this node is open(a path exists)
if (GetNodeContents(iMazeStatus, iRightUp) == (int)Status.Ready) //if this node is ready
{
Queue[iRear] = iRightUp; //add to Q
Origin[iRear] = iCurrent;
ChangeNodeContents(iMazeStatus, iRightUp, (int)Status.Waiting); //change status to waiting
iRear++;
}
iLeftDown = iCurrent + iCols - 1;
if (iLeftDown < iMax && iLeftDown >= 0 && iLeftDown / iCols == iCurrent / iCols + 1) //if bottom-left node exists
if (GetNodeContents(m_iMaze, iLeftDown) == empty) //if this node is open(a path exists)
if (GetNodeContents(iMazeStatus, iLeftDown) == (int)Status.Ready) //if this node is ready
{
Queue[iRear] = iLeftDown; //add to Q
Origin[iRear] = iCurrent;
ChangeNodeContents(iMazeStatus, iLeftDown, (int)Status.Waiting); //change status to waiting
iRear++;
}
iLeftUp = iCurrent - iCols - 1;
if (iLeftUp >= 0 && iLeftUp < iMax && iLeftUp / iCols == iCurrent / iCols - 1) //if upper-left node exists
if (GetNodeContents(m_iMaze, iLeftUp) == empty) //if this node is open(a path exists)
if (GetNodeContents(iMazeStatus, iLeftUp) == (int)Status.Ready) //if this node is ready
{
Queue[iRear] = iLeftUp; //add to Q
Origin[iRear] = iCurrent;
ChangeNodeContents(iMazeStatus, iLeftUp, (int)Status.Waiting); //change status to waiting
iRear++;
}
}
//change status of current node to processed
ChangeNodeContents(iMazeStatus, iCurrent, (int)Status.Processed);
iFront++;
}
//create an array(maze) for solution
iMazeSolved = new int[iRows, iCols];
for (int i = 0; i < iRows; i++)
for (int j = 0; j < iCols; j++)
iMazeSolved[i, j] = m_iMaze[i, j];
//make a path in the Solved Maze
iCurrent = iStop;
ChangeNodeContents(iMazeSolved, iCurrent, iPath);
for (int i = iFront; i >= 0; i--)
{
if (Queue[i] == iCurrent)
{
iCurrent = Origin[i];
if (iCurrent == -1) // maze is solved
return (iMazeSolved);
ChangeNodeContents(iMazeSolved, iCurrent, iPath);
//iMaze[iNodeNo / iCols, iNodeNo - iNodeNo / iCols * iCols] = iNewValue;
int x = iCurrent / iCols;
int y = iCurrent - iCurrent / iCols * iCols;
retList.Add(new System.Drawing.Point(x, y));
}
}
//no path exists
return null;
}
}
}