GridPather.cs

// This file created by Emma 'Eniko' Maassen
// Licensed under Creative Commons Attribution 3.0 Unported (CC BY 3.0)
// http://creativecommons.org/licenses/by/3.0/
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;

namespace Indigo.Framework.Random {
    public class GridPath {
        public GridCell[,] Grid;
        public GridCell From;
        public GridCell To;

        public GridPath(GridCell[,] grid, GridCell from, GridCell to) {
            Grid = grid;
            From = from;
            To = to;
        }

        public GridCell GetConnectedCell(GridCell cell, CellConnection con) {
            GridCell conCell = null;

            switch (con) {
                case CellConnection.East:
                    conCell = Grid[cell.X + 1, cell.Y];
                    break;
                case CellConnection.West:
                    conCell = Grid[cell.X - 1, cell.Y];
                    break;
                case CellConnection.South:
                    conCell = Grid[cell.X, cell.Y + 1];
                    break;
                case CellConnection.North:
                    conCell = Grid[cell.X, cell.Y - 1];
                    break;
            }

            return conCell;
        }

        /// <summary>
        /// Create a number of random connections between cells in the grid.
        /// </summary>
        /// <param name="count">Number of connections to make.</param>
        /// <param name="includeFinal">Allows making connections to/from the final cell in the path if true.</param>
        public void AddRandomConnections(int count, System.Random random, bool includeFinal = true) {
            // make list of cells that can be connected
            List<GridCell> connectableCells = new List<GridCell>();
            foreach (GridCell cell in Grid) {
                if (cell.HasUnconnectedNeighbors && (cell != To || includeFinal))
                    connectableCells.Add(cell);
            }

            for (int i = 0; i < count; i++) {
                if (connectableCells.Count == 0)
                    break;

                GridCell cell = null;

                while (connectableCells.Count > 0 &&
                    (cell == null || !cell.HasUnconnectedNeighbors || (!includeFinal && cell == To))) {
                    cell = connectableCells[random.Next(connectableCells.Count)];
                    if (!includeFinal) {
                        List<GridCell> uncNeigh = cell.GetUnconnectedNeighbors(this);
                        if (uncNeigh.Count == 1 && uncNeigh[0] == To) {
                            connectableCells.Remove(cell);
                            cell = null;
                        }
                    }
                }

                if (cell == null)
                    break;
 
                CellConnection con = cell.ConnectRandom(random);
                GridCell conCell = GetConnectedCell(cell, con);

                if (!includeFinal && conCell == To) {
                    cell.Disconnect(con);
                }
                else
                    conCell.ConnectedFrom(con);
                
                if (!cell.HasUnconnectedNeighbors)
                    connectableCells.Remove(cell);
                if (!conCell.HasUnconnectedNeighbors)
                    connectableCells.Remove(conCell);
            }
        }
    }

    public enum CellConnection {
        North,
        South,
        East,
        West
    }

    public class GridCell {
        public int X { get; set; }
        public int Y { get; set; }
        private List<CellConnection> connections;
        private List<CellConnection> neighbors;
        private List<CellConnection> unconnectedNeighbors;

        public GridCell(int x, int y, List<CellConnection> neighbors) {
            X = x;
            Y = y;
            connections = new List<CellConnection>();
            this.neighbors = neighbors;
            if (this.neighbors == null)
                this.neighbors = new List<CellConnection>();
            unconnectedNeighbors = new List<CellConnection>(this.neighbors);
        }

        public void Connect(CellConnection connection) {
            if (!Connections.Contains(connection)) {
                Connections.Add(connection);
                UnconnectedNeighbors.Remove(connection);
            }
        }

        public void ConnectedFrom(CellConnection side) {
            CellConnection con;
            switch (side) {
                case CellConnection.East:
                    con = CellConnection.West;
                    break;
                case CellConnection.West:
                    con = CellConnection.East;
                    break;
                case CellConnection.South:
                    con = CellConnection.North;
                    break;
                case CellConnection.North:
                default:
                    con = CellConnection.South;
                    break;
            }

            Connect(con);
        }

        public CellConnection ConnectRandom(System.Random random) {
            if (UnconnectedNeighbors.Count == 0)
                throw new NoUnconnectedNeighborsException("Error connecting GridCell to random neighbor");

            CellConnection con = UnconnectedNeighbors[random.Next(UnconnectedNeighbors.Count)];
            Connect(con);
            return con;
        }

        public CellConnection? ConnectToRandomConnectedNeighbor(System.Random random, GridPath path) {
            if (UnconnectedNeighbors.Count == 0)
                return null;

            List<CellConnection> possibleNeighbors = new List<CellConnection>(unconnectedNeighbors);
            while (possibleNeighbors.Count > 0) {
                CellConnection con = possibleNeighbors[random.Next(possibleNeighbors.Count)];
                GridCell cell = path.GetConnectedCell(this, con);

                if (cell.IsConnected) {
                    Connect(con);
                    return con;
                }
                else
                    possibleNeighbors.Remove(con);
            }

            return null;
        }

