http://pcg.wikidot.com/pcg-algorithm:dungeon-generation

先吐个槽，我想让unity自动生成roguelike类的地下城地图，但是非常反感长长的走廊，希望玩家在房间与房间中穿梭，但不能太复杂，做成迷宫状，玩家基本全职寻路了（个人不那么喜欢跑路玩）。

刚开始看到一个非常惊艳的方法

Procedural Dungeon Generation 

在计算过程中发现位置不能控制住，出现完全分离的两个部分，对于我这种这么纠结走廊的人来说，一个多余的走廊都不想要，实在接受不了，中途放弃了这个算法。

using UnityEngine;
using System.Collections;
using System.Collections.Generic;

public enum Direction
{
    North,East,South,West,Left,Right,
}
public class Test01 : MonoBehaviour {
    public Room room;
    public List<Room> rooms;
    public int roomsCount = 10;

    private class LineSegment
    {
        public Vector2 start;
        public Vector2 stop;

        public LineSegment(Vector2 start, Vector2 stop)
        {
            this.start = start;
            this.stop = stop;
        }
    }

    private Dictionary<Room, List<LineSegment>> neighborGraph = new Dictionary<Room, List<LineSegment>>();
    private Dictionary<Room, List<Room>> neighborRoomCollection = new Dictionary<Room, List<Room>>();
void Start () {
        rooms = new List<Room>();
        GameObject roomHolder = new GameObject();
        //1.开启创建房间协程
        StartCoroutine(createRooms(roomHolder));
}

    //创建房间
    IEnumerator createRooms(GameObject obj)
    {
        for (int i = 0; i < roomsCount; i++)
        {
            int roomWidth = Random.Range(6, 9);
            int roomHeight = Random.Range(6, 9);
            Vector2 roomPos = Random.insideUnitCircle * 8;
            room.RoomSetup(roomWidth, roomHeight, roomPos);
            room.GetComponent<Transform>().localScale = new Vector3(roomWidth, roomHeight, 1);
            //room.GetComponent<BoxCollider2D>().size = new Vector2(x, y);
            //以半径为5的区域随机位置
            Room temp=Instantiate(room, roomPos, Quaternion.identity) as Room;
            rooms.Add(temp);
            rooms[i].transform.SetParent(obj.transform);
            yield return null;
        }
        //2.开启物理计算位置是否完成协程
        StartCoroutine(checkSleep());

    }
    //检查物理计算是否完成
    IEnumerator checkSleep()
    {
        bool touching;
        do{
            touching = false;
            for (int i = 0; i < rooms.Count; i++)
            {
                Collider2D a = rooms[i].GetComponent<Collider2D>();
                for (int j = i + 1; j < rooms.Count; j++)
                {
                    Collider2D b = rooms[j].GetComponent<Collider2D>();
                    //相交检查
                    if (a.bounds.Intersects(b.bounds))
                        touching = true;
                }
                yield return null;
            }
        } while (touching == true);
        Debug.Log("check Ok");
        //3.开启房间位置吸附协程
        StartCoroutine(roomsPositionRound());
    }
    //房间位置整理
    IEnumerator roomsPositionRound()
    {
        for (int i = 0; i < rooms.Count; i++)
        {
            Destroy(rooms[i].GetComponent<Collider2D>());
            rooms[i].transform.position = new Vector3(
                Mathf.Floor(rooms[i].transform.position.x),
                Mathf.Floor(rooms[i].transform.position.y),
                rooms[i].transform.position.z);
            yield return null;
        }
        StartCoroutine(FindNeighbors());
    }

