A* algorithm for hex tiles

Question

I implemented the A* algorithm for pathfinding for a game of mine. The game uses hex rooms which are connected to each other by an int[] in the room class. Are there any pointers you can give me on my code?

public class Pathfinding
    {
        /// <summary>
        /// Finds a path from one room to another using the given algorithm, or A* by default. Returns null if a path is not found.
        /// </summary>
        /// <param name="start">The starting point</param>
        /// <param name="end">The end point</param>
        /// <param name="algorithm">The algorithm to find a path with</param>
        /// <returns>A list of rooms making a path, or null if there is not path.</returns>
        public static List<Room> FindPath(Room start, Room end, Cave cave, PathfindingAlgorithm algorithm = PathfindingAlgorithm.A_STAR)
        {
            switch (algorithm)
            {
                case PathfindingAlgorithm.A_STAR: return FindAStarPath(start, end, cave);

                default: throw new Exception();
            }
        }



    private static List<Room> FindAStarPath(Room start, Room end, Cave cave)
        {
            int MAX_TRAVERSED_ROOMS = cave.getRoomDict().Count;
            IPriorityQueue<AStarNode<Room>> openNodes = new HeapPriorityQueue<AStarNode<Room>>(MAX_TRAVERSED_ROOMS);
            List<AStarNode<Room>> closedNodes = new List<AStarNode<Room>>();

            Func<AStarNode<Room>, IEnumerable<AStarNode<Room>>> getNeighbors = (r) =>
            {
                return new List<int>(r.node.adjacentRooms).Select((a) => new AStarNode<Room>(cave.GetRoom(a), r));
            };
            // Add the start node with an F cost of 0
            openNodes.Enqueue(new AStarNode<Room>(start), 0);

            while (openNodes.Count != 0)
            {
                //The one with the least F cost
                AStarNode<Room> current = openNodes.Dequeue();
                closedNodes.Add(current);

                foreach (AStarNode<Room> neighbor in getNeighbors(current))
                {
                    // if we already processed this node
                    if (closedNodes.Contains<AStarNode<Room>>(neighbor)) continue;

                    int fCost = GetEstimatedScore(neighbor.node, end, cave) + neighbor.ParentCount;

                    if (openNodes.Contains<AStarNode<Room>>(neighbor))
                    {
                        double priority = -1;
                        foreach (AStarNode<Room> node in openNodes)
                        {
                            if (node.Equals(neighbor))
                            {
                                priority = node.Priority;
                                break;
                            }
                        }
                        if (fCost < priority)
                        {
                            openNodes.UpdatePriority(neighbor, fCost);
                        }
                    }
                    else
                    {
                        openNodes.Enqueue(neighbor, fCost);
                        if (neighbor.node.Equals(end))
                        {
                            // found the path
                            List<Room> path = new List<Room>();
                            AStarNode<Room> currentNode = neighbor;
                            while (currentNode.parent != null)
                            {
                                path.Insert(0, currentNode.node);
                                currentNode = currentNode.parent;
                            }
                            return path;
                        }
                    }
                }

            }
            // path not found
            return null;
        }
        private static int GetEstimatedScore(Room start, Room end, Cave cave)
        {
            Vector2 startPos = cave.RoomLayout[start.roomId].RoomPosition;
            Vector2 endPos = cave.RoomLayout[end.roomId].RoomPosition;
            // Manhattan distance
            return (int)Math.Round(Math.Abs(startPos.X - endPos.X) + Math.Abs(startPos.Y - endPos.Y));
        }
    }
    class AStarNode<T> : PriorityQueueNode
    {
        public AStarNode(T node)
        {
            this.node = node;
            this.parent = null;
        }

        public AStarNode(T node, AStarNode<T> parent)
        {
            this.node = node;
            this.parent = parent;
        }

        public T node;
        public AStarNode<T> parent;

        public int ParentCount
        {
            get
            {
                if (parent == null) return 0;
                return 1 + parent.ParentCount;
            }
        }

        //Should this method compare both the nodes and the parents or just the nodes?
        public override bool Equals(object obj)
        {
            if (obj == null)
                return false;

            if (obj.GetType() != GetType())
                return false;

            bool sameKey = node.Equals(((AStarNode<T>)obj).node);

            if (sameKey && node.Equals(default(T)))
                return ReferenceEquals(this, obj);

            return sameKey;
        }

        public override int GetHashCode()
        {
            if (node.Equals(default(T)))
                return base.GetHashCode();

            return GetType().GetHashCode() ^ node.GetHashCode();
        }
    }
    public enum PathfindingAlgorithm
    {
        A_STAR,
    }

