【游戏技术群】959392658  【游戏出海群】12067810
yzc88亚洲城 手机端
  • 开发者工具开发者工具
  • www.yzc88.comManual
  • 蛮牛杯蛮牛杯
  • Unity官方专区Unity官方专区
开发者专栏

关注:2422

当前位置:yzc88亚洲城 技术专区 开发者专栏

__________________________________________________________________________________
开发者干货区版块规则:

  1、文章必须是图文形式。(至少2幅图)
      2、文章字数必须保持在1500字节以上。(编辑器右下角有字数检查)
      3、本版块只支持在yzc88亚洲城原创首发,不支持转载。
      4、本版块回复不得无意义,如:顶、呵呵、不错......【真的会扣分的哦】
      5、......
__________________________________________________________________________________
查看: 2907|回复: 50
发新帖

[士郎] 随机地图拼接方法

  [复制链接]  [移动端链接]
排名
1
昨日变化

7318

主题

7860

帖子

3万

积分

Rank: 16

UID
1231
好友
185
蛮牛币
8818
威望
30
注册时间
2013-7-29
在线时间
3742 小时
最后登录
2019-2-22

社区QQ达人活力之星原创精华达人突出贡献奖财富之证yzc88亚洲城QQ群会员蛮牛妹VIP

跳转到指定楼层
楼主
yzc88亚洲城 2019-1-24 20:57:14 | 只看该作者 |只看大图 回帖奖励 |倒序浏览 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?注册帐号

x
游戏设计者总是希望关卡具有可复玩性(replayable)。尤其是对一些刷刷刷的游戏,闭着眼睛不迷路的地图实在是很枯燥。
要让地图有新鲜感,又不引入新的制作成本,随机性是一个重要的手段。

随机性,至少包括两类用法。

