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的地图
•均会有很明显的拼接痕迹
一丶用资源来拼接大地图:
•主要来源:/w6316485/article/details/76670286
•思路:
•将资源分别打入tag,进行分类,比如room,road等
•由一点出发,经过若干规则进行拼接,来生成地图。
•规则:
•房间只能链接走廊
•走廊连接房间或者连接处
•连接处只能连走廊
其实上图的红色箭头就可以发现,上面引用的博客,并没有处理2d重叠问题(当然也可能我理解错了!)
•拼接的方式:
•1.以Y轴作为基准,给每个方向定义一个Y值。
•2.在旋转后,进行向量偏移。
(这个方式无论是2D还是3D地图,都可以。)
•实现方式:
•初始化一个最初的节点。将这个节点的接入口压栈
•随机从prefab中取出一个符合规则的模型进行之前的操作
•将这个prefab模型的接入口压栈
•进行若干此迭代
存在的问题:
•有重叠!!!因为随机无法控制
•若模型均为矩形引入矩阵交判断,若交则同时将栈内的这个接入口剔除,并且销毁这个prefab
•若有多边形,拆成线段,判线段交。若相交同上。
线段交问题:百度一下吧很多资料! 我用的是快速排斥+跨立实验
地图上随机资源的生成
•对于每个子模型,在上面加上mark,在地图生成后,从这些mark上随机生成一些物品
•比如 棺材,罐子,可翻动的暗穴,或者是XXX神殿
暗黑3的生成方式:(来自百度)
•将地图中划分出若干方格:
•大方格(达数个屏幕):体现史诗事件
•中方格(整个屏幕):集群出现,来组成一个特定环境的地图
•小方格:体现区域边缘
•固定方格:刷新一些特殊事件
•宝箱方格:随着地图固定
Ps:据说暴雪有蓝贴大体解释了地图生成的方式。
时间大概是4月之前。。。官网做的搜索功能感人,我找不到了。。
二丶随机生成的地牢地图(之前的是地上的地图部分)
可以想到并实现的方式:
•1.由刚刚的模型随机拼接,只要基础单元足够小,规律性就不会很明显
•2.由基础的迷宫算法生成迷宫后,进行二次拼接
•生成多个基础迷宫后,再将多个迷宫连接起来
个人觉得第一种,实现的就不错,效果感觉还好,因为定义了规则之后完全可以达到程序想要的效果
不过第二种也可以实现,就做了一下
递归迷宫实现
思路:
•1.每次随机取到一个中间点,用十字形将地图分为四块。 (参数left,right,top,bottom)来传入这次需要切割的区域
•2.定义一个最小的面积,若这次需要切割的区域面积 小于 规定值,跳出
•3.在这个点,上下左右中的三个方向的(距离不一定是1)的任意位置开一个洞保证连通
•4.因为分了4个块,递归进入,重复1 2 3过程
demo在分享之后,想起来贴到git上吧