ps：记得当初大三上学期时候，曾经被问过一次，steam上一款地图如何生成，当时对这些东西不太了解，卒。这次一起补回来。。
以下很多实现均为猜测！！只是个人实现的方式
以几款游戏为例
•1. steam一款策略类游戏
•2.元气骑士
•3.火炬之光2与暗黑破坏神2
1.Kingdoms and castles
大体是一个随机的格子形地图，可以上面策略经营，并且有塔防元素。
细胞自动机生成地图：
•1.确定一个种子
•2.用一定比例的墙来填充整个地图
•3.用规则来刷新地图
•4.确保连通性（并重复若干次3操作）
5.用规则来模拟地图上资源的刷新位置
规则的选择
•1确定墙的比例：
•建议40~45%的用随机数来填充原地图
•2.刷新地图的规则：
•若想让地图块出现的比较规律，且块数较大，规则可以定义如下：
• 枚举每个地图点的位置,
• 若原来是墙：周围的8个方向其中墙的个数少于4，则变为路
• 若原来是路，周围墙的个数大于4，则变为墙。
•若想让地图块出现的较为分散，规则可定义如下：
•在上面的基础上，再加一层规律：
•若原来是路，周围8格内墙的个数大于5，或者，周围16格子内墙的数量小于2，则变为墙
确保是个连通图
•1.将所有地图块设置为未标记
•2.从每个路点开始作为深搜的起点，每次有未标记过的点则孤立的子图+1
•（保存x,y坐标为以后使用）
•标记当前点已走
•若上下左右四个方向其中有路，则将这个新的点作为深搜起点，函数压栈
•3.若子图个数大于2，则表示图不连通。
•将刚刚的x,y坐标取出，跑一次prim最小生成树(在跑的时候，需要记录下是从哪一个点松弛的，方便接下来连通)
•4.将拿跑prim之后得到的数组，在图上进行打通。这样将会得到一个连通图
ps：既然我ppt上写了，就直接打个prim的广告吧。
Prim算法
•1.取一个点作为起点A，，初始化所有点dis(A,i)的距离 = abs(Xa-Xi ) + abs(Ya-Yi)
•将dis[i]加入集合U
•2.进行子图个数-1次循环，得到需要连通的点的方式
•循环的内部步骤：
•从已有集合U中，取出最小的，且未走过的点index
•用这个index点来松弛所有的点.若可以松弛标记 father[可松弛的点] = index，并加入返回的数组中
•3.这样结束之后会得到一组ans二位数组 . Vector( x, y ) 表示 为了让图连通，我们需要将x到y点打通一条路径
用自定义的规则来生成地图上的资源
•比如刚才地图上的树，矿，水域等
•游戏里的水域可以用墙来表示，树的规则，我定义的是找到一块面积最大的墙拆掉作为树。
•当然这个也可以规定一块（或多块）指定面积和的大小不小于X的墙，来作为资源区域
2.元气骑士（一款不氪不肝的良心游戏。这不算广告吧！！！）
九宫格内生成随机连通的地图:
•随机生成七块地图，则这七块地图再九宫格内必定有连通的方式
•连通方式很多：可以用广搜连边 ，或者刚刚的最小生成树连边
•出生点与过关点的路径，必定是一个在地图上最长的路径，是一棵树的直径
地图上怪物的随机生成
•先选择环境，然后因不同的环境会有不同怪物。
•每次相同模块，怪物刷新点是固定的。
•（因为怪物刷新会提示，很明显，也有可能是固定了多个mark，从中随机选择若干个）
3.暗黑破坏神2与火炬之光2
均是自己猜想，并不是官方的做法
•先看一部分非地牢类的图： 比如
•暗黑2第一章的血鸦营地，大教堂，过地图的小路 ， 以及火炬之光2的地图
•均会有很明显的拼接痕迹
一丶用资源来拼接大地图：
•主要来源：https://blog.csdn.net/w6316485/article/details/76670286
•思路：
•将资源分别打入tag,进行分类，比如room，road等
•由一点出发，经过若干规则进行拼接,来生成地图。
•规则：
•房间只能链接走廊
•走廊连接房间或者连接处
•连接处只能连走廊
其实上图的红色箭头就可以发现，上面引用的博客，并没有处理2d重叠问题（当然也可能我理解错了！）
•拼接的方式：
•1.以Y轴作为基准，给每个方向定义一个Y值。
•2.在旋转后，进行向量偏移。
（这个方式无论是2D还是3D地图，都可以。）
•实现方式：
•初始化一个最初的节点。将这个节点的接入口压栈
•随机从prefab中取出一个符合规则的模型进行之前的操作
•将这个prefab模型的接入口压栈
•进行若干此迭代
存在的问题：
•有重叠！！！因为随机无法控制
•若模型均为矩形引入矩阵交判断，若交则同时将栈内的这个接入口剔除，并且销毁这个prefab
•若有多边形，拆成线段，判线段交。若相交同上。
线段交问题：百度一下吧很多资料！ 我用的是快速排斥+跨立实验
地图上随机资源的生成
•对于每个子模型，在上面加上mark，在地图生成后，从这些mark上随机生成一些物品
•比如 棺材，罐子，可翻动的暗穴，或者是XXX神殿
暗黑3的生成方式：（来自百度）
•将地图中划分出若干方格：
•大方格（达数个屏幕）：体现史诗事件
•中方格（整个屏幕）：集群出现，来组成一个特定环境的地图
•小方格：体现区域边缘
•固定方格:刷新一些特殊事件
•宝箱方格：随着地图固定
Ps：据说暴雪有蓝贴大体解释了地图生成的方式。
时间大概是2011年4月之前。。。官网做的搜索功能感人，我找不到了。。
二丶随机生成的地牢地图（之前的是地上的地图部分）
可以想到并实现的方式：
•1.由刚刚的模型随机拼接，只要基础单元足够小，规律性就不会很明显
•2.由基础的迷宫算法生成迷宫后，进行二次拼接
•生成多个基础迷宫后，再将多个迷宫连接起来
个人觉得第一种，实现的就不错，效果感觉还好，因为定义了规则之后完全可以达到程序想要的效果
不过第二种也可以实现，就做了一下
递归迷宫实现
思路：
•1.每次随机取到一个中间点，用十字形将地图分为四块。 （参数left,right,top,bottom）来传入这次需要切割的区域
•2.定义一个最小的面积，若这次需要切割的区域面积 小于 规定值，跳出
•3.在这个点，上下左右中的三个方向的（距离不一定是1）的任意位置开一个洞保证连通
•4.因为分了4个块，递归进入，重复1 2 3过程
demo在分享之后，想起来贴到git上吧