Roguelike 开发小组

创建于:2016-04-16

创建人: eastecho

60 信息 990 成员
Roguelike 开发的相关讨论
imymirror@Roguelike 开发小组 的内容(查看所有内容
迷宫的生成: DFS与BFS算法的实现
imymirror 2020-06-09

前言

我的迷宫代码的实现受到 liuyubobo 的影响.

liuyubobobo 迷宫的实现: GUI部分使用 java Swing, 编程语言是 Java.
我的迷宫代码实现: GUI部分使用 Cocos Creator 游戏引擎, 编程语言是 TypeScript.

Github源码地址 : https://github.com/zhigang26/maze-generalization 
如果感觉不错, 可以点击 star.

运行动画

非递推实现的随机地图生成过程演示:

Image title


非递推实现的随机地图生成寻路过程演示:

Image title


开发环境

  • 操作系统: Macos
  • 游戏引擎: Cocos Creator 2.3.4
  • 编程语言: TypeScript

迷宫定义

实现的迷宫是什么样子呢?

迷宫的定义如下:

  • 只有一个入口, 只有一个出口
  • 只有一个解
  • 路径是连续的
  • 绘制在一个方形的画布上: 不是其它图形, 圆形等
  • 墙和路径都占一个单元格

约定入口和出口: 入口在第2行第1列, 出口在最后一列的倒数第2行

Image title

算法与数据结构

迷宫的生成和寻路使用的算法:

  • BFS(Breadth-first search - Wikipedia) : 广度优先遍历
  • DFS(Depth-first search - Wikipedia): 深度优先遍历

涉及的数据结构的实现:
在 Script/algorithm 文件夹下:

  • List : 线性表, 队列和栈的一个接口定义
  • Queue : 队列, 广度优先遍历非递归实现需要用到
  • Stack : 栈, 深度优先遍历非递归实现需要用到
  • RandomQueue : 随机队列, 使生成的地图更加随机, 不过仍然有点像BFS
  • RandomQueue2 : 随机队列,RandomQueue的改进版, 地图更加随机了

代码的演示

代码的演示包含两个部分:

  1. 地图已经生成的情况下, 从入口开始寻路找到出口
  2. 如何生成地图, 在有迷雾的情况下动态演示地图生成过程.

共有 10 个演示, 可以在编辑器中通过 visualType 属性进行选择:

Image title


支持地图规模修改以及地图格子大小的修改:

Image title


Image title


(转发自:原日志地址

加入 indienova

  • 建立个人/工作室档案
  • 建立开发中的游戏档案
  • 关注个人/工作室动态
  • 寻找合作伙伴共同开发
  • 寻求线上发行
  • 更多服务……
登录/注册