游戏设计制作时是否会用到类似 ACM 中的算法设计？
Abstract Keywords Acm Acm
Citation Yao Qing-sheng.游戏设计制作时是否会用到类似 ACM 中的算法设计？.FUTURE & CIVILIZATION Natural/Social Philosophy & Infomation Sciences,20240808. https://yaoqs.github.io/20240808/you-xi-she-ji-zhi-zuo-shi-shi-fou-hui-yong-dao-lei-si-acm-zhong-de-suan-fa-she-ji/
转载自 游戏设计制作时是否会用到类似 ACM 中的算法设计？ - 知乎用户 3ZGB97 的回答
最近在做游戏，想要自动生成随机的地图，找到了一篇文章：Polygonal Map Generation for Games 这里有文章的 Flash Demo Polygon Map Generation demo（下面的图片都是转自这篇文章，不知道合适吗。）
如何生成这样的地图呢？可能是 Perlin 噪音，确实能有类似的效果，但是你 Perlin 出来的只是一堆点，看似连续，实际上离散的点，你没办法生成出区块。河流也不可能简单地生成。如何生成地图中各种区块呢？我们需要生成无限个比较随机的多边形，并且铺满整个平面。这样的多边形就是 Voronoi diagram
生成这货的算法叫做 Fortune’s algorithm 。算法特别复杂 Voronoi Diagram—— 维诺图。这里有算法的动态演示：http://www.raymondhill.net/voronoi/rhill-voronoi.html （也有 JS 源代码 Javascript-Voronoi/rhill-voronoi-core.js at master · gorhill/Javascript-Voronoi · GitHub 1718 行）
这个算法我花了很长时间才搞懂，也需要不少前置知识。实际上我也搞不懂为了避免暴露所以不细说了…… 但这个回答主要是想要提到这个算法。因为这个算法需要几何知识，也需要图论知识，为了实现还需要一颗 AVL 树或者红黑树，并且有几个麻烦的边界条件，如果有选手比赛的时候码出来就太厉害了……
先生成随机的点，然后将随机的点稍微搞得均匀一点（Lloyd’s algorithm），就以点生成维诺图。
生成了以后，用 Perlin 函数（或者别的噪音函数）给每一个区块着色，大致的地形就出来了（还需要用一个简单的洪水填充区分海与湖。）
然后，河怎么做呢？看这些区块的交点处，随机挑选一些交点，然后按照 Perlin 函数生成的高度图用 A* 算法走出一个搜索路径，就是河了。A* 在游戏开发里面实在太常用了，如萌萌哒的岛娘所说，寻路和搜素多多少少都要用到。
文章中还讲了道路和降雨之类的。相比之下，房间的生成就简单多了。
algorithm - Procedural… house with rooms generator
最后推荐一下这个网站
里面有很多游戏里面的算法，并且呢有很多动态的实例。另外此网站的这个页面
Amit’s Game Programming Information 干货非常多，应该是这个问题的最佳答案。
比如说迷宫的十种生成算法：the { buckblogs :here }: Maze Generation: Algorithm Recap
Address:Department of Natural/Social Philosophy & Infomation Sciences, CHINA
Biography...
转载或引用本文时请遵守许可协议，注明出处、不得用于商业用途！
Like this article? Support the author with
