Monster Farm 開發日誌 （六）基於MarkovChain的隨機名字生成器

光陰似箭，日月如梭，又到了我寫DevBlog的時辰了。由於周更平常又忙，zed上周就在掙扎不知道該寫啥，還羨慕我說我這周可以寫寫GDC的見聞，我就嗯了一聲。但實際上，作為一個有料的男人，我是不虛的，所以GDC見聞留給他，這次我要跟大家說我們怪物的隨機名字生成器。

由於我是個簡單的人，不擅長文化人的套路辭彙，自己看專業的專有名詞都會犯暈，所以在信息理論裡頭如果我用詞粗鄙了，請各位專業的哥哥姐姐們輕輕地噴。

那麼這個玩意兒原理很簡單，是這樣的，假如我訓練數據裡頭有四個名字"topdog"和"toto"，"toby"和"snoopy"，那麼通過統計就可以知道

to出現了3次，to後面一個字母有一次出現了p(topdog)，有一次出現了t(toto)有一次出現了b(toby)。

那麼假如我名字開頭隨機出來是to，並且隨機接的是p得到top,那麼我就可以查表找op後頭有可能接d或者y，假如接的是y，那就得到topy這個新的名字。

假如我名字開頭隨機出來是sn, 那就有可能出現sn->sno->snop->snopd->snopdo->snopdog這個新的名字。

剛剛說的是最基礎的markovchain的原理，他當然有很明顯的缺陷。剛剛我選擇每2個字母為一組做一個表，如果選擇每1個字母為一組做的表，那麼隨機出來的名字就會變得過度隨機，但是如果每3個字母隨機一次，那麼就會出現數據不足的問題，導致無法生成新的高質量的名字。

另外由於數據的限制，生成的數據缺少不確定性，比方to後面永遠不會接r。

另外如何判斷起點和終點如果不作判斷就會出現tototototo這樣的名字。

那麼解決這些個問題的方法是：

1.儲存3個字母2個字母1個字母生成的表，如果3個字母的表找不到對象，那就查找2個字母的表，不然就查找1個字母的表。

2.給每個樣本增加一定常量這樣to後面就會出現2次p，2次t，2次b，和各1次的acdefg...

3.起點和終點都加入等字母表數量的特殊的符號，比方兩個字母的表就可以是"&&topdog%%","**toto%%"

這樣我就把咱們的隨機名字生成的機制給講完了，是不是很簡單，很好理解？我記得我第一次看懂這原理的瞬間反應是。卧槽，人類真他媽的聰明，我要好好學習天天向上。

當然，雖然說了那麼多顯得我那麼屌，然而我卻並沒有實現它，因為我無情地在Github裡頭找到已經有大兄弟用C#實現了一遍的MarkovChain RandomNameGenerator，我就默默地把它下載了放進了工程里，嘻嘻。在此由衷地感謝一下Maurits Elbers以及Sam Twidale大大。

不知道大家會不會看到一個小學生式的開頭後就點了窗口的叉叉，看到語言匱乏的自己只能有卧槽和好好學習天天向上來表達自己的感情覺得很羞愧，如果我的日常用語和你們這些文化人的日常用語分別裝進訓練數據裡頭。我的樣本應該只會有「我操」，「操了」，「日了狗了」，結果生成的最多也就新生成一個「我操了狗了」。但你們的應該是祖國的大好河山，璀璨美麗的世界，啊，我操了狗了，編不下去了，我還是得多讀些書，能推薦些快速提升修養的書嗎？希望這篇又能承上啟下打個滿分，再次謝謝各位觀眾老爺們。

C# Implementation of MarkovChainNameGenerator

MagicMau/ProceduralNameGenerator

Original Haxe Implementation of MarkovChainNameGenerator

Tw1ddle/MarkovNameGenerator

MarkovChain Visual Explanation

Markov Chains

Names from a high order Markov Process and a simplified Katz back-off scheme

Names from a high order Markov Process and a simplified Katz back-off scheme

============================================================

如果您對Monster Farm的後續信息和更新感興趣，歡迎關注我們的微博：

或我們的專欄：紐大遊戲故事 知乎專欄

進入Hi-MoE遊戲組 | indienova 獨立遊戲 Hi_Moe小組，註冊後也可以討論或直接和我們互動。