Overworld

Overworld is a game for Playdate written in Lua that is inspired by AirXonix. It is a 1-bit action-puzzle where your goal is to fill a rectangle with pixels by slicing it's surface into pieces, one polygon at a time.

I'd like to extend on the original concept by introducing an open-world, jRPG-like gameplay. At the moment I'm in an early phase, trying to make the classic concept work without a lag.

👉 If you'd like to learn more about the original xonix game and its numerous clones, check out my notes about AirXonix.

Progress Tracker #

I decided to track the development process day-by-day to be able to see how much of an actual time it will take. It's been a humbling experience: the gameplay looked relatively simple and I didn't expect to get stuck knee-deep in technical issues for so long.

Day 1 #

Figured out how to draw the field, the player, and the trace (or the "attack path", as I call it below).

Day 2 #

Implemented a slow but working version of the floodfill algorithm to capture field areas. The painted area doesn't re-render until the player moves over it, not sure what is the problem.

Day 3 #

• Experimented with new sprites, fixed the screen redraw, reduced the field size for the capture algorithm to work faster.
• Fixed the redraw issue from the previous entry. It was due to me incorrectly using the .setBackgroundDrawingCallback() to render the field. Thing is, this helper is designed to put up a static picture as a background so that you never waste resources to re-render it, so you need to manually mark it as "dirty".
• Downloaded some free sprites from itch.io and a background from unsplash, further processed it with HyperDither. TODO: add links to the original art.

Day 4 #

Updated the diary entries in README.md, not much else done.

Day 5 #

Up until this point, all of the code resided in one file, so making changes to it became tedious. Spent the day to refactor the code to OOP clases following the Object Oriented Programming for the Playdate SDK tutorial.

Day 6 #

A couple days ago I learned about quadtree, a widespread data structure that can solve a few problems when it comes to performance. It got me excited, so I came up with an idea to track the captured area inside of a quadtree to replace the inefficient 400x270 grid.

Every polygon should split into a union of rectangles, allowing me to operate on a few hundred nodes rather than tens of thousands of pixels (or at least I thought so for quite some time – note from the future me). Now it feels like it will be much easier to implement the rest of the code on top of it: collisions and floodfill. All you need is a quadtree.

AI trigger warning: an LLM generated an almost working implementation of the tree. The result wasn't impressive but it was usable and removed a mental block that kept me from moving further. I only had to fix a few bugs and implement a visualizer to make sense of the tree.

Day 7 #

With the quadtree visualizer done the creative juice started flowing again, and I settled on the idea for the game: an open-world xonix. The game happens on an overworld map, with only a part of the map being visible at any given time. The overworld concept is coming from old jRPGs, as seen in Robin Sloan's game concept called Perils of the Overworld (click on the link to read the devlog, it's a curious little series).

• Refactored the LLM-generated code to do deterministic splits when inserting rectangles of odd dimensions into the tree.
• Due to using floats, the quadtree structure produced random tiny dents on the edges of the captured areas when translating to integer coordinates during the render process.
• Simply rounding up or down wasn't enough, as this in turn generated dents at the intersection of quadrants.

Well past midnight I started a research on how to integrate the player's attack path into the tree and learned a few things about polygon covering. Random thought: I really need to settle on the vocabulary for the game (i.e. "attack", "path", "captured area", "arena" vs "field etc).

Day 8 #

I've spent a bit more time reading about polygon covering and visualized a potential algorithm in Aseprite. After a bit of headscratching it was declared an unnecessary distraction: I already had a method to add a rectangle to the tree which I can reuse to store the attack path as a series of rectangles with width equal to 1. The side-effect of this decision was that now there's far more nodes in the tree, as it has to split many times. It's not laggy now, but might end up being laggy later in the game.

Yasna noted that the resulting pattern resembles a rug ornament, and Tyoma added that the data structure can be exploited for visual effects. I like the idea, there could be a carpet-themed level one day.

I tried out the Playdate collisions API by simply adding empty collision sprites on every tree node .addEmptyCollisionSprite(). Theoretically, I could add all the nodes as regular sprites. It works, but not perfectly: since collision sprites have boundaries, I randomly get stuck in the walls all the time. Also the collisions do not get triggered when crossing an active attack path.

Day 9 #

The built-in collisions engine worked well, so I won't have to reinvent the wheel. It's simple and fast, and it's based on an open source engine bump.lua. As a cherry on top, it was dead simple to add enemy movements once the player collisions were in place. Check out the demo visualization shipped with bump.lua, it shows how the internal data structure tracks objects of interest as the player moves through the map.

A couple workarounds I had to implement:

• There's an invisible wall outside of the arena to stop the player from falling through textures. Previously it was hardcoded but now it's taken care of by Playdate, giving me flexibility to use something other than a rectangle for the level shape.
• Segments of the captured area stopped the player at the intersection of tree nodes, so I had to change the movement logic and ignore collisions when not attacking.

Happy with how collisions turned out, I started questioning whether the game really needs a quadtree at this point. All I wanted it to do is to run the floodfill faster, but I am still using the old algorithm and don't have any idea how to switch it to trees.

Day 10 #

I'm trying not to give up on quadtrees, so I spent some time researching. A quadtree is normally used to speed up finding objects that are in close vicinity, i.e. "find all enemies in a blast radius of a hand-grenade". Truth is, there are no similar mechanics in xonix. I picked it for novelty and hoped for a little bit of magic to save me from solving the real problem: efficiently detecting isolated blobs of pixels on the screen.

Solving this problem with a tree is possible, but not at all straightforward. It can be done by recursively iterating over all neighbor nodes until the outside boundary is encountered, and detecting neighbours in a tree is no easy task. The Advanced Octrees 4: finding neighbor nodes by David Geier contains a great explanation and an incomplete code example.

There's a few more curious papers about the problem:

• Constant Time Neighbor Finding in Quadtrees
• Algorithms for connected component labeling based on quadtrees
• Connected Component Labelling using Quadtrees – A Bottom-up Approach
• Connected Component Labeling Using Quadtrees
• Connected Component Labeling Using Modified Linear Quadtrees

Day 11-12 #

I implemented David's algo for finding neighbors, and it worked perfectly, letting me build a tree-based recursive floodfill. That said, my floodfill algo painted the entire screen black instead of filling a closed area, and I couldn't catch the bug for some time.

Turns out, there were gaps in the tree which caused the floodfill to spill into adjacent areas. I managed to incorrectly implement both the tree construction and the tree visualization routines incorrectly, and one covered for the others: the tree looked perfectly gapless on the screen.

Another LLM-generated piece of code helped me find the bug. This time it created a browser-based visualizer which made spotting the gaps and locating all the edge-cases of the algorithm much simpler.

A screenshot from the visualizer: the grey cells are the cells that are marked as filled in the game

Somehow, the floodfill didn't work as I expected, and it was still slow. At this point the node counts is way above 10k, and the code is hard to follow, which is worse than my tree-less version by a margin by any measure I can think of.

Day 13 #

Today is the day: I gave up on quadtrees and went back to a simple grid representation. There's less code now and it is orders of magniture simpler to reason about. That said, my naive floodfill is as slow as before, so we're back to square one.

After the migration was completed, I tried running the game on Playdate for the first time, and to no surprise, it crashed immediately. Turns out even the earlier versions crashed on the real hardware. I suspect this happens because all of them abuse the Lua garbage collector which only becomes apparent on the device. The simulator is more forgiving as there is no memory limit.

This part – performance optimization – is what I have been subconsciously avoiding by using a "smart" data structure. I know next to nothing about game engine optimization and it is scary.

The ultimate solution to the problem would be either to reimplement the field data structure and the algorithm in C, or to reduce the field resolution from 220x220 to something like 100x100 or even less. These two options were around since the beginning but there should be a lot of low hanging fruits before I take this step.

I started by removing the float -> int conversion that happened two times per each coordinate per frame, which improved the situation substantially. Then, I replaced all the nice and readable string enums with integers, and topped it up by removing a class that represented a pixel in the grid. As a result, memory usage per frame dropped from 12Mb to 2Mb, letting me run the game on Playdate. Not bad! Although the game freezes for 5-7 seconds when the attacks end.

To fuel my motivation, I decided to step back from the engine and have some fun with the game itself. A few missing pieces were added: some basic sounds, a score system and the game over screen. This relatively low effort promoted Overworld from a prototype to a real game, nevermind it is still slow and boring.

The Wonky Horse is a metaphor for the text above

Day 14 #

Happy with the fact that the game actually runs on a playdate, and can be "beaten" to some extent, I decided to clean up my devlog and publish it on grains. Looking back at 14 separate days of work, I'm surprised how far I've gotten without giving up and switching to the next thing.

Day 15-16 #

I'm trying to improve performance by approaching it from two different angles: trying to pinpoint the current performance bottlenecks and at the same time thinking of alternative algorithms that I could switch to. Still learning to use the sampler view of the simulator. Switched the 2D grid data structure to a more efficient 1D table. Tried implementing floodfill without recursion, felt slower – not sure why.

Day 17 #

Tyoma stepped in to help me with peformance issues and in a matter of hours he resolved all of the open questions I had. He swapped the floodfill algo with a non-recursive version and created a stripped-down version of a game to isolate the issue further.

We confirmed that the game crashes on device due to CPU limits: Playdate OS runs a watchdog process that kills the game when the main loop hangs for 10 seconds. This information can be found in the error.log when the device is rebooted into the drive mode:

2024/02/12 17:26:15 /Games/overworld.pdx Run loop stalled for more than 10 seconds pc=0x2403F752 lr=0x24031317

Tyoma implemented a coroutine that animates the floodfill over multiple frames, unblocking the game loop:

My next goal is to move from a brute-force DFS flood-fill to something that doesn't require so many CPU cycles. I'll try to do the following:

• Increase the size of a single cell in the field
• Test the areas adjacent to the player. If no enemies found in one of them, fill it and stop the algo.
• Use Tyoma's coroutine floodfill as a visual candy, with an added function of making occasional lags look nice.