Cave.cs

/// <summary>
/// The cave object generates a cave system and places objects inside it (player, arrows, gold, etc)
/// Includes methods to get locations of game objects in cave
/// </summary>
public class Cave
{
    // Length of the apothem of each room as it should be drawn (virtual coords)
    private readonly int RoomNumSides;
    private readonly double RoomBaseApothem;
    public int TargetRoomWidth { get; protected set; }
    public int TargetRoomHeight { get; protected set; }


    public Cave(int RoomNumSides = 6, double RoomBaseApothem = 300)
    {
        this.RoomBaseApothem = RoomBaseApothem;
        this.RoomNumSides = RoomNumSides;

        this.TargetRoomWidth = (int)Math.Round(MathUtils.PolygonWidth(RoomNumSides, RoomBaseApothem));
        this.TargetRoomHeight = (int)Math.Round(MathUtils.PolygonHeight(RoomNumSides, RoomBaseApothem));
    }

    /// <summary>
    /// contains generated cave (dictionary of rooms)
    /// </summary>
    private Dictionary<int, Room> cave = new Dictionary<int, Room>();

    /// <summary>
    /// Gets the calculated positions for the available room IDs
    /// </summary>
    public Dictionary<int, RoomLayoutMapping> RoomLayout
    {
        get;
        protected set;
    }

    /// <summary>
    /// Gets the array of rooms in the cave
    /// </summary>
    public Room[] Rooms
    {
        get
        {
            return cave.Values.ToArray();
        }
    }

    public Room this[int RoomID]
    {
        get
        {
            return cave[RoomID];
        }
    }

    /// <summary>
    /// returns current cave on request
    /// </summary>
    /// <returns>current cave</returns>
    public List<Room> getRoomList()
    {
        return cave.Values.ToList<Room>();
    }
    /// <summary>
    /// Returns the current cave in dictionary form (roomId -> room)
    /// </summary>
    /// <returns></returns>
    public Dictionary<int, Room> getRoomDict()
    {
        return cave;
    }
    /// <summary>
    /// Gets the room with the id 
    /// </summary>
    /// <param name="id"></param>
    /// <returns></returns>
    public Room GetRoom(int id)
    {
        if (!cave.ContainsKey(id))
            return null;
       return cave[id];
    }
    /// <summary>
    /// Adds a room
    /// </summary>
    /// <param name="id"></param>
    /// <param name="connections"></param>
    /// <param name="gold"></param>
    /// <param name="arrows"></param>
    /// <param name="bats"></param>
    /// <param name="pit"></param>
    public void AddRoom(int id, int[] connections, int gold = 0, int arrows = 0, bool bats = false, bool pit = false)
    {
        this.cave[id] = new Room(){
            roomId = id,
            adjacentRooms = connections,
            gold = gold,
            arrows = arrows,
            bats = bats,
            pit = pit
        };

        if (bats == true && pit == true)
        {
            throw new InvalidRoomException("Can't have bats AND pit in one room");
        }

        if (connections.Length == 0)
        {
            throw new InvalidRoomException("Each room needs to be accessible");
        }

        if (id < 0)
        {
            throw new InvalidRoomException("Room can't have negative ID");
        }
    }
    /// <summary>
    /// Method to randomly generate cave (work in progress, feel free to pitch in)
    /// </summary>
    /// <param name="rooms"># of rooms needed in cave</param>
    /// <returns>randomly generated cave</returns>
    // Requirements for cave:
    // In list of all room connections, each room must appear 1/2 # of rooms times
    // Each room must have at least 1, no more than 3 doors
    public Cave randomCaveGen(int rooms)
    {
        Cave randomCave = new Cave();
        return randomCave;
    }

