Abstract

召喚于合成2是召合網(wǎng)絡(luò)的一款三消手游（至少對于本文及作者來說可以是）。由于其盤面較大，初始情況下的消除物種類較少，出現(xiàn)多消，即消除數(shù)量大于三的可能性很高。而在未指定落點(diǎn)的情況下，消除的落點(diǎn)又往往令玩家摸不著頭腦。因此在本文中作者提出了一種可能的，在無特殊效果的情況下，符合實(shí)驗(yàn)結(jié)果的一種解釋多消落點(diǎn)的模型。

Problem

1.1 在召喚與合成2中的消除過程

在徹底將問題抽象化之前，首先需要解釋的是在游戲中的消除流程。在游戲中，不考慮詞條，正負(fù)面效果，英雄主動和被動技能的話，可以把消除流程概括如下：

• 1. 玩家移動盤面

• 2. 判斷消除范圍

• 3. 合成需要消除的部分

• 4. 下落并重新填充因合成而產(chǎn)生的空位

• 5. 若仍有消除，回到2；否則回到1

其中，當(dāng)?shù)谝淮芜M(jìn)行2時(shí)，消除的落點(diǎn)必定是玩家進(jìn)行交換的格子，本文就不做解釋、驗(yàn)證和證明了。而在游戲中，盤體現(xiàn)為2維的方形棋盤，其中填充滿了數(shù)種可消除的棋子，或者是不可消除的負(fù)面格子，亦或者是不可消除、不反應(yīng)、不填充的null格用于修整盤的形狀。

接下來本文將簡略解釋2和3兩步，具體的實(shí)現(xiàn)在后文會有提及。第二步的消除范圍可以概括為：

1. 若同一方向上存在3個(gè)或以上的相同可消除物，則這一方向上的相同可消除物都在此消除范圍內(nèi)。此處的范圍指的是在方格盤中的八個(gè)方向。

2. 若兩個(gè)消除范圍共享至少一個(gè)格子，則這兩個(gè)消除范圍會被合并為同一個(gè)。

3. 同一盤面上可以同時(shí)存在多個(gè)不相交的消除范圍。

第三步就是消除與合成。在通常情況下，合成產(chǎn)物是被消除物同種且等階+1的可消除物。在游戲中體現(xiàn)為形態(tài)上升一級，額外形態(tài)為且被消除物的額外形態(tài)之和，同時(shí)盤面分?jǐn)?shù)（即形態(tài)中）增加被消除物的基礎(chǔ)分*（多消數(shù)量-2）。盤面分?jǐn)?shù)問題并非本文重點(diǎn)，以后有機(jī)會再行敘述。消除后，合成產(chǎn)物出現(xiàn)的格子就稱之為消除的落點(diǎn)，而除了落點(diǎn)之外的位置就變成空氣，待到后面被下落填充。

1.2 抽象化的多消落點(diǎn)問題

在闡述抽象化的問題之前，本文首先做出兩點(diǎn)假設(shè)。第一是多消落點(diǎn)是非隨機(jī)的，第二是多消落點(diǎn)是非枚舉的。做出這兩點(diǎn)假設(shè)是基于兩點(diǎn)觀測，其一是消除落點(diǎn)是可復(fù)現(xiàn)的，其二是消除范圍的形狀對于枚舉或查表來說過于復(fù)雜了。這兩點(diǎn)在實(shí)驗(yàn)中有所體現(xiàn)，但不會在本文進(jìn)行驗(yàn)證。

抽象化的消除落點(diǎn)問題可以這樣表述。在n*n的二維方格表中T，存在由若干方格組成的圖形集合g，假設(shè)由所有滿足條件的圖形g組成的集合G，存在一種映射f: G->T，使得G中的每個(gè)圖形都在T中對應(yīng)唯一的落點(diǎn)，求映射f。

其中，集合G中的元素g需要滿足如下條件：

1. 對g中的任意一點(diǎn)g，在四個(gè)方向上必須存在連續(xù)的至少三個(gè)格子（包括g本身）在g中。

2. g的尺寸必須大于等于3。

