[A5] How to implement smooth tile based movement

wixy00

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{
if (snake->animationTime == 0.0f)
{
  snake->animationOrigin.x = ((int)snake->head->position.x / CELL_SIZE) * CELL_SIZE;
  snake->animationOrigin.y = ((int)snake->head->position.y / CELL_SIZE) * CELL_SIZE;
}
  8
snake->animationTime += timeStep;
 10
float f = snake->animationTime * snakeSpeed;
 12
if (f >= 1.0f)
{
  snake->animationTime = 0.0f;
  f = 1.0f;
  pressSignal = false;
}
 19
if (direction == 3) //RIGHT
{
  snake->animationDestination.x = snake->animationOrigin.x + CELL_SIZE;
  snake->animationDestination.y = snake->animationOrigin.y;
}

if (direction == 2) //LEFT
{
  snake->animationDestination.x = snake->animationOrigin.x - CELL_SIZE;
  snake->animationDestination.y = snake->animationOrigin.y;
}
 31
if (direction == 1) //UP
{
  snake->animationDestination.x = snake->animationOrigin.x;
  snake->animationDestination.y = snake->animationOrigin.y - CELL_SIZE;
}
 37
if (direction == 0) //DOWN
{
  snake->animationDestination.x = snake->animationOrigin.x;
  snake->animationDestination.y = snake->animationOrigin.y + CELL_SIZE;
}
 43
snake->head->position.x = Lerp(snake->animationOrigin.x, snake->animationDestination.x, f);
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

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

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

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

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

MikiZX

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

Edgar Reynaldo

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

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
float f = timeStep * snakeSpeed;
   7
snake->animationOrigin.x = (int)snake->head->position.x- (int)snake->head->position.x%CELL_SIZE;
snake->animationOrigin.y = (int)snake->head->position.y- (int)snake->head->position.y% CELL_SIZE;
  10
// process fast movement in 1 tile increments (collision detection sweep)
while (f > 1.0f)
{
  14
  if (direction == 3) //RIGHT
  {
    snake->head->position.x += CELL_SIZE;
  }

  if (direction == 2) //LEFT
  {
    snake->head->position.x -= CELL_SIZE;
  }
  24
  if (direction == 1) //UP
  {
    snake->head->position.y -= CELL_SIZE;
  }
  29
  if (direction == 0) //DOWN
  {
    snake->head->position.y += CELL_SIZE;
  }
  34
  // do collision test here (head-fruit & head-tail)
  // do collision test here (head-fruit & head-tail)
  // do collision test here (head-fruit & head-tail)
  38
  f -= 1.0f;
  40
}
  42
// process remainder of the movement (the sub-tile movement)
if (direction == 3) //RIGHT
{
  snake->head->position.x += f* CELL_SIZE;
}
  48
if (direction == 2) //LEFT
{
  snake->head->position.x -= f* CELL_SIZE;
}
  53
if (direction == 1) //UP
{
  snake->head->position.y -= f* CELL_SIZE;
  57
}
if (direction == 0) //DOWN
{
  snake->head->position.y += f* CELL_SIZE;
}
  63
float temp_x, temp_y;
temp_x = (int)snake->head->position.x - (int)snake->head->position.x%CELL_SIZE;
temp_y = (int)snake->head->position.y - (int)snake->head->position.y% CELL_SIZE;
  67
// align to grid
if ( (direction == 3) || (direction == 2))
  if (old_direction == 1)
  {
  if (snake->head->position.y> temp_y +CELL_SIZE/2)
    snake->head->position.y = temp_y + CELL_SIZE;
  else
    snake->head->position.y = temp_y;
  }
  else if (old_direction == 0)
  {
  if (snake->head->position.y<temp_y + CELL_SIZE / 2)
    snake->head->position.y = temp_y ;
  else
    snake->head->position.y = temp_y + CELL_SIZE;
  }
  84
if ((direction == 1) || (direction == 0))
  if (old_direction == 3)
  {
    if (snake->head->position.x<temp_x - CELL_SIZE / 2)
      snake->head->position.x = temp_x - CELL_SIZE;
    else
      snake->head->position.x = temp_x ;
  }
  else if (old_direction == 2)
  {
    if (snake->head->position.x>temp_x + CELL_SIZE / 2)
      snake->head->position.x = temp_x + CELL_SIZE;
    else
      snake->head->position.x = temp_x ;
  }
 100
// do collision test here (head-fruit & head-tail)
// do collision test here (head-fruit & head-tail)
// do collision test here (head-fruit & head-tail)
 104
snake->animationDestination.x = (int)snake->head->position.x - (int)snake->head->position.x%CELL_SIZE;
snake->animationDestination.y = (int)snake->head->position.y - (int)snake->head->position.y%CELL_SIZE;
 107
if (abs(snake->animationDestination.x - snake->animationOrigin.x) >= CELL_SIZE) pressSignal = false;
if (abs(snake->animationDestination.y - snake->animationOrigin.y) >= CELL_SIZE) pressSignal = false;
 110
old_direction=direction;

 113}

Edgar Reynaldo

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

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

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

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

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

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

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

wixy00

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

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
 /// Quick check to see if the snake tries to eat itself
if (direction.x) {
  if ((direction.x == 1) && isMovingLeft) {
    // boom
  }
  if ((direction.x == -11) && isMovingRight) {
    // boom
  }
}
if (direction.y) {
  if ((direction.y == 1) && isMovingUp) {
    // boom
  }
  if ((direction.y == -1) && isMovingDown) {
    // boom
  }
}

wixy00

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}

Thread #617918. Printed from Allegro.cc