0

我在设计一种算法时遇到了麻烦，该算法几乎可以像在蛇游戏中一样使用包含线上所有点的数组来移动线。我会做类似...

for (int x = 0; i < array.length; i++) { 
     array[i] = array[i+1]
}
array[array.length] = (the new point)

但这每秒会发生很多次，而且速度很慢。我想过做一些类似的事情，但不是每次都移动每个数字，而是它们保持在数组中的相同位置，但保存一个 int 以跟踪接下来将删除哪个以及包含新数字。如果您对我刚才所说的内容有任何了解，请帮助我。谢谢

4

4 回答 4

5

使用循环缓冲区。这可以使用一个数组和两个索引（一个用于头部，一个用于尾部）来实现。如果蛇总是具有相同的长度，则可以使用单个索引。

使用这样的结构，您需要的整个操作可以在恒定时间内完成（即与数组的大小无关）。

于 2013-09-23T18:53:52.697 回答
1

您认为每次移动所有块都很慢是正确的。

有一种更有效的方法可以做到这一点。

只有第一个在最后的位置随着每次移动而改变。

所以，如果你有你的蛇array[i]和一个“头部”标记head，那么你可以简单地head穿过你的阵列，并用头部在该回合移动的位置覆盖下一个位置。

你刚刚覆盖的地方？那是尾巴所在的地方，你不再需要它了。

如果蛇长大，事情会变得有点棘手，但不会太多。

（正如 NPE 所指出的，数据结构是一个循环缓冲区。）

于 2013-09-23T18:59:50.713 回答
0 
int front, back, length; // 0<=front,back<length

increaseLength()
{
   back--;
   if(back<0)
      back=length-1;
}

goForward()
{
   front++;
   back++;
   if (front==length)
      front=0;

   if (back==length)
      back=0;
}

checkFull() // check every time you increase length
{
   if (back==front)
      return true;
   return false;
}
于 2013-09-23T19:04:13.550 回答
0

NPE 认为循环缓冲区是最佳解决方案是正确的。这是一个使用 C++ 的循环缓冲区的简单示例。注意模数运算符而不是if测试。

#include <iostream>

int main(int argc, char **argv)
{
    int front = 4;
    int back = 0;
    int length = 10;
    int snake[10] = { 1,1,1,1,1,0,0,0,0,0 };

    for (int i = 0; i < length * 3; i++)
    {
        for (int j = 0; j < length; j++)
            std::cout << snake[j] << " ";
        std::cout << std::endl;

        snake[back] = 0;
        front = (front + 1) % length;
        back = (back + 1) % length;
        snake[front] = 1;
    }
}

输出：

1 1 1 1 1 0 0 0 0 0
0 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 1 0 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 0 1 1 1 1 1 0
0 0 0 0 0 1 1 1 1 1
1 0 0 0 0 0 1 1 1 1
1 1 0 0 0 0 0 1 1 1
1 1 1 0 0 0 0 0 1 1
1 1 1 1 0 0 0 0 0 1
1 1 1 1 1 0 0 0 0 0
0 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 1 0 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 0 1 1 1 1 1 0
0 0 0 0 0 1 1 1 1 1
1 0 0 0 0 0 1 1 1 1
1 1 0 0 0 0 0 1 1 1
1 1 1 0 0 0 0 0 1 1
1 1 1 1 0 0 0 0 0 1
1 1 1 1 1 0 0 0 0 0
0 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 1 0 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 0 1 1 1 1 1 0
0 0 0 0 0 1 1 1 1 1
1 0 0 0 0 0 1 1 1 1
1 1 0 0 0 0 0 1 1 1
1 1 1 0 0 0 0 0 1 1
1 1 1 1 0 0 0 0 0 1

请注意输出如何很好地展示了蛇在缓冲区中“移动”。

于 2013-09-23T19:29:07.057 回答