MapBuilder.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Maze
{
    public class MapBuilder
    {
        private Random rng = new Random();

        [Flags]
        public enum Direction
        {
            None = 0,
            North = 1,
            South = 2,
            East = 4,
            West = 8,
        }

        public enum TileTypes
        {
            HallDeadEnd = 0,
            HallStraight = 1,
            HallCurved = 2,
            HallTee = 3,
            HallIntersection = 4,
            RoomDeadEnd = 5,
            RoomStraight = 6,
            RoomCurved = 7,
            RoomTee = 8,
            RoomIntersection = 9,
            RoomVault = 10,
        }

        private class Point
        {
            public int x { get; set; }
            public int y { get; set; }
            public Point(int x, int y)
            {
                this.x = x;
                this.y = y;
            }
            public override bool Equals(object obj)
            {
                return obj is Point ? (obj as Point).x == this.x && (obj as Point).y == y : false;
            }
        }

        //─│┌┐└┘├┤┬┴┼˂˃˄˅═║╔╗╚╝╠╣╦╩╬□█
        //─│┌┐└┘├┤┬┴┼<>^v═║╔╗╚╝╠╣╦╩╬o#
        private const string MasterTiles = "─│┌┐└┘├┤┬┴┼<>^v═║╔╗╚╝╠╣╦╩╬$.";
        private static char HallStraightCharEW = MasterTiles[0];
        private static char HallStraightCharNS = MasterTiles[1];
        private static char HallCurvedCharSE = MasterTiles[2];
        private static char HallCurvedCharSW = MasterTiles[3];
        private static char HallCurvedCharNE = MasterTiles[4];
        private static char HallCurvedCharNW = MasterTiles[5];
        private static char HallTeeCharNSE = MasterTiles[6];
        private static char HallTeeCharNSW = MasterTiles[7];
        private static char HallTeeCharSEW = MasterTiles[8];
        private static char HallTeeCharNEW = MasterTiles[9];
        private static char HallIntersectionChar = MasterTiles[10];
        private static char RoomDeadEndCharW = MasterTiles[11];
        private static char RoomDeadEndCharE = MasterTiles[12];
        private static char RoomDeadEndCharN = MasterTiles[13];
        private static char RoomDeadEndCharS = MasterTiles[14];
        private static char RoomStraightCharEW = MasterTiles[15];
        private static char RoomStraightCharNS = MasterTiles[16];
        private static char RoomCurvedCharSE = MasterTiles[17];
        private static char RoomCurvedCharSW = MasterTiles[18];
        private static char RoomCurvedCharNE = MasterTiles[19];
        private static char RoomCurvedCharNW = MasterTiles[20];
        private static char RoomTeeCharNSE = MasterTiles[21];
        private static char RoomTeeCharNSW = MasterTiles[22];
        private static char RoomTeeCharSEW = MasterTiles[23];
        private static char RoomTeeCharNEW = MasterTiles[24];
        private static char RoomIntersectionChar = MasterTiles[25];
        private static char RoomVaultChar = MasterTiles[26];
        private static char HallDeadEndChar = MasterTiles[27];


        private static char[] HallDeadEnd = new char[] { HallDeadEndChar };
        private static char[] HallStraight = new char[] { HallStraightCharEW, HallStraightCharNS };
        private static char[] HallCurved =
 new char[] { HallCurvedCharSE, HallCurvedCharSW, HallCurvedCharNE, HallCurvedCharNW };
        private static char[] HallTee =
 new char[] { HallTeeCharNSE, HallTeeCharNSW, HallTeeCharSEW, HallTeeCharNEW };
        private static char[] HallIntersection = new char[] { HallIntersectionChar };
        private static char[] RoomDeadEnd =
 new char[] { RoomDeadEndCharW, RoomDeadEndCharE, RoomDeadEndCharN, RoomDeadEndCharS };
        private static char[] RoomStraight = new char[] { RoomStraightCharEW, RoomStraightCharNS };
        private static char[] RoomCurved =
 new char[] { RoomCurvedCharSE, RoomCurvedCharSW, RoomCurvedCharNE, RoomCurvedCharNW };
        private static char[] RoomTee =
 new char[] { RoomTeeCharNSE, RoomTeeCharNSW, RoomTeeCharSEW, RoomTeeCharNEW };
        private static char[] RoomIntersection = new char[] { RoomIntersectionChar };
        private static char[] RoomVault = new char[] { RoomVaultChar };
        private static Dictionary<TileTypes, char[]> Tiles = new Dictionary<TileTypes, char[]>
        {
            { TileTypes.HallDeadEnd, HallDeadEnd},
            { TileTypes.HallStraight, HallStraight}, 
            { TileTypes.HallCurved, HallCurved}, 
            { TileTypes.HallTee, HallTee}, 
            { TileTypes.HallIntersection, HallIntersection},
            { TileTypes.RoomDeadEnd, RoomDeadEnd}, 
            { TileTypes.RoomStraight, RoomStraight}, 
            { TileTypes.RoomCurved, RoomCurved}, 
            { TileTypes.RoomTee, RoomTee}, 
            { TileTypes.RoomIntersection, RoomIntersection},
            { TileTypes.RoomVault, RoomVault},
        };

        private static Dictionary<Direction, char[]> HallDeadEndDirectionToChar =
 new Dictionary<Direction, char[]> { 
            { Direction.North, new char[] { HallDeadEndChar } },
            { Direction.South, new char[] { HallDeadEndChar } },
            { Direction.East, new char[] { HallDeadEndChar } },
            { Direction.West, new char[] { HallDeadEndChar } },
        };
        private static Dictionary<Direction, char[]> HallStraightDirectionToChar =
 new Dictionary<Direction, char[]> {
            { Direction.North, new char[] { HallStraightCharNS } },
            { Direction.South, new char[] { HallStraightCharNS } },
            { Direction.East, new char[] { HallStraightCharEW } },
            { Direction.West, new char[] { HallStraightCharEW } },
        };
        private static Dictionary<Direction, char[]> HallCurvedDirectionToChar =
 new Dictionary<Direction, char[]> {
            { Direction.North, new char[] { HallCurvedCharNE, HallCurvedCharNW } },
            { Direction.South, new char[] { HallCurvedCharSE, HallCurvedCharSW } },
            { Direction.East, new char[] { HallCurvedCharSE, HallCurvedCharNE } },
            { Direction.West, new char[] { HallCurvedCharSW, HallCurvedCharNW } },
        };
        private static Dictionary<Direction, char[]> HallTeeDirectionToChar =
 new Dictionary<Direction, char[]> {            
            { Direction.North, new char[] { HallTeeCharNSE, HallTeeCharNSW, HallTeeCharNEW } },
            { Direction.South, new char[] { HallTeeCharNSE, HallTeeCharNSW, HallTeeCharSEW } },
            { Direction.East, new char[] { HallTeeCharNSE, HallTeeCharSEW, HallTeeCharNEW } },
            { Direction.West, new char[] { HallTeeCharNSW, HallTeeCharSEW, HallTeeCharNEW } },
        };
        private static Dictionary<Direction, char[]> HallIntersectionDirectionToChar =
 new Dictionary<Direction, char[]> {        
            { Direction.North, new char[] { HallIntersectionChar } },
            { Direction.South, new char[] { HallIntersectionChar } },
            { Direction.East, new char[] { HallIntersectionChar } },
            { Direction.West, new char[] { HallIntersectionChar } },            
        };
        private static Dictionary<Direction, char[]> RoomDeadEndDirectionToChar =
 new Dictionary<Direction, char[]> {                
            { Direction.North, new char[] { RoomDeadEndCharN } },
            { Direction.South, new char[] { RoomDeadEndCharS } },
            { Direction.East, new char[] { RoomDeadEndCharE } },
            { Direction.West, new char[] { RoomDeadEndCharW } },                        
        };
        private static Dictionary<Direction, char[]> RoomStraightDirectionToChar =
 new Dictionary<Direction, char[]> {
            { Direction.North, new char[] { RoomStraightCharNS } },
            { Direction.South, new char[] { RoomStraightCharNS } },
            { Direction.East, new char[] { RoomStraightCharEW } },
            { Direction.West, new char[] { RoomStraightCharEW } },            
        };
        private static Dictionary<Direction, char[]> RoomCurvedDirectionToChar =
 new Dictionary<Direction, char[]> {
            { Direction.North, new char[] { RoomCurvedCharNE, RoomCurvedCharNW } },
            { Direction.South, new char[] { RoomCurvedCharSE, RoomCurvedCharSW } },
            { Direction.East, new char[] { RoomCurvedCharSE, RoomCurvedCharNE } },
            { Direction.West, new char[] { RoomCurvedCharSW, RoomCurvedCharNW } },                        
        };
        private static Dictionary<Direction, char[]> RoomTeeDirectionToChar =
 new Dictionary<Direction, char[]> {
            { Direction.North, new char[] { RoomTeeCharNSE, RoomTeeCharNSW, RoomTeeCharNEW } },
            { Direction.South, new char[] { RoomTeeCharNSE, RoomTeeCharNSW, RoomTeeCharSEW } },
            { Direction.East, new char[] { RoomTeeCharNSE, RoomTeeCharSEW, RoomTeeCharNEW } },
            { Direction.West, new char[] { RoomTeeCharNSW, RoomTeeCharSEW, RoomTeeCharNEW } },                        
        };
        private static Dictionary<Direction, char[]> RoomIntersectionDirectionToChar =
 new Dictionary<Direction, char[]> {
            { Direction.North, new char[] { RoomIntersectionChar } },
            { Direction.South, new char[] { RoomIntersectionChar } },
            { Direction.East, new char[] { RoomIntersectionChar } },
            { Direction.West, new char[] { RoomIntersectionChar } },                        
        };
        private static Dictionary<Direction, char[]> RoomVaultDirectionToChar =
 new Dictionary<Direction, char[]> {
            { Direction.None, new char[] { RoomVaultChar } },            
        };
        private static Dictionary<char, Direction> TilesToDirections = new Dictionary<char, Direction>
        {
            {'\0', Direction.None },
            {HallStraightCharEW, Direction.East | Direction.West },
            {HallStraightCharNS, Direction.North | Direction.South },
            {HallCurvedCharSE, Direction.South | Direction.East },
            {HallCurvedCharSW, Direction.South | Direction.West },
            {HallCurvedCharNE, Direction.North | Direction.East },
            {HallCurvedCharNW, Direction.North | Direction.West },
            {HallTeeCharNSE, Direction.North | Direction.South | Direction.East },
            {HallTeeCharNSW, Direction.North | Direction.South | Direction.West },
            {HallTeeCharSEW, Direction.East | Direction.South | Direction.West },
            {HallTeeCharNEW, Direction.East | Direction.North | Direction.West },
            {HallIntersectionChar, Direction.North | Direction.South | Direction.East | Direction.West },
            {RoomDeadEndCharW, Direction.West },
            {RoomDeadEndCharE, Direction.East },
            {RoomDeadEndCharN, Direction.North },
            {RoomDeadEndCharS, Direction.South },
            {RoomStraightCharEW, Direction.East | Direction.West },
            {RoomStraightCharNS, Direction.North | Direction.South },
            {RoomCurvedCharSE, Direction.South | Direction.East },
            {RoomCurvedCharSW, Direction.South | Direction.West },
            {RoomCurvedCharNE, Direction.North | Direction.East },
            {RoomCurvedCharNW, Direction.North | Direction.West },
            {RoomTeeCharNSE, Direction.North | Direction.South | Direction.East },
            {RoomTeeCharNSW, Direction.North | Direction.South | Direction.West },
            {RoomTeeCharSEW, Direction.East | Direction.South | Direction.West },
            {RoomTeeCharNEW, Direction.East | Direction.North | Direction.West },
            {RoomIntersectionChar, Direction.North | Direction.South | Direction.East | Direction.West },
            {RoomVaultChar, Direction.None },
            {HallDeadEndChar, Direction.None },
        };

        private char[,] Level;
        private Stack<Point> FutureEndpoints = new Stack<Point>();

        public void Build(int xSize, int ySize, int depth)
        {
            for (int j = 0; j < depth; j++)
            {
                Level = new char[xSize, ySize];

                TileTypes nextType = GetRoomType();

                Point loc = new Point(rng.Next(0, xSize), rng.Next(0, ySize));

                Direction restrictions = Direction.None;

                Stack<TileTypes> LevelTiles =
 new Stack<TileTypes>(GetLevelTiles(xSize * ySize - 1, depth));

                for (int i = 1; i < xSize * ySize; i++)
                {
                    //Console.Out.WriteLine(string.Format("Found {0}.", nextType.ToString()));
                    PlaceTile(nextType, loc, restrictions);
                    //PrintMap();

                    FindFutureEndpoints(loc);

                    if (FutureEndpoints.Count == 0)
                    {
                        FutureEndpoints.Push(FindSecretPassage());
                        //Console.Out.WriteLine("Found secret passage.");
                    }

                    loc = FutureEndpoints.Pop();

                    restrictions = FindRestrictions(loc);

                    nextType = LevelTiles.Pop();
                }

                //Console.Out.WriteLine(string.Format("Found {0}.", nextType.ToString()));
                PlaceTile(nextType, loc, restrictions);
                PrintMap();
                Console.Out.WriteLine();
            }
        }
        
        private IEnumerable<TileTypes> GetLevelTiles(int count, int depth)
        {
            List<TileTypes> tts = new List<TileTypes>();

            if (rng.Next(100) > 35) { tts.Add(TileTypes.RoomVault); }
            tts.Add(GetRoomType());

            while (tts.Count < count)
            {
                tts.Add(rng.Next(0, 12) < 7 ? GetRoomType() : GetHallType());
            }

            tts.Shuffle();
            return tts;
        }

        private void PrintMap()
        {
            for (int y = 0; y < Level.GetLength(1); y++)
            {
                for (int x = 0; x < Level.GetLength(0); x++)
                {
                    Console.Out.Write(Level[x, y]);
                }
                Console.Out.WriteLine();
            }
        }

        private Point FindSecretPassage()
        {
            for (int y = 0; y < Level.GetLength(1); y++)
            {
                for (int x = 0; x < Level.GetLength(0); x++)
                {
                    if (Level[x, y] == '\0' &&
                        ((IsLegalX(x + 1) && Level[x + 1, y] != '\0') ||
                        (IsLegalX(x - 1) && Level[x - 1, y] != '\0') ||
                        (IsLegalY(y + 1) && Level[x, y + 1] != '\0') ||
                        (IsLegalY(y - 1) && Level[x, y - 1] != '\0')))
                    {
                        return new Point(x, y);
                    }
                }
            }

            throw new Exception("What?");
        }

        private Direction FindDesires(Point current)
        {
            return
                (IsLegalX(current.x + 1) && Level[current.x + 1, current.y] == '\0' ?
 Direction.East : Direction.None) |
                (IsLegalX(current.x - 1) && Level[current.x - 1, current.y] == '\0' ?
 Direction.West : Direction.None) |
                (IsLegalY(current.y + 1) && Level[current.x, current.y + 1] == '\0' ?
 Direction.South : Direction.None) |
                (IsLegalY(current.y - 1) && Level[current.x, current.y - 1] == '\0' ?
 Direction.North : Direction.None);
        }

        private Direction FindRestrictions(Point current)
        {
            return
                (IsLegalX(current.x + 1) &&
 TilesToDirections[Level[current.x + 1, current.y]].HasFlag(Direction.West) ?
 Direction.East : Direction.None) |
                (IsLegalX(current.x - 1) &&
 TilesToDirections[Level[current.x - 1, current.y]].HasFlag(Direction.East) ?
 Direction.West : Direction.None) |
                (IsLegalY(current.y + 1) &&
 TilesToDirections[Level[current.x, current.y + 1]].HasFlag(Direction.North) ?
 Direction.South : Direction.None) |
                (IsLegalY(current.y - 1) &&
 TilesToDirections[Level[current.x, current.y - 1]].HasFlag(Direction.South) ?
 Direction.North : Direction.None);
        }

        private void FindFutureEndpoints(Point loc)
        {
            Direction directions = TilesToDirections[Level[loc.x, loc.y]];
            if (directions.HasFlag(Direction.North) && IsLegalLocation(loc.x, loc.y - 1))
            {
                AddEndpointIfNew(new Point(loc.x, loc.y - 1));
            } // Not an else if because a tile can have multiple flags set
            if (directions.HasFlag(Direction.South) && IsLegalLocation(loc.x, loc.y + 1))
            {
                AddEndpointIfNew(new Point(loc.x, loc.y + 1));
            }
            if (directions.HasFlag(Direction.East) && IsLegalLocation(loc.x + 1, loc.y))
            {
                AddEndpointIfNew(new Point(loc.x + 1, loc.y));
            }
            if (directions.HasFlag(Direction.West) && IsLegalLocation(loc.x - 1, loc.y))
            {
                AddEndpointIfNew(new Point(loc.x - 1, loc.y));
            }
        }

        private void AddEndpointIfNew(Point point)
        {
            if (!FutureEndpoints.Contains(point) && Level[point.x, point.y] == '\0')
            {
                FutureEndpoints.Push(point);
            }
        }

        private bool IsLegalLocation(int x, int y)
        {
            return x >= 0 && y >= 0 && x < Level.GetLength(0) && y < Level.GetLength(1);
        }

        private bool IsLegalX(int x)
        {
            return x >= 0 && x < Level.GetLength(0);
        }

        private bool IsLegalY(int y)
        {
            return y >= 0 && y < Level.GetLength(1);
        }

        private void PlaceTile(TileTypes nextType, Point loc, Direction direction = Direction.None)
        {
            var tiles = Tiles[nextType];
            var vals = new Tuple<int, int>[tiles.Length];
            int highVal = 0;
            for (int i = 0; i < tiles.Length; i++)
            {
                var tile = tiles[i];
                vals[i] = new Tuple<int, int>(i, (int)(TilesToDirections[tile] & direction));
                if (vals[i].Item2 > highVal) { highVal = vals[i].Item2; }
            }
            var highTiles = vals.Where(y => y.Item2 == highVal).Select(x => tiles[x.Item1]).ToArray();

            if (highTiles.Count() > 1)
            {
                var desire = FindDesires(loc);
                highVal = 0;
                vals = new Tuple<int, int>[highTiles.Length];
                for (int i = 0; i < highTiles.Length; i++)
                {
                    var tile = highTiles[i];
                    vals[i] = new Tuple<int, int>(i, (int)(TilesToDirections[tile] & desire));
                    if (vals[i].Item2 > highVal) { highVal = vals[i].Item2; }
                }
                highTiles = vals.Where(y => y.Item2 == highVal).Select(x => highTiles[x.Item1]).ToArray();
            }

            Level[loc.x, loc.y] = SelectFromArray(highTiles);
        }

        private char SelectFromArray(char[] array)
        {
            return array[rng.Next(0, array.Length)];
        }

        private TileTypes GetRoomType()
        {
            return rng.Next(10) == 0 ? TileTypes.RoomDeadEnd : GetTile(6, 10);
        }

        private TileTypes GetHallType()
        {
            return rng.Next(10) == 0 ? TileTypes.HallDeadEnd : GetTile(1, 5);
        }

        private TileTypes GetTile(int low, int highEx)
        {
            return (TileTypes)rng.Next(low, highEx);
        }
    }
}