    /// <summary>
    /// Updates the internal layout calculations (adapts to new cave connections)
    /// </summary>
    public void RegenerateLayout()
    {
        RoomLayout = MapUtils.GetRoomLayout(cave.Values.ToArray(), RoomBaseApothem, RoomNumSides, TargetRoomWidth, TargetRoomHeight);
    }
}
/// <summary>
/// Class which represents one room which is part of the cave system
/// </summary>
public class Room
{
    /// <summary>
    /// room's location in cave
    /// </summary>
    public int roomId;
    /// <summary>
    /// how much gold the room contains (gold >= 0)
    /// </summary>
    public int gold;
    /// <summary>
    /// how many arrows the room contains (arrows >= 0)
    /// </summary>
    public int arrows;
    /// <summary>
    /// true if room contains bats, false if not
    /// </summary>
    public bool bats;
    /// <summary>
    /// true if room contains a pit, false if not
    /// </summary>
    public bool pit;
    /// <summary>
    /// what other rooms this room is connected to
    /// </summary>
    public int[] adjacentRooms;

    public override string ToString()
    {
        return string.Format(
                "Room {{id: {0}, has bats: {1}, has pit: {2}, gold: {3}, arrows: {4}}}",
                roomId,
                bats ? "yes" : "no",
                pit ? "yes" : "no",
                gold,
                arrows
            );
    }
    public override bool Equals(Object obj)
    {
        // If parameter is null return false.
        if (obj == null)
        {
            return false;
        }

        // If parameter cannot be cast to Room return false.
        Room p = obj as Room;
        if ((Object)p == null)
        {
            return false;
        }

        // Shoullddddd be good enough...
        return roomId == p.roomId;
    }
    public override int GetHashCode()
    {
        return roomId;
    }

}

Mephy · Accepted Answer · 2015-04-25 02:49:53Z

Your enum+switch design to choose which algorithm to apply is very procedural. In an object-oriented world, it is much more common to see:

public interface IPathfinder {
    List<Room> FindPath(Room start, Room end, Cave cave);
}

public class AStarPathfinder : IPathfinder {
    public List<Room> FindPath(Room start, Room end, Cave cave) {
        // ...
    }
}

And consider changing the return type List<Room> to the more generic IList<Room>. It is usually considered best practice to expose interfaces instead of concrete implementations. Check this StackOverflow discussion.

Your lambda function is cluttering the visual space of your algorithm implementation, I would rather put it in a separate private method. In this function, r is not a meaningful name: even anonymous functions should have meaningful names for its parameters. Room.adjacentRooms is of type int[], and it implements IEnumerable<int>, so no need to instantiate a new List<int>.

private IEnumerable<AStarNode<Room>> GetNeighbors(AStarNode<Room> roomNode, Cave cave) {
    return roomNode.node.adjacentRooms
        .Select(roomIndex => new AStarNode<Room(cave.GetRoom(roomIndex), roomNode));
}

Similar to the IPathfinder interface, you could not restrain yourself to using only one heuristic (GetEstimatedScore). You could set a general interface for heuristics

 public interface IHeuristic {
     int Estimate(Room start, Room end, Cave cave);
 }

 public class ManhattanDistanceHeuristic : IHeuristic {
     public int Estimate(Room start, Room end, Cave cave) {
        Vector2 startPos = cave.RoomLayout[start.roomId].RoomPosition;
        Vector2 endPos = cave.RoomLayout[end.roomId].RoomPosition;
        return (int)Math.Round(Math.Abs(startPos.X - endPos.X) + Math.Abs(startPos.Y - endPos.Y));
    }
 }

And of course, add a IHeuristic property to your AStarPathfinder class, so you can inject this dependency later.

Your class AStarNode<T> is implicitly declared as internal visibility, but I suppose only the AStarPathfinder class would use it, so it could be a private class inside AStarPathfinder. Furthermore, while the generics is cool, I also suppose it is only ever getting instanced as AStarNode<Room>, so you could've kept it simpler.

Your Room class has room (ha.) for some improvement. First, it has public read-write fields, including an array. You did fine in the visibility for the other classes, but here it is thrown away. Furthermore, your gold and arrows fields have comments about the possible values, but there is no checking. They should be properties instead, so you can enforce these values.

Personally, I dislike the ToString method. It should be used solely for debugging purposes. That is because it has no semantic value, so your formatting methods should have another name. That said, your implementation simply looks like it was made so your debugging/immediate window would be easier to read, so I recommend removing it later, when you don't need it anymore.

null as X is still null, so your Equals method can be reduced to:

public override bool Equals(object other) {
    Room otherRoom = other as Room;
    return otherRoom != null && roomId == otherRoom.roomId;
}

