PacMaze

Introduction
介绍

PacMaze is a game independently developed by WaterCoFire for the DIICSU DI32002 - Games Programming module assignment.
PacMaze 是 WaterCoFire 为 DIICSU DI32002 - Games Programming（游戏编程）课程作业独立开发的一款游戏。

In this game, you need to control Pacboy to eat all the dots in a complex maze while avoiding the hungry Ghostrons who are looking for you as their main course for their dinner party!
在这款游戏中，您需要操控 Pacboy 在错综复杂的迷宫中吃掉所有豆子，同时躲避那些饥肠辘辘的 Ghostron 们 —— 它们正寻找您，作为它们晚餐派对上的主菜！

Inspired by the Pac-Man game (Namco, 1980), while retaining many classic elements, PacMaze introduces a large number of original elements:
受《吃豆人》游戏（南梦宫，1980 年）启发，PacMaze 在保留了许多经典元素的同时，引入了大量原创元素：

• 3D Gaming
  3D 游戏

• Switching between TPV and FPV
  第三人称视角与第一人称视角之间切换

• Map Editor for customising your ideal map, from difficulty to wall layout
  用于自定义您的理想地图的地图编辑器，从地图难度设置到地图墙体布局设置

• Plenty of original props that grant various strategic abilities
  大量原创道具，赋予您各式各样的战略能力

• Random events that add fun and unpredictability (free to choose to enable or not!)
  随机事件，为游戏增添趣味与不可预测性（可自由选择是否启用！）

Map Overview
地图概览

This diagram introduces all the elements that appear in a typical PacMaze game map (11×11).
该图介绍了一个典型的 PacMaze 游戏地图 (11×11) 中出现的全部元素。

If you are a DIICSU Comp Sci student
如果您是 DIICSU 计算机专业的学生

This diagram is not a correct submission example of the “Game Map Sketch” section of Assignment 1 in the DI32002 - Games Programming module, as it does not illustrate all of the information required for that section. This diagram is only a portion of the original image that WaterCoFire took from the own submission.
此图并不是一个 DI32002 - Games Programming（游戏编程）课程中 Assignment 1 的“游戏地图草图”部分的正确提交示例，因为它没有阐明所有该部分要求的信息。此图仅是 WaterCoFire 从本人提交的原图中截取的一部分。

Game Screenshot (Examples)
游戏效果图（部分示例）

Home Page
主页

Map Select Page
选择地图页面

Gameplay (in TPV)
进行游戏（以第三人称视角）

Map Editor
地图编辑器

Algorithms & Techniques
算法与技术

PacMaze has some cool built-in algorithms and techniques, including:
PacMaze 内置了一些非常酷的算法和技术，这包括：

Finite State Machine (FSM) for Ghostrons
用于 Ghostron 的有限状态机（FSM）

FSM is used for Ghostron behaviours for it provides a clean and well-structured way to handle Ghostron’s states (Chase, Normal Wander, Scared Wander, Stall), each with its own logic and transitions.
有限状态机被应用于了 Ghostron 们的行为，因为它提供了一种干净且结构清晰的方式来处理 Ghostron 们的状态（追逐、正常游荡、惊慌时的游荡、停滞），每个状态都有其独特的逻辑和转换规则。

Unique Personalities & Behaviours for Different Types of Ghostron
不同类型的 Ghostron 的独特性格与行为特征

To enhance the playability of the game, inspiration is taken from the classic Pac-Man game (Namco, 1980): Different types of Ghostron are designed to have different personalities, i.e., different behaviours.
为了提升游戏的可玩性，PacMaze 从经典的《吃豆人》游戏（南梦宫，1980 年）中汲取灵感：不同类型的 Ghostron 被设计成具有不同的个性，即不同的行为模式。

For example, Blue Ghostrons are “introverted”, Yellow Ghostrons are “curious”, Green Ghostrons are “sensitive”.
例如，蓝色 Ghostron 是“内向”的，黄色 Ghostron 是“好奇”的，绿色 Ghostron 是“敏感”的。

Improved Distribution Algorithm and Braid Algorithm
改进版的分配算法与编织算法

As most classic maze generation algorithms can’t avoid generating dead ends, PacMaze took inspiration from the Distribution Algorithm and Braid Algorithm by Ioannidis (2016), which are capable of generating Braid Mazes. Braid Mazes refer to mazes with no dead ends (Hybesis - H.urna, 2019).
由于大多数经典迷宫生成算法无法避免生成死胡同，PacMaze 借鉴了 Ioannidis（2016 年）提出的分配算法和编织算法，这两种算法能够生成编织迷宫。编织迷宫指的是没有死胡同的迷宫（Hybesis - H.urna，2019 年）。

The Distribution Algorithm generates a distribution matrix determining the number of neighbours for each tile, and the Braid Algorithm generates the maze based on the distribution matrix.
分配算法生成一个分布矩阵，确定每个格子的邻居数量，而编织算法则根据分布矩阵生成迷宫。

