Allegro.cc - Online Community
Post Reply

Allegro.cc Forums » Programming Questions » [A5] How to implement smooth tile based movement

Credits go to Edgar Reynaldo and MikiZX for helping out!
rss feed Print
[A5] How to implement smooth tile based movement
wixy00
Member #17,122
September 2019

Hi, I've been searching for a good way to implement smooth tile based movement to my Snake game. For now I'm using something along those lines:

#SelectExpand
1void UpdateSnake(Snake *snake, float timeStep) 2{ 3 if (snake->animationTime == 0.0f) 4 { 5 snake->animationOrigin.x = ((int)snake->head->position.x / CELL_SIZE) * CELL_SIZE; 6 snake->animationOrigin.y = ((int)snake->head->position.y / CELL_SIZE) * CELL_SIZE; 7 } 8 9 snake->animationTime += timeStep; 10 11 float f = snake->animationTime * snakeSpeed; 12 13 if (f >= 1.0f) 14 { 15 snake->animationTime = 0.0f; 16 f = 1.0f; 17 pressSignal = false; 18 } 19 20 if (direction == 3) //RIGHT 21 { 22 snake->animationDestination.x = snake->animationOrigin.x + CELL_SIZE; 23 snake->animationDestination.y = snake->animationOrigin.y; 24 } 25 26 if (direction == 2) //LEFT 27 { 28 snake->animationDestination.x = snake->animationOrigin.x - CELL_SIZE; 29 snake->animationDestination.y = snake->animationOrigin.y; 30 } 31 32 if (direction == 1) //UP 33 { 34 snake->animationDestination.x = snake->animationOrigin.x; 35 snake->animationDestination.y = snake->animationOrigin.y - CELL_SIZE; 36 } 37 38 if (direction == 0) //DOWN 39 { 40 snake->animationDestination.x = snake->animationOrigin.x; 41 snake->animationDestination.y = snake->animationOrigin.y + CELL_SIZE; 42 } 43 44 snake->head->position.x = Lerp(snake->animationOrigin.x, snake->animationDestination.x, f); 45 snake->head->position.y = Lerp(snake->animationOrigin.y, snake->animationDestination.y, f); 46}

It seems like this method is not very efficient and the movement might be jerky, at least for me.
It would be great if someone could provide some examples of good way to implement it.

Source code

MikiZX
Member #17,092
June 2019

I've tried your game on my PC and printing out the f values (defined on line 11) during the game loop it becomes apparent that the value of f is set abruptly to 1.00 ever so often.
I would not use Lerp for calculating the position as this would interpolate between two fixed points (and void any 'surplus' movement that definitively appears).
I'll try to explain by example. If your rectangle is moving by steps of 0.3 (f=0.3) then you are getting this:
step1: 0.0
step2: 0.3
step3: 0.6
step4: 0.9
step5: 1.0 (when in fact the rectangle should be moved beyond the Lerp range by 0.2).

So in fact by setting the f to 1 (in cases when it should be larger than this) you are instructing the rectangle to sort of pause at certain points and this is what breaks the smooth movement.

I hope this helps. If I was to program this movement I would simply multiply the direction by time elapsed, add this to the actual position and do a kind of line sweep between the old and the new position to determine which tiles I have moved over (for cases where the snake would cross multiple tiles in a single game loop step) so these tiles could be added to the snake's tail.

wixy00
Member #17,122
September 2019

I'm not sure if I understand your idea correctly but wouldn't movement not be aligned to the grid then? By interpolating between two fixed points I'm sure that it will be aligned properly.

MikiZX
Member #17,092
June 2019

I see your point. The possible solution to this that I can see, while keeping the Lerp, is to keep any eventual value, of 'f' variable, above the 1.0 in a new variable and include this new variable in the next f value calculation that will occur (at next step of game loop)?

Possibly something like this:

  float f = old_f_value+snake->animationTime * snakeSpeed;

  if (f >= 1.0f)
  {
    snake->animationTime = 0.0f;
    old_f_value=f-1.0f;
    f = 1.0f;
    pressSignal = false;
  }
  else
  {
  old_f_value=0.0f;
  }

p.s. Sorry, I have not tested this yet so no guarantee it works.

wixy00
Member #17,122
September 2019

So I tried your method and now movement is actually more choppier than before.

MikiZX
Member #17,092
June 2019

Sorry to hear that. Bump from my end then.. :(

Edgar Reynaldo
Member #8,592
May 2007
avatar

Think about what you're actually doing. Clipping 'f' is essentially setting a maximum speed.

And then interpolating between the current tile and the next is effectively limiting the speed to one tile per update.

You should be able to animate anything with any time delta, simply based on the snake speed.

Drop the lerp, and drop the 1 tile per frame limit and set it to the snake speed.

Then adjust your collision detection to use a sweep check as advised above. This is easy because you're sweeping an AABB along an axis, so it remains an AABB. And it's only in one direction so calculating the intercept time with an object rectangle like the snake's food or body segments is easy.

Just a note, in the original snake game, it starts off very slow and gradually increases speed. As well, the snake gains a body segment for every fruit or two or three that it eats. So the game is still slightly incomplete at this point.

MikiZX
Member #17,092
June 2019

This problem got me interested enough to write the movement function myself. It works OK though it is probably not the most elegant way of making this work. If you with to try it, the function is:

#SelectExpand
1unsigned char old_direction; 2 3void UpdateSnake(Snake *snake, float timeStep) 4{ 5 6 float f = timeStep * snakeSpeed; 7 8 snake->animationOrigin.x = (int)snake->head->position.x- (int)snake->head->position.x%CELL_SIZE; 9 snake->animationOrigin.y = (int)snake->head->position.y- (int)snake->head->position.y% CELL_SIZE; 10 11 // process fast movement in 1 tile increments (collision detection sweep) 12 while (f > 1.0f) 13 { 14 15 if (direction == 3) //RIGHT 16 { 17 snake->head->position.x += CELL_SIZE; 18 } 19 20 if (direction == 2) //LEFT 21 { 22 snake->head->position.x -= CELL_SIZE; 23 } 24 25 if (direction == 1) //UP 26 { 27 snake->head->position.y -= CELL_SIZE; 28 } 29 30 if (direction == 0) //DOWN 31 { 32 snake->head->position.y += CELL_SIZE; 33 } 34 35 // do collision test here (head-fruit & head-tail) 36 // do collision test here (head-fruit & head-tail) 37 // do collision test here (head-fruit & head-tail) 38 39 f -= 1.0f; 40 41 } 42 43 // process remainder of the movement (the sub-tile movement) 44 if (direction == 3) //RIGHT 45 { 46 snake->head->position.x += f* CELL_SIZE; 47 } 48 49 if (direction == 2) //LEFT 50 { 51 snake->head->position.x -= f* CELL_SIZE; 52 } 53 54 if (direction == 1) //UP 55 { 56 snake->head->position.y -= f* CELL_SIZE; 57 58 } 59 if (direction == 0) //DOWN 60 { 61 snake->head->position.y += f* CELL_SIZE; 62 } 63 64 float temp_x, temp_y; 65 temp_x = (int)snake->head->position.x - (int)snake->head->position.x%CELL_SIZE; 66 temp_y = (int)snake->head->position.y - (int)snake->head->position.y% CELL_SIZE; 67 68 // align to grid 69 if ( (direction == 3) || (direction == 2)) 70 if (old_direction == 1) 71 { 72 if (snake->head->position.y> temp_y +CELL_SIZE/2) 73 snake->head->position.y = temp_y + CELL_SIZE; 74 else 75 snake->head->position.y = temp_y; 76 } 77 else if (old_direction == 0) 78 { 79 if (snake->head->position.y<temp_y + CELL_SIZE / 2) 80 snake->head->position.y = temp_y ; 81 else 82 snake->head->position.y = temp_y + CELL_SIZE; 83 } 84 85 if ((direction == 1) || (direction == 0)) 86 if (old_direction == 3) 87 { 88 if (snake->head->position.x<temp_x - CELL_SIZE / 2) 89 snake->head->position.x = temp_x - CELL_SIZE; 90 else 91 snake->head->position.x = temp_x ; 92 } 93 else if (old_direction == 2) 94 { 95 if (snake->head->position.x>temp_x + CELL_SIZE / 2) 96 snake->head->position.x = temp_x + CELL_SIZE; 97 else 98 snake->head->position.x = temp_x ; 99 } 100 101 // do collision test here (head-fruit & head-tail) 102 // do collision test here (head-fruit & head-tail) 103 // do collision test here (head-fruit & head-tail) 104 105 snake->animationDestination.x = (int)snake->head->position.x - (int)snake->head->position.x%CELL_SIZE; 106 snake->animationDestination.y = (int)snake->head->position.y - (int)snake->head->position.y%CELL_SIZE; 107 108 if (abs(snake->animationDestination.x - snake->animationOrigin.x) >= CELL_SIZE) pressSignal = false; 109 if (abs(snake->animationDestination.y - snake->animationOrigin.y) >= CELL_SIZE) pressSignal = false; 110 111 old_direction=direction; 112 113}

Edgar Reynaldo
Member #8,592
May 2007
avatar

That's a lot of code to do such a simple thing....

#SelectExpand
1int dx = (direction == 2)?1:((direction == 3)?-1:0); 2int dy = (direction == 1)?1:((direction == 0)?-1:0); 3 4Rectangle srect = snake_rect.sweep(dt*snake_speed*dx , dt*snake_speed*dy); 5if (srect.collides_with(fruit_rect)) { 6 score += 1; 7} 8else if (...) { 9 /// Handle edges 10} 11else if (...) { 12 /// Handle snake body segments 13} 14else { 15 /// Update normally 16}

wixy00
Member #17,122
September 2019

Could you tell me what should I search to get more information about this method? It would be nice to understand your code :)

Edgar Reynaldo
Member #8,592
May 2007
avatar

Sure, let me demystify it a little bit.

#SelectExpand
1enum DIRECTION { 2 DOWN = 0, 3 UP = 1, 4 LEFT = 2, 5 RIGHT = 3 6}; 7 8struct DXY { 9 int x; 10 int y; 11}; 12 13static const struct DXY movedir[4] = { 14 {0 , 1},/// down 15 {0 , -1},/// up 16 {-1 , 0},/// left 17 {1 , 0} /// right 18}; 19 20typedef struct Rectangle { 21 double x,y,rx,by;/// left x, top y , right x , bottom y 22}; 23 24Rectangle SweepRectangle(const Rectangle& rect , double dx , double dy) { 25 Rectangle r = rect; 26 r.x += (dx>0)?0:dx; 27 r.y += (dy>0)?0:dy; 28 r.rx += (dx>0)?dx:0; 29 r.by += (dy>0)?dy:0; 30 return r; 31} 32 33/// In update loop 34 Rectangle swept = SweepRectangle(snake_head_rect , dt*snake_speed*DXY[direction].x , dt*snake_speed*DXY[direction].y); 35 if (swept.Overlaps(fruit)) { 36 /// ate some sweet fruit 37 score += 1; 38 remove_fruit(); 39 place_new_fruit(); 40 } 41 else if (swept.Overlaps(edges) { 42 /// died 43 } 44 else if (swept.Overlaps(body)) { 45 /// ate ourselves 46 } 47 else { 48 /// move normally 49 snake_head_rect.MoveBy(dt*snake_speed*DXY[direction].x , dt*snake_speed*DXY[direction].y); 50 }

Sweep just means extend the shape in its forward movement direction. Search for sweep test / sweep check , sweep collision check , etc...

This is slightly psuedocode but you should get the idea. Make an enum to store the direction, and some const data on the direction of movement for each direction by xy values and then make a rectangle struct, and fill in a couple functions like Sweep, Overlap(Edge&), Overlap(Rectangle&) and so on.

wixy00
Member #17,122
September 2019

After a while I came up with fairly simple method of calculating time which is needed to travel to the closest grid-aligned point. It's being triggered when direction has changed. Everything is nicely aligned and the movement is smooth (ofc Logic is to be fixed) but I don't know what I should do when getting close to the edges. I tried aligning to the edges - CELL_SIZE independently from pressSignal but it's hard to change direction when you've got only one frame for this ;) Any ideas?

Game.c & GameObjects.c

Edgar Reynaldo
Member #8,592
May 2007
avatar

Your logic looks sound.

If the intercept time to the edge is less than the update delta, then it has collided. You know it will only hit the edge if it is traveling towards it, and you know how far away it is, so t = dz/speed .

wixy00
Member #17,122
September 2019

Try making a turn just before the edge. This is what I don't know how to handle. Aligning to the edge - CELL_SIZE doesn't seem to help at all probably because it happens only in one tick before colliding. Sorry for misunderstending, I feel like I didn't explain it well. And by the way, is cpu usage high after launching it on your computer too?

Snake.exe

Edgar Reynaldo
Member #8,592
May 2007
avatar

The solution should be simple. Make your movement check before your update.

wixy00
Member #17,122
September 2019

I'm really close to solving my problem. However, I discovered one bug and I don't know how to solve it. Here is a short example so you can test it yourself. For example, try going down and press (almost at once) A/S and then W. Square goes directly upwards which is bad for my snake logic. How can I prevent this behaviour?

#SelectExpand
1#include <stdio.h> 2#include <stdbool.h> 3#include <math.h> 4#include <allegro5/allegro.h> 5#include <allegro5/allegro_primitives.h> 6 7#define FPS 60.0f 8#define CELL_SIZE 20 9 10typedef struct position 11{ 12 int x, y; 13} Position; 14 15typedef struct snake 16{ 17 float x, y; 18 float animationTime; 19 Position animationOrigin, animationDestination; 20} Snake; 21 22ALLEGRO_DISPLAY *display; 23ALLEGRO_EVENT_QUEUE *eventQueue; 24bool gameOver = false; 25float lastFrameTime = 0.0f, elapsedTime = 0.0f, timeSinceLastUpdate = 0.0f; 26float TimePerFrame = 1.0f / FPS;; 27Snake snake; 28bool isMovingUp = false, isMovingDown = false, isMovingLeft = false, isMovingRight = false; 29bool hasAnimationEnded = true; 30Position direction; 31Position futureDirection; 32const float speed = 300; 33 34void Setup(); 35void Run(); 36void Free(); 37void ProcessEvents(); 38void UpdateSnake(Snake *snake, float elapsedTime); 39void Render(const Snake *snake); 40void HandleInput(int keycode, bool isPressed); 41Position CalculatePosition(float x, float y); 42float CalculateTime(float x, float y, float timeStep); 43 44int main(void) 45{ 46 Setup(); 47 Run(); 48 Free(); 49 50 return 0; 51} 52 53void Setup() 54{ 55 if (!al_init() || !(display = al_create_display(800, 600))) 56 exit(EXIT_FAILURE); 57 if (!al_install_keyboard() || !al_init_primitives_addon()) 58 exit(EXIT_FAILURE); 59 60 eventQueue = al_create_event_queue(); 61 al_register_event_source(eventQueue, al_get_keyboard_event_source()); 62 al_register_event_source(eventQueue, al_get_display_event_source(display)); 63 64 snake = (Snake) { 400.0f, 300.0f, 0.0f, (Position) { 400, 300 }, (Position) { 400, 300 } }; 65 futureDirection = (Position) { 0, -1 }; 66} 67 68void Run() 69{ 70 while (!gameOver) 71 { 72 elapsedTime = (float)al_get_time() - lastFrameTime; 73 lastFrameTime = (float)al_get_time(); 74 75 timeSinceLastUpdate += elapsedTime; 76 77 while (timeSinceLastUpdate > TimePerFrame) 78 { 79 timeSinceLastUpdate -= TimePerFrame; 80 81 ProcessEvents(); 82 UpdateSnake(&snake, TimePerFrame); 83 } 84 85 Render(&snake); 86 } 87} 88 89void Free() 90{ 91 al_destroy_display(display); 92 al_destroy_event_queue(eventQueue); 93} 94 95void ProcessEvents() 96{ 97 ALLEGRO_EVENT events; 98 al_get_next_event(eventQueue, &events); 99 100 switch (events.type) 101 { 102 case ALLEGRO_EVENT_KEY_DOWN: 103 HandleInput(events.keyboard.keycode, true); 104 break; 105 106 case ALLEGRO_EVENT_KEY_UP: 107 HandleInput(events.keyboard.keycode, false); 108 break; 109 110 case ALLEGRO_EVENT_DISPLAY_CLOSE: 111 gameOver = true; 112 break; 113 } 114} 115 116void Render(const Snake *snake) 117{ 118 al_clear_to_color(al_map_rgb(255, 255, 255)); 119 120 al_draw_filled_rectangle(100, 100, 120, 120, al_map_rgb(0, 0, 0)); 121 al_draw_filled_rectangle(snake->x, snake->y, snake->x + CELL_SIZE, snake->y + CELL_SIZE, al_map_rgb(0, 0, 0)); 122 123 al_flip_display(); 124} 125 126void HandleInput(int keycode, bool isPressed) 127{ 128 if (keycode == ALLEGRO_KEY_W) 129 isMovingUp = isPressed; 130 if (keycode == ALLEGRO_KEY_S) 131 isMovingDown = isPressed; 132 if (keycode == ALLEGRO_KEY_A) 133 isMovingLeft = isPressed; 134 if (keycode == ALLEGRO_KEY_D) 135 isMovingRight = isPressed; 136 137 if (keycode == ALLEGRO_KEY_ESCAPE) 138 gameOver = true; 139} 140 141void UpdateSnake(Snake *snake, float timeStep) 142{ 143 if (isMovingUp && futureDirection.y != 1) 144 futureDirection = (Position) { 0, -1 }; 145 else if (isMovingDown && futureDirection.y != -1) 146 futureDirection = (Position) { 0, 1 }; 147 else if (isMovingLeft && futureDirection.x != 1) 148 futureDirection = (Position) { -1, 0 }; 149 else if (isMovingRight && futureDirection.x != -1) 150 futureDirection = (Position) { 1, 0 }; 151 152 if (hasAnimationEnded) 153 { 154 direction = futureDirection; 155 hasAnimationEnded = false; 156 } 157 158 float f = CalculateTime(snake->x, snake->y, timeStep); 159 160 snake->x += (speed * fabs(f) * direction.x); 161 snake->y += (speed * fabs(f) * direction.y); 162} 163 164Position CalculatePosition(float x, float y) 165{ 166 Position temp; 167 168 temp.x = ((int)x / CELL_SIZE) * CELL_SIZE; 169 temp.y = ((int)y / CELL_SIZE) * CELL_SIZE; 170 171 if (direction.x == 1) 172 temp.x += CELL_SIZE; 173 174 if (direction.y == 1) 175 temp.y += CELL_SIZE; 176 177 return temp; 178} 179 180float CalculateTime(float x, float y, float timeStep) 181{ 182 Position temp = CalculatePosition(x, y); 183 184 if (fabs(temp.x - x) > timeStep * speed || fabs(temp.y - y) > timeStep * speed) 185 return timeStep; 186 187 if (direction.x != futureDirection.x && direction.y != futureDirection.y) 188 { 189 hasAnimationEnded = true; 190 191 if (direction.x != 0) 192 return (temp.x - x) / speed; 193 else 194 return (temp.y - y) / speed; 195 } 196 197 return timeStep; 198}

Edgar Reynaldo
Member #8,592
May 2007
avatar

The solution is easy. Make it travel at least one square before allowing it to change direction, and if it tries to 'eat itself' then kill it, that's a bad move.

Here's an example to check for if the snake is eating itself (tries to move the opposite direction it is going) :

#SelectExpand
1 /// Quick check to see if the snake tries to eat itself 2 if (direction.x) { 3 if ((direction.x == 1) && isMovingLeft) { 4 // boom 5 } 6 if ((direction.x == -11) && isMovingRight) { 7 // boom 8 } 9 } 10 if (direction.y) { 11 if ((direction.y == 1) && isMovingUp) { 12 // boom 13 } 14 if ((direction.y == -1) && isMovingDown) { 15 // boom 16 } 17 }

wixy00
Member #17,122
September 2019

Okay, fixed it. Thank you for your help and patience :)

#SelectExpand
1bool during = false; 2 3void UpdateSnake(Snake *snake, float timeStep) 4{ 5 float f = CalculateTime(snake->x, snake->y, timeStep); 6 7 if (!during) 8 { 9 if (isMovingUp && futureDirection.y != 1) 10 futureDirection = (Position) { 0, -1 }; 11 else if (isMovingDown && futureDirection.y != -1) 12 futureDirection = (Position) { 0, 1 }; 13 else if (isMovingLeft && futureDirection.x != 1) 14 futureDirection = (Position) { -1, 0 }; 15 else if (isMovingRight && futureDirection.x != -1) 16 futureDirection = (Position) { 1, 0 }; 17 18 during = true; 19 } 20 21 snake->x += (speed * fabs(f) * direction.x); 22 snake->y += (speed * fabs(f) * direction.y); 23 24 if (hasAnimationEnded) 25 { 26 direction = futureDirection; 27 hasAnimationEnded = false; 28 during = false; 29 } 30} 31 32float CalculateTime(float x, float y, float timeStep) 33{ 34 Position temp = CalculatePosition(x, y); 35 36 if (direction.x != futureDirection.x && direction.y != futureDirection.y) 37 { 38 if (fabs(temp.x - x) > timeStep * speed || fabs(temp.y - y) > timeStep * speed) 39 return timeStep; 40 else 41 { 42 hasAnimationEnded = true; 43 44 if (direction.x != 0) 45 return (temp.x - x) / speed; 46 else 47 return (temp.y - y) / speed; 48 } 49 } 50 51 during = false; 52 53 return timeStep; 54}

Post Reply
Go to: