// Author: FreeKnight 2014-09-02
#include "stdafx.h"
#include <iostream>
#include <string>
#include <random>
#include <cassert>
 
/*
簡(jiǎn)單邏輯流程描述：
將整個(gè)地圖填滿(mǎn)土
在地圖中間挖一個(gè)房間出來(lái)
選中某一房間（如果有多個(gè)的話(huà)）的墻壁
確定要修建某種新元素
查看從選中的墻延伸出去是否有足夠的空間承載新的元素
如果有的話(huà)繼續(xù)，不然就返回第 3 步
從選中的墻處增加新的元素
返回第 3 步，直到地牢建設(shè)完成
在地圖的隨機(jī)點(diǎn)上安排上樓和下樓的樓梯
最后，放進(jìn)去怪獸和物品
*/
//-------------------------------------------------------------------------------
// 暫時(shí)支持的最大的地圖塊個(gè)數(shù)
#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
 
// 房間和走廊的合計(jì)最大個(gè)數(shù)
#define DEFAULT_FEATURE_NUM 1000
 
// 嘗試生成房間和走廊的測(cè)試次數(shù)（即步長(zhǎng)）
#define MAX_TRY_TIMES  1000
 
// 默認(rèn)創(chuàng)建房間的概率（100-該值則為創(chuàng)建走廊的概率）
#define DEFAULT_CREATE_ROOM_CHANCE  70
 
// 走廊長(zhǎng)度
#define MIN_CORRIDOR_LEN   3
#define MAX_CORRIDOR_LEN   6
//-------------------------------------------------------------------------------
// 格子塊
enum class Tile
{
  Unused, // 沒(méi)用的格子（土塊）
  DirtWall,  // 墻壁
  DirtFloor,  // 房間地板
  Corridor,  // 走廊
  Door,  // 房門(mén)
  UpStairs,  // 入口
  DownStairs // 出口
};
//-------------------------------------------------------------------------------
// 朝向
enum class Direction
{
  North,  // 北
  South,  // 南
  East,  // 東
  West,  // 西
};
//-------------------------------------------------------------------------------
class Map
{
public:
 
  Map():
    xSize(0), ySize(0),
    data() { }
 
  // 構(gòu)造函數(shù)，全屏填土
  Map(int x, int y, Tile value = Tile::Unused):
    xSize(x), ySize(y),
    data(x * y, value) { }
 
  // 填充某塊類(lèi)型
  void SetCell(int x, int y, Tile celltype)
  {
    assert(IsXInBounds(x));
    assert(IsYInBounds(y));
 
    data[x + xSize * y] = celltype;
  }
 
  // 獲取某塊類(lèi)型
  Tile GetCell(int x, int y) const
  {
    assert(IsXInBounds(x));
    assert(IsYInBounds(y));
 
    return data[x + xSize * y];
  }
 
  // 設(shè)置一塊區(qū)域?yàn)橹付?lèi)型塊
  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);
      }
    }
  }
 
  // 判斷一塊是否在有效范圍內(nèi)
  bool IsXInBounds(int x) const
  {
    return x >= 0 && x < xSize;
  }
 
  // 判斷一塊是否在有效范圍內(nèi)
  bool IsYInBounds(int y) const
  {
    return y >= 0 && y < ySize;
  }
 
  // 判斷一個(gè)區(qū)域是否已被使用過(guò)
  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;
  }
 
  // 判斷一個(gè)地圖塊周?chē)欠衽R接某種地圖塊
  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;
  // 全部地圖塊數(shù)據(jù)
  std::vector<Tile> data;
};
//-------------------------------------------------------------------------------
class DungeonGenerator
{
public:
  int m_nSeed;   // 隨機(jī)數(shù)種子
  int m_nXSize, m_nYSize; // 地圖最大寬高 
  int m_nMaxFeatures; // 房間和走廊的最大個(gè)數(shù)
  int m_nChanceRoom;  // 創(chuàng)建房間的概率【0,100】
  int m_nChanceCorridor;  // 創(chuàng)建走廊的概率【0,100】 該概率+創(chuàng)建房間的概率應(yīng)當(dāng) = 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: 滿(mǎn)地圖填土
    auto map = Map(m_nXSize, m_nYSize, Tile::Unused);
 
    MakeDungeon(map, rng);
 
    return map;
  }
 
