I'm trying to do exactly what this guy is doing but I think he may have less requirements than me because the answers in that post don't seem like they'd work for my game. Let me inline his algorithm so my question is easier to understand:

The easiest solution is to loop from tail to head and set the position of the current to the next segment's position, ie: segment[i].position = segment[i - 1].position

I think the key difference between our requirements is I want to move each piece less than its own width/height on every tick. For example:

Pretend these squares are aligned horizontally (I drew it unaligned because I think it makes it easier to see what's going on). The red H is where the head currently is. The red T is where the tail currently is. The black H' is where the head should be next tick. So the snake is moving right to left. If I use the algorithm described above, won't the segments overlap or start driving apart? Let me play it out step by step:

1. Create H'.position
2. T.position = H.position
3. H.position = H'.position

The result of this would bee:

What algorithm can I use to make sure that all the pieces move at the same speed and stay the same distance apart from each other?

---

I'll give my idea, but I'm skeptical of it because my research doesn't show anyone else using this:

Each segment will store it's coordinates and its direction. EG: [[50, 50, LEFT], [100, 50, LEFT]]. The head is index 0, the tail is index 1. The speed at which the snake moves is 10, even though the segments are 50x50.

Each tick I'll do this:

1. If the mouse was pressed, overwrite the nextDirection variable with the direction that was pressed. Otherwise, nextDirection is whatever it was last tick. In this example, lets assume someone pressed UP.
2. Iterate the array and apply the direction to each tick. EG: [[40, 50, LEFT], [90, 50, LEFT]]
3. Shift the directions from head to tail and set the head's new direction to nextDireciton. EG: [[40, 50, UP], [90, 50, LEFT]]
4. Repeat every tick.

Does this algorithm seem like it would work? Part of the reason I'm asking is because it's more plicated than the other guy's algorithm so I feel like I'm doing something wrong. And also, the more I think about his algorithm, the less it seems like it can work.

---

Rewording My Problem

Pretend each segment of the snake is a 20x20 pixel rectangle. Each tick, I want the head to move 5 pixels in some direction. How do I make sure all the segments stay touching each other?

@Rafe's description below in a ment is:

Consider the ordered set of locations occupied by the snake at step t, with the leftmost being the tail and the rightmost being the head: {A, B, C, D, E}. At step t+1, the ordered set of locations occupied by the snake is {B, C, D, E, F} where the tail has moved from A to B and the head has moved from E to F.

And I don't think this algorithm works because:

Yes but if the width of A = B = C = D = E = F = 20px. Shifting {A, B, C, D, E} so that it bees {B, C, D, E, F} just added 20px to the right side and removed 20px from the left side. Doesn't this mean he moved 20px, not 5px? I want to move 5px, not 20px If you're saying that's acplished with your suggestion, please explain how. I don't see it.

I'm trying to do exactly what this guy is doing but I think he may have less requirements than me because the answers in that post don't seem like they'd work for my game. Let me inline his algorithm so my question is easier to understand:

The easiest solution is to loop from tail to head and set the position of the current to the next segment's position, ie: segment[i].position = segment[i - 1].position

I think the key difference between our requirements is I want to move each piece less than its own width/height on every tick. For example:

Pretend these squares are aligned horizontally (I drew it unaligned because I think it makes it easier to see what's going on). The red H is where the head currently is. The red T is where the tail currently is. The black H' is where the head should be next tick. So the snake is moving right to left. If I use the algorithm described above, won't the segments overlap or start driving apart? Let me play it out step by step:

1. Create H'.position
2. T.position = H.position
3. H.position = H'.position

The result of this would bee:

What algorithm can I use to make sure that all the pieces move at the same speed and stay the same distance apart from each other?

---

I'll give my idea, but I'm skeptical of it because my research doesn't show anyone else using this:

Each segment will store it's coordinates and its direction. EG: [[50, 50, LEFT], [100, 50, LEFT]]. The head is index 0, the tail is index 1. The speed at which the snake moves is 10, even though the segments are 50x50.

Each tick I'll do this:

1. If the mouse was pressed, overwrite the nextDirection variable with the direction that was pressed. Otherwise, nextDirection is whatever it was last tick. In this example, lets assume someone pressed UP.
2. Iterate the array and apply the direction to each tick. EG: [[40, 50, LEFT], [90, 50, LEFT]]
3. Shift the directions from head to tail and set the head's new direction to nextDireciton. EG: [[40, 50, UP], [90, 50, LEFT]]
4. Repeat every tick.

Does this algorithm seem like it would work? Part of the reason I'm asking is because it's more plicated than the other guy's algorithm so I feel like I'm doing something wrong. And also, the more I think about his algorithm, the less it seems like it can work.

---

Rewording My Problem

Pretend each segment of the snake is a 20x20 pixel rectangle. Each tick, I want the head to move 5 pixels in some direction. How do I make sure all the segments stay touching each other?

@Rafe's description below in a ment is:

Consider the ordered set of locations occupied by the snake at step t, with the leftmost being the tail and the rightmost being the head: {A, B, C, D, E}. At step t+1, the ordered set of locations occupied by the snake is {B, C, D, E, F} where the tail has moved from A to B and the head has moved from E to F.

And I don't think this algorithm works because:

Yes but if the width of A = B = C = D = E = F = 20px. Shifting {A, B, C, D, E} so that it bees {B, C, D, E, F} just added 20px to the right side and removed 20px from the left side. Doesn't this mean he moved 20px, not 5px? I want to move 5px, not 20px If you're saying that's acplished with your suggestion, please explain how. I don't see it.

• javascript
• algorithm
• canvas
• coffeescript

Share Improve this question Follow edited Jun 20, 2020 at 9:12 CommunityBot 111 silver badge asked Jun 4, 2013 at 18:37 Daniel KaplanDaniel Kaplan 67.6k5757 gold badges268268 silver badges403403 bronze badges 2

• What do you expect to happen when it turns? If they're moving less than the length of a segment, you're going to have them not line up correctly around a turn. – Aaron Dufour Commented Jun 4, 2013 at 20:53
• @AaronDufour That's fine. If the algorithm works, they'll straighten out if you go straight for a long enough direction, right? – Daniel Kaplan Commented Jun 4, 2013 at 20:57

Add a ment  | 

5 Answers 5

Sorted by: Reset to default 3

I know you're ignoring the grid but what about making the distance the snake moves forward some number that factors your big block size evenly?

Let's say that you're moving forward only half of the width/height of your block.

Now you can optimize a bit.

• Start a counter, n, that runs throughout the game.
• Display the blocks that prise the snake (n = 0). Let's call this snake_even.
• Next move (n = 1), create the blocks that prise the next snake by moving them all forward 1/2 unit. Let's call this snake_odd.
• For all subequent moves, you display either snake-even or snake_odd, but you can create snake_even(n+2) from snake_even(n), or snake_odd(n+2) from snake_odd(n) just by changing the head to the new position and writing over the tail.
• Whenever the snake eats something, add the length to whichever snake_xxxx you're on, and then add the length to the other one.

If you want to move forward only 1/5th of the height, you'd do the same thing, but you'd have five arrays to keep track of instead of two.

Additional info based on your added example (20x20 px segments moving 5 px each step):

Take a 4-segment snake moving to the right. Segment sizes are 20x20 px, and they move 5 px per move. I'll define the snakes as a list of coordinates (x, y). I'll mark the head with 'H' and the snake will cycle by moving right in the list, cycling back to the beginning if needed.

// n = 0
snake_0 => H(60, 0), (40, 0), (20, 0), (0, 0)

// Snake is moving to the right.
// n = 1 -- construct snake_1 from snake_0 and display that one (n % 4 = 1)
snake_1 => H(65, 0), (45, 0), (25, 0), (5, 0)

// n = 2 -- construct snake_2 from snake_1 and display that one (n % 4 = 2)
snake_2 => H(70, 0), (50, 0), (30, 0), (10, 0)

// n = 3 -- construct snake_3 from snake_2 and display that one (n % 4 = 3)
snake_3 => H(75, 0), (55, 0), (35, 0), (15, 0)

// n = 4 -- Now just move the head, and re-use all but the tail of snake_0
snake_0 => (60, 0), (40, 0), (20, 0), H(80, 0)

// n = 5
snake_1 => (65, 0), (45, 0), (25, 0), H(85, 0)

// n = 6
snake_2 => (70, 0), (50, 0), (30, 0), H(90, 0)

// etc.

Now one thing I forgot to take into account was the direction each segment needs to move. That could be stored right alongside the coordinate. But I think that part you probably understand already.

Here's how I implemented this algorithm:

Basically, I created a Segment class. Each one has a list of pivots. Whenever the head changes direction, I populate the list of pivots in each of the segments. Whenever a segment collides with a pivot, it changes to the direction of the segment in front of it. I then remove that pivot from it's list.

The one downside is you've got to make it so the snake moves by a factor of its own size, otherwise it won't collide with the pivot.

so, the snake's head moves freeform, and You check for self-collisions?

The easiest way I see is have a list of positions of the snake head in subsequent frames, then draw the rest of segments at every k-th position from previous head positions. Then at the next frame, You append another head position to the list, and again draw the remaining segments at every k-th position.

If the snake speed is variable, You will have to also vary k, to make the snake not stretch (also possibly interpolate between the head positions). This is simple math.

In his situation, each segment just moved to where its predecessor was one tick back.

Think of the segments having a solid bar between their centers. If that isn't correct the snake will stretch and bunch up as it moves.

The difference between you and him is that he had longer solid bars so there wasn't overlap.

But if the bar is the length of a movement, each segment will just go where the previous segment was one tick ago. The head is the exception and will move the direction specified by the last mouse click.

Now ... what if the length of the bar is longer than or shorter than the length of a movement.

I think, in that case, you would have to move the head first and then move each segment so it is still the same distance from the previous segment (the one closer to the head).

The hard part is caused by the movement amount not being equal to the distance. When the head changes direction, the 2nd segment has to change both X and Y or it will not be the same distance from the head as it was.

I suggest you:

1. Calculate where the H' is. This is the position of the head after the tick.
2. Calculate the direction from T to H' and
3. move T along that vector until it is the right distance from H.

Useful part ends here ...

This Part (below here) Isn't Right

I'll leave it here because what is wrong is that it was moving the tail the same distance the head moved. What it should do is move the tail to where it is the same distance from the head as it was before. ('oneTick' isn't relevant for the tail. We should set the distance between segments at the start and use that length.)

Assume 'oneTick' is the length to move per tick. And 'direction' is UP, DOWN, LEFT or RIGHT

if (direction == UP) H'.x = H.x - oneTick;
else if (direction == LEFT) H'.y = H.y - oneTick;
... more elses for the other directions ...

ratio = (H'.x - T.x) / (H'.y - T.y);
dy2 = oneTick * oneTick / (ratio * ratio + 1);
dy = Math.sqrt(dy2);
dx = ratio * dy;

T'.x = T.x + dx; // or minus depending on direction
T'.y = T.y + dy; // or minus ...

The direction has to do with the sign of H'.y - T.y (for y) and similarly for x.

From the specification, if you consider the set of locations occupied by the snake, only the head and tail change at each step. Therefore you could use a circular buffer to represent the snake and update its position in O(1) time rather than O(n).