The overall theme of this month has been “fighting with rectangles,” but let me start by getting a few non-rectangle things out of the way:

Non-Rectangle Stuff

Opponent Improvements

These pink guys have been in the project since the original mock up art, and in general have been the first game objects to receive ‘generic’ versions of things that were originally hard-coded for the player, like platformer physics. I have a few variations of them made to test out different gameplay ideas. The original actor object was super simple, basically just patrolling left and right and changing direction when bumping into a wall. This month, I’ve been consolidating the different versions of him into a single, slightly more versatile character. I rounded out his animation to include pivoting to turn around, and added a pouncing attack which is telegraphed with a half-second warm-up. He can also hop over small obstacles and swim underwater.

One issue I’ve had with these guys is that they sometimes group together, making it difficult to see how many of them are in one spot. I’ve added a collision check which pushes them away from each other, but only if they are both in motion horizontally and facing the same direction. If too many are colliding together, they will also start pouncing as a rough indicator of how many of them are bunched up.

Migrating Underwater Logic To Platformer Toolkit

I moved a bunch of underwater / swimming state and logic from the player to the general-purpose platformer state module. This is tedious work because the swimming code was just kind of shoehorned into the player’s tick callback, but now other actors get to share the same physics damping and wet-vs-dry sensing routines.

Target Selection and Group Affiliation

I’ve been slowly changing how opponents work so that they can select from multiple targets instead of exclusively hounding the player. Up to this point, they’ve used a function to look up the player, get a reference to the actor table, and refresh that reference on every new tick. If the player actor can’t be found, that reference becomes nil, and the opponent needs to check this before attempting to access any player data.

The player lookup function can be replaced with a function that runs a linear search through the scene’s actor table, using a callback function to evaluate each actor as a target. (This is not optimized at all, so the search construct includes a cooldown timer to prevent multiple instances from hammering the scene with linear searches every tick.) Anyways, targets can now be selected based on proximity, group affiliation, remaining HP, how long they’ve been operational, etc, instead of just “find me the player!”

Right now, I’m looking at three groups:

player: You, and maybe some helper actors which could be damaged or destroyed.
yikes: The pink dudes.
bots: The robots with the sunglasses.

All of these groups are hostile to all other groups, but generally, the Bots should prioritize the player as a target, while the pink dudes should give the player and Bots the same weight.

I had to rework how damage is exchanged, because it only considered player-to-enemy and enemy-to-player transactions. I also needed slightly different ‘defeat event’ graphics and sounds for when enemies attack other enemies, so that they don’t get mistaken for player actions.

TODO tags and issue tracking

When I notice a problem or have an idea for something in the codebase, I leave comments tagged with the word TODO followed by a priority number and quick explanation. I have too many of these now, and the codebase has grown pretty large, so I need some way to log issues outside of the codebase and to datestamp and log troubleshooting work.

I looked for some kind of desktop issue tracker, but it seems like most of them are either web services you log into or deploy yourself. Maybe I’m using the wrong keywords. For now, I’m logging issues as numbered Lua files in a separate ‘issues’ directory, using this table as a template:

local i = {}

i.status = "open"
i.name = ""
i.date = "2020/"
i.type = ""
i.sev = 
i.desc = ""
i.log = {
"",
"",
}

return i

Issue visibility is pretty bad right now. Eventually I’ll have to use something more robust, but I can at least grep the whole directory for keywords, and add the ticket numbers to relevant points in the codebase as comments.

Rectangle Stuff

Rectangle Fitting

Testing rectangle-fitting algorithms in a separate LOVE test project.

Recently, startup times for this project have been getting a bit high. I timed the engine init tasks and found a couple of functions that were taking a long time to complete: map initialization and texture atlas creation.

The map init times were long because I had recently created new, very large maps that are mostly empty, and the map initializer also performs some grunt work on them which is eventually going to be the build system’s responsibility. This should sort itself out once I move init tasks around, so no big deal.

