Tiled world with smooth movement transitions

[darkfrei]

Hi all!

Do you have good solutions how to move the object from one tile to the next one and make this transition smooth?

For example the movement system like in chess, checkers, 15 puzzle, or other such tiled games with smooth animation of movement.

[pgimeno]

Lerp.

I did that in MazezaM for LIKO-12 (that's a game distributed with the console itself). https://github.com/LIKO-12/LIKO-12/releases

[knorke]

One way would be to to store the player/object coordinates twice:
1) where the player "actually" is, use these coordinates for physics.
2) where to draw the player, in screen coordinates, only used for graphics.

In update(dt) you make the draw-coordinates slowly follow the physics-coordinates.

[RNavega]

If you're talking about movements that the program does for the user, like those automated slow movements in chess games etc, LERP as they suggested works great. You have a point A and a point B, and the object is traveling between them. LERP is executed with a formula, you should read about it in here: https://medium.com/swlh/youre-using-ler ... 579052a3c3

Code: Select all

local current_x = point_a.x + (point_b.x - point_a.x) * t
local current_y = point_a.y + (point_b.y - point_a.y) * t

Since 't' should be in the range from 0 to 1, the rate-of-change of 't' controls how fast the object will travel between the points. What should that rate be so that the object travels at a certain fixed speed in pixels per-second? You can find that by getting the distance between the points and dividing by the desired speed in pixels per-second, the result is the rate of change that 't' should have per-second.

Code: Select all

local distance = math.sqrt(
    (point_b.x - point_a.x)^2 + (point_b.y - point_a.y)^2
)

local desired_speed = 10 -- (10 pixels per-second)
local rate_of_change = distance / desired_speed

function love.update(dt)
    -- Advance t. It slowly changes from 0 to 1.
    t = t + (rate_of_change * dt)
    
    -- Check if t reached 1, if so consider the LERP ended.
    if t >= 1.0 then
        t = 1.0
        lerp_is_finished()
    end
end

If, however, you're talking about slow movements between tiles when the object is being controlled by the player, such as with a JRPG game, then you need to do it a bit differently.

You don't know when the player will release the movement key that is making the object move around. When that does happen, the object will either be at a tile center, or be inbetween tile centers.
If you want your objects to always be aligned to tile centers, then when the player releases the movement key you will have to do a corrective movement, moving the object ahead to the next tile center that's in front of them in the direction that they were traveling.
For this you need some tools, like being able to find out what tile that the object is within. If all tiles are squares then this can be found by taking the object position and dividing it by the length of the tile side.

Code: Select all

-- A tile is a square, I chose the size of 32px x 32px.
local tile_width = 32

local object_tilemap_x = object_world_x / tile_width
local object_tilemap_y = object_world_y / tile_width

From this point you can know a few things:

• (Assuming that you create all objects already centered on tiles)
• Say that object_tilemap_x results in something like "2.73". This means that the player is in column 2 (starting from zero, so it's the third column), and is 73% between the tile centers in the X direction.
• Say that object_tilemap_y results in something like "0.5". This means that the player is in row 0, and is 50% between the tile centers in the Y direction, so they're already centered, vertically.
• The object is within tile [2, 0] (the math.floor() of 2.73 and 0.5), and is moving to the right because the fractional part of object_tilemap_x is bigger than 0.5 (50%) so they crossed the tile center to the right, and are between columns 2 and 3.

To do the corrective movement to place the object on the tile centers of [3, 0], you can do either of these things:

1. Use LERP with the fixed speed (fixed rate-of-change) set to the same speed that the object was moving with, so the movement 'feels' the same. The object will travel from tile-center A to tile-center B.
2. Use the same movement code that you use for keyboard-controlled movement to keep moving the object in the direction that they were moving, and keep checking every frame if the object crosses tile-center B in that direction. When that happens, snap the object to tile-center B and stop the movement.

Regardless of what method you use, you need to keep track of the object state between frames, like "what they're doing for the time being". You can do this by making use of a finite state machine, which is a way to structure your code so that different actions are clearly separated and can transition from one to the next. I don't know how familiar you are with using a F.S.M., this is an amazing article explaining how it works: https://gameprogrammingpatterns.com/state.html

[Gunroar:Cannon()]

Lerp/ tweening is my best friend.

[pgimeno]

As for the formula for lerp, there are several ways to write it, and each has its advantages and disadvantages.

This formulation:

Code: Select all

return a + (b - a) * t

is close to being the best one, but it has a problem: when t = 0 the result equals a exactly, but when t = 1, it does not always equal b.

This other formulation:

Code: Select all

return (1-t) * a + t * b

does equal a exactly when t = 0 and b exactly when t = 1; however, the result is not always monotonic. This means that the function can decrease sometimes, even when it's supposed to be never decreasing. That's very visible when a = b: it should always return the same result but it actually fluctuates a lot.

The best formulation I've found so far is:

Code: Select all

return t < 0.5 and a + (b - a) * t or b - (b - a) * (1 - t)

That one is monotonic; it also equals a when t = 0 and equals b when t = 1. It has the problem that it is slower, in that it uses a comparison and thus a branch. However, most of the time the branch is predictable by the CPU's branch prediction unit.

https://math.stackexchange.com/question ... erpolation

[darkfrei]

Maybe just so? Increase the t until it will be exactly 1.

Code: Select all

-- cropped lerp
return math.max(0, math.min(1, (1-t) * a + t * b))

[pgimeno]

No, that's not a fix, even if your formulation is corrected (it's wrong as is). It's not about the range of t.