You have a strange comment on the Equals saying "Shoullddddd be good enough...". I don't know the answer, but it is a strange design anyway: what does a room uses its id for? Is it really a data pertaining to this object? Or it is used only for places outside its scope?

Furthermore, you GetHashCode uses only roomId to generate the hash, but this value is mutable. Never ever use mutable values on GetHashCode. You can find some discussion about the topic in this SO question and some general discussion about GetHashCode in Eric Lippert's blog.

The variable naming is also a bit weird, with the need of comments to clarify things. That is never a good thing. Also, your Cave.AddRoom method has additional rules for the room: you can't have bats and pit, and each room must be accessible. And about this rule of bats and pit, you could design it as an enum. And your adjacent rooms could have a more generic type. All that said, I would've probably written your room as:

public class Room {

    public enum RoomDangers {
        None,
        Bats,
        Pit
    }

    private int gold;
    private int arrows;
    private IEnumerable<int> adjacentRooms;

    public RoomDangers Dangers { get; set; }

    public int Gold {
        get {
            return gold;
        }
        set {
            if (value < 0)
                throw new ArgumentException("value", "value must be >= 0");
            gold = value;
        }
    }

    public int Arrows {
        get {
            return arrows;
        }
        set {
            if (value < 0)
                throw new ArgumentException("value", "value must be >= 0");
            arrows = value;
        }
    }

    public IEnumerable<int> AdjacentRooms {
        get {
            return adjacentRooms;
        }
        set {
            if (value == null)
                throw new ArgumentNullException("value");
            if (!value.Any())
                throw new ArgumentException("value", "there must be at least one room connected");
            adjacentRooms = value;
        }
    }

}

However, I would really investigate to see if I can turn this mutable class into an immutable one, setting all the properties in the constructor and not letting them change after that.

Your Cave class seems to be a bit off: it both controls the layout of a given cave, using the graph generated by the connections of the rooms, and... generates new caves? Or something else? Maybe is it doing too much? I'm confused by the goal of this class.

Personally, I think you should have an immutable class called Cave, and another class called CaveGenerator or something alike.

Like I removed the roomId for the rooms, I think you should transform your Dictionary<int, Room> to a simple IList<Room>. It still gives you access to rooms according to an integer index, but keeps the code much simpler.

But design aside, here's nit-picks about the Cave class:

I dislike optional parameters. I would rather see this constructor as an overloaded one. Or even better, don't provide the default values at all: they don't seem to be really a default value. In any non-wrap-around hex grid, you'll have hexes that ignore the 6-connected-rooms default value. And if you use your Cave for non-hex systems (it isn't bound to), this default value isn't relevant at all. Furthermore, the value 300 to the apothem seems... random? I don't know what a 300 apothem means to a cave. It is the size in pixels of the apothems you're using for your game?

The method names getRoomDict, getRoomList and randomCaveGen doesn't follow the PascalCase, but rather the camelCase, commonly used in Java. But in C#, stick to PascalCase for methods (even private ones) and camelCase for variables.

All these methods and properties about dealing with dictionaries, as I said before, I would not use them, because I would not use dictionaries. So I'll skip directly into the AddRoom method.

if (someBoolean == true) is uncommon. Usually, you see if (someBoolean). It makes more sense when reading the code, check: if (String.IsNullOrEmpty("abc") == true) vs if (String.IsNullOrEmpty("abc")). That said, if (bats == true && pit == true) should read if (hasBats && hasPit).

The method first creates the room, and then check if it has any errors. This is really weird, are you really going to add the room even if it has errors? Fortunately, we've moved the checks to the Room class, so our AddRoom method doesn't need it anymore. Even more, this method can simply receive a room. And even more, if we expose our IList<Room>, we don't need this method at all.

Thank you! And the cave generation code doesn't actually generate the cave, but it takes the graph of caves and generates positions for each room. Should I still have another class for this? — Kyranstar, Apr 24 at 23:58
@Kyranstar added more content to the answer, covering more the Room and Cave classes. — Mephy, Apr 25 at 2:51

asked	4 months ago
viewed	128 times
active	4 months ago

current community

your communities

more stack exchange communities

A* algorithm for hex tiles

1 Answer 1

Your Answer

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

Hot Network Questions

current community

your communities

more stack exchange communities

A* algorithm for hex tiles

1 Answer 1

Your Answer

Sign up or log in

Post as a guest

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

Related

Hot Network Questions