實作Lua Closure二合一洗牌發牌機

dice-triangle

(圖片來源:maniacworld.com)

亂數 (Randomness),是每一位程式設計者們熟悉又親切的好朋友,無論我們開發製作的是哪一種類型的遊戲,亂數機制總是在遊戲設計程序與撰寫程式碼的過程中,扮演著不可或缺的重要角色。亂數最重要的用途,就是提供遊戲世界中必要的「不確定性」,只要能夠將這份「不確定性」的設計機制運用得宜,就可以為玩家們帶來許多驚喜感與樂趣元素。

然而,有許多時候,亂數的產生並不只是使用 rand() 函式般單純容易而已。在某些遊戲機制裡,無邊無際的亂數數值,並不能滿足程式設計者或企畫設計者所想達到的目標——我們需要的是「亂中有序」——能夠在某個限定範圍之內產生亂數。

何謂「亂中有序」?撲克牌遊戲就是一個最好的實例。撲克牌由 4 種花色與 13 種數字,組合成 52 張「牌組」。而「洗牌」(Shuffle) 動作可以定義為:在一組有限的集合元素內,進行亂數排列的程序。只要將牌組洗完之後,就可以按照牌堆的排列順序,開始一張張地進行「發牌」動作了。

對於程式設計者來說,不論是使用哪一種程式語言,要實作出洗牌與發牌的功能都不是件太困難的事情。假設,我們可以使用 Lua 語言來實作洗牌發牌機,是否能夠創造出什麼樣有趣的變化?

由於 Lua 是一種無須宣告變數資料型別的程式腳本語言,所以在 Lua 中我們可以非常便利地對任意數量、任意類型的「資料集合」進行洗牌的動作。下列的 Lua 函式 RandShuffle(),接受一個 table 型別的參數做為洗牌用的「牌組」:

function RandShuffle(deck)
    -- 首先確認傳入的參數型態是 table
	assert(type(deck) == "table");

    -- 將 deck 的所有元素複製至暫用的 clone 中
	local clone = {};
	for k, v in pairs(deck) do
		clone[k] = v;
	end

	-- 取得元素集合的大小
	local range = table.maxn(deck);

	-- 巡訪 deck 結構
	for k, v in pairs(deck) do
    	-- 藉由亂數機制,決定要取出的 clone 索引值
		local index = math.random(1, range);
		
	    -- 在 clone 中移除該元素,塞回原來的 deck 中
		deck[k] = table.remove(clone, index);
		
		-- 將亂數取值的範圍減1
		range = range - 1;
	end
end

無論 deck 結構中的資料,是數字型別、字串型別或甚至另一個 table 結構,只要經過 RandShuffle() 程序的操作,就可以得到一副經過亂數排列,也就是洗牌後的 deck 牌組:

-- 數字型別的牌組
NumberDeck = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
-- 洗牌
RandShuffle(NumberDeck);

-- 字串型別的牌組
StringDeck = { "Apple", "Banana", "Cherry", "Lemon", "Orange" };
-- 照樣洗牌
RandShuffle(StringDeck);

-- table結構的牌組
ComplexDeck =
{
	{ 1, Monday, "Apple" },
	{ 2, Tuesday, "Banana" },
	{ 3, Wednesday, "Cherry" },
	{ 4, Thursday, "Lemon" },
	{ 5, Friday, "Orange" },
};
-- 洗!洗!洗!
RandShuffle(ComplexDeck);

但是到目前為止,我們只是得到了一副洗過牌的牌組,接下來該如何進行「發牌」動作呢?

站在使用者的立場思考,我們會希望發牌功能可以一次發出一張牌,並且在整副牌組全部使用過後,自動重新進行洗牌。所以,在此需要另一個輔助函式 OutputCard() 來完成發牌程序:

-- 發牌計數器
g_Counter = 0;

function OutputCard(deck)
    -- 紀錄目前的發牌數
	g_Counter = g_Counter + 1;

    -- 如果發牌數大於總牌數
	if (g_Counter > table.maxn(deck)) then
		-- 重新洗牌
		RandShuffle(deck);
		-- 重設發牌計數器
		g_Counter = 1;
	end

	-- 回傳一張牌
	return deck[g_Counter];
end

實作出「洗牌機」RandShuffle() 與「發牌機」OutputCard() 後,就可以很便利地使用:

-- 牌組
MyDeck = { ... };

-- 先將 g_Deck 洗牌
RandShuffle(MyDeck);

-- 發牌
MyCards = {};
-- 第1張牌
MyCards[1] = OutputCard(MyDeck);
-- 第2張牌
MyCards[2] = OutputCard(MyDeck);
-- 第3張牌
MyCards[3] = OutputCard(MyDeck);
-- 第4張牌
MyCards[4] = OutputCard(MyDeck);
-- 第5張牌
MyCards[5] = OutputCard(MyDeck);