Now the atlas init: it used a rectangle-fitting algorithm that gets less efficient with every additional sprite-frame that needs to be arranged. This was a concern when I originally started working on the atlas, but the completion time was bearable then, and I thought I would eventually migrate the arranging part of the atlas to build time. That hasn’t happened yet, and it’s beginning to stall a bit on 633 sprite frames now. Testing the algorithm with 1500 randomly-sized rectangles causes my OS to bring up the “this app isn’t responding, want me to kill it?” message box.

I made some dumb micro-optimizations and got a small speed gain of about 100 milliseconds or so, but that doesn’t actually solve the problem. I considered rearranging individual spritesheets into compacted squares at build time, then fitting whole spritesheets onto the atlas. This maybe would have helped (and I may still implement it later on), but during the process of splitting the rectangle-fitting code out of the atlas module, I found a recursive tree-based implementation in JavaScript that’s half the size and which runs near-instantaneously. I converted it to Lua and whoa, issue solved.

I had designed the atlas to place map tiles in a separate pass along the top, whereas sprites were placed near the bottom. This had issues with tiles that have different dimensions, so I merged the functions that arrange sprites and tiles into one.

Changing AABB Origin Point

Oh no what is wrong with me. Up to this point, all actor hitboxes have had their origin points in the top-left corner. If you had an actor with a 16×16 hitbox, and it was positioned at 100, 100, then its upper-left point would be at 100, 100, and its bottom-right point would be 116,116. This is good for comparing rectangle positions against other rectangles, but it gets pretty irritating higher up in the actor callback logic, where you more frequently compare actors based on their center coordinates, not their edges.

When the origin is top-left:

if actor1.x + actor1.w*0.5 > actor2.x + actor2.w*0.5 then
    actor.facing = -1
else
    actor.facing = 1
end

When it’s the center:

if actor1.x > actor2.x then
    actor1.facing = -1
else
    actor1.facing = 1
end

This is a simple example, and the branch could be collapsed into a Lua and/or one-liner, but it gets pretty gnarly when four or more centered coordinates need to be compared. The other solution I considered was to add a method to actors to assign their center position to local variables:

function methods:center()
    return self.x + self.w * 0.5, self.y + self.h * 0.5
end

-- ...

local px, py = player:center()
local yx, yy = yikes:center()

if yx > px then
    yikes.facing = -1
else
    yikes.facing = 1
end

This is a little less verbose, but if the position of either actor needs to be modified, you still need to assign to the table fields, and if you use those locals in this scope again by mistake, they will hold stale coordinates. I guess one could also make an “isRightOf(a1, a2)” kind of function.

Weighing these choices, I felt that there is likely going to be more actor callback code that needs the center coordinates than there will be low-level collision code that needs plain XYWH. I’m more likely to screw up and make a typo in that larger body of code than I am in the smaller set, and a bug in the collision code will have much higher visibility and likely get fixed or mitigated sooner than a bug in an actor callback, which might only be called in one area of the whole game.

So this is a not a quick change, and it can’t be started and then put on hold until the work is done — the game is totally busted in the meantime — so after ensuring that I made a backup of the project folder, I went through every actor callback file, and then the collision and platformer state code, and changed every line I could find that referenced an actor’s position.

I was thrilled when I launched the game again and it didn’t fail with a syntax error. However, just about everything related to platformer physics and displaying sprites relative to actor positions was broken.

Uuuuuggggggh.

I’m glad I went ahead with this change, but it was not fun to do on a project with a ton of existing stuff. I had to retest every single existing actor for issues, and I didn’t catch some problems until much later.

Fixed-Grid Spatial Partitioning

Testing partitioning of collision checks.

I started investigating this last September, but dropped it because actor-to-actor collision detection was running OK at about 100 rectangles. My current test maps have more actors spread out over wider areas now, and additionally, I’m writing actors that scan for targets by proximity, so I now have a greater need to cut down on those linear search times.

The last chapter of Game Programming Patterns gives an overview of spatial partitions. Build New Games also has an article on fixed-grid partitions that I found helpful.