一种是初始状态随机和过程选择随机,比如minecraft。Minecraft中的地形,包括湖泊、沙漠、森林,每个地图都由一个随机种子生成。相同的种子可以生成完全相同的地图,而不同的种子生成的地图则差异很大。(https://zhuanlan.zhihu.com/p/26789589, https://www.zhihu.com/question/20754279, https://www.reddit.com/r/gamedev/comments/16yyqw/how_does_minecraft_generate_structures_especially/



第二类是利用已有的素材做二次加工,使用的素材本身带有随机特性。自然界的云彩,水流,火焰,岩石等整体上很美观,却又不属于完全的随机。利用这些素材做二次加工可以做成很多细节丰富,整体上也不违和的效果。比如在已有数学形式上附加一个小扰动(如Perlin noise),是一种增加细节的有效方法。(http://gulu-dev.com/post/2014-11-16-open-world, https://blog.codingnow.com/2014/09/sandbox_world.html



前一种较容易将生成过程形成算法,在游戏运行过程中动态运行。拼接的效果由算法和预设的约束共同决定。后一种一般由地图设计者操作,地图设计者评价最终效果并决定是否合用。


下面总结了一些随机地图拼接的例子,总体上属于第一种使用随机的方法。



暗黑3
类似于拼图游戏(http://www.zhihu.com/question/35430956),暗黑3的地图由一系列预先制作好的图块拼成。





暗黑3地图的最小单位是tile,每个tile的属性包括大小、形状,以及其上的路点、事件类型等。给定一系列的基本tile(https://www.diablowiki.net/Randomization),以及tile之间的连接关系,地图可以在游戏过程中由tile动态拼接完成。拼接过程中,选择哪个tile,如何旋转摆放tile,都是随机的。最终生成的地图大小也是随机的。





随机不是随意。tile之间必须满足相应的拼接关系。拼接后的地图如果有很多的死胡同,过多或过少的成片区域,玩家的体验也会大打折扣。下一个案例中通过区分tile类型和约定tile的连接规则避免生成不符合预期效果的地图。


Daggerfall
Daggerfall的思路和暗黑3类似(https://gamedevelopment.tutsplus.com/tutorials/bake-your-own-3d-dungeons-with-procedural-recipes--gamedev-14360),组成地图的基本单位也是tile。

在Daggerfall中tile分为三类:
房间:有一个或多个出口
走廊:一个很窄很长的区域,有两个出口,可能是一个斜坡
连接处:有三个以上出口的小的空间





房间一般用于boss战斗区域,对应于地图上较大的区域。走廊占用的区域较小,承载简单的剧情和战斗。连接处则用于组装和连通。Daggerfall中,房间只能连接走廊,连接处只能连接走廊,走廊可以连接房间或连接处。而且tile之间不能互相穿插,这一点可以用BBox判定。
生成算法:

1)选择有最多出口数的tile作为初始拼图
2)对每个未连接的出口生成一个符合条件的模块
3)重新建立一个目前未连接的出口的列表,重复第二步

另外,地图要素(比如可打碎的罐子,墙上忽明忽暗的火炬等)是附着在tile上的。在组件的地面或墙面上标记一些mark点,每个mark点上随机生成一些匹配的要素。在暗黑3中,地图要素还包括事件等逻辑要素。


POE
POE的玩法类似暗黑3,但是地图拼接方法则有不同(https://www.youtube.com/watch?v=GcM9Ynfzll0https://gamedev.stackexchange.com/questions/148418/procedurally-generating-dungeons-using-predefined-rooms)。
首先,在一个给定大小的地图上选择两个房间,一个是Start,一个是End。
然后将整个地图切分成一系列的房间(房间的大小也是预设的)。
给每一个房间随机分配一个权重(用颜色表示)
利用每个房间的权重,找到从Start到End的一条最短路径
在这条最短路径上,将相邻的房间打通,这样就形成了从Start到End的唯一一条可通行路径。
最后,再增加一些路径分支。
Rogue

http://www.roguebasin.com/index.php?title=Basic_BSP_Dungeon_generation
Rogue算是随机地图生成的鼻祖了,使用的算法也很简单。

Rogue中生成的地图是固定大小的。给定一个地图大小,不断的切分每个区域,直到每个区域的大小和预设的房间大小差不多大为止。切分时有两个参数需要选择,一个是切分方向,可以是水平切分或竖直切分,另一个是切分位置。这两个参数都是通过随机确定的(当然,为了使最终的结果反映设计者的偏好,可以使用normal分布等方式函数做随机。)


切分完成后,我们得到了一系列的房间。这些房间在逻辑上都挂在一颗BSP树的叶子节点。接下来,按BSP树的层次将各房间连通。每个房间和自己的兄弟房间建立连接关系。每个中间节点和自己的兄弟节点建立连接关系。最终所有的房间都能直连或通过其他房间间接连通。





TinyKeep
TinyKeep提供了一种全新的地图生成方法(http://tinykeep.com/dungen/https://github.com/SSYGEN/blog/issues/7http://blog.tinykeep.com/2013/09/just-sneaky-quick-update-from-us-today.htmlhttps://www.reddit.com/r/gamedev/comments/1dlwc4/procedural_dungeon_generation_algorithm_explained/),步骤如下:
1)首先设置地图cell大小,比如设置成150. 虽然可用设置成任意值,但是值越大,地图就越复杂
2)对每个cell,生成一个矩形。矩形的长和宽是在一个长度范围内随机的。虽然随机范围并不是关键,但是通常情况下应该设置成和cell数目成正比例关系。

需要注意的是,我这里使用的不是uniformly distributed random number算法,而是使用了Park-Miller Normal Distribution。该算法生成的随机数偏好小的整数,最终结果是边长小的矩形占了大多数。


除此之外,还保证矩形的长和宽比例在一定范围内。我们既不希望看到方形的房间,但是也不希望看到非常瘦的房间。
3)到此为止,我们在一个小的区域中生成了150个随机边长的矩形,大部分都是和其他矩形重叠的。下面我们将用一个算法调整矩形位置,让所有的矩形都不和其他矩形重叠,但与此同时,保持矩形之间尽量紧挨着。

4)然后,把所有的空白处添上1x1的cell。结果是一个由不同大小的矩形填成的网格,每个矩形都不和其他矩形重叠,而矩形之间也没有空白
5)接下来,我们判定哪些cell应该属于房间。方法很简单,每个cell,如果其长和宽超过一个阈值都被认为属于一个房间。由于我们生成随机数时大部分都是很小的矩形,所以我们生成的矩形只有很小一部分属于房间。