但光是這樣還不夠完善。假設我們需要一次操作兩副以上相同的牌組怎麼辦?有沒有其他方法,可以不使用全域變數 g_Counter 做為發牌的計數器?在 Lua 缺少物件導向設計機制特性的情形下,能不能將「洗牌機」與「發牌機」合而為一,讓使用者得以更直覺地操作洗牌與發牌程序?

答案就是 Lua Closures。利用 Lua 語言提供的 Closure 特性,就可以幫助我們輕巧且優雅地達成目標:

function RandDeck(t)
	assert(type(t) == "table");

    -- Closure所使用的upvalues
	local pool = t;
	local counter = table.maxn(t);

    -- 回傳一個匿名函式
	return function()
		counter = counter + 1;

		if (counter > table.maxn(pool)) then
			RandShuffle(pool);
			counter = 1;
		end

		return pool[counter];
	end
end

上列函式 RandDeck() 的回傳值是一個「匿名函式」,而在這個匿名函式中所做的事情,與先前在 OutputCard() 函式中進行的程序相同。根據 Lua Closures 的功能規範,在 RandDeck() 中宣告為區域變數的 pool 與 counter,被稱為 external local variable 或 upvalue。

藉由 upvalue 的特性,程式設計者得以在函式之間保存變數值,並且讓底下的匿名函式進行讀寫動作。對於全域或 RandDeck() 函式外部的程式碼來說,pool 與 counter 是完全不可見的變數;但是對於底下的匿名函式來說,pool 與 counter 的功用就像是物件導向語言中的「成員變數」(member variables) 一樣。

而 RandDeck() 的使用方式也很簡單明瞭,以 52 張撲克牌為例:

-- 撲克牌牌組
--   花色:c, d, h, s 分別代表 club, diamond, heart, spade 四種花色
--   數字:1 至 13
Poker = 
{
	"c1", "c2", "c3", "c4", "c5", "c6", "c7", "c8", "c9", "c10", "c11", "c12", "c13",
	"d1", "d2", "d3", "d4", "d5", "d6", "d7", "d8", "d9", "d10", "d11", "d12", "d13",
	"h1", "h2", "h3", "h4", "h5", "h6", "h7", "h8", "h9", "h10", "h11", "h12", "h13",
	"s1", "s2", "s3", "s4", "s5", "s6", "s7", "s8", "s9", "s10", "s11", "s12", "s13",
};

-- 創造一副牌組
g_Deck = RandDeck(Poker);

MyCard = {};
-- 呼叫 g_Deck() 發第1張牌
MyCard[1] = g_Deck();
-- 呼叫 g_Deck() 發第2張牌
MyCard[2] = g_Deck();
-- 呼叫 g_Deck() 發第3張牌
MyCard[3] = g_Deck();

-- 創造多副不同的牌組
g_Deck1 = RandDeck(Poker);
g_Deck2 = RandDeck(Poker);
g_Deck3 = RandDeck(Poker);

MyCard = {};
-- 使用 g_Deck1() 發第1張牌
MyCard[1] = g_Deck1();
-- 使用 g_Deck2() 發第2張牌
MyCard[2] = g_Deck2();
-- 使用 g_Deck3() 發第3張牌
MyCard[3] = g_Deck3();

結合之前的 RandShuffle() 與 RandDeck() 寥寥可數的幾行程式碼,就完成了雙效合一的洗牌發牌機。

最後,可以再進一步修改 RandDeck() 函式,讓它能夠一次發出複數張的牌:

-- 發牌機加強版
function RandMultiDeck(t)
	assert(type(t) == "table");

	local pool = t;
	local counter = table.maxn(t);

	return function(num)
		num = num or 1;
		
		if (num == 1) then
			counter = counter + 1;
			
			if (counter > table.maxn(pool)) then
				RandShuffle(pool);
				counter = 1;
			end
	
			return pool[counter];
		else
			if (counter + num > table.maxn(pool)) then
				RandShuffle(pool);
				counter = 1;
			end
	
			local result = {};
			for index = counter, counter + num - 1 do
				table.insert(result, pool[index]);
			end

			counter = counter + num;
			
			return result;
		end
	end
end

-- 創造一副牌組
g_Deck = RandMultiDeck(Poker);

-- 一次發出5張牌!
MyCard = g_Deck(5);

在這篇文章裡,雖然只介紹了非常簡單的洗牌與發牌應用,但應該不難看出 Lua Closures 的威力所在。對於習慣使用 C/C++ 或 Java 語言的程式設計者來說,一開始可能會比較難以理解 Lua Closures 的概念,但只要熟悉了它的運作方式,就可以使用 Lua 做到許多目前 C++ 語言無法達成的事情。

關於洗牌與發牌,你是否有更好更巧妙的作法?關於 Lua Closures,你有更棒更實用的應用嗎?歡迎各位給予指教及討論。

