Some floor and obstacle types now support custom surface arrays with linear interpolation.
This month, I finished a teardown and rewrite of the collision and platforming systems that I started in February. I committed to a pseudo fixed-point coordinate scheme so that sub-pixel positions can be represented with whole numbers (or more specifically, so that hitbox edges can be calculated without interference from floating point rounding.) Along the way, I added a new kind of platform actor, and an optional, heightmap-like surface mode for actor-based one-way floors/walls/ceilings (pictured above.) I also changed the rendering code to offset entities and the camera position by 0.5, so that they round to the nearest pixel.
While these changes are more or less good to go on the core codebase side, converting existing actor scripts and toolkits has turned out to be more work than expected. I wanted to wrap up these changes by the end of March, but I probably won’t get it done until mid-April.
Refactoring Collision + Platforming Code
I refactored the project’s low-level collision code, and how the platforming toolkit uses collision functions. It’s always been a bit iffy, especially when it comes to checking the right and bottom sides of axis-aligned rectangles. I really didn’t want to do this (again), because it totally killed my momentum, but 1) after adding barricade actors, the platforming state got too complicated for me to follow, and 2) small errors in the foundational intersect + resolve code have been the root cause of so many weird problems. The catalyst for this was realizing that no in-game hitbox was capable of standing flush with tilemapped walls to the right: there was always a one-pixel gap. That’s just wrong.
I sat down with a pen and paper and sketched out what I wanted to support. Item 1: Consider an actor with a 16×16 hitbox, surrounded by eight 16×16 obstacle tiles. The actor has zero gravity and is remaining still, and the tilemap is also not moving. In this state, the actor should never be considered bumping into any of the tiles, even though its right X coordinate is the same as the left X coordinate of the third column of blocks (and its bottom Y is the same as the 3rd row’s top Y.)
Nothing moving, nothing overlapping.
If the actor moves the tiniest amount possible to the right, then it should bump into the 3rd column of blocks, and its position should be corrected such that its right X is once again the column’s left X. The same applies to the other three directions. Visually, there should not be any gaps between the actor box and the tiles it is adjacent to.
Item 2: Consider two actors with tall, pillar-like hitboxes, with the same Y position, and X positions spaced apart by an arbitrary amount (say, 32 pixel units.) Between these actors is a smaller actor, which is adjacent to but (for our purposes) not considered overlapping either pillar (so the center square’s left X is the left column’s right X, and its right X is the right column’s left X.)
Every tick, all three actors are shifted to the right by an arbitrary amount. If this amount is a whole number, then all three actors move without any intersections occurring. If the amount has a fractional part, like 0.1, then we occasionally see intersection events due to rounding.
Moving 1 pixel per tick in this game is very fast: such an actor will travel the breadth of the screen in about two seconds, so while that wouldn’t exhibit the transient collision problem, it’s not really suitable as the “slowest possible” speed.
Item 1 represents the game’s overall intersection and positioning problems, and item 2 represents accumulating floating point error.
I considered two options for fixed point positioning:
- A) Blow up the numbers so that one pixel unit maps to a power-of-two number, like 256 or 65536
- B) Store sub-pixel positions as a separate set of variables (self.x_part, self.y_part?) and increment the real XY variables when the sub-positions are beyond a certain range
I ended up going with option A, using a sub-pixel range of 4096. Double-precision floating point can store integer values up to 2^53, and most of that range is never going to be used in a pixel art game, so I might as well take advantage of it. Additionally, the game should be able to cope with non-integer values sneaking into coordinates without totally breaking.
I ended up also incorporating option B in a few select cases, namely platforming devices which other actors may stand on. Storing the sub-pixel position in a separate pair of variables and moving by discrete chunks reduces the appearance of jitter when the standing actors are not aligned with the platform, which is most of the time. More on this later.
Dealing with Item 1
One of the first things I did was remove some positioning shortcuts, which might have resulted in differing values depending on how they were rounded as doubles. Changing things like:
local x1 = self.x - self.w*0.5 local x2 = x1 + self.w
To:
local x1 = self.x - self.w*0.5 local x2 = self.x + self.w*0.5
I don’t know if this was really causing issues in my specific case, but a quick test showed that ‘x2 = x1 + self.w’ did not always give the same result as ‘x2 = self.x + self.w*0.5’ when incrementing X by a sub-integer amount. I decided it’d be best to standardize these expressions until I get a chance to deal with item 2.
I went through the collision functions and removed various “helpful tweaks” that I had added over time to bandage over problems. One nasty thing in particular: adding and subtracting an “airgap” constant value. I used this for positioning things next to each other with a very small bit of spacing (like 0.0001) so that they would be close but not considered overlapping. For example, if an actor bumped into a wall at X 16, its right side would become X 15.9999. This was why nothing could stand directly next to walls to the right. I hadn’t noticed because most of my hitboxes are smaller than their associated sprites. I just assumed the hitbox visualizer had a positioning bug until I started looking deeper into it.
I removed airgaps from actor-to-actor positioning code, but still needed a tiny number for comparing right/bottom positions against tilemap tiles. This was necessary until I could switch the positioning system over to whole numbers, at which point I could replace them with ‘minus one’.
The next thing was to ensure that collision functions were using the correct comparison operators. To allow things to be close together with no gaps, I needed ‘>’ and ‘<‘. To detect if an actor is standing on a floor, I needed ‘>=’ instead. No weird stuff like the actor sticking a tiny bit into the floor.
When doing big platforming code restructuring / bug-hunting, I find it helpful to replace the player actor with a simplified version. No animations, no attacks, no damage. Basically just a rectangle that can jump. Using this stand-in, I worked through the platforming tick function and tried to make each step more sensible.
I refactored code which queried multiple positions in a tilemap. Previously this code called functions which did bounds checking and flooring for every call. I wrapped the safety operations in the calling function, and made “unsafe” versions of the called functions, which take input that should already be validated. I don’t know if this makes much of a performance difference, but it is easier to follow. I also cleaned up a lot of iffy tile position and angled surface interpolation code. I think it’s a pretty common phenomenon to be dumbfounded by some of your own past programming choices. Some of my expressions were flat-out wrong, and I’m surprised that certain features related to angled surfaces worked at all.
I had several booleans for representing an actor’s current ‘grounded’ state, and what kind of floor they could connect to: on_solid for flat tiles, on_slope for sloped tiles, on_plank for fall-through tiles, and on_ext for standing on top of another actor. ‘grounded’ would be true at the end of the platformer tick function if any of these bools were true. This started organically, when I first added slopes to the engine, and just kept getting worse with each new platforming feature.
The thing is that all of these grounding sub-states were mutually exclusive. So I did that horrible thing again where I cram all of these states into one variable: grounded. This introduced some subtle bugs, and I got very close to throwing up my hands and undoing the changes. I’m glad I didn’t, because it led to me stepping through all of the foot-to-ground code and finding things that could be simplified.
Environment tiles can have special attributes for representing things like conveyor belts. I was attempting to detect these tiles after the fact, with another map query at the end of the function. It makes more sense to cache the tile definition of the first ground connection, and pass that onto code that handles things like conveyors.
Detour 1/3: Fixing Blocking Actor Collision Handling
I realized while working on this that blocking actors have a substantial shortcoming: I dealt with actors moving into blocks and pushing them back out on each axis independently, but I didn’t consider situations where the blocking actor is the one moving. So now actors push themselves out of blocks, and blocking actors also push actors out of the way when they move, on both axes independently.
Actors correcting themselves against blocks:
Old blocking behavior, not accounting for block movement:
New blocking behavior:
Detour 2/3: “Board” Actors
Another variation on blocking actors. To keep this straight:
- Blocking actors behave like rectangular obstacles. Actors treat collisions with them as if they collided with the tilemapped environment (or at least, it’s supposed to be similar.)
- Blocks can block on their top, bottom, left and right sides independently. This is intended to reduce collision conflicts for blocks which are supposed to terminate against other kinds of obstacles, like barriers that obstruct to the left and right, but connect to a floor and a ceiling.
- Barricades are like blocks, except that they can only be an obstacle in one direction at a time: up, down, left or right. As this actor only ever deals with one axis, it’s easier to implement sloped barricades via right triangle subshapes than it would have been with blocks.
- Boards are a new implementation of floating platforms. They work similar to barricades, except that while touching any piece of a barricade counts as a collision, boards only consider a thin sliver of their hitbox. Actors may jump up through the board and land on it, and fall down depending on their configuration.
I need boards because the existing floating platform stuff doesn’t quite use the same collision detection logic as blocks/barricades, and I want these devices to all behave consistently.
Detour 3/3: Arbitrary Surfaces for Barricades and Boards
This is mainly for boards (to be honest, it’s 90% of the reason why I made boards in the first place), but I decided to make it work with barricades as well.
These surfaces are heightmap-like tables with an arbitrary number of points. The array is mapped to hitbox dimensions, and the point of collision is determined by interpolating the actor’s center coord against the two closest array values.
There are two interpolation modes: linear and left-neighbor. The latter doesn’t feel right most of the time, but might be useful in some special cases with floors.
Here is a left-facing barricade with six surface points, arranged in a moving sine wave pattern.
This should offer some flexibility in designing levels. Some surface ideas:
Dealing with Item 2
This one went a lot rougher. What variables should be scaled, and when? Should scaled positions and dimensions be cached so that they’re easy to grab and use as part of expressions? How do I pass the scaling amount to each source file that needs to know it? When is the scaling amount defined: at build time, at run time? What if a chunk of code attempts to scale something before the scale is set? Which source files dealing with positions and dimensions are capable of functioning without knowledge of the scaling amount?
It’s probably best to make such a change close to the beginning of a project, because it touches so many aspects of the codebase. Like with item 1, I came very close to backing out of the changes, but concerns about floating point rounding when determining the edges of hitboxes compelled me to follow through.
Scale coordinates at build time, start-up time, or on-demand?
I considered using the macro system I wrote in February for injecting coordinate-scaling constants into the code, but source files need to have a special directive in order for the preprocessor to do anything with it, and every additional file touched by the preprocessor slows down build time.
I ended up putting the value in a core file, coord_sys.lua, and using require() to pull in the value in any core/toolkit source file that needs it. I added a self:getCoordScale() method for actors so that I don’t have to require() that file in every other actor script.
Many things need scaling, so I made a different source file to do the grunt-work of scaling up positions and dimensions in maps, geometric shape objects, spawn points, and actor templates, after those things have been loaded into the engine, and before program control is handed over to the game project. This catches a lot of stuff, but doesn’t fix actor velocity assignments or ad hoc changes to dimensions, which I need to hunt down and modify by hand.
When rendering objects now, I have to divide the incoming XY coords and WH dimensions by the coord-scale. Sprite coordinates, dimensions and offsets are not scaled. Viewport position and dimensions are also not scaled, but viewport scrolling offsets are, since they are so often tied to the position of an actor. Tilemaps store two copies of tile width and height: one in scaled form, and the other in pixels.
Interpolated angled surfaces also need to be floored, or else you risk getting non-integer positions when actors collide against them. Ditto for any velocity numbers that are multiplied or divided, like (self.xvel = self.xvel * 1.01).
While it’s more or less working on the core side, I still have about 200 actors to review and fix up.
Pros
- Reduce theoretical chance of rounding errors when calculating hitbox edges
- Odd-numbered hitbox dimensions become even after being multiplied by an even value, and can be halved later on without worrying about introducing decimal values
- Can slide shapes together without collisions occurring due to rounding
Cons
- Adds multiplication and division operators / wrapper functions everywhere
- Any hitbox that has fallen out of integer alignment will cause any hitbox that it collides with and position-corrects to also fall out of alignment
- Any positions that do fall out of alignment are subject to more floating point rounding error, since they’re bigger numbers
- Multiplying two scaled numbers results in an over-scaled number. You have to divide the result by the coord-scale to bring it back down.
At this point, I don’t know if it was really worth it.
Troubleshooting actor hitbox interpolation by looking at the coordinates in a chart. Flooring the value at the wrong bracket level resulted in coarse size differences.
Block+Barricade Actor Refactor
The code that dealt with collisions against blocks/barricades/boards was pretty hairy, so I worked on reducing duplicated logic. Before, blocks, barricades and boards all had their own response code, which was 90% the same. Now, we pass the block actor to one of four functions which gets the positioning and angle information for the left, right, top or bottom side. With that info, we don’t need to care (or we can care a bit less) about what kind of block or sub-shape it is, and just operate on the provided facts: the surface collision point is here, the normal vector is this, etc.
Changing Plank Designations
Planks are terrain tiles that actors may collide with selectively, depending on parameters in the terrainDef and the actor’s platformer state table. Originally, this terrain state was binary: either it was a plank or it wasn’t. I realized I’d like to have some planks that the player could jump up past but not fall back down through, so I made ‘superplanks’, a third state.
This stuff broke during my platform code refactor, and the existing logic was messy, so I got rid of the three separate states and replaced them with a bitmask:
Main Modes: 000 PLANK_NONE: No plank behavior 001 PLANK_SCAF: "Scaffolding", intended for non-player devices and machinery. 010 PLANK_NORM: Player should stand on and be able to fall through 100 PLANK_SUPE: Player should stand on, but not fall through Shared states, for the sake of completeness: 011 PLANK_SCAF_NORM 110 PLANK_NORM_SUPE 111 PLANK_ALL
I have nothing implemented for the scaffolding plank type, but it would be nice for setting up platforms that only non-player entities can stand on.
Sprite Stuff
The drawSprite() function contained a chain of about seven if-elseif blocks to handle each sprite mode, and it was getting difficult to follow. I reorganized it so that every major sprite-mode can have a separate draw function. This should simplify adding or removing sprite-modes from the codebase.
I added some per-sprite cropping parameters so that small chunks of images can be assembled and moved around independently. I threw this in rather quickly, and being based on love.graphics.setScissor(), it doesn’t respect transformations like scaling or rotation.
I got rid of “frame chunks”, where each animation frame could have multiple quads associated with it, each with their own offsets. I added this back in January 2020, but basically never used it outside of some quick tests. My rationale was that it would help with designing large entities with repetitive graphical components, such as tower-like obstacles. Since then, the engine now supports multiple independent sprites per actor, and this is far more flexible than embedding additional read-only quads into frameDefs.
I don’t remember if this was intentional or an oversight, but sprites displaying tile art didn’t support displaying animated tiles. I got that working while doing some other cleanup.
I changed sprite flipping and mirroring parameters from boolean true/false to -1/+1. This replaces a couple of if branches with multiplication in the sprite render function. Not sure if it makes any difference. It probably doesn’t.
Sprite Offsetting
Made some changes to how sprite offsets work in two areas.
First: I’m now offsetting all sprite rendering by +0.5, +0.5. This removes a top and left bias. Before, when a creature was at an exact coordinate like 64, 64, and moved very slowly to the right (say 0.1 pixels per second), it would take a few ticks for the sprite to snap to the next pixel column. However, if that same actor moved very slowly to the left from 64, 64, then it would immediately snap one pixel left. Now, it takes an equal or near-equal amount of time for that actor to cross pixel boundaries.
Take this example sprite, which is 4×4 pixels in size. Assume the actor/hitbox it’s attached to is also a 4×4 rectangle. (Ignore the coordinate-scaling stuff in this example.)
In these GIFs, The semi-transparent grid represents integral positions. The big sliding cross is the actor’s center point.
Before:
After:
I think I tried to do this last month or in January, but underlying problems in the collision and positioning code got in the way. Anyways, I made this change, and somehow went for a while without noticing that the viewport scrolling offset and tilemaps also need to be offset in a similar manner, or otherwise actors and maps snap across pixel boundaries at different times, which looks awful. It took me some time to get this looking correct with parallax scrolling layers.
Second: I’ve added some offset modes to sprites to simplify special-case placement scenarios:
- Relative to actor’s center coord (the default and previously only mode)
- Relative to actor’s previous sprite (or actor center coord if this is the actor’s first sprite)
- Relative to world. x0y0 is world origin.
- Relative to the viewport. x0y0 is the upper-left corner of the viewport.
I did this because some of the offsetting code was getting pretty hairy, now that coordinates are scaled. Offsets still do not factor into actor sprite culling, so in those cases you’d want to disable culling for that actor entirely.
Position Accumulators
Some more info on platform devices moving in discrete pixel chunks. Earlier, I made a service for these types of actors to allow them to move without separate accumulators while also shifting their cargo by discrete pixel amounts. Visually, this looked right, but I neglected to consider a pretty big problem with how edges are dealt with.
Before the cargo service. If the platform and cargo were aligned, everything looked OK:
If they were not aligned, you’d get jitter due to passing pixel column boundaries at different times. This is technically correct behavior, and less noticeable at higher resolutions, but at 480×270 it’s rather distracting.
Cargo shifting without an accumulator for the platform’s sub-pixel position. This is done by comparing the platform actor’s previous per-pixel position against its current position. If these values aren’t equal, then the cargo is shifted by the difference.
Now here’s the problem I didn’t consider. What if the actor is teetering on the edge of the platform? The cargo could be shifted beyond the horizontal bounds of the platform, causing it to fall off.
Now, with the accumulator. It doesn’t matter what alignment the cargo has, and it’s not going to get booted off the edge as a result of the shifting code.
Redrawing the player’s legs
I realized that the new collision and sprite offsetting code makes the player look like he’s hovering over ledges by one pixel column. I widened the gap between his feet, and thickened his legs a bit. It was either that or make the hitbox narrower, but it’s already pretty narrow as it is. I planned to make his shoes larger as well, but it’s difficult to find a good shoe shape which can be rotated slightly as part of the walking frames.
The new idle stance, in turn, looked a little off when on sloped floors, so I made an additional idle stance with the legs closer to the bottom-center point for those cases. It kind of looks like he needs to go to the robot bathroom, but it’s good enough in context.
Project Outlook
February feels like ages ago.
This game has now been broken for more than a month. Not good. I hope the changes I made are worth it. I have nothing concrete for April, just fixing up the remaining actors that have yet to be ported to the new coordinate system. I’ll post more around the end of the month, probably.
Stats
Codebase Issue Tickets: 50
Total LOC: 108210
Core LOC: 36769
Estimated Play-through Time: N/A (Still busted, pending conversion of actor code to new coordinate system.)
