# Generating a graph from a rectangular grid for graph searching

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));
}
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;
}

{
if (!IsWithinGrid(location))
{
throw new ArgumentException("Wall location must be within the grid", nameof(location));
}
return this;
}

{
if (!IsWithinGrid(location))
{
throw new ArgumentException("Water location must be within the grid", nameof(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++)
{
}
}
for (var x = 4; x < 7; x++)
{
for (var y = 0; y < 10; 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() : "-")));
}

}


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?

• This code looks really nice!

Coordinate

• [DebuggerDisplay] is redundant when you override ToString().

• I don't mind readonly fields for X and Y there. This is a slight performance optimization. Further reading

• I usually throw in equality operators when overriding equality:

 public static bool operator ==(Coordinate left, Coordinate right)
{
return left.Equals(right);
}

public static bool operator !=(Coordinate left, Coordinate right)
{
return !left.Equals(right);
}


• This algorithm will generate collisions for new Coordinate(1, 2) == new Coordinate(2, 1). May or may not be an issue.

• No need to call X.GetHashCode() as it returns the value.

• Here is an alternative implementation:

 public override int GetHashCode()
{
unchecked
{
return (X*397) ^ Y;
}
}


Graph

• I prefer writing AllNodes like this:

 public IEnumerable<T> AllNodes
{
get { return Edges.Keys; }
}


Or if you are using C#6 public IEnumerable<T> AllNodes => Edges.Keys;

• I prefer IReadOnlyList<T> in all places, it closes the door to accidentally having something lazy that executes on every call. For max performance you want to pass the raw array T[].

• Depending on how it is used KeyValuePair<T, IReadOnlyList<T>>[] can have better performance than Dictionary<T, IReadOnlyList<T> due to dictionary being a pretty expensive allocation. If there are many elements and you do many lookups per dictionary they are probably right.

Ending here, really nice code, not much of a review.

As with all things related to performance, profile first and profile after if you decide to optimize.

• Thanks - your comments about GetHashcode are very helpful as in a rectangular grid (a, b) and (b, a) are very likely to occur so definitely want to avoid collisions there.
– RobH
Feb 28, 2016 at 21:11
• I should probably have split up the microoptimization stuff from the review. Mar 4, 2016 at 13:37

I would like to point out that while your code is clear and well written, if your actual goal is to experiment with A*, you don't need to be so literal with using a directed graph. A simple two-dimensional array of weights is perfectly usable for A*. In fact this is exactly what many interactive javascript demos of A* do. It looks as though your final graph is this way too.

If in the future you want to experiment with a sparse graph or a non-rectangular grid (like a hex map or something), with a little work your code is a good starting spot for that.