There are a couple of ways to set this up and I had some difficulty picking which one to start with. You can add the actors to partition zones by their center coordinates, so that an actor exists in only one zone at a time, or you can add them to each zone that they currently overlap, taking their full width and height into account. If you do the former, then rectangles larger than half the zone dimensions will need additional handling, or else some overlaps won’t register. With the latter, you can end up iterating over the same rectangle-to-rectangle collisions if two rectangles inhabit multiple zones, and so you have to maintain a list of collisions that have already been processed.

For collision detection, I started with a points-only implementation, but the zone size would have to be at least twice as big as the biggest actor that appears on the map, and I don’t know what the tallest or widest actor in the game will be yet. Even if I never have an on-screen visible character as large as the screen, it’s still nice to be able to do things like create a one-off invisible actor as tall as the screen to serve as a trigger for a one-off event. I started over with every zone keeping track of every actor that overlaps it.

As expected, results vary depending on the actor quantity and density. I backtracked and implemented a center-point version, and its performance also varies.

In this screenshot, the majority of all creatures being tracked in the spatial partition are in two adjacent zones in the upper-left. Situations like this can be slower than just brute-force checking everything against everything else.

I implemented a second spatial partition to reduce the search time for actors evaluating targets by proxy. This one uses center points, and actors that are opted into the “targetable” service are responsible for adding, migrating and removing themselves from the zone structures.

I ended up disabling both of these to work on the next item…

Splitting Up Tilemaps

Prototyping multiple maps per scene-context in a separate LOVE test project. The rectangles represent maps, and the lines show how maps are linked together.

I went for the map chunking thing again, against my better judgement (last attempt was in March.) This time I was actually successful, but as predicted, it was a slog to convert the existing codebase over.

I broke it down into a few separate problems:

Converting the existing scene-context to support multiple map chunks
Resolving actor-to-map collisions across multiple chunks
Arranging and linking chunks together into whole areas
Activating and deactivating chunks based on player location or presence

1 and 2 are heavily interdependent, and 4 can’t really be worked on until the others are in place, so I started playing around with 3 in a separate LOVE test project, using some generic rectangle structures in place of map chunks.

I took a quick look at Tiled to see if it had any tools for arranging chunked maps. It does indeed have a ‘World’ structure that displays a map made out of several chunks as one whole, but the docs say you can’t change the layout of the chunks from the GUI. Making a separate tool just for this purpose probably isn’t worth the effort right now, so I came up with a set of functions to define ‘site’ and ‘room’ entities, and to arrange room instances within sites.

This prototype code generates the layout shown in the screenshot above:

local world = roomFit.newWorld()
local r = {}

-- Make some rooms
r[1] = world:addRoom(64, 64)
r[2] = world:addRoom(32, 32)
r[3] = world:addRoom(16, 64)
r[4] = world:addRoom(64, 16)
r[5] = world:addRoom(32, 32)
r[6] = world:addRoom(32, 32)
r[7] = world:addRoom(32, 32)
r[8] = world:addRoom(32, 32)
r[9] = world:addRoom(48, 72)
r[10] = world:addRoom(128, 16)
r[11] = world:addRoom(64, 64)
r[12] = world:addRoom(96, 16)


-- Position and link rooms
r[1]:attachRight(r[2], "top")
r[1]:attachBottom(r[7], "left")
r[1]:attachLeft(r[8], "bottom")

r[2]:attachBottom(r[3], "left")

r[3]:attachRight(r[4], "top")

r[4]:attachRight(r[5], "top")

r[5]:attachRight(r[6], "top")

r[8]:attachTop(r[9], "right")

roomFit.link(r[9], r[1], "two-way")

r[9]:attachRight(r[10], "top")

r[11].x = 96
r[11].y = 96

r[11]:attachLeft(r[12], "bottom", 0, "one-way")

This is a pain to decipher after 24 hours of having written it, but it’s not too bad as long as the number of discrete chunks in a site doesn’t exceed a half-dozen or so rooms. For a big nonlinear adventure that covers a lot of ground, you’d absolutely want some kind of visual tool to arrange the graph and anchor rectangles flush against other rectangles.

