GameRes游资网

 找回密码
 立即注册
返回列表
查看: 2475|回复: 1

游戏常用算法:四种迷宫生成算法

[复制链接]
发表于 2018-11-23 16:35:22 | 显示全部楼层 |阅读模式
游戏程序
平台类型:  
程序设计:  
编程语言:  
引擎/SDK:  
文/寂灭万乘

简介

所谓迷宫生成算法,就是用以生成随机的迷宫的算法

迷宫生成算法是处于这样一个场景:

一个row行,col列的网格地图,一开始默认所有网格四周的墙是封闭的

要求在网格地图边缘,也就是网格的边上打通2面墙

所有网格都至少保证网格周围至少有一堵墙打通

所有网格都能通过打通的墙能形成一条通路

博主已实现RecursiveBacktracking(递归回溯),RecursiveSegmentation(递归分割),随机Prim算法,Kruskal+并查集四种迷宫生成算法,这篇文章主要对这四种算法进行简要的介绍

基于Unity的迷宫生成算法代码实现

1.gif

Github链接

递归回溯算法

复杂度

空间:O(n),时间:O(n),n为迷宫节点数row*col

原理

以一个栈作为辅助的数据结构,用以记录打通区域的顺序,用以回溯

一开始随机在地图中选择一个区域,加入栈。

之后在之前选择的区域周围随机选择一个未打通的区域,将新选择的区域和之前选择区域的墙打通,并把新的区域的加入栈

如果四周的区域都打通,就让栈出栈,将当期所选择的区域设置栈新的栈顶,表示回退到上一个区域

之后递归的按之前的步骤选择下一个区域直到所有区域都被打通


缺点

2.png

这种算法实现思路极为简单,但通路过于明显,甚至有可能会出现上图中的迷宫,很尴!!!

递归分割算法

复杂度

递归空间复杂度:O(row*col),最好时间复杂度:O(lgrow+lgcol),最坏时间复杂度O(row*col)

原理

将矩形地图用十字分成四个小矩阵

在四个小矩形相邻的四个面上各随机打通一面墙,使通路导通。

然后对所有小矩形重复之前分割操作

如果矩阵已经无法分割了,也就是行数或列数为一时,就将矩阵内部的墙全部打通

优缺点

生成的迷宫有明显的矩形成分,不自然,适合简单如FPS,ACT等游戏

3.png

随机Prim算法

复杂度

空间:O(row*col),时间:O(墙数=(row-1)*col+row*(col-1))

原理

随机选择一个区域作为当前区域

将区域四周未打通的墙加入列表中

while(列表不为空)

随机从列表选择一面墙

如果墙两边区域存在一区域未被打通,就打通这面墙,并将这面墙两边区域附近未打通的墙加入列表

从列表中移除这面墙

优缺点

自然的迷宫,很难走,适合真正的迷宫游戏

4.png

Kruskal+并查集

5.png

复杂度

空间:O(row*col),时间:O(墙数=(row-1)*col+row*(col-1))

原理

这个算法巧妙的使用了并查集,运用并查集判断整个迷宫的导通问题

  1. 把所有墙加入墙列表中

  2. while(墙列表不为空)

  3.   随机从墙列表选择一堵墙,用并查集判断墙两边区域是否导通
  4.   ​
  5.       不导通就打通这堵墙
  6.   ​
  7.   从墙列表中移除这堵墙
复制代码

博客地址:https://www.cnblogs.com/millionsmultiplication/p/9568766.html


您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|稿件投递|广告合作|关于本站|GameRes游资网 ( 闽ICP备05005107-1 )

GMT+8, 2018-12-15 03:56

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