6)接下来,我们要把各房间连接起来。先用Delaunay Triangulation算法将每个房间的中心点构造出一个graph。现在所有的房间都连起来了,而且连线不会互相交叉

7)然后用最小生成树算法删去其他的边。这保证了所有的房间都连起来,所以是可达的

8)最小生成树算法看起来不错,但是生成的地图没有环,还是有点单调。这是另一个极端。所以我们额外在最小生成树上加一些边(比如在Delaunay Triangulation中选15%的边)。最终结果是一个由所有房间组成的图,每个房间都可达,且有一些环,不至于太单调。

9)然后,我们把每一个边转换成一个L形的折线,每个cell只要和这个折线有交点都会被保留为一个corridor tile。由于cell的大小不固定,生成的corridor的边缘是扭曲而不均匀的,这正是一个dungeon所需要的。






知乎@realTOM







点评

随机地图拼接方法  yzc88亚洲城 2019-1-25 01:37

跟我念“站长妹纸萌萌哒!”我说站长,你说YO!爱你们么么哒~
7日久生情
2109/5000
排名
1508
昨日变化
5

0

主题

670

帖子

2109

积分

Rank: 7Rank: 7Rank: 7Rank: 7

UID
135463
好友
0
蛮牛币
272
威望
0
注册时间
2016-1-23
在线时间
599 小时
最后登录
2019-2-23
沙发
yzc88亚洲城 2019-1-24 21:17:05 | 只看该作者
随机地图拼接方法
[发帖际遇]: 一个袋子砸在了 wasdml123 头上,wasdml123 赚了 1 蛮牛币. 幸运榜 / 衰神榜

6蛮牛粉丝
1421/1500
排名
4444
昨日变化
35

0

主题

844

帖子

1421

积分

Rank: 6Rank: 6Rank: 6

UID
254705
好友
1
蛮牛币
1379
威望
0
注册时间
2017-11-16
在线时间
247 小时
最后登录
2019-2-22
板凳
yzc88亚洲城 2019-1-25 08:16:50 | 只看该作者
6666666666666666666666666666666666

5熟悉之中
926/1000
排名
3440
昨日变化
3

0

主题

271

帖子

926

积分

Rank: 5Rank: 5

UID
181447
好友
0
蛮牛币
1073
威望
0
注册时间
2016-11-6
在线时间
227 小时
最后登录
2019-2-16
地板
yzc88亚洲城 2019-1-25 08:23:22 | 只看该作者
随机地图拼接方法 [修改]

5熟悉之中
883/1000
排名
2333
昨日变化
7

0

主题

150

帖子

883

积分

Rank: 5Rank: 5

UID
26073
好友
0
蛮牛币
3466
威望
0
注册时间
2014-5-21
在线时间
129 小时
最后登录
2019-2-22
5#
yzc88亚洲城 2019-1-25 08:39:27 | 只看该作者
牛逼牛逼!在线佩服

2初来乍到
115/150
排名
13600
昨日变化
264

0

主题

23

帖子

115

积分

Rank: 2Rank: 2

UID
308426
好友
0
蛮牛币
262
威望
0
注册时间
2018-12-16
在线时间
24 小时
最后登录
2019-2-23
6#
yzc88亚洲城 2019-1-25 09:03:26 | 只看该作者
aaaaaaaaaaaaaaaaaaaaa

5熟悉之中
866/1000
排名
16821
昨日变化
8

