在面试中设计简单的贪婪蛇游戏的数据结构

Question

在面试中设计简单的贪婪蛇游戏的数据结构

4

这不是一个实际问题，我只想在这里讨论和学习数据结构设计，听说Google在面试中会问到这个问题。请指导我如何改进我的设计，谢谢！

起初，我想使用双端队列来存储蛇身体部分的x、y坐标对。

deque<pair<x, y>> snakeBodyParts;

因为蛇在移动中很容易推前，所以创建新的坐标对作为新头部基于旧的头部位置和当前方向，然后从后面弹出以删除尾部。通过这种方式移动、吃和检查头部是否碰到墙壁都是O(1)的操作，并且可以使用队列(deque)轻松实现。但是检查新头部位置是否与蛇身重叠将需要循环遍历所有身体部位的位置 - O(L)时间复杂度，其中L是身体部分的数量。

为了改进它，我考虑将所有坐标放入无序集合(C++)或哈希集合(Java)，同时仍保持我的旧队列，这可以使我以O(1)的时间检查头部是否撞到身体。但我不知道这是否是个好主意，因为它几乎会将内存和代码量增加一倍，每当我添加/删除队列时，我都需要对我的哈希集合进行操作。

unordered_set<pair<int, int>, pair_hash> bodyPartsSet;

我曾考虑过创建一种类似于链表的结构，不同之处在于它指向前一个节点：

SnakeBodyNode {
    int x;
    int y;
    SnakeBodyNode * prev;
}

然后我还需要两个指向头和尾的指针，以及一个方向变量。

SnakeBodyNode * head;
SnakeBodyNode * tail;
char dir;

然而我并没有看到这种方法的任何优点，仍然需要哈希来实现O(1)的检查头是否碰撞身体。

我的双端队列+哈希的设计中是否存在缺陷，或者有更好的想法可以分享吗？

- Arch1tect

上次我写贪吃蛇游戏时，只存储了两个坐标：蛇头的位置（用于向前移动蛇头）和蛇尾的位置（通过删除蛇尾来向前移动蛇尾）。我通过检测蛇头要移动到的单元格中像素的颜色来检测碰撞。但说实话，这种设计相当有限。但在8位微处理器上非常快速。 - Galik

你的网格有多大？我更倾向于选择更简单的队列实现。即使线性搜索很耗费资源，你只需要遍历包含几百个节点的队列。 - user1

@Galik 嗯...我真的不明白这样删除tail指针的工作方式，一旦你使用tail指针将其删除，你又如何更新tail指针呢？ - Arch1tect

@user1 是的，我认为贪吃蛇的身体在游戏中通常不会变得太长。我甚至觉得时间复杂度对于这么简单的游戏来说并不重要。 - Arch1tect

是的，你说得对。那已经很久了，我可能遗漏了一些东西。也许效率在于我只需要绘制蛇头并删除尾部？也许我只需要存储蛇改变方向的点...？ - Galik

显示剩余2条评论

1个回答

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

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

- domehead100 · Accepted Answer

我建议使用unordered_set。您的考虑因素如下：

快速插入新头部 - 对于unordered_set，这是O(1)。
快速删除现有尾部 - 对于unordered_set，这是O(1)。
无重复项（检查头部是否与身体相交） - 对于unordered_set，这是有保证的（它不允许重复项）。

在插入新头部时，您不必特别检查它是否与身体相交；如果确实相交，您将收到错误提示。