18 thoughts on “實作Lua Closure二合一洗牌發牌機

  1. 慘了竟然看不懂囧
    可以請半路前輩稍微解說一下Closures是怎麼樣的東西呢?

  2. 我試寫了另一個方法去實現 RandShuffle()。就是把第 i 個元素,和自己至最後一個元素中抽一個來交換。這樣好像比較簡單, 而且沒有額外 table 開銷:

    function RandShuffle(deck)
    assert(type(deck) == “table”);
    local range = table.maxn(deck);
    for i = 1, range – 1 do
    local index = math.random(i, range);
    deck[i], deck[index] = deck[index], deck[i]
    end
    end

    range – 1 是因為最後一個元素只會和自己交換, 所以不用做. 因為每個元素都和其中一個未曾 shuffle 的元素(包括自己)交換, 所以這方法應該是對的。

  3. Closures 應該是匿名函式以及它擁有(已捆綁)的參數。
    把函式與參數包裝起來就方便了把乎叫者和實行本體分開,即是在某處建立乎叫然而在另一處執行。

  4. @Necromancer:
    摘錄一段 Wikipedia 中對於 Closure 的說明:「A closure is a first-class function with free variables that are bound in the lexical environment.」

    簡言之,在 Lua 語言中實現的 Closure 機制,是個 first-class function,並且擁有一組限定在 lexical scoping 內使用的 upvalue。如果不瞭解何謂 first-class function 的話,請參考 Lua Functions 小節中的說明。

    @Milo:
    利用元素交換,省下了一個 table 的開銷,確實是個好做法!

    @Ricky:
    其實 Closure 與 Anonymous Function 兩者的意義內涵有所不同,只是因為大多數的程式語言,都以匿名函式的做法來實現 Closure 機制,所以很容易令人誤以為 Closure 就等同於匿名函式加上 upvalue。

  5. 應該要profile一下看是Lua的swap assignment還是remove比較快

    因為swap通常會產生unnamed temporary variable,
    而大部分的scripting language的variable creation都超慢
    在loop裏面做會特別明顯~

    呼叫remove時有給它index所以我猜速度是O(1),
    但是如果index只是當counter的話速度會是O(N),
    則用swap的方式會比較快很多~

    題外話
    可不可以推薦一些不錯的免費profiler? Windows平台用的~ 感恩~

  6. @R2D2:
    嗯,有道理。還是應該要先做過 profiling,才能確實知道哪一種實做方式的效能比較好。不過我和 Windows 平台的免費 profiler 很不熟,所以沒辦法給你推薦哩。可以參考看看 Ricky 介紹的連結!

    @Ricky:
    感謝你的補充!

  7. 有個缺點:如果要用發牌機做不止一種工作呢?(即需要兩個以上的method)
    我覺得可以改良成message based的方式

    假如遊戲規則特殊,除了發牌以外還有把牌放回牌組的情況
    定義一些動作ID
    DECK_GETCARD=1
    DECK_RETURNCARD=2

    傳回來的函式物件改成如下
    function(actionID, param1, param2) –要幾個參數就宣告幾個
    裡面用一堆if…elseif(Lua沒有switch)根據actionID決定要做什麼事,param1和param2的意義依actionID而定

    其實這很像Windows UI的WndProc運作的方式

    Lua也有模擬class method的語法,像deck:getCard()這樣

    函式包物件和物件包函式哪個好用?見仁見智

    @R2D2:
    用os.clock()

  8. @Shark:
    將發牌機弄成 message-based 多功能用途的物件,是個可以延伸的方向,不過也要考慮會不會使程式碼變得過於複雜難用。只要記得利用 Lua function 是 first-class value 這項特點,就可以節省許多不必要的 if-else 或其他控制結構囉。

    另外,R2D2 指的應該是整合方案的 profiler 模組或第三方軟體。如果要自己用 os.clock() 慢慢做的話,當然沒問題,但是會花上很多額外的時間精力。

  9. @R2D2:
    os.clock() 確實無法提供 Profiler 所需的精密時間解析度哩。

    在我目前有使用 Lua 的專案裡,還沒有達到需要用 Profiler 來做效能調校的程度;如果有需求的話,我應該會考慮用看看 LuaProfiler 吧。

  10. 原本在文章中,最後一段程式碼裡的「發牌機加強版 」有點問題,在某種狀況下可能無法產出正確的牌,現在已經修改成正確的版本囉。

    若有人要拿去用的話,記得先做完整的測試,如有發現臭蟲問題也歡迎回報!感謝! :D

  11. @Derek:
    你好,

    我沒有學過 Python,看了一下你的程式碼,Python 似乎有內建的 shuffle 函式可用?再加上 Closure 的功能,果然將程式碼簡化不少哪~

    謝謝你的資訊! ^^

  12. 0-0 小弟在筆記本上安裝了UBUNTU,正為找不到LUA的相應開發環境而發愁。不知道猴兄可有推薦?不勝感激。

  13. @antiar:
    你好,

    所謂的開發環境,你是指好用的程式碼編輯器嗎?我記得 Eclipse 有 Lua 的語法 plugin,你可以嘗試看看。

  14. Pingback: Lua扑克洗牌发牌源码 | MiuGames!|缪游戏

Leave a Reply