注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

永恒的遗失古都-亚特兰蒂斯

一个游戏开发者的个人博客。

 
 
 

日志

 
 

随机地牢迷宫算法_C++简版  

2014-09-02 23:38:00|  分类: 程序相关 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

原文链接:http://www.roguebasin.com/index.php?title=Dungeon-Building_Algorithm

某志改写了部分,代码使用了C++11特性。代码下面直接复制执行即可。注释已经很详细,不再啰嗦。

效果如下:

随机地牢迷宫算法_C++简版 - 自由骑士笃志 - 永恒的遗失古都-亚特兰蒂斯



// 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;

}



----------------------------------------------------

若百度看的不爽,可以到这里看   http://www.oschina.net/code/snippet_1159242_38504

  评论这张
 
阅读(37)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017