接下來，必須嚴(yán)謹(jǐn)?shù)亩x方向。對于n*n的二維方格表來說，其中的任意格子x具有坐標(biāo)(a,b)，而a, b都是范圍[0, n)之中的整數(shù)。與一般的習(xí)慣不同，本文根據(jù)召喚與合成中的代碼邏輯，將a定義為縱軸坐標(biāo)，b定義為橫軸坐標(biāo)，且(0, 0)在左下角。那么四個(gè)方向按定義及游戲內(nèi)的判定順序分別是：

1. 上下：形如(a + i, b)，i是整數(shù)且(a+i)在范圍[0, n)之中的格子，在x的上下方向上

2. 右左：形如(a, b + i)，i為整數(shù)且(b+i)在范圍[0, n)之中的格子。

3. 右上-左下：(a + i, b + i)

4. 左上-右下：(a + i, b - i)

值得注意的是，在游戲中的判定順序是按上面表述的順序進(jìn)行的，且同一方向中先判定i的正方向再判定i的負(fù)方向。另外，本文假設(shè)三消和多消的落點(diǎn)計(jì)算邏輯共通，因此多消落點(diǎn)與消除落點(diǎn)等價(jià)。

實(shí)驗(yàn)方法

作者提出了多種消除落點(diǎn)模型，在這一段僅闡述最終符合實(shí)驗(yàn)結(jié)果的一種。首先作者假設(shè)圖形g實(shí)際上是一個(gè)有序集合，集合內(nèi)的排序是在判定消除范圍的過程中進(jìn)入集合的順序。而落點(diǎn)將會是集合中序號序號的中點(diǎn)，即集合尺寸的一半(從0開始數(shù)且向下取整)。

實(shí)驗(yàn)數(shù)據(jù)可以根據(jù)游戲內(nèi)英雄試用的功能獲得。由于該模式的盤面只有5*5，實(shí)驗(yàn)數(shù)據(jù)的覆蓋面有限，但作者懶得管。

而決定進(jìn)入集合的順序的過程則稍顯復(fù)雜。根據(jù)不久前的消除解謎活動可知，填充空氣的順序是從下到上，從左往右。而起點(diǎn)在左下角且優(yōu)先從下往上。作者假設(shè)消除范圍的判定遵循同樣的邏輯。那么因此在圖形g的所有元素(a, b)中，擁有最小的b且a最小的格子永遠(yuǎn)是判定起點(diǎn)，其序號記為0。?接下來把起點(diǎn)位計(jì)入一個(gè)棧中。重復(fù)以下操作直到棧為空：從棧中取最后一位(stack pop)，按順序檢查四個(gè)方向是否有三個(gè)以上(兩個(gè)以上加上本身)連續(xù)的格子在g中，若存在，則把1到正方向末端推入棧中(stack push)，再把-1到負(fù)方向末端推入棧中。此處檢查和推入棧中的順序與前文定義方向時(shí)相同。

這個(gè)過程寫成偽代碼如下

• 取圖形左下角為0

• 把位置0加入棧中

• 若棧不為空則循環(huán)：

• 從棧中取出x

• 循環(huán)四個(gè)方向：

• 若此方向有三個(gè)以上連續(xù)的元素y_i在g中，則把正方向推入棧，再把負(fù)方向推入棧。若已標(biāo)號，則不重復(fù)入棧。

• 子循環(huán)結(jié)束

• 循環(huán)結(jié)束

• 按推入棧的順序標(biāo)記g中元素的序號，返回序號為|g|/2的元素。

實(shí)驗(yàn)結(jié)果

這里也放出大部分作為實(shí)驗(yàn)的結(jié)果，黃色格子和紅色格子代表消除范圍，而紅色格子是消除落點(diǎn)。雖然由于下落是沿縱軸的因此同一縱軸上的結(jié)果在游戲中等價(jià)，但是對于本問題而言并非如此。

這兩張圖沒有列出直線消除的情況，原因是過于簡單，按順序表過去就是了。

而根據(jù)上述模型編號后，可以看到紅色格子與序號中點(diǎn)重合。

經(jīng)過編號后可以看出，三消落點(diǎn)在編號1，四五消落點(diǎn)是編號2，六七落點(diǎn)是3，以此類推。顯而易見的實(shí)驗(yàn)得出的落點(diǎn)符合模型。