Getting the concept into the main project, it’s less bad IMO:

local my_site = mapSite.addSite("site_abcd", 256, 256)
local ra = my_site:attachRoom("room_a", 128, 0)
local rb = my_site:attachRoom("room_b")
local rc = my_site:attachRoom("room_c")
local rd = my_site:attachRoom("room_d")

ra:attachRight(rb)
ra:attachLeft(rc)
rc:attachBottom(rd)

This creates the following area built out of four small 8×8 maps:

Note: These maps are small just for testing purposes. I’m planning on rooms being 2-8 screens worth of area.

Onto problem 1: making scenes multi-map. I added a new directory to the project to hold the Lua source files that define sites, and I added a function during startup that converts all existing legacy maps to sites containing just one room. Rooms are instantiated within the scene table as scene.rooms[], and the existing scene.map reference was made to point to the first room (under the hood, rooms are pretty much the same structure as maps). I couldn’t blast scene.map right away because so many actors and other scripts depended on being able to reach into it and pull out map dimensions, tile dimensions and other things like that. In any case, this was enough to modify the scene renderer to draw each room, and to start work on problem 2: porting over collision detection code.

I hit a wall on this because of a depth-mapping feature that I added back in March. It expanded maps to support having any arbitrary number of layers, and to place actors on any layer by matching a ‘depth’ number between actor and layer. The goal was to allow actors to travel through structures that overlap other structures, like a tunnel that passes behind another area. It was complicated and not very efficient, because one small 16×8 tunnel in a larger 256×256 map would still require a full 256×256 map layer, and if every layer can be collided with, then every layer also needs a navigation mask layer (to help with platformer state.) Additionally, to make it safer to rearrange the ordering of layers in Tiled for drawing purposes, the depth number didn’t correspond to the layer’s index in the map file, but to a ‘depth’ tag in one of the layers. It was difficult to keep track of.

I went for a simpler design, where rooms have only one collision layer. They also get the depth value that individual map layers had in the previous scheme. Rooms at different depths can overlap, enabling the same kind of plane-shifting behavior as before. They no longer have to be the same map or tile dimensions, and they can be moved away from the site origin. This is way better than the previous system. I gave rooms optional background and foreground layers as well, just so that decorating levels is a bit more convenient within Tiled.

The existing environment collision checks only considered one tilemap aligned at 0,0. I added a part to the scene-running loop to build a list of which rooms each actor is overlapping, and that list is passed to higher-level “room-aware” collision functions.

I went through the existing collision functions and sorted them into two categories:

Room-level: x0y0 is the upper-left corner of the room and its tilemap.
Site-level: x0y0 is the site origin. Receives a list of rooms that the actor is overlapping, and runs room-level functions on each of them in a for loop, until one of them returns a value of interest, or the loop completes (return false / nil / ‘default terrain’). When a value is returned, a reference to the room table is also returned so that the calling code can use the room’s XY position as offsets for collision response.

If an actor is straddling two or more rooms, then the collision functions will be run once for each room. This should be OK so long as the following conditions are met:

“Hot” parts of levels — sections with complex terrain, many creatures or big boss encounters — are not situated at the seams of rooms.
No rooms at the same depth-plane overlap with conflicting terrain data. Imagine two rooms at depth level 1, with sloped hills going in opposite directions at the same tile positions, in an ‘X’ formation. What happens when an actor walks to that location? This code isn’t equipped to deal with it, and setting up tiebreaker rules to select only one room to sample from could backfire if the room you want isn’t selected for whatever reason. If the rooms stay flush against each other with no overlap, then this isn’t a problem.

There’s another issue: an actor is only be able to see tiles belonging to rooms that it currently overlaps. If an actor needs to sample tiles beyond its bounding box, like a 16×16 projectile that senses obstacle tiles 32 pixels from its center, then it won’t be able to see obstacles outside of its current room. As a band-aid, I added a room_pad value to actors, which increases the size of their bounding box for the room overlap check. So the 16×16 projectile could have a pad value of 24, making it sense rooms within a 32×32 perimeter. I’d imagine that setting this too high in too many actors could lead to overhead issues, but some kinds of objects need it to work.

