21
\$\begingroup\$

Often I will want to use a speed value such as 2.5 for moving my character in a pixel-based game. Collision detection will generally be more difficult if I do that, though. So I end up doing something like this:

moveX(2);
if (ticks % 2 == 0) { // or if (moveTime % 2 == 0)
    moveX(1);
}

I cringe on the inside every time I have to write that, is there a cleaner way to move a character with non-integer speed values or will I remain stuck doing this forever?

\$\endgroup\$
  • 11
    \$\begingroup\$ Have you considered making your integer unit smaller (eg. 1/10th of a display unit) then 2.5 translates to 25, and you can still treat it as an integer for all checks and treat every frame consistently. \$\endgroup\$ – DMGregory Dec 1 '16 at 21:25
  • 6
    \$\begingroup\$ You may consider adopting Bresenham line algorithm which can be implemented using only integers. \$\endgroup\$ – n0rd Dec 2 '16 at 0:42
  • 1
    \$\begingroup\$ This is a commonly done on old 8bit consoles. See articles like this one for an example of how subpixel movement is implemented with fixed point methods: tasvideos.org/GameResources/NES/BattleOfOlympus.html \$\endgroup\$ – Lucas Dec 2 '16 at 2:42
13
\$\begingroup\$

Bresenham

In the old times, when people were still writing their own basic video routines for drawing lines and circles, it was not unheard of to use the Bresenham line algorithm for that.

Bresenham solves this problem: you want to draw a line on the screen which moves dx pixels in the horizontal direction while at the same time spanning dy pixels in the vertical direction. There is an inherent "floaty" character to lines; even if you have integer pixels, you end up with rational inclinations.

The algorithm has to be fast though, which means that it can use integer arithmetic only; and it also gets away without any multiplication or division, only addition and subtraction.

You can adapt that for your case:

  • Your "x direction" (in terms of the Bresenham algorithm) is your clock.
  • Your "y direction" is the value you want to increment (i.e., the position of your character -- careful, this is not actually the "y" of your sprite or whatever on the screen, more an abstract value)

"x/y" here are not the location on the screen, but the value of one of your dimensions in time. Obviously, if your sprite is running in an arbitrary direction across the screen, you will have multiple Bresenhams running separately, 2 for 2D, 3 for 3D.

Example

Let's say you want to move your character in a simple movement from 0 to 25 along one of your axes. As it is moving with speed 2.5, it will arive there at frame 10.

This is the same as "drawing a line" from (0,0) to (10,25). Grab Bresenham's line algoritm and let it run. If you do it right (and when you study it, it will very quickly become clear how you do it right), then it will generate 11 "points" for you (0,0), (1,2), (2,5), (3,7), (4,10) ... (10,25).

Hints on adaptation

If you google that algorithm and find some code (Wikipedia has a pretty large treaty on it), there are some things you need to watch out for:

  • It obviously works for all kinds of dx and dy. You are interested in one specific case though (i.e., you will never have dx=0).
  • The usual implementation will have several different cases for the quadrants on the screen, depending on whether dx and dy are positive, negative, and also whether abs(dx)>abs(dy) or not. You of course also pick what you need here. You have to make especially sure that the direction which is increased by 1 every tick is always your "clock" direction.

If you apply these simplifications, the result will be very simple indeed, and get completely rid of any reals.

\$\endgroup\$
  • 1
    \$\begingroup\$ This should be the accepted answer. Having programmed games on the C64 in the 80's, and fractals on PC's in the 90's, i still cringe at using floating point wherever I can avoid it. Or course, with FPUs ubiquitous in today's processors, the performance argument is mostly moot, but floating point arithmetic still needs a lot more transistors, drawing more power, and many processors will shut down their FPUs completely while not in use. So avoiding floating point will make your mobile users thank you for not sucking empty their batteries so quickly. \$\endgroup\$ – Guntram Blohm Dec 4 '16 at 11:19
  • \$\begingroup\$ @GuntramBlohm The accepted answer works perfectly fine when using Fixed Point too though, which I think is a good way to do it. How do you feel about fixed point numbers? \$\endgroup\$ – leetNightshade Dec 6 '16 at 20:28
  • \$\begingroup\$ Changed this to the accepted answer after finding out this is how they did it in the 8-bit and 16-bit days. \$\endgroup\$ – Accumulator Dec 9 '16 at 5:34
26
\$\begingroup\$

There is a great way to do exactly what you want.

In addition to a float velocity you'll need to have a second float variable which will contain and accumulate a difference between real velocity and rounded velocity. This difference is then combined with velocity itself.

#include <iostream>
#include <cmath>

int main()
{
    int pos = 10; 
    float vel = 0.3, vel_lag = 0;

    for (int i = 0; i < 20; i++)   
    {
        float real_vel = vel + vel_lag;
        int int_vel = std::lround(real_vel);
        vel_lag = real_vel - int_vel;

        std::cout << pos << ' ';
        pos += int_vel;
    }
}

Output:

10 10 11 11 11 12 12 12 12 13 13 13 14 14 14 15 15 15 15 16

\$\endgroup\$
  • 5
    \$\begingroup\$ Why do you prefer this solution over using float (or fixedpoint) for both velocity and position and only rounding the position to whole integers in the very end? \$\endgroup\$ – CodesInChaos Dec 3 '16 at 15:46
  • \$\begingroup\$ @CodesInChaos I don't prefer my solution over that one. When I was writing this answer I didn't know about it. \$\endgroup\$ – HolyBlackCat Dec 3 '16 at 17:41
16
\$\begingroup\$

Use floating values for movement and integer values for collision and rendering.

Here's an example:

class Character {
    float position;
public:
    void move(float delta) {
        this->position += delta;
    }
    int getPosition() const {
        return lround(this->position);
    }
};

When you move you use move() which accumulates the fractional positions. But collision and rendering can deal with integral positions by using the getPosition() function.

\$\endgroup\$
  • \$\begingroup\$ Note that in case of a networked game, using floating point types for world simulation might be tricky. See e.g. gafferongames.com/networking-for-game-programmers/…. \$\endgroup\$ – liori Dec 3 '16 at 17:20
  • \$\begingroup\$ @liori If you have a fixed point class that acts like a drop-in replacement for float, doesn't that mostly resolve those issues? \$\endgroup\$ – leetNightshade Dec 6 '16 at 20:26
  • \$\begingroup\$ @leetNightshade: depends on the implementation. \$\endgroup\$ – liori Dec 7 '16 at 13:34
  • 1
    \$\begingroup\$ I would say the issue is non existent in practice, what hardware capable of running modern networked game does not have IEEE 754 floats??? \$\endgroup\$ – Sopel Dec 8 '16 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.