討論

4.1 可能的代碼實(shí)現(xiàn)

這里給出一種可能的偽代碼（雖然是py)。這段偽代碼包括了1.1節(jié)中提到的判斷消除范圍和消除落點(diǎn)的計(jì)算。whz不對此py代碼的可靠性和正確性做出保證，因?yàn)檫@是我隨手寫的，僅供參考。

4.2 邏輯的成因分析

其實(shí)簡單觀察就能發(fā)現(xiàn)，這個(gè)模型中的搜索過程既不是DFS也不是BFS。這是一種畸形的搜索過程。同時(shí)也不是一種高效的實(shí)現(xiàn)方法，因?yàn)樵谘h(huán)四個(gè)方向?qū)ふ蚁嗤锏倪^程中多次重復(fù)嘗試探索了幾個(gè)格子。將其搜索遍歷的過程換成樹形會更明顯

由于DFS與BFS分別對應(yīng)棧和隊(duì)列，其過程會相對簡潔和直觀。作者推測實(shí)現(xiàn)該過程的程序員對于如何在循環(huán)中遍歷四個(gè)方向有困難或是其他原因拒絕使用循環(huán)，因此用來BFS類似的過程來標(biāo)記需要探索的格子，這樣可以線性地寫出四個(gè)方向的檢測。同時(shí)可能為了節(jié)約內(nèi)存，此程序員希望使用DFS所類似的棧結(jié)構(gòu)盡快降低待探索格子的數(shù)量，因此做了一個(gè)結(jié)合。作者詢問了朋友且搜索了相關(guān)算法，沒有找到這樣搜索算法的名字，大概這也是一種創(chuàng)新吧。

4.3 相同過程的其他實(shí)現(xiàn)

前文提到，作者最開始提出了不止一種模型，在這一節(jié)中就簡單敘述一下。其中兩種分別對應(yīng)了深度優(yōu)先搜索DFS和寬度優(yōu)先搜索BFS，在此不再贅述。

另外一種算法是合并法，也是作者認(rèn)為效率更高的模型。即，對盤中格子進(jìn)行循環(huán)，若四個(gè)方向上至少有1個(gè)方向的正負(fù)一格和本格相同，則這是一個(gè)范圍。若新的范圍與之前存在的范圍重合，則合并兩個(gè)或多個(gè)。此時(shí)落點(diǎn)仍然可以是進(jìn)入范圍的順序（當(dāng)然這樣與實(shí)驗(yàn)結(jié)果不符）。這個(gè)方法下格子被調(diào)用的次數(shù)固定，每個(gè)格子不超過4次（自身四個(gè)方向）+8次（由周邊發(fā)起的探索）。同時(shí)具有實(shí)現(xiàn)簡潔和運(yùn)算簡單的優(yōu)勢其實(shí)也沒有好多少（沒什么別的意思whz只是覺得召合優(yōu)化太菜）。

運(yùn)算模型其實(shí)還包括重心模型，方向優(yōu)先模型之類的需要坐標(biāo)運(yùn)算的模型，很遺憾都被排除出去了。我就是很難理解為什么是這么個(gè)不論不類的算法。

結(jié)語

whz也是消除游戲的老玩家了，老版開心消消樂也有兩千多關(guān)通關(guān)加一千多關(guān)滿星，可惜這消消樂后來硬堆難度和無用的系統(tǒng)，削道具獲取就退了。偶然看到召合就下下來玩玩，有各種詞條的情況下變化也挺多，當(dāng)然本文并沒有進(jìn)行討論。因?yàn)橛蟹謹(jǐn)?shù)的存在后來也是萌生了想要暴力運(yùn)算最優(yōu)解的想法，為此消除落點(diǎn)問題就成了繞不過去的砍。由于沒有找到教程就自己解了個(gè)迷，很有趣啊，愚蠢的程序員。

Reference

什么寫這玩意還要寫引用。圖是我excel做的，實(shí)驗(yàn)是在游戲內(nèi)完成的。那張樹圖是百度(Google)找的BFS順序樹改的。感謝Aliujiji的答疑，以及不棄教程里的的那張3*3范圍內(nèi)的五消圖（雖然我沒有放到文中而且另外做了一張）。