I recently reviewed some code implementing some heuristics which has piqued my interest in the A* graph searching algorithm. I'm going to do that in a bit but first I need a way to create a graph in order to work on...
I could have used Point from System.Drawing, but I didn't want to include the whole assembly for the single struct. That's potentially a bad reason but here's my reinvented Coordinate structure anyway:
[DebuggerDisplay("({X}, {Y})")]
internal struct Coordinate : IEquatable<Coordinate>
{
internal int X { get; }
internal int Y { get; }
public Coordinate(int x, int y)
{
X = x;
Y = y;
}
public static Coordinate operator +(Coordinate a, Coordinate b)
{
return new Coordinate(a.X + b.X, a.Y + b.Y);
}
public static Coordinate operator -(Coordinate a, Coordinate b)
{
return new Coordinate(a.X - b.X, a.Y - b.Y);
}
public override bool Equals(object obj)
{
if (obj is Coordinate)
{
return Equals((Coordinate)obj);
}
return false;
}
public override int GetHashCode()
{
int hash = 17;
hash = hash * X.GetHashCode();
hash = hash * Y.GetHashCode();
return hash;
}
public bool Equals(Coordinate other)
{
return other.X == X && other.Y == Y;
}
public override string ToString()
{
return $"({X}, {Y})";
}
}
I decided I would treat each point as a 'tile' and have the cost on that tile rather than weighting the edges directly. I chose null as the value representing an impassible tile... I'm not sure I like that now so thoughts welcome.
[DebuggerDisplay("Location: {Location}, Cost: {Cost}")]
internal sealed class MapTile : IEquatable<MapTile>
{
internal MapTile(Coordinate location, int? cost = null)
{
Location = location;
Cost = cost;
}
internal Coordinate Location { get; }
internal int? Cost { get; }
public bool Equals(MapTile other)
{
if (ReferenceEquals(other, null))
{
return false;
}
return Location.Equals(other.Location) && Cost == other.Cost;
}
public override bool Equals(object obj)
{
return Equals(obj as MapTile);
}
public override int GetHashCode()
{
int hash = 17;
hash = hash * Location.GetHashCode();
hash = hash * Cost.GetHashCode();
return hash;
}
public override string ToString()
{
return $"Location: {Location}, Cost: {Cost}";
}
}
The underlying data structure for the map is really straightforward:
internal sealed class Graph<T>
{
public IEnumerable<T> AllNodes { get; }
private IDictionary<T, IEnumerable<T>> Edges;
internal Graph(IDictionary<T, IEnumerable<T>> edges)
{
if (edges == null)
{
throw new ArgumentNullException(nameof(edges));
}
Edges = new ReadOnlyDictionary<T, IEnumerable<T>>(edges);
AllNodes = Edges.Keys;
}
internal IEnumerable<T> Neighbours(T node)
{
return Edges[node];
}
}
In order to create a simple 2D rectangular map, I created this map generator class:
internal class RectangularMapGenerator
{
private int height;
private int width;
private HashSet<Coordinate> walls = new HashSet<Coordinate>();
private HashSet<Coordinate> water = new HashSet<Coordinate>();
private static readonly Coordinate[] CardinalDirections = new[]
{
new Coordinate(0, 1),
new Coordinate(1, 0),
new Coordinate(0, -1),
new Coordinate(-1, 0)
};
public RectangularMapGenerator(int width, int height)
{
if (height < 0)
{
throw new ArgumentOutOfRangeException(nameof(height));
}
if (width < 0)
{
throw new ArgumentOutOfRangeException(nameof(width));
}
this.height = height;
this.width = width;
}
internal RectangularMapGenerator AddWall(Coordinate location)
{
if (!IsWithinGrid(location))
{
throw new ArgumentException("Wall location must be within the grid", nameof(location));
}
walls.Add(location);
return this;
}
internal RectangularMapGenerator AddWater(Coordinate location)
{
if (!IsWithinGrid(location))
{
throw new ArgumentException("Water location must be within the grid", nameof(location));
}
water.Add(location);
return this;
}
private bool IsWithinGrid(Coordinate c)
{
return c.X >= 0 && c.X < width && c.Y >= 0 && c.Y < height;
}
private IEnumerable<MapTile> CreateEdges(MapTile tile)
{
if (walls.Contains(tile.Location))
{
return Enumerable.Empty<MapTile>();
}
return (from d in CardinalDirections
let newLocation = tile.Location + d
where IsWithinGrid(newLocation) && !walls.Contains(newLocation)
select CreatMapTile(newLocation))
.ToArray();
}
private MapTile CreatMapTile(Coordinate location)
{
int? cost = null;
if (!walls.Contains(location))
{
cost = water.Contains(location) ? 5 : 1;
}
return new MapTile(location, cost);
}
internal Graph<MapTile> Build()
{
var edges = new Dictionary<MapTile, IEnumerable<MapTile>>();
for (var x = 0; x < width; x++)
{
for (var y = 0; y < height; y++)
{
var location = new Coordinate(x, y);
var tile = CreatMapTile(location);
edges[tile] = CreateEdges(tile);
}
}
return new Graph<MapTile>(edges);
}
}
An example of actually creating a map is (I only wrote this for CR so not really wanting it to be reviewed):
static void Main(string[] args)
{
var mapBuilder = new RectangularMapGenerator(10, 10);
for (var x = 1; x < 4; x++)
{
for (var y = 7; y < 9; y++)
{
mapBuilder.AddWall(new Coordinate(x, y));
}
}
for (var x = 4; x < 7; x++)
{
for (var y = 0; y < 10; y++)
{
mapBuilder.AddWater(new Coordinate(x, y));
}
}
var graph = mapBuilder.Build();
foreach (var row in graph.AllNodes.GroupBy(n => n.Location.Y))
{
Console.WriteLine(
string.Join(" ",
row.OrderByDescending(a => a.Location.X)
.Select(a => a.Cost.HasValue ? a.Cost.Value.ToString() : "-")));
}
Console.ReadKey();
}
Running the above outputs a map of "costs" that looks like this (which is obviously a river with a boat house next to it ;) ). I've used the convention of origin in the top left with y increasing down and x increasing to the right like it does in the html canvas. (Edit: No it doesn't! Should have used OrderBy for the x axis, not OrderByDescending... Result is that the origin is actually in the top right and x increases to the left.)
I haven't done this sort of thing before (and I have a Physics background so no CS classes to fall back on) so I'm looking for comments on all aspects of the code. Is putting the cost on a tile a reasonable trade off for simplicity, or should I introduce a more modelled edge with the cost on that instead?
