OCaml 中的游戏数据结构

Question

我目前正在开发一个游戏/模拟计算机，如物流系统（如我的世界 mod 应用能量学）。

游戏的主要部分是块的二维网格。

所有的块都有共同的属性，比如位置。

但是应该有不同类型的块，例如：

• 物品容器，
• 输入和输出总线，
• 等等。

在命令式面向对象语言（如 Java）中，我将使用以下方法实现：

• 一个主块类
  • 具有共同的属性，如位置
• 然后有子类
  • 从块类继承
  • 这些子类将实现不同块类型的不同属性。

在ocaml我有点迷失了。

我可以创建继承的对象，但这在 Java 中不起作用。

例如：

• 我不能将不同子类的对象放在一个列表中。

我还想通过将数据与逻辑分开来以不同的方式处理数据结构。我不会向对象添加方法。我尝试使用记录而不是对象。

我不知道如何实现不同的块类型。

我尝试使用这样的自定义数据类型：

type blockType = Container | Input | Output | Air
type block = {blockType :blockType; pos :int * int}

我努力添加单独的附加属性。我尝试向块记录类型添加一个实体字段，该字段将包含其他属性：

type entity = Container of inventory | OutputEntity of facing | InputEntity of facing | NoEntity

（其中库存和面也是自定义类型）

这个解决方案感觉不太合适。

我遇到的一个问题是我想对输入和输出类型的块执行逻辑操作。我必须重复这样的代码：

let rotateBlock block =
  match block.blockType with
  | Input -> {block with entity = nextDirection block.entity}
  | Output -> {block with entity = nextDirection block.entity}
  |  _ -> block

这两种类型并没有那么糟糕，但我计划添加更多，因此在可扩展性方面这是一个很大的负面影响。

这种结构的另一个批评点是它有点不一致。我使用记录中的一个字段来实现块级别的不同类型和实体级别的多个构造函数。我这样做是为了能够轻松访问每个块的位置，block.pos而不是使用模式匹配。

我对这个解决方案并不满意。

要求

我希望有人能指出我关于数据结构的正确方向。

Answer 1

您正在努力满足相互竞争的目标。您不能同时拥有刚性静态块模型和动态可扩展块类型。所以你需要选择。幸运的是，OCaml 为两者提供了解决方案，甚至为两者之间的某些东西提供了解决方案，但与中间解决方案一样，它们在两者中都有些糟糕。所以让我们试试。

使用 ADT 的刚性静态层次结构

我们可以使用 sum 类型来表示对象的静态层次结构。在这种情况下，我们很容易添加新的方法，但很难添加新的对象类型。作为基本类型，我们将使用一个多态记录，该记录使用具体块类型进行参数化（具体块类型本身可以是多态的，这将允许我们构建层次结构的第三层等等）。

type pos = {x : int; y : int}
type 'a block = {pos : pos; info = 'a}
type block_info = Container of container | Input of facing | Air | Solid

其中info是附加的具体块特定的有效载荷，即 type 的值block_info。这个解决方案允许我们编写接受不同块的多态函数，例如，

let distance b1 b2 = 
  sqrt ((float (b1.x - b2.x))**2. + (float (b1.y - b2.y)) **2.)

该distance函数具有类型'a blk -> 'b blk -> float并将计算任何类型的两个块之间的距离。

该解决方案有几个缺点：

1. 难以扩展。添加一种新的块是很难的，你基本上需要事先设计你需要什么块，并希望你以后不需要添加新的块。看起来您希望需要添加新的块类型，因此此解决方案可能不适合您。但是，我相信如果您将每个块视为世界语法的句法元素，您实际上将需要非常少量的块类型，您很快就会注意到块类型的最小集合非常小。特别是，如果您将块递归，即，如果您将允许块组合（即，同一块中不同块的混合）。

2. 您不能将不同种类的块放在同一个容器中。因为要做到这一点，您需要忘记块的类型。如果你这样做，你最终会得到一个仓位容器。我们将尝试通过使用存在类型在我们的中间解决方案中缓解这种情况。

3. 您的类型模型没有施加正确的约束。世界约束是世界由块组成，每个坐标要么有块，要么没有块（即，它是虚空）。在您的情况下，两个块可能具有相同的坐标。

使用 GADT 的层次结构不是那么严格

