點算法陣列

Question

我在設計一個算法時會遇到麻煩，這個算法幾乎可以像在蛇遊戲中一樣使用一個數組來保存線上的所有點。我會做類似...

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

但是這會發生多次，每秒很慢。我想過做類似的事情，但不是每次都移動每個數字，而是保持在數組中的相同位置，但保存一個int以跟蹤哪一個將被刪除，哪一個將包含新的數字。 如果您有任何想法我剛剛說過，請幫助我。謝謝

Answer 1

使用circular buffer。這可以使用一個數組和兩個索引（頭一個，尾一個）來實現。如果蛇總是具有相同的長度，則可以使用單個索引逃脫。

有了這樣的結構，您需要的整個操作可以在恆定時間內完成（即與陣列的大小無關）。

Answer 2

你認爲每次移動所有塊都很慢是正確的。

有一個更有效的方法來做到這一點。

只有最後一個位置的第一個位置隨着每個移動而改變。

所以，如果你有你的蛇array[i]和「頭」標記head那麼你可以簡單地行軍head通過您的陣列並覆蓋在頭部感動，又將下一個位置。

你剛剛被重寫的地方？那是尾巴的地方，你不再需要它了。

如果蛇長大，它會變得有點棘手，但不會太多。

（的數據結構，如NPE指出的，是環形緩衝器。）

Answer 3

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; 
} 

Answer 4

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 

通知輸出如何很好地說明了蛇 「移動」 通過緩衝器。