Gameboy Development Forum

language does not matter, if we are speaking about algorythm. it may be like this:

1. you have infinite cycle in your code. every cycle you should first assign the delta values in all directions, that your character should move if there might be no collisions on it's way. those values may depend on the previous cycle, or be some constants, or table values. for example, if you have gravity downwards, you should alvays assign N to the dY value.
2. then you should check collisions on the way, as if your character actiually moved in those directions. if collision exists, then you should correct the value. If there is a floor in Y + dY, then dy = 0.
3. after all checks, you should commit those corrected delta-values to character coordinates, e.g. Y = Y + dY. if dY at the beginning of the cycle was 1 (gravity), and the floor interrupted the falling by setting dY to 0, then Y will not change, and your character continue standing.
4. move your sprite to the new corrected coordinates.
5. goto 1

you may see how this works in my "dizzy" game in the neibour topic. it is written in c, but, as i said before, it does not matter if we are speaking about algorythms.

Last edited by toxa (2020-04-08 16:49:22)

calculations that results into movements less than a pixel is a waste of resources. just calculate some objects one frame, other objects another frame, etc. it is hard to fit an entire game cycle into one vblank period, anyway.

Subpixel calculations are absolutely not a waste of resources. They serve to provide smooth movement with rounding errors below the pixel. For the game engine I am currently working on, I use 12.4 fixed-point, which has a total of 16 bits, a "pixel range" of 4096 (you'd have a hard time coming up with levels this large), and a precision of 16 units per pixel. This is reasonable (I do think that 256 units per pixel is wasteful, you don't need *that much* precision do you?)
As an added bonus, this plays particularly nice with 16-pixel metatiles, because converting from "units" to pixels is a division by 16, and further dividing by 16 amounts to a total division by 256: just grab the high byte, fam!

toxa wrote:

calculations that results into movements less than a pixel is a waste of resources. just calculate some objects one frame, other objects another frame, etc. it is hard to fit an entire game cycle into one vblank period, anyway.

