CODEWITHSUNDEEP
arraysalgorithm
seanlossef
seanlossef

Reputation: 15

Array of points algorithm

I'm having trouble designing an algorithm that will pretty much make a line move like in a snake game using an array that holds all the points on the line. I would do something like...

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

but this will happen many times a second and it is very slow. I thought of doing something similar but instead of moving each number every time, they stay in the same position in the array but an int is saved to keep track of which one will be removed next and which will contain the new nummber. If you have any idea what I just said, please help me. Thanks

Upvotes: 0

Views: 93

Answers (4)

Carey Gregory
Carey Gregory

Reputation: 6846

NPE is correct that a circular buffer is the best solution. This is a simple example of a circular buffer using C++. Notice the modulus operators instead of if tests.

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

Output:

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

Notice how the output nicely demonstrates the snake "moving" through the buffer.

Upvotes: 0

hasan
hasan

Reputation: 24195

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

Upvotes: 0

John
John

Reputation: 16007

You're correct to think that moving all of the blocks each time is slow.

There is a more efficient way to do it.

Only the first at last positions change with each move.

So, if you have your snake array[i] and a "head" marker head then you can simply march head through your array and overwrite the next location with where the head moved that turn.

The place you just overwrote? That was where the tail was, and you don't need it anymore.

It gets a little trickier if the snake grows, but not too much more so.

(The data structure, as NPE points out, is a circular buffer.)

Upvotes: 1

NPE
NPE

Reputation: 500903

Use a circular buffer. This can be implemented using an array and two indices (one for head, one for tail). If the snake always has the same length, you can get away with using a single index.

With such a structure, the entire operation that you require can be done in constant time (i.e. independent of the size of the array).

Upvotes: 5

Related Questions