2
\$\begingroup\$

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.)

Results of map generator

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?

\$\endgroup\$
2
\$\begingroup\$

A couple of comments:

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

About GetHashCode

  • 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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – RobH Feb 28 '16 at 21:11
  • \$\begingroup\$ I should probably have split up the microoptimization stuff from the review. \$\endgroup\$ – Johan Larsson Mar 4 '16 at 13:37
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.