I got the player colliding properly with adjacent, grid-aligned rooms, and was patting myself on the back until I realized there was a huge oversight: any room which is not grid-aligned gives the wrong collision response. The collision code expects the map to be grid-aligned and uses modulo operators everywhere (like ‘local x_mod = self.x % tile_width’). I had to go through the code and account for room offsets in every response, usually by creating a temporary set of XY coordinates offset from the room position, modifying those values, then assigning them back to the actor once the work was finished. It’s a mess, and I don’t know when I’ll get back to cleaning up and refactoring, but it seems to be holding together.

I could have cut my losses and just required that all maps be grid-aligned. (Maybe I’ll get overwhelmed and do exactly that later on.) Once a project has any higher-level content, it’s usually a bad idea to start making big changes to the low-level codebase. All that content has to be thoroughly retested, and in some cases thrown out.

Finally onto problem 4: activating and deactivating rooms. This is ultimately what I wanted out of all of these changes, but there were some sticking points about the implementation that I didn’t consider. Here are some continuity issues and how I decided to handle them:

If a room is deactivated, what happens to the actors inside of it?
- They are despawned, unless they have an override flag set.
If an actor can move from room to room, should it be despawned when the original room deactivates, or when the room it currently resides in does?
- Actors will keep a room_ownership index, which determines which room possesses the right to try despawning them. Actors have an additional boolean flag, can_transfer_rooms, which allows room ownership to be updated to the most recently-visited room automatically.
Can the player cause duplicate creatures to spawn by entering and exiting rooms while leading them around?
- When an actor is created from a room spawnpoint list, it locks or ‘checks out’ the spawnpoint. While locked, the scene can’t create another actor from it. When the actor is removed from the scene:
  - If the reason for removal doesn’t involve the player, it unlocks the spawnpoint, and a new actor can later be spawned from it.
  - If the player is responsible, then the spawnpoint remains locked.
- All spawnpoint locks are cleared when the player loses or when there is a level change.
- Actors created by other actors are not covered by this, and without additional checks, there could be duplicates if the player leads them around from room to room and back.
What if an actor jumps in the air, just out of the room boundaries, when the room is deactivated?
- While the actor inhabits no room, even if can_transfer_rooms is true, then room_ownership remains set to the last-visited room.
What if deactivating one room leaves a gaping pit for actors in an adjacent room to fall down through?
- The engine won’t do anything to stop them 🙂 The expectation is that room terrain / geometry should prevent this from happening. As a failsafe, the scene is configured to cull actors which have moved out-of-bounds from either the room with ownership, or the whole site boundaries by 512 pixels. This failsafe can backfire if it removes important actors for whatever reason, so culling can be disabled on a per-actor basis.
- The engine could be designed to prevent all movement outside of rooms in empty site space, maybe by treating room edges without neighbouring links as impassable. I haven’t thought this through.
What determines a site’s boundaries?
- The default boundaries are the maximum / minimum positions of rooms in the site, as determined during creation of the structure. The bounds are not automatically updated if rooms move around, but can be updated manually later on if needed.

I ended up going a bit further with this, adding a world structure which sites are attached to. Only one world can be active in a scene at a time, and changing worlds resets the scene state, but a world can have multiple sites with multiple rooms each, and sites can be spun up or down on-demand. When a room is toggled, it disappears from view and isn’t considered for collision checks, but the room instance is still in RAM, and ready to reappear with a function call. When a site is toggled, it adds or removes their associated rooms completely from the scene.

Before adding worlds and supporting multiple sites per scene, I made a test site with sixty-four instances of the same 256×256 map attached horizontally. It took the player avatar about 30 seconds to traverse one room, so a full edge-to-edge trip would be about 32 minutes. It consumed over 400MB of Lua memory though, and paused the whole application while setting up the scene, which is why I looked into adding and removing sites on demand. I don’t plan on having any levels that large in this project, but it’s nice to have flexibility.

