OCaml中用于跟踪游戏棋盘的数据结构

Question

OCaml中用于跟踪游戏棋盘的数据结构

6

我相对OCaml还比较陌生，我想实现一个类似四连棋的游戏。我需要一些数据结构来保持游戏状态。游戏板是一个4x4的正方形，共有16个格子。我正在寻找在OCaml中表示这个游戏板的方法，使得检索整列、整行或对角线上所有元素变得容易和快速。我将在这个游戏中进行极小化搜索，因此速度非常重要。

到目前为止，我考虑过使用一维列表。列表的问题在于很难确定哪些元素属于每一行/列/对角线，然后通过List.map等方法检索它们。

我考虑使用Array.make 4 (Array.make 4 Empty);。这对于行来说非常完美。很容易获取并对其进行模式匹配。但是在单独的列和对角线上执行模式匹配是一件苦差事。

我想做的是编写一个函数，该函数接受一个游戏板，并返回一个包含所有行/列/对角线的列表列表。然后，我想执行例如match (rows,columns,diagonals) with (Empty, Empty, Empty, Empty) -> something这样的操作。

- user1815201

4

你是追求优雅还是原始速度？如果是原始速度，那么我认为你的整个游戏板适合32位。但是，如果你想学习OCaml，优雅可能更好。在所有语言中，处理位看起来都很相似。 - Jeffrey Scofield

3个回答

1

你可以考虑使用相应坐标来对瓦片进行索引，这样，你的一维列表中的元素将具有以下形式：

(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);;

还可以使用一个整数（在一维列表中的瓦片索引）来索引瓦片，但这需要在过滤函数中进行一些计算（给定索引，找出坐标，然后决定它是否属于所需的行/列/对角线）。

- Asiri Rathnayake

1

有时匹配不起作用。在这里，我认为您应该尽可能使用函数，然后获取单元格的行或列就不会那么复杂，甚至可以通过反转索引顺序从一种表示转换到另一种表示。

如果我使用以下类型：

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)

对于对角线，有两组，一组从左上到右下，另一组则相反（从右上到左下）：

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)

那么我猜检查一行、一列或者一条对角线只需要检查该行的四个单元格就可以了。

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

等等。

- didierc

详细的解释。这看起来非常像我预期代码的样子，但我并不能完全将思想转化为代码。我有点遗憾你不能沿列进行模式匹配，但我想你不能拥有一切。 - user1815201

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jrouquie · Accepted Answer

由于长度固定，请使用数组而不是链表：它们使用更少的内存，并且读写速度更快。

恐怕您需要编写一个函数来获取对角线，没有简单的模式匹配。当您写下“在[对角线]上执行某些操作”时，我假设您正在考虑一个函数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在行/列/对角线上操作即可。

一旦代码正常工作并且您转向优化，您可能需要查看位向量：如果树中存储了大量位置，则减少内存占用意味着更多的高速缓存命中和更快的执行。您甚至可以自己将位置编码为单个整数，但这是一项棘手的工作，您不希望过早地这样做。