通过使用存在性 GADT，我们可以放宽先前解决方案的一些限制。存在的想法是你可以忘记块的类型，然后恢复它。这本质上与变体类型（或 C# 中的动态类型）相同。使用existentials，您可以拥有无​​限数量的块类型，甚至可以将它们全部放在同一个容器中。本质上，存在被定义为忘记其类型的 GADT，例如，第一个近似

type block = Block : block_info -> {pos : pos; info : block_info}

所以现在我们有一个统一的块类型，即用块有效载荷的类型在本地量化。您甚至可以进一步移动，并使block_info类型可扩展，例如，

type block_info = ..
type block_info += Air

您可以选择使用一些现有的库，而不是自己构建存在性表示（这是 GADT 中的一个很好的练习）。在 OPAM 存储库中搜索“universal values”或“universals”，有几种解决方案。

这个解决方案更加动态，允许我们在同一个容器中存储相同类型的值。层次结构是可扩展的。这当然是有代价的，因为现在我们不能对特定方法有一个单一的定义点，事实上，方法定义会分散在您的程序中（有点接近 Common Lisp CLOS 模型）。然而，这是可扩展动态系统的预期价格。此外，我们失去了模型的静态属性，因此我们将在模式匹配中使用大量通配符，并且我们不能依赖类型系统来检查我们是否涵盖了所有可能的组合。主要问题仍然是我们的模型不正确。

面向对象的结构不那么僵化

OCaml 具有面向对象层（因此得名），因此您可以构建经典的 OO 层次结构。例如，

class block x y = object
   val x = x
   val y = y 
   method x = x
   method y = y 
   method with_x x = {< x = x >}
   method with_y y = {< y = y >}
end

class input_block facing = object
   inherit block 
   val facing = facing
   method facing = facing
   method with_facing f = {< facing = f >}
end

这个解决方案本质上接近于第一个解决方案，除了您的层次结构现在可以扩展，但代价是方法集现在是固定的。虽然你可以通过使用向上转换忘记块的具体类型来将不同的块放在同一个容器中，但这没有多大意义，因为 OCaml 没有向下转换运算符，所以你最终会得到一个容器坐标。我们仍然有同样的问题——我们的模型不正确。

使用享元的动态世界结构

这个解决方案同时杀死了两只兔子（我相信这应该是它在 Minecraft 中的实现方式）。让我们从第二个问题开始。如果您将使用具有该项目所有属性的具体记录来表示您的世界中的每个项目，那么您最终将得到大量重复项和极端的内存消耗。这就是为什么在实际应用中使用称为Flyweight的模式。因此，如果您考虑可扩展性，您最终仍会使用这种方法。Flyweight 模式的思想是你的对象通过使用有限映射共享属性，并且对象本身被表示为标识符，例如，

type block = int
type world = {
  map : pos Int.Map.t;
  facing : facing Int.Map.t;
  air : Int.Set.t;
}

where'a Int.Map.t是从intto的映射'a，Int.Set.t是一组整数（我在Core这里使用库）。

事实上，您甚至可能决定不需要封闭世界类型，而只需要一堆有限映射，其中每个特定模块添加和维护自己的一组映射。您可以使用抽象类型将此映射存储在中央存储库中。

您还可以考虑以下块类型的表示，而不是一个整数，您可以使用两个整数。第一个整数表示一个块的身份，第二个表示它的相等性。

type block = {id : int; eq : int}

这个想法是游戏中的每个块都有一个独特的id，即使它们“像两滴水”一样相等，也可以将它与其他块区分开来。并且eq将表示两个块的结构相等，即具有完全相同属性的两个块将具有相同的eq编号。如果您的世界结构未关闭（因为在这种情况下属性集未关闭），则此解决方案很难实现。

这个解决方案的主要缺点是它太动态了，以至于让 OCaml 类型系统无法工作。这是一个合理的惩罚，实际上你不能拥有一个在静态时间完全验证的动态系统。（除非你有一种具有依赖类型的语言，但这是一个完全不同的故事）。

总而言之，如果我要设计这种游戏，我会使用最后一个解决方案。主要是因为它可以很好地扩展到大量块，这要归功于 hashconsing（Flyweight 的另一个名称）。如果可扩展性不是问题，那么我将构建具有不同组合运算符的块的静态结构，例如，

type block = 
  | Regular of regular
  | ...  
  | Compose of compose_kind * block * block

type compose_kind = Horizontal | Vertical | Inplace

现在world只是一个街区。不过，这个解决方案是纯数学的，并不能真正扩展到更大的世界。