2D随机地图的生成

时间:2024-03-22 18:24:37

ps:记得当初大三上学期时候,曾经被问过一次,steam上一款地图如何生成,当时对这些东西不太了解,卒。这次一起补回来。。

以下很多实现均为猜测!!只是个人实现的方式

以几款游戏为例

1. steam一款策略类游戏

2.元气骑士

3.火炬之光2与暗黑破坏神2

 

1.Kingdoms and castles 

大体是一个随机的格子形地图,可以上面策略经营,并且有塔防元素。

2D随机地图的生成

细胞自动机生成地图

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 ) 表示 为了让图连通,我们需要将xy点打通一条路径

用自定义的规则来生成地图上的资源 

比如刚才地图上的树,矿,水域等

游戏里的水域可以用墙来表示,树的规则,我定义的是找到一块面积最大的墙拆掉作为树。

当然这个也可以规定一块(或多块)指定面积和的大小不小于X的墙,来作为资源区域

2.元气骑士(一款不氪不肝的良心游戏。这不算广告吧!!!

2D随机地图的生成

九宫格内生成随机连通的地图

随机生成七块地图,则这七块地图再九宫格内必定有连通的方式

连通方式很多:可以用广搜连边 ,或者刚刚的最小生成树连边

出生点与过关点的路径,必定是一个在地图上最长的路径,是一棵树的直径

 

地图上怪物的随机生成

先选择环境,然后因不同的环境会有不同怪物。

每次相同模块,怪物刷新点是固定的

因为怪物刷新会提示,很明显,也有可能是固定了多个mark,从中随机选择若干个)

 

3.暗黑破坏神2与火炬之光2

均是自己猜想,并不是官方的做法

先看一部分非地牢类的图: 比如

暗黑2第一章的血鸦营地,大教堂,过地图的小路 , 以及火炬之光2的地图

均会有很明显的拼接痕迹

2D随机地图的生成2D随机地图的生成一丶用资源来拼接大地图:

主要来源:https://blog.csdn.net/w6316485/article/details/76670286

思路:

将资源分别打入tag,进行分类,比如roomroad

由一点出发,经过若干规则进行拼接,来生成地图。

规则:

房间只能链接走廊

走廊连接房间或者连接处

连接处只能连走廊

2D随机地图的生成

其实上图的红色箭头就可以发现,上面引用的博客,并没有处理2d重叠问题(当然也可能我理解错了!)

拼接的方式:

1.Y轴作为基准,给每个方向定义一个Y值。

2.在旋转后,进行向量偏移。

(这个方式无论是2D还是3D地图,都可以。)2D随机地图的生成

2D随机地图的生成

实现方式:

初始化一个最初的节点。将这个节点的接入口压栈

随机从prefab中取出一个符合规则的模型进行之前的操作

将这个prefab模型的接入口压栈

进行若干此迭代

 

存在的问题: 

有重叠!!!因为随机无法控制 

若模型均为矩形引入矩阵交判断,若交则同时将栈内的这个接入口剔除,并且销毁这个prefab

若有多边形,拆成线段,判线段交。若相交同上。

线段交问题:百度一下吧很多资料! 我用的是快速排斥+跨立实验

2D随机地图的生成

地图上随机资源的生成

对于每个子模型,在上面加上mark,在地图生成后,从这些mark上随机生成一些物品

比如 棺材,罐子,可翻动的暗穴,或者是XXX神殿

 

暗黑3的生成方式:(来自百度)2D随机地图的生成

将地图中划分出若干方格:

大方格(达数个屏幕):体现史诗事件

中方格(整个屏幕):集群出现,来组成一个特定环境的地图

小方格:体现区域边缘

固定方格:刷新一些特殊事件

宝箱方格:随着地图固定

Ps:据说暴雪有蓝贴大体解释了地图生成的方式。

时间大概是20114月之前。。。官网做的搜索功能感人,我找不到了。。

二丶随机生成的地牢地图(之前的是地上的地图部分)

2D随机地图的生成

可以想到并实现的方式:

 

1.由刚刚的模型随机拼接,只要基础单元足够小,规律性就不会很明显

2.由基础的迷宫算法生成迷宫后,进行二次拼接

生成多个基础迷宫后,再将多个迷宫连接起来

 

个人觉得第一种,实现的就不错,效果感觉还好,因为定义了规则之后完全可以达到程序想要的效果

 

不过第二种也可以实现,就做了一下

递归迷宫实现2D随机地图的生成

思路:

1.每次随机取到一个中间点,用十字形将地图分为四块。 (参数left,right,top,bottom)来传入这次需要切割的区域

2.定义一个最小的面积,若这次需要切割的区域面积 小于 规定值,跳出

3.在这个点,上下左右中的三个方向的(距离不一定是1)的任意位置开一个洞保证连通

4.因为分了4个块,递归进入,重复1 2 3过程

 

demo在分享之后,想起来贴到git上吧