遊戲設計製作時是否會用到類似 ACM 中的演算法設計？

12-29

因為看見演算法設計題中經常會有以一個偏遊戲風格的故事然後設計一個演算法，這在真正遊戲製作中會不會經常用到呢？

最近在做遊戲，想要自動生成隨機的地圖，找到了一篇文章：Polygonal Map Generation for Games 這裡有文章的 Flash Demo Polygon Map Generation demo

（下面的圖片都是轉自這篇文章，不知道合適嗎。）

如何生成這樣的地圖呢？可能是 Perlin 噪音（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* 在遊戲開發裡面實在太常用了，如萌萌噠的島娘所說，尋路和搜素多多少少都要用到。Introduction to A*

文章中還講了道路和降雨之類的。

相比之下，房間的生成就簡單多了。

algorithm - Procedural... house with rooms generator

最後推薦一下這個網站 Red Blob Games 裡面有很多遊戲裡面的演算法，並且呢有很多動態的實例。

另外此網站的這個頁面 Amit』s Game Programming Information 乾貨非常多，應該是這個問題的最佳答案。

比如說迷宮的十種生成演算法：the { buckblogs :here }: Maze Generation: Algorithm Recap

都是搬運這個網站的內容，特別羞愧，但是我遊戲也才剛開始寫……沒有乾貨了……

主要是搜索和尋路。。。。

雖然可能和樓主問的不一樣，但是實際項目中真見過一個典型演算法問題：動態規劃-背包問題

卡牌遊戲，玩家同時帶最多5張卡，每張卡有一個cost和一個戰鬥力，卡組總cost不能超過玩家領導力上限。策劃要求實現一個「推薦隊伍」功能，推薦出總戰鬥力最高的隊伍（僅考慮基本戰鬥力之和）。

羅列下自己遇到過的

1.LRU

2.A*

3.Dijkstra

4.TopK

5.紅黑樹

6.B/B+樹

具體運行場景，待續。。

有個系列的書叫《遊戲編程精粹》，裡面講了遊戲開發領域各種演算法和工程實踐。感覺涉及到複雜演算法與數據結構的，主要是圖形學和計算幾何這一塊，比如碰撞檢測、路徑規劃、地形生成。

除了@徐釀泉@唐飛虎幾位回答的。

我補充一些其他思路：

最近在做社交系統，也在想可以不可以基於「多維空間中兩個向量夾角的餘弦公式」這類的推薦演算法，幫我篩選出一批相似的人；然後讓人與人之間交互更有效率這樣的演算法應用。

個人做遊戲的等級還太低，不過到目前為止用到的主要演算法就背包主要會用排序，地圖尋路會用到搜索，ai會用到行為樹，而其他方面就主要是數據匹配和查找了。

作為遊戲行業多年從業人員，負責的說，有，但是很少

太多了，尤其是RTS類

好想學寫AI啊orz