我打算写一个游戏(如果你听说过的话，它叫做“Qwirkle”)，其中一个二维游戏场存储玩家放入其中的石头的位置。第一个玩家将石头放在任何地方，其他玩家可以从任何一侧(左/右/顶部和底部)连接到它。游戏领域本身不限于会破坏游戏创意的固定大小。但是，石头的数量限制为玩家可以在开始时定义的值。
由于游戏逻辑，我需要使用索引对石头进行循环。然而，由于玩家可以从任何一侧添加石头，我需要一个可扩展到任何方向(例如，负索引方向和正索引方向)的列表。
性能并非不重要，因为我需要在一个回合中检查多个石头。
当然，最好的办法是访问像 _stones[-3,5] 这样的石头来访问位置 -3、5 的石头。
我认为可以从任何一侧插入和弹出的堆栈(如 PushBack/PushFront)对此很有用，但我不太确定如何在 C# 中实现这一点。
是否有像我正在考虑的那样预先实现的列表/堆栈，或者我的方法是否完全奇怪？
最佳答案
您想要的数据结构是一个不可变的四叉树。如果棋盘大部分是空的，那么使用不可变的四叉树可以让您表示基本上没有大小限制的棋盘；一个万亿乘一万亿的单元板只比一个 32×32 的单元板多占用几个字节的内存。不可变四叉树可以很容易地按照您描述的方式进行索引，并且在给定旧四叉树和编辑的情况下计算新四叉树很简单。
多年来，我已经多次编写不可变四叉树算法，很长一段时间以来我一直想写一系列关于它们的博客文章，但我从来没有这样做过。当我这样做时，我会回来更新这个答案。
与此同时，这篇关于 Gosper 算法的 Dobbs 博士文章是我用来了解不可变四叉树如何工作的文章。
http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478
关于c# - 列出哪些指数可以向两个方向扩展？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15503001/