This program demonstrates that the first formula does not always give b when t = 1:

Code: Select all

local function lerp(a, b, t)
  return a + (b - a) * t
end

assert(lerp(0.2, 0.9, 1) == 0.9) -- fails
assert(lerp(1, 0.1, 1) == 0.1) -- fails

(Edit: That produces problems in games that expect the final value to be equal to the last, e.g. compare the final value to the passed value)

This program demonstrates the lack of monotonicity of the middle formulation:

Code: Select all

local function lerp(a, b, t)
  return (1-t) * a + t * b
end

assert(lerp(5, 5, 0.19) == 5) -- fails
assert(lerp(4, 5, 0.95) <= lerp(4, 5, 0.9500000000000001)) -- fails

(Edit: I've seen games produce irregular movement just for using this formulation)

The third formulation does not suffer from either problem.

There is a fourth possible formulation:

Code: Select all

local function lerp(a, b, t)
  return t == 1 and b or a + (b - a) * t
end

That one forces returning b when t = 1, but I'm not sure about whether that's desirable or even monotonic. In the Stack Overflow link I posted, a commenter said that it's guaranteed to be monotonic, but I'm not sure. I'm also worried about a possible bump in precision in that last step.

[darkfrei]

The best solution is to use the t as a part of power two, for example 1/64 of tile size for 64 steps between first and second tiles.

[RNavega]

@pgimeno thanks a lot for the insights on the variants of LERP. If I understood you right, it's okay to freely use the optimized form (a + (b-a) * t) in your game, provided that you:
1) Don't assume that the result will have the exact values of A or B, even if t is 0 or 1. It'll be extremely close (to the point of not being noticeable by the viewer), just not floating-point equal.
2) Do rely on 't' crossing the bounds of range [0.0, 1.0] to consider the interpolation finished. For instance, if the speed of the interpolation is positive, wait for t to be greater-than-or-equal-to 1.0 to consider it finished, and if the speed is negative, wait for t to be less-than-or-equal-to 0.0 to consider it finished. This way you don't have rely on the interpolated result.

The best solution is to use the t as a part of power two, for example 1/64 of tile size for 64 steps between first and second tiles.

If that's the movement speed then you defined only the distance, it's still missing the time.
Movement speed is distance over time, like "5 miles per hour", or "10 meters per second" and such.

When your game is played by many different systems there'll be systems with fast refresh rates and slow refresh rates. The only way to make sure that objects in your game move with the same speed no matter the refresh rate of the system is to use that 'dt' value that love.update() gives you, so you can scale the object speed in terms of how much time has passed.

The object has a certain speed that you chose after testing -- like that 1/64 (let's say it's pixels, so it's 1/64 = 0.015625 px).
That 'dt' value in love.update() tells you how much time in seconds has passed since the last call to that function.
So to move the object with its scaled speed for that frame, you multiply it with dt:

Code: Select all

function love.update(dt)
    myObject.x = myObject.x + (myObject.speedX * dt)
    myObject.y = myObject.y + (myObject.speedY * dt)
end

If 'dt' is big (meaning, a long time has passed since the last love.update call), then the object speed will be scaled up and the object will travel a longer step to cover for that longer time.
If 'dt' is small (not much time has passed, as usual with 60FPS, 144FPS etc), the object will travel a shorter step.