In order to make the generated map more playable and suitable for PacMaze, many improvements are made based on the original scheme. Through the analysis, four patterns of a PacMaze map are summarised by WaterCoFire, and the Distribution Algorithm is optimised accordingly so that the neighbour distribution matrix it generates conforms to the law. The Braid Algorithm has also been optimised by WaterCoFire in that it no longer relies solely on random logic, but instead treats tiles differently based on their location as well as their number of neighbours distributed.
为了使生成的地图更具可玩性并适合 PacMaze，PacMaze 基于原始方案进行了多项改进。通过分析，WaterCoFire 总结了出 PacMaze 地图的四种特征，并相应优化了分配算法，使其生成的邻居分布矩阵符合总结出的规律。WaterCoFire 也对编织算法也进行了优化，使其不再单纯依赖随机逻辑，而是根据格子的所在位置及其被分配的邻居数量的不同进行差异化处理。

This improvement ensures that the final generated maps can have designed characteristics and provide better playability than random generation.
这一改进确保了最终生成的地图能够具备所设计的特征，并比随机生成提供更好的可玩性。

Click here to learn more about the details of the algorithm scheme improvement.
如您想了解关于这一算法方案改进的更多细节，请点击此处。

Modified Breadth First Search (BFS) for Map Legality Check
用于地图合法性检查的修改版广度优先搜索（BFS）

To ensure game experience, a valid PacMaze map must fulfil the following rules:
为了确保游戏体验，一个合法的 PacMaze 地图必须满足以下规则：

• Reachability. Each tile on the map must be reachable.
  可到达性。 地图上的每个格子都必须可到达。
• Ease of Reachability. The player’s path from the centre of the map to each tile must not be too long, and the shortest path length (from the centre) for all tiles should be less than or equal to 22 tiles.
  易到达性。 玩家从地图中心到每个格子的路径长度不应过长，且（从中心点出发）前往所有格子的最短路径长度均应小于或等于 22 个格子。
• No Dead Ends. That is, there should not be a tile with no walls on only one side. This does not mean that all tiles should have more than two walls, given the existence of boundaries.
  无死胡同。 即不应存在仅有一侧无墙的格子。这并不意味着所有格子都必须拥有超过两面墙，因为存在地图的边界。

BFS is used for legality checking as it is ideal for shortest path discovery and reachability analysis. As BFS does not directly identify dead ends, a small modification is made: the number of neighbours of each traversed tile will be checked. If it is one-neighbour, then it is considered a dead-end.
广度优先搜索在此处被用于合法性检查，因为它非常适合最短路径发现和可达性分析。由于广度优先搜索无法直接识别死胡同，因此对其进行了一项小修改：将检查每个遍历的格子的邻居数量。如果邻居数量为 1，则此格子被视为死胡同。

Mouse Position Detection & Highlight Interaction
鼠标位置检测与高亮互动

In order to provide a more intuitive experience in the Map Editor, in some edit modes, the current mouse position needs to be checked in order to achieve highlighting effect. This gives players real-time feedback. In the process, Unity’s Raycast system is used for detecting mouse ray collisions with game objects.
为了在地图编辑器中提供更为直观的操作体验，在某些编辑模式下，需要检测当前鼠标位置以实现高亮效果。这为玩家提供了实时反馈。在此过程中，Unity 的 Raycast 系统被用于检测鼠标射线与游戏对象的碰撞。

Secure Save/Read of Map Data
地图数据的安全保存/读取

All the map settings can be stored as a JSON file to ensure map data persistence. This allows players to preserve their custom maps and settings, and ensures that they can reload and edit/play their customised creations at any time.
所有地图设置均可存储为 JSON 文件以确保地图数据的持久性。这使玩家能够保存自定义地图和设置，并确保他们随时可以重新加载并编辑/游玩其自定义创作的地图。

To prevent malicious players from cheating by tampering with map data, an AES encryption algorithm with random Initialisation Vectors (IVs) is also used to encrypt/decrypt map data.
为防止恶意玩家通过篡改地图数据进行作弊，还采用了带有随机初始化向量（IV）的 AES 加密算法对地图数据进行加密/解密。

Accessing
访问

The PacMaze project (including source code) has been open-sourced on GitHub.
PacMaze 项目（含源代码）已在 GitHub 上开源。

For reference only. Please consciously refrain from all infringement of others’ IP rights as well as academic misconduct.
仅供参考。请您自觉杜绝一切侵犯他人知识产权以及学术不端的行为。

🔗 PacMaze on GitHub

References
引用

This reference list is in Harvard style.
本引用列表采用 Harvard 风格。

Hybesis - H.urna. (2019) Maze generations: Algorithms and Visualizations. Analytics Vidhya. Available at: https://medium.com/analytics-vidhya/maze-generations-algorithms-and-visualizations-9f5e88a3ae37 (Accessed: 4 May 2025).

Ioannidis P.L. (2016) Procedural Maze Generation. Bachelor Thesis. National and Kapodistrian University of Athens. Available at: https://pergamos.lib.uoa.gr/uoa/dl/object/1324569/file.pdf (Accessed: 6 May 2025).

Namco. (1980) Pac-Man [Video game]. Bandai Namco Entertainment, Arcade.

All third-party graphics/audio resources used in PacMaze (and their licences) can be found in the README in the GitHub repository of this project.
PacMaze 使用的所有第三方图像/音频资源（及它们的许可证）均可在本项目 GitHub 仓库的 README 文档中被找到。