    IEnumerator FindNeighbors()
    {
        Room a, b, c;
        float abDist, acDist, bcDist;
        bool skip;
        for (int i = 0; i < roomsCount; i++)
        {
            a = rooms[i];
            for (int j = i + 1; j < roomsCount; j++)
            {
                skip = false;
                b = rooms[j];
                abDist = GetDist(a, b);
                for (int k = 0; k < roomsCount; k++)
                {
                    if (k == i || k == j) continue;
                    c = rooms[k];
                    acDist = GetDist(a, c);
                    bcDist = GetDist(b, c);
                    if (acDist < abDist && bcDist < abDist)
                        skip = true;
                    if (skip)
                        break;
                }
                if (!skip)
                {
                    if (!neighborGraph.ContainsKey(a))
                    {
                        neighborGraph.Add(a, new List<LineSegment>());
                        neighborRoomCollection.Add(a, new List<Room>());
                    }
                    Vector2 aCenter = a.GetComponent<Transform>().position ;
                    Vector2 bCenter = b.GetComponent<Transform>().position;
                    aCenter += new Vector2(a.roomWidth * 0.5f, a.roomHeight * 0.5f);
                    bCenter += new Vector2(b.roomWidth * 0.5f, b.roomHeight * 0.5f);
                    neighborGraph[a].Add(new LineSegment(aCenter,bCenter));
                    neighborRoomCollection[a].Add(b);
                    yield return new WaitForSeconds(0.001f);
                }
            }
        }
    }

    float GetDist(Room a, Room b)
    {
        Vector2 aPos = a.GetComponent<Transform>().position;
        Vector2 bPos = b.GetComponent<Transform>().position;
        return Mathf.Pow((aPos.x + a.roomWidth * 0.5f) - (bPos.x + b.roomWidth * 0.5f), 2) + Mathf.Pow((aPos.y + a.roomWidth * 0.5f) - (bPos.y + b.roomWidth * 0.5f), 2);
    }

    void Update()
    {
        foreach (Room r in neighborGraph.Keys)
        {
            foreach (LineSegment l in neighborGraph[r])
            {
                Debug.DrawLine(l.start, l.stop, new Color(1f, 1f, 0f, 0.5f));
            }
        }
    }
}

最后选取了这种方法，一开始没有太看得上，用了发现好东西简单而优美，而我的代码丑的自己都惊了。

一种 Roguelike 地牢生成算法

带墙壁的效果

人物活动范围

using UnityEngine;
using System.Collections;
using System.Collections.Generic;

public enum Directions
{
    North,East,South,West,
}
public class test : MonoBehaviour {
    private enum TileType
    {
        Dirt,Floor,Wall,Door,Corner,
    }
    private int bb;
    private TileType[][] grid;
    private int COLS = 80;
    private int ROWS = 80;
    public GameObject[] Type;
    private float scale = 0.1f;
    private GameObject boardHolder;
    private Directions dir;
    private Vector2 roomPos;
    private Vector2 doorPos;
    private int roomWidth;
    private int roomHeight;
    private int roomCount;
void Start () {
        roomCount = 0;
        boardHolder = new GameObject();
        //StartCoroutine(aa()); 
        init();
}
    private void init()
    {
        grid = new TileType[COLS][];
        for (int i = 0; i < grid.Length; i++)
        {
            grid[i] = new TileType[ROWS];
        }
        createFirstRoom();
        //StartCoroutine(createFeature());
        while (roomCount < 30)
            createFeature();
        InstantiateTiles();
        Debug.Log(grid[0][0]);
    }

    private void createFeature()
    {
        do
        {
            selectPoint();
        } while (!inState());
        if (createRoom((int)roomPos.x, (int)roomPos.y, roomWidth, roomHeight))
        {
            int tx = (int)doorPos.x;
            int ty = (int)doorPos.y;
            grid[tx][ty] = TileType.Door;
            switch (dir)
            {
                case Directions.North:
                    grid[tx][ty + 1] = TileType.Floor;
                    break;
                case Directions.East:
                    grid[tx + 1][ty] = TileType.Floor;
                    break;
                case Directions.South:
                    grid[tx][ty - 1] = TileType.Floor;
                    break;
                case Directions.West:
                    grid[tx - 1][ty] = TileType.Floor;
                    break;
                default:
                    break;
            }
            roomCount++;
        }
    }