0

主题

574

帖子

866

积分

Rank: 5Rank: 5

UID
199204
好友
1
蛮牛币
409
威望
0
注册时间
2017-1-5
在线时间
252 小时
最后登录
2019-2-21
7#
yzc88亚洲城 2019-1-25 09:11:25 | 只看该作者
谢谢分享

7日久生情
1919/5000
排名
2824
昨日变化
8

2

主题

993

帖子

1919

积分

Rank: 7Rank: 7Rank: 7Rank: 7

UID
209046
好友
0
蛮牛币
2654
威望
0
注册时间
2017-3-30
在线时间
410 小时
最后登录
2019-2-22
8#
yzc88亚洲城 2019-1-25 09:30:50 | 只看该作者
随机地图拼接方法

5熟悉之中
912/1000
排名
6283
昨日变化
49

0

主题

575

帖子

912

积分

Rank: 5Rank: 5

UID
300432
好友
1
蛮牛币
1282
威望
0
注册时间
2018-10-18
在线时间
113 小时
最后登录
2019-2-23
9#
yzc88亚洲城 2019-1-25 09:34:32 | 只看该作者
厉害,大佬NB

5熟悉之中
582/1000
排名
4684
昨日变化
22

0

主题

65

帖子

582

积分

Rank: 5Rank: 5

UID
256911
好友
1
蛮牛币
6648
威望
0
注册时间
2017-11-29
在线时间
207 小时
最后登录
2019-2-22

迈向小康

10#
yzc88亚洲城 2019-1-25 09:41:33 | 只看该作者
可以的,66666

排名
39555
昨日变化
27

0

主题

10

帖子

29

积分

Rank: 1

UID
153843
好友
0
蛮牛币
35
威望
0
注册时间
2016-6-27
在线时间
14 小时
最后登录
2019-1-29
11#
yzc88亚洲城 2019-1-25 09:41:47 | 只看该作者
不错,很好,哈哈

6蛮牛粉丝
1496/1500
排名
1698
昨日变化
1

9

主题

184

帖子

1496

积分

Rank: 6Rank: 6Rank: 6

UID
119532
好友
1
蛮牛币
1064
威望
0
注册时间
2015-8-24
在线时间
537 小时
最后登录
2019-2-22
QQ
12#
yzc88亚洲城 2019-1-25 09:42:57 | 只看该作者
求源码楼主发出来吧或者制作成插件
[发帖际遇]: 一个袋子砸在了 李明宇01 头上,李明宇01 赚了 1 蛮牛币. 幸运榜 / 衰神榜

7日久生情
2739/5000
排名
668
昨日变化

6

主题

478

帖子

2739

积分

Rank: 7Rank: 7Rank: 7Rank: 7

UID
46577
好友
1
蛮牛币
3158
威望
0
注册时间
2014-9-24
在线时间
949 小时
最后登录
2019-2-19
13#
yzc88亚洲城 2019-1-25 11:38:30 | 只看该作者
干货很实用,感谢分享!

7日久生情
1681/5000
排名
2133
昨日变化
5

1

主题

81

帖子

1681

积分

Rank: 7Rank: 7Rank: 7Rank: 7

UID
219633
好友
0
蛮牛币
1585
威望
0
注册时间
2017-4-27
在线时间
951 小时
最后登录
2019-2-23
14#
yzc88亚洲城 2019-1-25 11:51:44 | 只看该作者
厉害,大佬NB

4四处流浪
317/500
排名
7871
昨日变化
2

0

主题

37

帖子

317

积分

Rank: 4

UID
248481
好友
0
蛮牛币
57
威望
0
注册时间
2017-10-12
在线时间
118 小时
最后登录
2019-2-23
15#
yzc88亚洲城 2019-1-25 13:35:25 | 只看该作者
谢谢分享!

您需要登录后才可以回帖 登录 | 注册帐号

本版积分规则

快速回复 返回顶部 返回列表