private:
  // 獲取隨機(jī)int
  int GetRandomInt(RngT& rng, int min, int max) const
  {
    return std::uniform_int_distribution<int>(min, max)(rng);
  }
 
  // 獲取隨機(jī)方向
  Direction GetRandomDirection(RngT& rng) const
  {
    return Direction(std::uniform_int_distribution<int>( static_cast<int>(Direction::North), static_cast<int>(Direction::West) )(rng));
  }
 
  // 創(chuàng)建走廊
  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));
 
    // 設(shè)置走廊長(zhǎng)度
    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;
 
    // 檢查整個(gè)走廊是否在地圖內(nèi)
    if (!map.IsXInBounds(xStart) || !map.IsXInBounds(xEnd) || !map.IsYInBounds(yStart) || !map.IsYInBounds(yEnd))
      return false;
 
    // 檢查走廊區(qū)域是否有被占用
    if (!map.IsAreaUnused(xStart, yStart, xEnd, yEnd))
      return false;
 
    map.SetCells(xStart, yStart, xEnd, yEnd, Tile::Corridor);
 
    return true;
  }
 
  // 創(chuàng)造房間
  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 );
 
    // 創(chuàng)建的房間最小是4 * 4，隨機(jī)出房間大小
    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;
 
    // 根據(jù)房間朝向隨機(jī)出房間起始和終結(jié)位置
    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;
    }
 
    // 要保證生成的房間一定四個(gè)點(diǎn)都在地圖中
    if (!map.IsXInBounds(xStart) || !map.IsXInBounds(xEnd) || !map.IsYInBounds(yStart) || !map.IsYInBounds(yEnd))
      return false;
 
    // 要保證房間所占用土地未被其他地占用
    if (!map.IsAreaUnused(xStart, yStart, xEnd, yEnd))
      return false;
 
    // 周?chē)N墻
    map.SetCells(xStart, yStart, xEnd, yEnd, Tile::DirtWall);
    // 房間內(nèi)鋪地板
    map.SetCells(xStart + 1, yStart + 1, xEnd - 1, yEnd - 1, Tile::DirtFloor);
 
    return true;
  }
 
 
  // 創(chuàng)建一個(gè)房間或者走廊
  bool MakeRoomOrCorridor(Map& map, RngT& rng, int x, int y, int xmod, int ymod, Direction direction) const
  {
    // 隨機(jī)選擇創(chuàng)建類(lèi)型（房間或者走廊）
    auto chance = GetRandomInt(rng, 0, 100);
 
    if (chance <= m_nChanceRoom)
    {
      // 創(chuàng)建房間
      if (MakeRoom(map, rng, x + xmod, y + ymod, MAX_ROOM_WIDTH, MAX_ROOM_HEIGHT, direction))
      {
        // 當(dāng)前位置設(shè)置門(mén)
        map.SetCell(x, y, Tile::Door);
 
        // 刪除門(mén)旁邊的墻壁，改建為墻壁
        map.SetCell(x + xmod, y + ymod, Tile::DirtFloor);
 
        return true;
      }
 
      return false;
    }
    else
    {
      // 創(chuàng)建走廊
      if (MakeCorridor(map, rng, x + xmod, y + ymod, MAX_CORRIDOR_LEN, direction))
      {
        // 當(dāng)前位置設(shè)置門(mén)
        map.SetCell(x, y, Tile::Door);
 
        return true;
      }
 
      return false;
    }
  }
 
 
  // 對(duì)全地圖進(jìn)行隨機(jī)處理生成房間和走廊
  bool MakeRandomFeature(Map& map, RngT& rng) const
  {
    for( auto tries = 0 ; tries != MAX_TRY_TIMES; ++tries)
    {
      // 獲取一個(gè)有意義的地形格
      int x = GetRandomInt(rng, 1, m_nXSize - 2);
      int y = GetRandomInt(rng, 1, m_nYSize - 2);
 
      // 獲取一個(gè)隨機(jī)墻壁 或者 走廊
      if (map.GetCell(x, y) != Tile::DirtWall && map.GetCell(x, y) != Tile::Corridor)
        continue;
 
      // 保證該墻壁和走廊不臨接門(mén)
      if (map.IsAdjacent(x, y, Tile::Door))
        continue;
 
      // 找個(gè)臨接墻壁或者走廊的格子 創(chuàng)建新房間或者走廊
      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;
  }
 
  // 隨機(jī)制作出入口
  bool MakeRandomStairs(Map& map, RngT& rng, Tile tile) const
  {
    auto tries = 0;
    auto maxTries = MAX_TILES_NUM;
 
    for ( ; tries != maxTries; ++tries)
    {
      // 隨機(jī)獲取一個(gè)非邊緣的點(diǎn)
      int x = GetRandomInt(rng, 1, m_nXSize - 2);
      int y = GetRandomInt(rng, 1, m_nYSize - 2);
 
      // 如果周?chē)鷽](méi)有地板并且沒(méi)有走廊（通路）的話(huà)，直接放棄
      if (!map.IsAdjacent(x, y, Tile::DirtFloor) && !map.IsAdjacent(x, y, Tile::Corridor))
        continue;
 
      // 周?chē)辉试S有門(mén)
      if (map.IsAdjacent(x, y, Tile::Door))
        continue;
 
      map.SetCell(x, y, tile);
 
      return true;
    }
 
    return false;
  }
 
  // 隨機(jī)生成地牢
  bool MakeDungeon(Map& map, RngT& rng) const
  {
    // step2 : 在正中間創(chuàng)建一個(gè)房間
    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 << "生成地牢已滿(mǎn)。（當(dāng)前房間和走廊個(gè)數(shù)為： " << features << "）." << std::endl;
        break;
      }
    }
 
    // 創(chuàng)建隨機(jī)入口點(diǎn)
    if (!MakeRandomStairs(map, rng, Tile::UpStairs))
      std::cout << "創(chuàng)建入口點(diǎn)失??！" << std::endl;
 
    // 創(chuàng)建隨機(jī)出口點(diǎn)
    if (!MakeRandomStairs(map, rng, Tile::DownStairs))
      std::cout << "創(chuàng)建出口點(diǎn)失??！" << std::endl;
 
    return true;
  }
};
 
 
#include <windows.h>
void ResetConsoleSize()
{
  HANDLE hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
  // 獲取標(biāo)準(zhǔn)輸出設(shè)備句柄
  CONSOLE_SCREEN_BUFFER_INFO bInfo;  // 窗口緩沖區(qū)信息
  GetConsoleScreenBufferInfo(hOut, &bInfo );
  COORD size = {1000, 800};
  SetConsoleScreenBufferSize(hOut,size); // 重新設(shè)置緩沖區(qū)大小
  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<< " _ 下劃線(xiàn)表示地板 " << std::endl;
  std::cout<< " # 表示墻壁 " << std::endl;
  std::cout<< " . 點(diǎn)表示走廊 " << std::endl;
  std::cout<< " + 表示門(mén) " << std::endl;
  std::cout<< "純黑表示啥都沒(méi)有，是障礙" << 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;
}