    private void selectPoint()
    {
        bool inWall = true;
        int x, y;
        TileType tt, tb, tl, tr;
        do
        {
            x = Random.Range(2, COLS - 2);
            y = Random.Range(2, ROWS - 2);

            if (grid[x][y] == TileType.Wall)
            {
                tt = grid[x][y + 1];
                tb = grid[x][y - 1];
                tl = grid[x - 1][y];
                tr = grid[x + 1][y];
                if (tt == TileType.Dirt && (tl == TileType.Wall && tr == TileType.Wall))
                {
                    dir = Directions.North;
                    inWall = false;
                }//North
                else if (tb == TileType.Dirt && (tl == TileType.Wall && tr == TileType.Wall))
                {
                    dir = Directions.South;
                    inWall = false;
                }//South
                else if (tl == TileType.Dirt && (tt == TileType.Wall && tb == TileType.Wall))
                {
                    dir = Directions.West;
                    inWall = false;
                }//West
                else if (tr == TileType.Dirt && (tt == TileType.Wall && tb == TileType.Wall))
                {
                    dir = Directions.East;
                    inWall = false;
                }//East
            }
        } while (inWall);
        doorPos = new Vector2(x, y);
    }
    private bool inState()
    {
        Vector2 Pos = doorPos;
        int fw = Random.Range(6, 12);
        int fh = Random.Range(6, 12);
        if (dir == Directions.North || dir == Directions.South)
        {
            if (Pos.x - fw / 2 - 1 < 1 || Pos.x + fw / 2 + 1 > COLS - 1)
                return false;
            Pos.x -= Mathf.CeilToInt(fw * 0.5f);
            if (dir == Directions.North)
            {
                Pos.y += 1;
                if (Pos.y + fh > ROWS - 1)
                    return false;
            }
            else
            {
                Pos.y -= fh + 1;
                if (Pos.y < 1)
                    return false;
            }
        }
        else
        {
            if (Pos.y - fh / 2 - 1 < 1 || Pos.y + fh / 2 + 1 > ROWS - 1)
                return false;
            Pos.y -= Mathf.CeilToInt(fh * 0.5f);
            if (dir == Directions.East)
            {
                Pos.x += 1;
                if (Pos.x + fw > COLS - 1)
                    return false;
            }
            else
            {
                Pos.x -= fw + 1;
                if (Pos.x < 1)
                    return false;
            }
        }
        roomPos = Pos;
        roomWidth = fw;
        roomHeight = fh;
        return true;
    }

    private void createFirstRoom()
    {
        int fw = Random.Range(6, 12);
        int fh = Random.Range(6, 12);
        //create room
        createRoom((COLS / 2 - fw / 2), (ROWS / 2 - fh / 2), fw, fh);

    }

    private bool createRoom(int s, int e, int w, int h)
    {
        w += s;
        h += e;
        //check Area
        if (checkArea(s, e, w, h) && (s != w && e != h))
        {
            for (int i = s; i <= w; i++)
            {
                for (int j = e; j <= h; j++)
                {
                    if (i == s || i == w || j == e || j == h)
                        grid[i][j] = TileType.Wall;
                    else
                        grid[i][j] = TileType.Floor;
                }
            }
            grid[s][e] = TileType.Corner;
            grid[w][e] = TileType.Corner;
            grid[s][h] = TileType.Corner;
            grid[w][h] = TileType.Corner;
            return true;
        }
        return false;
    }

    private bool checkArea(int s, int e, int w, int h)
    {
        for (int i = s; i < w; i++)
        {
            for (int j = e; j < h; j++)
            {
                if (grid[i][j] != TileType.Dirt)
                    return false;
            }
        }
        return true;
    }

    private void InstantiateTiles()
    {
        for (int i = 0; i < COLS; i++)
        {
            for (int j = 0; j < ROWS; j++)
            {
                switch (grid[i][j])
                {
                    case TileType.Dirt:
                        InstantiateFromArray(Type[0], i, j);
                        break;
                    case TileType.Floor:
                        InstantiateFromArray(Type[1], i, j);
                        break;
                    case TileType.Wall:
                        InstantiateFromArray(Type[2], i, j);
                        break;
                    case TileType.Door:
                        InstantiateFromArray(Type[3], i, j);
                        break;
                    case TileType.Corner:
                        InstantiateFromArray(Type[4], i, j);
                        break;
                    default:
                        break;
                }
            }
        }

    }

    private void InstantiateFromArray(GameObject prefab, int xCoord, int yCoord)
    {
        float x = (float)xCoord * scale;
        float y = (float)yCoord * scale;
        prefab.GetComponent<Transform>().localScale = new Vector2(scale, scale);
        GameObject tileInstance = Instantiate(prefab, new Vector2(x, y), Quaternion.identity) as GameObject;
        tileInstance.transform.parent = boardHolder.transform;
    }

}