Work is still progressing (between study and work-proper) on Roguelikish.
I've added A* pathfinding. As a result, you actually do some path finding to move when you click somewhere, and your party isn't quite as stupid when trying to follow.
I figured since I'd done it, that the pathfinding code could be useful. It's released under the following license:
Lachlan's Very Public Licence - which is a slightly modified
Unlicense
This is free and unencumbered software released into the public domain.
Anyone is free to copy, modify, publish, use, compile, sell, or
distribute this software, either in source code form or as a compiled
binary, for any purpose, commercial or non-commercial, and by any
means.
In jurisdictions that recognize copyright laws, the author or authors
of this software dedicate any and all copyright interest in the
software to the public domain. We make this dedication for the benefit
of the public at large and to the detriment of our heirs and
successors. We intend this dedication to be an overt act of
relinquishment in perpetuity of all present and future rights to this
software under copyright law.
If you use the source, the Author (Lachlan Kingsford) would actually like to know - but it's by no means necessary. Feel welcome to provide a copy of what you do via email, or comment on www.nerdygentleman.com. Attribution is also nice and appreciated, but again, by no means necessary.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.
I've attempted to implement the A* algorithm as described on
A* Pathfinding for Beginners. There's probably bugs. Diagonals are costly (they cost 1.4 x the movement of verticals). The comments are probably old, inaccurate, or just plain wrong and probably shouldn't be relied on. The programming style is amateur, but it works.
The function provides a list<coord> of the path to take to reach coord end from coord start.
Any questions - I may or may not be able to answer. I implemented the algorithm, but only mostly understood it.
//Required classes
public class coord
{
public int X;
public int Y;
public coord() { X = 0; Y = 0; }
public coord(int _X, int _Y) { X = _X; Y = _Y; }
public static bool operator==(coord first, coord second)
{
return ((first.X == second.X) && (first.Y == second.Y));
}
public static bool operator !=(coord first, coord second)
{
return !((first.X == second.X) && (first.Y == second.Y));
}
}
public class workingPathVertex : IComparable<workingPathVertex>
{
public coord V;
public int G;
public int H;
public int F() { return G + H; }
public workingPathVertex parent ;
public workingPathVertex(coord _V, workingPathVertex _Parent, int _G, int _H)
{
V = _V;
parent = _Parent;
G = _G;
H = _H;
}
public int CompareTo(workingPathVertex that)
{
return (that.F() > F()) ? -1 : 1;
}
}
//Functions
//Relies on two 2d boolean arrays - which can fairly easily be written out.
//One is CheckCollision(int, int) which returns whether the tile can be collided
// with - and whether the thing on the tile can be collided with. So - players
// would make it return to
//The other is TileCollides (int,int) which returns whether the tile can be
// collided with. Behaviour is controlled from "playercollides" arg
//Some debugging codes still in there, and the comments are old, barely updated
// and possibly flatly wrong.
public List<coord> GetPath(coord start, coord end, bool PlayerCollides = true)
{
List<workingPathVertex> openList = new List<workingPathVertex>();
List<workingPathVertex> closedList = new List<workingPathVertex>();
workingPathVertex startV = new workingPathVertex(start, null, 0, Manhatten(start,end)) ;
workingPathVertex V = startV;
const int STRAIGHT_COST = 10;
const int DIAG_COST = 14;
for (int ix = -1; ix < 2; ix++)
{
for (int iy = -1; iy < 2; iy++)
{
if (!(ix == 0 && iy == 0))
{
coord i = new coord(V.V.X + ix, V.V.Y + iy);
if (PlayerCollides ? (!CheckCollision(i.X,i.Y)) : (!TileCollides(i.X, i.Y)))
{
openList.Add(new workingPathVertex(i, V, V.G + (((ix == 0) || (iy == 0)) ? STRAIGHT_COST : DIAG_COST), Manhatten(i, end)));
}
}
}
}
openList.Remove(V);
closedList.Add(V);
bool finished = false;
bool succeeded = false;
workingPathVertex endVertex = null;
bool surroundtarget = false;
if (PlayerCollides ? (CheckCollision(end.X,end.Y)) : (TileCollides(end.X, end.Y))) {
surroundtarget = true;
bool surroundPossible = false;
for (int ix = -1; ix < 2; ix++)
{
for (int iy = -1; iy < 2; iy++)
{
if (!(ix == 0 && iy == 0))
{
coord i = new coord(V.V.X + ix, V.V.Y + iy);
surroundPossible = (PlayerCollides ? (!CheckCollision(i.X, i.Y)) : (!TileCollides(i.X, i.Y))) || surroundPossible;
}
}
}
finished = !surroundPossible;
};
//This is lazy looping I know, but it's late, and I'm tired, and it should work
while (!finished)
{
V = openList.Min();
openList.Remove(V);
closedList.Add(V);
////Debuggy stuff
//Console.WriteLine("ITERATION:\n V moved is " + V.V.X.ToString() + " " + V.V.Y.ToString());
//Console.WriteLine("OPEN LIST:");
//foreach (workingPathVertex Z in openList)
//{
// Console.WriteLine(Z.V.X.ToString() + "\t" + Z.V.Y.ToString() + ") " + Z.F() + "\t" + Z.G + "\t" + Z.H);
//}
//foreach (workingPathVertex Z in closedList)
//{
// Console.WriteLine(Z.V.X.ToString() + "\t" + Z.V.Y.ToString() + ") " + Z.F() + "\t" + Z.G + "\t" + Z.H);
//}
if (!surroundtarget)
{
if ((V.V.X == end.X) && (V.V.Y) == end.Y) { finished = true; succeeded = true; endVertex = V; };
}
else
{
if ((Math.Abs(V.V.X - end.X) <= 1) && ((Math.Abs(V.V.Y - end.Y) <= 1))) { finished = true; succeeded = true; endVertex = V; };
}
//Find lowest F
for (int ix = -1; ix < 2; ix++)
{
for (int iy = -1; iy < 2; iy++)
{
if (!(ix == 0 && iy == 0))
{
coord i = new coord(V.V.X + ix, V.V.Y + iy);
workingPathVertex closePath = closedList.Find((f) => { return ((f.V.X == i.X) && (f.V.Y == i.Y)); });
if ((closePath == null) && (PlayerCollides ? (!CheckCollision(i.X, i.Y)) : (!TileCollides(i.X, i.Y))))
{
workingPathVertex iPath = openList.Find((f) => { return ((f.V.X == i.X) && (f.V.Y == i.Y)); });
if (iPath != null)
{
//If iPath is already on openList
int GviaV = V.G + (((ix == 0) || (iy == 0)) ? STRAIGHT_COST : DIAG_COST);
if (GviaV < iPath.G) { iPath.G = GviaV; iPath.parent = V; }
}
else
{
//If iPath is not on the openlist
iPath = new workingPathVertex(i, V, V.G + (((ix == 0) || (iy == 0)) ? STRAIGHT_COST : DIAG_COST), Manhatten(i, end));
openList.Add(iPath);
}
}
}
}
}
if (openList.Count <= 0) { finished = true; }
}
if (succeeded)
{
//Console.WriteLine("SUCCESS: ");
List<coord> path = new List<coord>();
workingPathVertex nextVertex = endVertex;
while (nextVertex != null)
{
//Console.WriteLine(nextVertex.V.X.ToString() + " " + nextVertex.V.Y.ToString());
path.Add(nextVertex.V);
nextVertex = nextVertex.parent;
}
path.Reverse();
path.RemoveAt(0);
return path;
}
else
{
//Console.WriteLine("FAILED");
return null;
}
}
//Calculates manhatten distance
int Manhatten(coord A, coord B)
{
return (Math.Abs(A.X - B.X) + Math.Abs(A.Y + B.Y));
}
}
Edit (12.29AM 13/02/2013 AEDST) Fixed Bug
