概說棧在遊戲的應用(上)
棧(Stack)是一種後進先出(LIFO)的數據結構。升降機的比喻最為直白，亦最難忘，但持著升降機概念的人卻往往不能把棧用得好 — 我說的就是我。
不得不說，棧的印象很容易受限於算法。經典例子是深度優先樹探索(DFS)。
| function dfs(value, tree) { | |
| queue = [] | |
| queue.push(tree) | |
| while (queue.length > 0) { | |
| node = queue.pop() | |
| if (node.value === value) | |
| return node | |
| for (const child of node.children) | |
| queue.push(child) | |
| } | |
| return null | |
| } |
by 開首就將根節點壓棧，然後 “出棧、比較、將子節點壓棧”這個操作一直重覆下去。
升降機的比喻在此行不通。當然，可以說成: “升降機從頂樓接載一個人出發，下降一層後，一個人出去了，幾個人進來了。升降機再下一屠，剛才進來的幾個人當中最接近門口的一個人出去了，這次沒有人進來…”。升降機的比喻缺少了最重要的部分，就是任務。
棧比較少用，隊列(queue)卻經常地用到。隊列就是一道生產線，每當從生產線拿出，就會進行加工消化掉。同樣，出棧後會進行某種任務(task)。深度優先之所以需要用棧正是因為進行任務的過程中會產生子任務(sub-task)，而子任務比現有任務更為優先。 廣度優先(BFS)亦會產生子任務，不過搜索現在所在層數更重要，於是使用的是隊列。不難看出，使用棧的關鍵在於”單一任務的完成取決於子任務的完成”。
把握優先子任務的概念後，是時候把棧的應用到遊戲中。
- 回合制卡牌遊戲
另外cards棄牌區本身是一個stack，玩家的行動受最頂的牌影響。當可以出牌，就把牌置於棄牌區頂部。沒法出牌時，視乎是不是被罰牌，要一直找到罰完為止，此處使用了另一個棧，負責做罰牌，罰完就把牌放回去，類近於很經典的雙棧動作還原應用。
每次從牌頂拿一張牌到手上，再檢查手上的牌是不是Draw Two。如果是DrawTwo就摸2張牌，一直直到手上的牌不再是Draw Two，此時把DrawTwo逐張放回去。
不論是隊列還是棧，這兩個數據結構和其他數據結構最大的不同之處是它們不是儲存和尋找的工具，是以內容物到程序跑完會完全出來為前提。不論是壓入棧頂的東西，還是被壓在下面的沉積物，基本上最後都會跑出來。(在雙棧動作還原中，按一下還原後做別的動作，會直接扔掉儲存了被還原動作的整個棧)
玩家出牌代碼如下:
| class Player { | |
| performRound(cards) { | |
| // 假定這些人工智障總是使出第一張能使出的牌 | |
| const lastCard = this.deck.peek() | |
| foreach(const card of this.deck) { | |
| switch (lastCard.type) { | |
| case 'number': | |
| // 牌頂數字 可打同色數字/同數字異色/同色功能牌/萬能卡 | |
| if (card.color == lastCard.color || card.number == lastCard.number || card.type == 'wild') { | |
| this.deck.push(card) | |
| return | |
| } | |
| break | |
| case 'effect': | |
| // 牌頂功能牌 可打任意色同類功能牌/萬能卡 | |
| if (card.effect == lastCard.effect || card.type == 'wild') { | |
| this.deck.push(card) | |
| return | |
| } | |
| break | |
| case 'wild': | |
| // 牌頂萬能牌(轉色) | |
| // 這裡不管了 發現沒有指定打哪種色的變數 | |
| break | |
| } | |
| } | |
| // 處理無法出牌 | |
| if (card.effect == 'DrawTwo') { | |
| // 這裡把棄牌抽起, 抽到下面一直沒有draw two為止 | |
| const pile = [] | |
| pile.push(this.deck.pop()) | |
| while (pile.peek().effect == 'DrawTwo') { | |
| drawCards(2) | |
| pile.push(this.deck.pop()) | |
| } | |
| // 最後還原棄牌區 | |
| while (pile.length) { | |
| this.deck.push(pile.pop()) | |
| } | |
| } | |
| else if (card.effect == 'DrawFour') { | |
| // 同理 總之Draw Four不能跟Draw Two和普通轉色牌混起來用 我說的就是! | |
| // 這裡把棄牌抽起, 抽到下面一直沒有draw four為止 | |
| const pile = [] | |
| pile.push(this.deck.pop()) | |
| while (pile.peek().effect == 'DrawFour') { | |
| drawCards(4) | |
| pile.push(this.deck.pop()) | |
| } | |
| // 最後還原棄牌區 | |
| while (pile.length) { | |
| this.deck.push(pile.pop()) | |
| } | |
| } | |
| else | |
| // 沒牌出, 摸1張 | |
| drawCards(1) | |
| } | |
| } |
細心的人應該已經發現了”當玩家n-1被罰DrawTwo後，玩家n沒有能出的牌，會重複被罰DrawTwo”的bug… 為了使牌堆能隨時重洗(特別是多人的情況很多時候會不夠牌摸)，不太建議把”空牌”放在棄牌堆裡。反而，會推薦儲存上一名玩家的動作來判定是不是被罰DrawTwo。另外，也不建議把萬能變色卡被指定的顏色儲存在卡上面，我更偏向儲存下一家”出牌的條件”。由於篇幅主要表達棧，這裡跳過實作，自己腦補吧。
下篇續。
