时间戳

首页 > 解决方案 > 如何在c上的蛇游戏中产生随机食物？

c - 如何在c上的蛇游戏中产生随机食物？

问题描述

我正在尝试使用 C 创建一个蛇游戏。

我正在尝试找到一种有效的算法来产生随机的食物位置。

这是我当前的 generateFood() 函数算法：

  1. 生成随机食物坐标
  2. 而坐标在蛇头上|| 身体：
  3. 生成新的随机食物坐标

该算法适用于游戏的前半部分，但当蛇开始变大时。随机获取坐标以最终获得空闲位置将花费更长的时间复杂性并且极其不一致。

我正在考虑将所有空坐标放入链表并移动随机步骤以到达坐标。它会根据蛇的坐标进行相应的更新，以便它可以在第一次运行时生成随机食物。

但我发现这种方法不必要地复杂，可能会占用大量内存和时间。

有没有其他方法可以让我在 C 上更有效地做到这一点？谢谢

标签： c

解决方案

我认为你需要 2 个数组。

一个包含所有自由像素的位置，另一个，自由像素图将包含自由像素阵列中每个像素的位置，如果它是自由的。

每当您占用一个新像素时，您都会将其从空闲像素阵列中移除。如果它是最后一项，您只需减少可用像素的计数器。如果它不是自由像素阵列的最后一个像素，您将首先将其与自由阵列的最后一个像素“交换”。

由于自由像素数组和自由像素图是相互链接的，占用一个新像素只需要对结构进行 O(1) 次更新；同样适用于再次释放像素时。

现在，为食物随机选择0一个空闲像素真的很容易，这是一个 O(1) 操作 - 只需从通过中选择一个数字，然后从空闲像素阵列中n_free_pixels - 1选择像素。ith

对于这种方法，每个像素需要大约 4-8 字节的额外内存；如果说 320x200 就足够了，那么 256k 的每个像素需要 4 个字节（两个数组都有无符号的短裤）。但是，如果您将食物放在网格中，并且如果蛇占据了网格位置的任何部分，则认为网格位置不可用，那么您可以少得多。

为简单起见，考虑一个 2x2 地图。一开始所有像素都是免费的，所以地图的内容是

Free pixel map        Free pixel list
+-----+-----+
|0    |1    |         | 0 | 1 | 2 | 3 
|  0  |  1  |
|     |     |
+-----+-----+         n_free = 4
|2    |3    |
|  2  |  3  |
|     |     |
+-----+-----+

然后你想选择一个像素来占据，并选择一个介于 0 和 n_free - 1 之间的数字。在这种情况下为 1。现在你从索引 1 处的空闲像素列表中获取像素位置（这也是 1）...

Free pixel map        Free pixel list
+-----+-----+
|0    |1    |         | 0 | 1 | 2 | 3 
|  0  |  1  |               ^
|     |     |
+-----+-----+         n_free = 4
|2    |3    |
|  2  |  3  |
|     |     |
+-----+-----+

我们将该像素标记为在免费像素图中保留

Free pixel map        Free pixel list
+-----+-----+
|0    |1    |         | 0 | 1 | 2 | 3 
|  0  |  #  |               
|     |     |
+-----+-----+         n_free = 4
|2    |3    |
|  2  |  3  |
|     |     |
+-----+-----+

由于空闲列表中的位置不是最后一个，我们将最后一个元素（像素 3）交换到该位置，并更新空闲映射以指向该索引，最后减n_free一：

Free pixel map        Free pixel list
+-----+-----+
|0    |1    |         | 0 | 3 | 2 
|  0  |  #  |               ^
|     |     |
+-----+-----+         n_free = 3
|2    |3    |
|  2  |  1  |
|     |  ^  |
+-----+-----+

如果像素1随后被释放，我们可以将它添加n_free到空闲列表的位置，并修改地图指向该元素，最后增加n_free；新状态将是

Free pixel map        Free pixel list
+-----+-----+
|0    |1    |         | 0 | 3 | 2 | 1
|  0  |  3  |                       ^
|     |     |
+-----+-----+         n_free = 4
|2    |3    |
|  2  |  1  |
|     |     |
+-----+-----+

推荐阅读