World/Site/Room diagram.

So, one more issue for multiple rooms. ‘Navmasks’ are auxiliary tilemap layers that are generated automatically and provide navigation cues for actors with platformer movement. Specifically, it’s very important to know if a solid block is facing empty space on each of its four sides. If it is, then that side is flagged to block actors from moving in from that direction.

Where this is really beneficial is in preventing solid blocks from interfering with other kinds of terrain. For example, if a solid is neighbouring a sloped surface tile, then the block_ingress flag is not set for that side, and this prevents the solid block from being considered in collision responses near the slope.

The problem arises when the edges of a navmask are updated. As is, navmasks can’t be multi-room aware in a way that’s fast and predictable. It’d be feasible if every room shared the same tile dimensions and was grid-aligned, but that’s not guaranteed. Even if it were, it would be slower to update edges, since they’d have to check neighbouring navmask structures every time.

Up to this point, all out-of-bounds navmask reads returned a negative response (false / nil / ‘inhabitable space’.) I’ve added a per-room flag which makes it so that reads can instead return a value from the clamped coordinate. If a getInfo() call was made for x-1 y1, then the value at x0 y1 is returned.

Here is a visualization of four navmasks without clamping across multiple 8×8 rooms (three rooms joined horizontally, one room joined at the bottom-left that’s kinda hard to see.) The bright lines represent blocking edges of solid tiles, meaning that the platformer movement code aggressively tries to stop actors from moving past those lines. There are lines along the edges of the navmask boundaries, which may be desirable in some cases, but a cause of movement bugs in other cases.

Here’s the same set of rooms and navmasks with clamping.

I’m undecided on whether to make one flag for the whole room, or to have a separate flag for the four edges of each room.

Dang, this topic just goes on and on. I ran into a couple of issues with multiple site instances per world, mainly caused by the ability to place multiple copies of a room and multiple copies of a site:

How do I link sites together? I ended up with some functions to designate certain rooms within sites as inter-site gateways. This way, rooms can view neighbours that belong to other sites.
Positioning sites relative to each other was also tricky. Figuring out how wide or tall a site is and how far it extends out relative to its center point is a bit much when trying to fit things together with functions in a Lua file. The dimensions of one room changing can alter the dimensions of the whole site. I made it so that sites can copy point-shapes stored within individual room definitions and “promote” them to site-anchors with the correct offsets. These anchors can then be used to position two sites flush together.

Very last final bit on this topic this month I swear: In the old one-scene-one-map system, the maps contained some additional non-tilemapped shape data representing spawn-points, camera rules, and generic info that actors may use for pathing (like a floating platform that follows the points of a polygon.) I’ve opted to keep this data with the rooms, and not try to merge them into one set of scene-level arrays. Which set of rooms to scan becomes a new issue. We can scan:

Just the room that an actor considers its owner
Every room the actor is overlapping
All currently-live rooms
Every room-definition that’s listed in every site that’s part of the current world

I need to come up with a clean way of doing all of these which isn’t just tons of nested for loops. This is a good and bad thing, because it cuts down on linear search times through shapes, but actors may not get the full scope of their surroundings if they only look at the room they belong to.

Here is a visualization of a larger test world layout. White squares are rooms, blue squares are sites (some partly or fully obscured by the white squares.) The room marked ‘B’ corresponds to room 2 in the visualization.

Project Outlook

I made some good changes, but I feel like I’m even further from a finished game than I was in March. On the bright side, being a throwback pixel art game, there are only so many pixel-art-appropriate things to tack onto an engine until there’s nothing else to do. Most of my remaining feature wishlist items relate to enemy behavior management, building contraptions out of multiple linked actors, using shaders to simulate palette swapping, stuff like that.

I’ve started tracking some daily stats related to the project. In June, I’ll start including some line charts with total # of issue tickets and total line-count at the end of these posts.

Bolero Devlog (May 2020)