I very very VERY heavily dispute this. Even a game I partially wrote that abused tile streaming was at 40% (and that's because I was doing a lot of fancy stuff) without enemy AI or collision. Another engine I'm making is at 40% when at full NPC render load (which is a fairly expensive operation given all that it does). Most commercial games, even unoptimized ones (lookin' at ya, Capcom) run below 100% CPU. This is definitely not an excuse. If anything, striving for 30 fps may make sense when doing a DMG game, since the slow CD response time creates some kind of motion blur.


Anyways, to implement physics, you definitely should follow real-world physics, as mentioned before: store position and speed for each moving actor, and apply accelerations to the speed.
The two edge cases that don't fit super well into that model are collision detection and speed caps.

Collision detection is generally handled by resetting speed along the axis that got collision after moving the actor accordingly. I came up with a different scheme I haven't had an occasion to test yet: after computing the target position, check for collision, and alter the actor's speed to match exactly the desired displacement. Example: the player is 2 pixels away from a wall, and has a horizontal speed component of 3 pixels; collision detection kicks in and sets the speed to 2 pixels/frame; then the player gets moved by exactly that, and is now flush with the wall. Assuming the wall doesn't move, the speed should be forced at 0 on the following frame.
Examples of differences are that movement against an object moving away from the actor should be smoother instead of jittery; or that "grazing" the corner of a platform doesn't kill all of the player's horizontal momentum. Idk about the pros and cons, but it sounds reasonable imo.

Speed caps are generally either hard or soft. A hard cap is looking at the speed, and capping it at a certain value. I recommend having one no matter what because collision detection algorithms tend to break at large speeds (including raycasting). My camera redraw code can only handle the camera moving at most 8 pixels per frame (because it only redraws up to one row of tiles per movement), so I also cap player speeds at that because I don't want the player to outrun the camera, this ain't Sonic! (Also, keeping the speeds low means it still fits in a byte, even with signed 4.4 fixed-point)

Soft caps are done by applying a deceleration to the player's speed, relative to the player's speed. (WARNING: since this is physics we're talking about, there's some math below. I'm doing my best to explain it clearly, including plots you can toy with, but it may be a bit difficult to follow.) In C, you'd do `actor->speed -= actor->speed * DECELERATION_FACTOR;` with that constant being, of course, between 0 and 1 exclusive. Inverse powers of two are an easy pick[1], since general-purpose division is kinda hard on the GB CPU, but dividing by 2 is as easy as shifting right.
I expressed the above in the sense of applying a deceleration force, as in real life, but you can also express it as a scaling operation:

// All following lines are equivalent, they aren't supposed to be executed in order :p
spd -= spd * f; // f being the deceleration factor
spd = spd - spd * f; // Without the shorthand operator
spd = spd * 1 - spd * f; // To make the line below more obvious
spd = spd * (1 - f); // Factorize by speed
spd *= 1 - f; // Use shorthand operator

It's not immediately obvious how this caps the speed, but you can consider that this is how real-world physics work (Ever heard of "terminal velocity"? Drop Felix Baumgartner from the sky, his friction with air will fight against gravity and bring him to that speed). Or you can do a lil' bit of math:

Let s be the actor's speed, w the acceleration applied on each frame (from walking, for example), and f the deceleration factor.
We first have the walking acceleration applied to s:
  s + w
Then deceleration applied, for which we will prefer the multiplication form since it's more convenient here:
  (s + w) × (1 - f)
And we want to know when that is equal to the initial speed, giving us the equation
  (s + w) × (1 - f) = s
⇔ s + w - sf - wf = s
⇔ w - sf - wf = 0
⇔ w(1 - f) = sf
⇔ s = w(1 - f) / f
⇔ s = w(1/f - 1)

Thus, the soft cap is the inverse of the friction factor, minus one, times the acceleration[2].
For convenience and illustration, I've plotted the gain of speed in one frame depending on the speed, for arbitrarily chosen w and f (w = 1 px/frame² and f = 1/4, but I've made it convenient to fiddle with them). You can see that the "soft cap" is where the plotted function equals 0, which you can verify to be 3 with this example.
Also notice the negative part to the right of the graph, which implies that speeds too high will also get "pulled" towards the max speed, though not instantly.

Though, there are an infinite number of values that give the same soft cap (try w = 3 and f = 1/2), so there's another factor to take into account: how fast that top speed is reached. Compare the evolution of speed with w = 1, f = 1/4 and w = 3, f = 1/2[3]: notice how the latter approaches[4] top speed much faster. Since the f coefficient is basically drag, you can infer that the smaller it is, the more actors will be dragged down. And to get an identical top speed with a higher drag, the player needs to be Usain Bolt. Note also that the value of f will affect how quickly the player slows down when it stops walking.

The "soft cap" mechanism is implemented through drag, which you probably will want in a platformer anyways; I think you should start by figuring out how fast you want the player to decelerate to set f, then tweak w to get a good top speed. You can also make those parameters dynamic (lower drag when the player is in the air or on ice, increase w when running...)


[1]: It's actually not just inverse powers of two, but any multiple of those. For example, here's how to get 5/8ths of the accumulator:

sra a
ld b, a ; b is 1/2 of a = 4/8ths of a
sra a
sra a ; We have 1/8th of the original now
add a, b ; 1/8 + 4/8 = 5/8

This has precision errors when the speed is a very low negative number (because `sra a` rounds towards $FF for negative numbers, not 0), but depending on the coefficient you chose and how the value is used, this may stabilize on its own. Otherwise, you can trap values between -5/8 and 5/8 both inclusive, and hardcode them to 0.
[2]: Actually, it's "times the acceleration times 1 frame" because otherwise the units don't match up; but for the numerical value, multiplying by 1 is meaningless, and the explanation is probably already confusing enough.
[3]: While Wolfram Alpha is able to understand the parameters when plotting functions, it has more trouble with sequences, so I put the values directly. Sorry
[4]: If we follow math strictly, there is no top speed to be reached; the sequence gets closer and closer to the limit (here 3 px/frame), but is always strictly increasing. However, computers have fixed precision (especially here with fixed-point), so the sequence will eventually stabilize in practice.

You're implying that subpixels are hard, when they really aren't. They are actually transparent; compare these two snippets that move the player by (an average of) 0.5 pixels per frame:

    ; With counters
    ld a, [wMovementCounter]
    dec a
    jr nz, .noMovement
    ld a, [wPlayer_YPos]
    inc a
    ld [wPlayer_YPos], a
    ld a, [wPlayer_YPos + 1]
    adc a, 0
    ld [wPlayer_YPos + 1], a
    ld a, 2
.noMovement
    ld [wMovementCounter], a

    ; With 12.4 fixed-point (= 2**4 = 16 subpixels per subpixel)
    ld a, [wPlayer_YPos]
    add a, 8 ; 8 subpixels = half a pixel
    ld [wPlayer_YPos], a
    ld a, [wPlayer_YPos + 1]
    adc a, 0
    ld [wPlayer_YPos + 1], a

The other difference is when rendering, where you'd take the low byte of the screen-relative position for the former, and take the low byte of that position divided by 16 for the latter. But dividing by 16 is especially easy:

    ; Assuming screen-relative position is in bc
    ld a, c
    xor b
    and $F0
    xor b
    swap a
    ; There you go!

A problem with the counter approach is that it mucks with speed; for example, if you want your player to be able to walk slowly at 0.5 px/frame, and also run at 2 px/frame, either you always have the counter active, and thus the player will alternate between not moving and moving by 4 pixels; or you store the player speed and the counter separately, which doesn't make a lot of sense, does it? Subpixels uniformize the thing, and let you manipulate speed smoothly without having to worry aboout when to use the counter when whe to use a speed.

I thus argue that subpixels aren't hard. You can abstract them away by considering them like you'd consider pixels, only the rendered world is scaled down (in this case, 16x). So they really are simple, and they're less error-prone than counters, since you only deal with them at the time of rendering; the rest of time, you deal with "units". So a tile isn't 8 pixels wide, it's 128 units wide.

If you want your camera to have linear interpolation, using pixels isn't satisfactory without some kind of hack/workaround. (Here's a good read on 2D cameras, one part deals with lerping, which can be appreciable even on Game Boy.)
Lerping is done by taking the displacement by which you want to make your camera move, and only moving the camera by a fraction of that. In pseudo-code:

displacement = target_pos - current_pos
displacement = displacement / factor // Generally a power of 2
current_pos = current_pos + displacement

This makes the camera movement somewhat smoother. Anyways, assuming a factor of 16, and not using subpixels, this would mean that the camera wouldn't budge unless the displacement is at least 16; this would create a 32-pixel "camera window" in the middle of the screen, which may or may not be desirable. Subpixels make the problem disappear.