用於跟蹤OCaml中的遊戲板的數據結構

我對OCaml相當陌生，我想實現類似於四線遊戲的遊戲。我需要的是一些數據結構來保持遊戲狀態。遊戲板是一個4×4的廣場，總共有16塊瓷磚。我正在尋找OCaml中的這種表示方法，它可以方便快捷地檢索（或者做一些操作）整個列，行或對角線上的所有元素。我會在這個遊戲上做極限微型搜索，這就是爲什麼速度很重要。用於跟蹤OCaml中的遊戲板的數據結構

到目前爲止，我已經考慮了一維列表。列表的問題在於，很難確定哪些元素屬於每行/每列/對角線，然後使用例如List.map來檢索它們。

我想過使用Array.make 4 (Array.make 4 Empty);;。當涉及到行時，這絕對是完美的。它很容易得到它們並在其上進行模式匹配。但在單獨的列和對角線上進行模式匹配是一件苦差事。

我希望能夠做的是有一個函數，需要一個遊戲板並返回包含所有行/列/對角線的列表列表。然後我想要做，例如，match (rows,columns,diagonals) with (Empty, Empty, Empty, Empty) -> something。

來源

2012-11-10 user1815201

你要高雅或原始速度？如果是原始速度，在我看來你的整個遊戲棋盤都適合32位。但如果你想學習OCaml，優雅可能會更好。處理位在每種語言中看起來都很相似 –

有時匹配不起作用。在這裏，我認爲你應該嘗試儘可能地使用函數，然後讓你的細胞先行或列先行不會那麼複雜，甚至可以通過顛倒索引順序從一個表示移動到另一個表示。

如果我使用下列類型：

type color = Red | Yellow;; 
type cell = Empty | Color of color;; 
type board = Array.make 4 (Array.make 4 Empty);;

和第一決定列，則以下功能將得到我的行或列：

let column (b: board) i j = b.(i).(j) 
let row (b: board) i j = b.(j).(i)

對於對角線，有2臺其中一個從左上朝向右下，另一個從另一個方向（右上至左下）：

let ldiag (b: board) i j = b.((i + j) mod 4).(j) 
let rdiag (b: board) i j = b.((i - j + 4) mod 4).(j)

然後我猜測檢查行，列或對角線只是檢查該行的4個單元的問題。

let check predicate linef k = predicate (linef b k 0) && 
           predicate (linef b k 1) && 
           predicate (linef b k 2) && 
           predicate (linef b k 3)

然後例如，檢查是否有一個對角線的紅色：

let has_line linef b color = 
    let cmp x = x = color in 
    let check k = check cmp linef b k in 
    check 0 || check 1 || check 2 || check 3 

let has_ldiag b color = has_line ldiag b color 
let has_rdiag b color = has_line rdiag b color 

let has_red_diagonal b = has_ldiag b Red | has_rdiag b Red

等等

來源

2012-11-12 00:34:26 didierc

徹底的解釋。這看起來非常像我期望的代碼看起來像，但我沒有完全能夠把想法放到代碼中。我有點難過，你不能沿着列做模式匹配，但我想你不能擁有這一切。謝謝！ – user1815201

由於長度是固定的，因此首選數組優先於列表：它們使用較少的內存並且讀取和寫入速度更快。

恐怕你需要編寫一個函數來獲取對角線，沒有簡單的模式匹配。當你寫「在[對角線]上做一些操作」時，我假設你正在考慮一個函數f，它需要一個長度爲4的數組來存儲元素，例如[|Empty;Empty;Empty;Empty|]。也許f可能會取而代之的位置p，並在位置內的指數數組： f p [|x1,y1; x2,y2; x3,y3; x4,y4|]將提取正方形p.(x1).(y1) ... p.(x4).(y4)。然後只需通過不同的x和y即可使f在行/列/對角線上操作。

一旦代碼正在工作並且轉向優化，如果在minmax搜索的樹中存儲了很多位置，則可能需要查看bitvectors：，這意味着更多的內存佔用意味着更多緩存命中和更快的執行。你可能想要自己在一個int中編碼一個位置，但這是一項棘手的工作，你不想過早做。

來源

2012-11-10 22:24:42 jrouquie

你的意思是說p是一個函數，它需要座標並返回值？當長度固定時，爲什麼數組更適合列表？ – user1815201

（我已經更新了關於數組vs列表的答案）。 'f'（不是'p'）是一個函數，它接受座標並返回「該值」，例如，如果在給定座標處的所有4個方塊都是空的，則爲'true'。 'f'必須在給定座標處查找正方形的內容，因此它也需要接收位置'p'作爲參數。所以'f'是'position - >（int * int）數組 - > bool'的類型。 – jrouquie

如何用相應的座標索引你的瓷磚？所以，你的一個-d名單上的元素會是這樣的形式：

(int * int * ref tile)

然後你就可以過濾行/列/對角線這樣的：

第n行：（前提：0 < = N，U，v < = 3）

List.filter tiles (fun x -> match x with (u, v, _) -> u = n);;

n列：（前提：0 < = N，U，V < = 3）

List.filter tiles (fun x -> match x with (u, v, _) -> v = n);;

對角線1：（前提：0 < = U，V < = 3）

List.filter tiles (fun x -> match x with (u, v, _) -> u = v);;

對角線2：（前提條件：0 < = u，v < = 3）

List.filter tiles (fun x -> match x with (u, v, _) -> u + v = 3);;

也應該可以使用一個整數（一維d列表中的瓦片的索引）爲瓦片編制索引，但這需要在濾波器函數中進行一些計算（給定索引，計算出座標，然後決定它是否屬於所需的行/列/對角線）。

來源

2012-11-11 11:36:49

用於跟蹤OCaml中的遊戲板的數據結構

回答

相關問題