C++實現隨機生成迷宮地牢

2020-01-26 15:08:17
字體：大中小
來源：轉載
供稿：網友
可以用這個地圖核心做成一個無限迷宮類的游戲
main.cpp
// Author: FreeKnight 2014-09-02#include "stdafx.h"#include <iostream>#include <string>#include <random>#include <cassert> /*簡單邏輯流程描述：將整個地圖填滿土在地圖中間挖一個房間出來選中某一房間（如果有多個的話）的墻壁確定要修建某種新元素查看從選中的墻延伸出去是否有足夠的空間承載新的元素如果有的話繼續，不然就返回第 3 步從選中的墻處增加新的元素返回第 3 步，直到地牢建設完成在地圖的隨機點上安排上樓和下樓的樓梯最后，放進去怪獸和物品*///-------------------------------------------------------------------------------// 暫時支持的最大的地圖塊個數#define MAX_TILES_NUM  10000 // 房間的大小#define MAX_ROOM_WIDTH  8#define MAX_ROOM_HEIGHT 8#define MIN_ROOM_WIDTH  4#define MIN_ROOM_HEIGHT 4 // 房間和走廊的合計最大個數#define DEFAULT_FEATURE_NUM 1000 // 嘗試生成房間和走廊的測試次數（即步長）#define MAX_TRY_TIMES  1000 // 默認創建房間的概率（100-該值則為創建走廊的概率）#define DEFAULT_CREATE_ROOM_CHANCE  70 // 走廊長度#define MIN_CORRIDOR_LEN   3#define MAX_CORRIDOR_LEN   6//-------------------------------------------------------------------------------// 格子塊enum class Tile{  Unused, // 沒用的格子（土塊）  DirtWall,  // 墻壁  DirtFloor,  // 房間地板  Corridor,  // 走廊  Door,  // 房門  UpStairs,  // 入口  DownStairs // 出口};//-------------------------------------------------------------------------------// 朝向enum class Direction{  North,  // 北  South,  // 南  East,  // 東  West,  // 西};//-------------------------------------------------------------------------------class Map{public:   Map():    xSize(0), ySize(0),    data() { }   // 構造函數，全屏填土  Map(int x, int y, Tile value = Tile::Unused):    xSize(x), ySize(y),    data(x * y, value) { }   // 填充某塊類型  void SetCell(int x, int y, Tile celltype)  {    assert(IsXInBounds(x));    assert(IsYInBounds(y));     data[x + xSize * y] = celltype;  }   // 獲取某塊類型  Tile GetCell(int x, int y) const  {    assert(IsXInBounds(x));    assert(IsYInBounds(y));     return data[x + xSize * y];  }   // 設置一塊區域為指定類型塊  void SetCells(int xStart, int yStart, int xEnd, int yEnd, Tile cellType)  {    assert(IsXInBounds(xStart) && IsXInBounds(xEnd));    assert(IsYInBounds(yStart) && IsYInBounds(yEnd));     assert(xStart <= xEnd);    assert(yStart <= yEnd);     for (auto y = yStart; y != yEnd + 1; ++y)    {      for (auto x = xStart; x != xEnd + 1; ++x)      {        SetCell(x, y, cellType);      }    }  }   // 判斷一塊是否在有效范圍內  bool IsXInBounds(int x) const  {    return x >= 0 && x < xSize;  }   // 判斷一塊是否在有效范圍內  bool IsYInBounds(int y) const  {    return y >= 0 && y < ySize;  }   // 判斷一個區域是否已被使用過  bool IsAreaUnused(int xStart, int yStart, int xEnd, int yEnd)  {    assert(IsXInBounds(xStart) && IsXInBounds(xEnd));    assert(IsYInBounds(yStart) && IsYInBounds(yEnd));     assert(xStart <= xEnd);    assert(yStart <= yEnd);     for (auto y = yStart; y != yEnd + 1; ++y)    {      for (auto x = xStart; x != xEnd + 1; ++x)      {        if (GetCell(x, y) != Tile::Unused)        {          return false;        }      }    }     return true;  }   // 判斷一個地圖塊周圍是否臨接某種地圖塊  bool IsAdjacent(int x, int y, Tile tile)  {    assert(IsXInBounds(x - 1) && IsXInBounds(x + 1));    assert(IsYInBounds(y - 1) && IsYInBounds(y + 1));     return (GetCell(x - 1, y) == tile || GetCell(x + 1, y) == tile ||      GetCell(x, y - 1) == tile || GetCell(x, y + 1) == tile);  }   // 輸出地圖  void Print() const  {    for (auto y = 0; y != ySize; y++)    {      for (auto x = 0; x != xSize; x++)      {        switch(GetCell(x, y))        {        case Tile::Unused:          std::cout << " ";          break;        case Tile::DirtWall:          std::cout << "#";          break;        case Tile::DirtFloor:          std::cout << "_";          break;        case Tile::Corridor:          std::cout << ".";          break;        case Tile::Door:          std::cout << "+";          break;        case Tile::UpStairs:          std::cout << "<";          break;        case Tile::DownStairs:          std::cout << ">";          break;        };      }       std::cout << std::endl;    }     std::cout << std::endl;  } private:  // 地圖總寬高  int xSize, ySize;  // 全部地圖塊數據  std::vector<Tile> data;};//-------------------------------------------------------------------------------class DungeonGenerator{public:  int m_nSeed;   // 隨機數種子  int m_nXSize, m_nYSize; // 地圖最大寬高   int m_nMaxFeatures; // 房間和走廊的最大個數  int m_nChanceRoom;  // 創建房間的概率【0,100】  int m_nChanceCorridor;  // 創建走廊的概率【0,100】 該概率+創建房間的概率應當 = 100   typedef std::mt19937 RngT;public:  DungeonGenerator( int XSize, int YSize ):    m_nSeed(std::random_device()()),    m_nXSize( XSize ), m_nYSize( YSize ),    m_nMaxFeatures( DEFAULT_FEATURE_NUM ),    m_nChanceRoom( DEFAULT_CREATE_ROOM_CHANCE )  {    m_nChanceCorridor = 100 - m_nChanceRoom;  }   Map Generate()  {    assert( m_nMaxFeatures > 0 && m_nMaxFeatures <= DEFAULT_FEATURE_NUM);    assert( m_nXSize > 3 );    assert( m_nYSize > 3 );     auto rng = RngT(m_nSeed);    // step1: 滿地圖填土    auto map = Map(m_nXSize, m_nYSize, Tile::Unused);     MakeDungeon(map, rng);     return map;  } private:  // 獲取隨機int  int GetRandomInt(RngT& rng, int min, int max) const  {    return std::uniform_int_distribution<int>(min, max)(rng);  }   // 獲取隨機方向  Direction GetRandomDirection(RngT& rng) const  {    return Direction(std::uniform_int_distribution<int>( static_cast<int>(Direction::North), static_cast<int>(Direction::West) )(rng));  }   // 創建走廊  bool MakeCorridor(Map& map, RngT& rng, int x, int y, int maxLength, Direction direction) const  {    assert(x >= 0 && x < m_nXSize);    assert(y >= 0 && y < m_nYSize);     assert(maxLength > 0 && maxLength <= std::max(m_nXSize, m_nYSize));     // 設置走廊長度    auto length = GetRandomInt(rng, MIN_CORRIDOR_LEN, maxLength);     auto xStart = x;    auto yStart = y;     auto xEnd = x;    auto yEnd = y;     if (direction == Direction::North)      yStart = y - length;    else if (direction == Direction::East)      xEnd = x + length;    else if (direction == Direction::South)      yEnd = y + length;    else if (direction == Direction::West)      xStart = x - length;     // 檢查整個走廊是否在地圖內    if (!map.IsXInBounds(xStart) || !map.IsXInBounds(xEnd) || !map.IsYInBounds(yStart) || !map.IsYInBounds(yEnd))      return false;     // 檢查走廊區域是否有被占用    if (!map.IsAreaUnused(xStart, yStart, xEnd, yEnd))      return false;     map.SetCells(xStart, yStart, xEnd, yEnd, Tile::Corridor);     return true;  }   // 創造房間  bool MakeRoom(Map& map, RngT& rng, int x, int y, int xMaxLength, int yMaxLength, Direction direction) const  {    assert( xMaxLength >= MIN_ROOM_WIDTH );    assert( yMaxLength >= MIN_ROOM_HEIGHT );     // 創建的房間最小是4 * 4，隨機出房間大小    auto xLength = GetRandomInt(rng, MIN_ROOM_WIDTH, xMaxLength);    auto yLength = GetRandomInt(rng, MIN_ROOM_HEIGHT, yMaxLength);     auto xStart = x;    auto yStart = y;    auto xEnd = x;    auto yEnd = y;     // 根據房間朝向隨機出房間起始和終結位置    if (direction == Direction::North)    {      yStart = y - yLength;      xStart = x - xLength / 2;      xEnd = x + (xLength + 1) / 2;    }    else if (direction == Direction::East)    {      yStart = y - yLength / 2;      yEnd = y + (yLength + 1) / 2;      xEnd = x + xLength;    }    else if (direction == Direction::South)    {      yEnd = y + yLength;      xStart = x - xLength / 2;      xEnd = x + (xLength + 1) / 2;    }    else if (direction == Direction::West)    {      yStart = y - yLength / 2;      yEnd = y + (yLength + 1) / 2;      xStart = x - xLength;    }     // 要保證生成的房間一定四個點都在地圖中    if (!map.IsXInBounds(xStart) || !map.IsXInBounds(xEnd) || !map.IsYInBounds(yStart) || !map.IsYInBounds(yEnd))      return false;     // 要保證房間所占用土地未被其他地占用    if (!map.IsAreaUnused(xStart, yStart, xEnd, yEnd))      return false;     // 周圍種墻    map.SetCells(xStart, yStart, xEnd, yEnd, Tile::DirtWall);    // 房間內鋪地板    map.SetCells(xStart + 1, yStart + 1, xEnd - 1, yEnd - 1, Tile::DirtFloor);     return true;  }    // 創建一個房間或者走廊  bool MakeRoomOrCorridor(Map& map, RngT& rng, int x, int y, int xmod, int ymod, Direction direction) const  {    // 隨機選擇創建類型（房間或者走廊）    auto chance = GetRandomInt(rng, 0, 100);     if (chance <= m_nChanceRoom)    {      // 創建房間      if (MakeRoom(map, rng, x + xmod, y + ymod, MAX_ROOM_WIDTH, MAX_ROOM_HEIGHT, direction))      {        // 當前位置設置門        map.SetCell(x, y, Tile::Door);         // 刪除門旁邊的墻壁，改建為墻壁        map.SetCell(x + xmod, y + ymod, Tile::DirtFloor);         return true;      }       return false;    }    else    {      // 創建走廊      if (MakeCorridor(map, rng, x + xmod, y + ymod, MAX_CORRIDOR_LEN, direction))      {        // 當前位置設置門        map.SetCell(x, y, Tile::Door);         return true;      }       return false;    }  }    // 對全地圖進行隨機處理生成房間和走廊  bool MakeRandomFeature(Map& map, RngT& rng) const  {    for( auto tries = 0 ; tries != MAX_TRY_TIMES; ++tries)    {      // 獲取一個有意義的地形格      int x = GetRandomInt(rng, 1, m_nXSize - 2);      int y = GetRandomInt(rng, 1, m_nYSize - 2);       // 獲取一個隨機墻壁 或者 走廊      if (map.GetCell(x, y) != Tile::DirtWall && map.GetCell(x, y) != Tile::Corridor)        continue;       // 保證該墻壁和走廊不臨接門      if (map.IsAdjacent(x, y, Tile::Door))        continue;       // 找個臨接墻壁或者走廊的格子 創建新房間或者走廊      if (map.GetCell(x, y+1) == Tile::DirtFloor || map.GetCell(x, y+1) == Tile::Corridor)      {        if (MakeRoomOrCorridor(map, rng, x, y, 0, -1, Direction::North))          return true;      }      else if (map.GetCell(x-1, y) == Tile::DirtFloor || map.GetCell(x-1, y) == Tile::Corridor)      {        if (MakeRoomOrCorridor(map, rng, x, y, 1, 0, Direction::East))          return true;      }      else if (map.GetCell(x, y-1) == Tile::DirtFloor || map.GetCell(x, y-1) == Tile::Corridor)      {        if (MakeRoomOrCorridor(map, rng, x, y, 0, 1, Direction::South))          return true;      }      else if (map.GetCell(x+1, y) == Tile::DirtFloor || map.GetCell(x+1, y) == Tile::Corridor)      {        if (MakeRoomOrCorridor(map, rng, x, y, -1, 0, Direction::West))          return true;      }    }     return false;  }   // 隨機制作出入口  bool MakeRandomStairs(Map& map, RngT& rng, Tile tile) const  {    auto tries = 0;    auto maxTries = MAX_TILES_NUM;     for ( ; tries != maxTries; ++tries)    {      // 隨機獲取一個非邊緣的點      int x = GetRandomInt(rng, 1, m_nXSize - 2);      int y = GetRandomInt(rng, 1, m_nYSize - 2);       // 如果周圍沒有地板并且沒有走廊（通路）的話，直接放棄      if (!map.IsAdjacent(x, y, Tile::DirtFloor) && !map.IsAdjacent(x, y, Tile::Corridor))        continue;       // 周圍不允許有門      if (map.IsAdjacent(x, y, Tile::Door))        continue;       map.SetCell(x, y, tile);       return true;    }     return false;  }   // 隨機生成地牢  bool MakeDungeon(Map& map, RngT& rng) const  {    // step2 : 在正中間創建一個房間    MakeRoom(map, rng, m_nXSize / 2, m_nYSize / 2, MAX_ROOM_WIDTH, MAX_ROOM_HEIGHT, GetRandomDirection(rng));     for (auto features = 1; features != m_nMaxFeatures; ++features)    {      if (!MakeRandomFeature(map, rng))      {        std::cout << "生成地牢已滿。（當前房間和走廊個數為： " << features << "）." << std::endl;        break;      }    }     // 創建隨機入口點    if (!MakeRandomStairs(map, rng, Tile::UpStairs))      std::cout << "創建入口點失敗！" << std::endl;     // 創建隨機出口點    if (!MakeRandomStairs(map, rng, Tile::DownStairs))      std::cout << "創建出口點失敗！" << std::endl;     return true;  }};  #include <windows.h>void ResetConsoleSize(){  HANDLE hOut = GetStdHandle(STD_OUTPUT_HANDLE);   // 獲取標準輸出設備句柄  CONSOLE_SCREEN_BUFFER_INFO bInfo;  // 窗口緩沖區信息  GetConsoleScreenBufferInfo(hOut, &bInfo );  COORD size = {1000, 800};  SetConsoleScreenBufferSize(hOut,size); // 重新設置緩沖區大小  SMALL_RECT rc = {0,0, 1000-1, 800-1};  // 重置窗口位置和大小  SetConsoleWindowInfo(hOut,true ,&rc);}void FlushReadme(){  std::cout<< "=================================" << std::endl;  std::cout<< " < 表示入口 " << std::endl;  std::cout<< " > 表示出口 " << std::endl;  std::cout<< " _ 下劃線表示地板 " << std::endl;  std::cout<< " # 表示墻壁 " << std::endl;  std::cout<< " . 點表示走廊 " << std::endl;  std::cout<< " + 表示門 " << std::endl;  std::cout<< "純黑表示啥都沒有，是障礙" << std::endl;  std::cout<< "=================================" << std::endl;} int main(){  ResetConsoleSize();  FlushReadme();   DungeonGenerator* pGenerator = new DungeonGenerator( 150, 50 );  if( pGenerator == NULL )    return -1;  auto map = pGenerator->Generate();  map.Print();   int n;  std::cin >> n;}
演示圖：