        public void Disconnect(CellConnection connection) {
            connections.Remove(connection);
            unconnectedNeighbors.Add(connection);
        }
        
        public List<GridCell> GetUnconnectedNeighbors(GridPath path) {
            if (!HasUnconnectedNeighbors)
                return null;

            List<GridCell> unconnectedNeighbors = new List<GridCell>();
            List<CellConnection> cons = new List<CellConnection>();
            if (X > 0)
                cons.Add(CellConnection.West);
            if (X < path.Grid.GetUpperBound(0))
                cons.Add(CellConnection.East);
            if (Y > 0)
                cons.Add(CellConnection.North);
            if (Y < path.Grid.GetUpperBound(1))
                cons.Add(CellConnection.South);

            foreach (CellConnection con in Connections) {
                cons.Remove(con);
            }
            foreach (CellConnection con in cons) {
                unconnectedNeighbors.Add(path.GetConnectedCell(this, con));
            }

            return unconnectedNeighbors;
        }

#region Properties
        public bool IsConnected {
            get {
                return connections.Count > 0;
            }
        }
        public bool HasUnconnectedNeighbors {
            get {
                return unconnectedNeighbors.Count > 0;
            }
        }
        public List<CellConnection> Connections { get { return connections; } }
        public List<CellConnection> Neighbors { get { return neighbors; } }
        public List<CellConnection> UnconnectedNeighbors { get { return unconnectedNeighbors; } }
#endregion
    }

    public static class GridPather {
        private static GridPath GetPath(int xSize, int ySize, int? seed = null, Point? fromPoint = null) {
            GridCell[,] grid = new GridCell[xSize, ySize];
            GridPath path = new GridPath(grid, null, null);

            System.Random random;
            if (seed.HasValue)
                random = new System.Random(seed.Value);
            else
                random = new System.Random();

            List<GridCell> unconnectedRooms = new List<GridCell>(xSize * ySize);

            // create cells and add possible neighbors
            for (int y = 0; y < ySize; y++) {
                for (int x = 0; x < xSize; x++) {
                    List<CellConnection> neighbors = new List<CellConnection>();
                    if (x > 0)
                        neighbors.Add(CellConnection.West);
                    if (x < xSize - 1)
                        neighbors.Add(CellConnection.East);
                    if (y > 0)
                        neighbors.Add(CellConnection.North);
                    if (y < xSize - 1)
                        neighbors.Add(CellConnection.South);
                    grid[x, y] = new GridCell(x, y, neighbors);
                    unconnectedRooms.Add(grid[x, y]);
                }
            }

            if (fromPoint.HasValue)
                path.From = grid[fromPoint.Value.X, fromPoint.Value.Y];
            else
                path.From = grid[random.Next(xSize), random.Next(ySize)];
            GridCell curCell = path.From;

            // connect rooms randomly until the path ends
            while (curCell.HasUnconnectedNeighbors) {
                CellConnection con = curCell.ConnectRandom(random);
                unconnectedRooms.Remove(curCell);

                curCell = path.GetConnectedCell(curCell, con);
                curCell.ConnectedFrom(con);
                unconnectedRooms.Remove(curCell);
            }

            // connect unconnected rooms
            while (unconnectedRooms.Count > 0) {
                unconnectedRooms.Shuffle(random);
                for (int i = 0; i < unconnectedRooms.Count; i++ ) {
                    curCell = unconnectedRooms[i];
                    CellConnection? con = curCell.ConnectToRandomConnectedNeighbor(random, path);
                    if (curCell.IsConnected)
                        unconnectedRooms.RemoveAt(i);
                    if (con.HasValue) {
                        GridCell conCell = path.GetConnectedCell(curCell, con.Value);
                        conCell.ConnectedFrom(con.Value);
                        unconnectedRooms.Remove(conCell);
                    }
                }
            }
            path.To = curCell;

            return path;
        }
    }

    public class NoUnconnectedNeighborsException : Exception {
        public NoUnconnectedNeighborsException(string desc) : base(desc + "; already connected to all neighbors.") { }
    }

    public static class ShuffleExtension {
        /// <summary>
        /// Shuffles list.
        /// </summary>
        /// <param name="list">List to shuffle.</param>
        /// <param name="rng">System.Random instance to use for randomizing.</param>
        public static void Shuffle<T>(this IList<T> list, System.Random rng) {
            int n = list.Count;
            while (n > 1) {
                n--;
                int k = rng.Next(n + 1);
                T value = list[k];
                list[k] = list[n];
                list[n] = value;
            }
        }

        /// <summary>
        /// Shuffles list.
        /// </summary>
        /// <param name="seed">Seed to use for randomizing.</param>
        public static void Shuffle<T>(this IList<T> list, int seed) {
            Shuffle(list, new System.Random(seed));
        }

        /// <summary>
        /// Shuffles list, creates a new randomizer to shuffle with.
        /// </summary>
        public static void Shuffle<T>(this IList<T> list) {
            Shuffle(list, new System.Random());
        }
    }
}