OCaml中的游戏数据结构

Question

我目前正致力于像物流系统这样的计算机的游戏/模拟（如Minecraft mod应用的energestics）。

游戏的主要部分是2d网格块。

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

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

• 项目的容器，
• 输入和输出总线，
• 等等

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

• 主要类块 与位置等共同属性
• 然后有子类 继承自块类 这些子类将实现不同块类型的不同属性。

在qazxsw poi我有点失落。

我可以创建继承的对象，但这不像Java那样有用。

例如：

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

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

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

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

ocaml

我努力添加个别附加属性。我试图将一个实体字段添加到块记录类型，该类型将保存其他属性：

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

轻松访问每个块的位置，而不是使用模式匹配。

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

请求

我希望有人可以指出我在数据结构方面的正确方向。

Answer 1

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

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

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

block.pos

其中

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类型的值。该解决方案允许我们编写接受不同块的多态函数，例如，

block_info

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

函数具有类型distance，并将计算任何类型的两个块之间的距离。

该解决方案有几个缺点：

1. 难以延伸。添加一种新的块很难，你基本上需要预先设计你需要的块，并希望将来不需要添加新的块。看起来你期望你需要添加新的块类型，所以这个解决方案可能不适合你。但是，我相信如果你将每个块视为世界语法的语法元素，你实际上需要非常少量的块类型，你很快就会发现块类型的最小集合非常小。特别是，如果你将块递归，即，如果你将允许块组合（即，同一块中不同块的混合）。
2. 您不能将不同类型的块放在同一个容器中。因为要做到这一点，你需要忘记块的类型。如果你这样做，你最终会得到一个容器的容器。我们将尝试通过使用存在类型在我们的中间解决方案中缓解这一点。
3. 您的类型模型不会施加正确的约束。世界约束是世界由块组成，并且每个坐标要么具有块，要么没有块（即，它是空白）。在您的情况下，两个块可能具有相同的坐标。

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

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

'a blk -> 'b blk -> float

所以现在我们有一个统一的块类型，用块有效载荷的类型进行局部量化。您甚至可以进一步移动，并使type block = Block : block_info -> {pos : pos; info : block_info} 类型可扩展，例如，

block_info

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

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

没有那么刚性的结构与OO

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

type block_info = ..
type block_info += Air

此解决方案基本上接近第一个解决方案，除了您的层次结构现在可以按照现在修复方法集的价格进行扩展。虽然你可以通过使用向上转换忘记具体类型的块来将不同的块放在同一个容器中，但这没有多大意义，因为OCaml没有向下转换操作符，所以你最终会得到一个容器坐标。我们仍然有同样的问题 - 我们的模型不对。

使用Flyweights的动态世界结构

这个解决方案同时杀死了两个兔子（我相信这应该是它在Minecraft中实现的方式）。让我们从第二个问题开始吧。如果您将使用具有该项目的所有属性的具体记录来表示您的世界中的每个项目，您将最终得到大量重复和极大的内存消耗。这就是为什么在现实世界的应用程序中使用了一种名为

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

的模式。因此，如果您考虑可扩展性，您仍将最终使用此方法。 Flyweight模式的想法是您的对象通过使用有限映射来共享属性，并且对象本身被表示为标识符，例如，

Flyweight

其中

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

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

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

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

Core

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

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

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

eq

而现在

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

type compose_kind = Horizontal | Vertical | Inplace

只是一个街区。这个解决方案虽然是纯数学的，但并没有真正扩展到更大的世界。

Answer 2

听起来很有趣。

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

你其实可以。假设你有很多不同的块对象都有'衰变'方法。你可以有一个函数“让我得到decayables”，它可以把所有这些块放在一个列表中，然后你可以在定时间隔迭代列表并在每个块上应用衰减方法。这一切都很好，并且很容易与OCaml的对象系统一起使用。你不能做的是从该列表中取出一个'decayable'并说，实际上，这也总是一个AirBlock，我想把它当作一个成熟的AirBlock，而不是一个可以腐烂的。

...

world

每种类型只能有240个变体。如果您计划拥有比此更多的块，获得额外空间的简单方法是对块进行分类并使用例如块。 type blockType = Container | Input | Output | Air 而不是Solid Rock | Liquid Lava。

Rock | Lava

库存中块的位置是什么？从世界上的地方开采出来的街区的位置是什么，现在有点坐在地上，等待被捡起来？为什么不保留数组索引中的位置或用于表示世界中块的位置的映射键？否则你还必须考虑块具有相同位置或不可能位置的含义。

type block = {blockType :blockType; pos :int * int}

我并没有真正遵循这个输入/输出的东西，但似乎在这个函数中你对某种属性感兴趣，比如“如果旋转则有下一个方向面”。为什么不命名该属性并使其匹配？

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

Answer 3

块类型很有趣，因为每种类型都有不同的操作。

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

type block = {
  id : blockType;
  burnable : bool;
  consumable : bool;
  wearable : bodypart option;  (* None - not wearable *)
  hitpoints : int option;      (* None - not destructible *)
  oriented : direction option; (* None - doesn't have distinct faces *)
}

let rotateBlock block =
  match block.oriented with
  | None -> block
  | Some dir -> {block with oriented = Some (nextDirection dir)}

let burn block =
  match block.burnable, block.hitpoints with
  | false, _ | true, None     -> block
  | true, Some hp when hp > 5 -> { block with hitpoints = Some (hp - 5) }
  | true, Some hp             -> ash

我的直觉告诉我你可以使用GADT来创建块上的操作类型，并为模拟器轻松实现一个求值器。

更新以回答您的评论：

如果您有所有变体的共同信息，您需要提取它们，您可以想象如下：

type container = { specificinfo : int ; etc ...}
type bus .....

type block = 
    | Item of  position * container    
    | Bus of position * bus

type inventory = block list