Mandelbrot Explorer in Pico-8

Here’s a link to immediately play the game/simulator/explorer described in this post and here’s the source code in case you’re interested in exploring that.

Controls are standard keys/buttons for Pico-8:

  • up/down/left/right arrows to move around
  • if on the computer, “Z” and “X” keys to zoom in/out
  • if on mobile, “O” and “X” buttons to zoom in/out
  • Hidden (and confusing) settings adjustment mode can be chosen from the menu (accessible by the “-” shaped start button on mobile or “enter” key on the computer) under the “settings” option, in which case up/down/left/right turn into adjusting the cutoff and iteration count respectively. Choose “navigate” from the menu to go back to navigation.

I wanted to learn more about fractal geometry and complex numbers, mainly in hopes of being able to use them in simulated game universes, so I figured a fun first pass would be building a mandelbrot generator in my favorite game framework, Pico-8.

There’s a lot of reasons why this is a bad idea:

  • It’s slow, in fact, the lua expressions are intentionally slowed down so it runs at the same speed on every platform.
  • It does not give any direct GPU access, all written expressions get executed through the lua interpreter.
  • All numbers are represented by 32 bits, 16 bits for whole numbers and 16 bits for fractional numbers, eg 0x0000.0000 to 0xffff.ffff which means you can only zoom in somewhere around 1000x before the math breaks down from being unable to divide the region the camera covers into pixel-sized units for computation.
  • Using arrow keys and Z/X for exploring an equation isn’t very intuitive.

However, it does let me slap it on a static page and rapidly iterate without having to learn a single new tool or library, so for that reason I’m a huge fan of it for doing prototyping and exploration.

The Responsive Tortoise

Not having access to the GPU (not to mention having every expression be artificially slowed down) means we’re not going to be able to calculate every of the 128×128 pixels while doing 60 frames per second. What we can do though is calculate and draw some of the pixels each frame, and then after a number of frames the picture will be complete.

The naive way to approach this would be start at the top left and work our way across each row, and that would be fine except you wouldn’t have a clue of what you’re looking at until it’s calculated around half of the pixels so you can see around half of the screen. That’s a problem when you want to navigate around quickly and keep restarting the draw process every time you move.

Instead, what I did was start with an extremely low resolution render (8×8 pixels) which meant only 64 coordinates to calculate – a lot by hand but doable in 1/60 of a second by a computer, even with something as slow as Pico-8. At that point, after the first frame, you have some hint at what the final image might be. From there it continues to increase the resolution until it fills it all out at the native 128×128, which takes many frames but usually only about 5-10 seconds which isn’t very long to wait.

The trick was how to gradually keep increasing the resolution without wasting work in the process? Basically, I use the top left corner of each oversized pixel to determine what color the whole region that oversized pixel covers, and then I redraw over the other parts of the oversized pixel with progressively smaller pixels until every 128×128 spot on the screen has had exactly one calculation done for its coordinate. This is difficult to explain, but if you watch the animation or play the game and keep an eye on the top left corner of each mega-pixel as it enhances the image you’ll see the color never gets replaced.

Breaking the 0x0000.0001 Barrier

I thought this would be an interesting opportunity to try to build my bit-management math skills and see if I can view things at a smaller scale than the above described version could. The only way this is possible in Pico-8 is by representing a number with a list of numbers, eg, to represent 64 bits of data in a world made of only 32 bit numbers you can simply use two 32 bit numbers and split the data between them.

This took some doing to figure out, but I ended up with a polynomial kind of representation, like the first number is just multiplied by 1, the second number is multiplied by 0.5^32, the third number is multiplied by 0.5^64, so if your numbers were 3, 4, 5 then your represented number would be 3*1 + 4*0.5^32 + 5*0.5^64. We of course can’t actually multiply this out in the program since the result would be too small, but we don’t need to, we can just keep representing it in parts as we do the math with normal old polynomial addition (add all similar multipliers together) and multiplication (multiply all multipliers of each side against all multipliers of the other side) rules.

Turns out this works quite nicely with the whole complex number thing, because complex numbers are multi-part too, eg, 5+6i. So the rational and complex component of that complex number end up having a list of sub-numbers to represent arbitrary precision.

And to avoid leaving anything out, my examples here talk about 32 bits but there’s actually only 31 since 1 bit is for positive/negative and screws everything up if you try to use it when leveraging the native addition and multiplication. My code worked around that but it’s too nitty-gritty to get into here, so I’m just going to gloss over that part.

Dealing with Overflows

Unfortunately, we still have to deal with overflows. If you multiply 0x0.001 by 0x0.001 then you get 0x0.000001 but we can only represent numbers as small as 0x0.0001 so the result we’d get back would be 0x0000 with no hints at what kind of overflow we had. If we knew the overflow, then we could carry it over, shift it way to the left (so the bit was at the most significant, not least significant, spot), and add it to the number representing the next level of bits.

After a lot of brainstorming I figured out how to do this though. In the above example, for multiplication, to figure out what the carry is that we want to send to the “right” (ie, to the number representing the next least significant set of bits) it’s a multistep process:

  • Shift both numbers 8 bits to the left (0x0.001 becomes 0x0.1)
  • Multiply them together (0x0.1 squared becomes 0x0.01)
  • Shift the result 16 bits to the left (0x0.01 becomes 0x100.0)
  • Add that to the next lower bit range (so it’s now 0x0.0 + 0x100.0 * 0.5^32)

A similar process is done but opposite to calculate what value is carried left to the next more significant bit range.

Impact on Speed

As you might imagine, converting the relevant variables to this complex polynomial representation induces an explosion of extra calculations and had a DRASTIC impact on speed and made running the same high-level calculations as before basically impossibly slow. I spent a bit of time trying to limit various things to try to get the speed to be vaguely bearable but it was still way too slow to be able to reasonably navigate anywhere.

I did my best on the math but taking a look at a known coordinate suggested that while it was indeed mostly working, there were still a few glitches to work out… It seemed like something around my representation of positive/negative wasn’t quite right. I am tempted to keep working on it, but due to the speed the utility is essentially nilch so I think I’ll abandon the project here and move on to greener pastures.

If you’re curious about the complex number library I made (although I recommend you not try to use it) you can find the code in a separate branch (infinite_zoom) here and if you want to try this super slow, glitchy monstrosity you can play it with this link.

Divided Single-Player Colored-Tile Prototype History

This post mainly catalogues the series of changes I waded through in game prototyping adventures for a month or two, mostly for my own purposes. If you’d like to skip to playing the final result, it’s here.

This is a list of all the significant, stable versions of a game prototype I occasionally worked on during evenings for a month or two. I adjusted the exported index.html to optionally take in a query param of blob that points to a git SHA and it will load the index.js corresponding to that point in the code history.

TL;DR – I can make playable links to past code!

I found myself backtracking too much while working on a more complex, multiplayer version of this game so I decided to spend some time with a single-player prototype version of it for awhile so I could quickly shift the rules around to get a feel for what works and what doesn’t without a week of coding for each trial. Each of these chunks of changes mostly correspond to less than a full day of work. The first link with the 7 digit hex text is a link to play the game at that version, the “browse” or “compare” links take you to the source code diff that correspond to the described changes.

The eventual goal of this project is much more complex than these prototypes suggest, their purpose is to really focus on the gameplay mechanics possibilities that come out of a world made of tiles that can be one of either of two colors, or neither, as well as creatures that are made of the same color energy as the tiles (referred to after this as “mobs”) which have some sort of “conservation of energy” type relationship with the color in the tiles. The player is an interloper of sorts that can blend in with either of the colors harmoniously or fight against the current chaotically.

In the eventual game there will be more robust goals and interactions between systems (this colored tile system would be one of many of those) but for the purpose of these prototypes consider your goal to be moving down to the bottom of the grid without getting surrounded. For the first handful of them that might be a bit too easy, so alternatively try arranging tile colors into a certain pattern. Basically just move around the game universe and get a feel for it.

Controls: up, down, left, right – moves selection cursor
mobile: “O” button to select a move, “X” button to change targeted direction (later prototypes only)
pc: “Z” key to select a move, “X” key to change targeted direction (later prototypes only)

7a6b4b5 (browse) – first js export

  • moving only, no interaction with room
  • no sounds
  • ugly colors
  • no mobs

8a0326f (compare) – added mobs and pathfinding-derived moves

  • mobs added that move towards you and block you
  • they move to where you were, not where you’re going, so too easy to avoid them
  • they spawn all around a tile when you pick it up so if you pick up a lone tile they completely surround you
  • if you know how the game works there’s no challenge, if you don’t then it’s too suddenly punishing
  • you only pick up/drop a tile when you choose to, no advantage to holding color
  • you can move over any tile you want while not holding color
  • can’t hold more than one of a color
  • can’t kill mobs in any way
  • mobs only chase you when you’re holding color

05d9748 (compare) – added sound effects

  • mobs don’t move if you don’t move
  • sound effects which ended up sticking around for awhile
  • pathfinding animations for mob and player, they all move at the same time although the mobs still move towards where the player was
  • pick up and drop automatically when moving
  • only spawn 1 mob per color action
  • better mob colors

520888b (compare) – more aggressive mobs, more sfx, animation improvements

  • cursor selection visual tweaks
  • all mobs chase you when gray
  • mobs cancel out with each other when adjacent
  • add slight quadratic easing for movement
  • make mobs appear to come out of your avatar when spawning
  • add sfx for movement, failing to move the cursor, and mobs canceling out
  • player moves slower while no color
  • 2 mobs spawn from every color action

dd916d7 (compare) – mobs chase player, back to 1 mob spawning, selection visual tweaks

  • mobs go to where player moves to, not where player moved from
  • 1 mob spawns for each color action
  • circular selection icon
  • clearer avatar shape/color to make seeing the background tile easier and the avatar color change more obvious

92a02a7 (compare) – huge scrolling map, mobs cancel out from spawning

  • map extended below the screen
  • a panning camera that follows the avatar added
  • when spawning mobs via color actions, prioritize any mobs that can cancel out as targets automatically
  • because of how many enemies there are and poor optimizations, there’s moments of noticable lag when the enemies are pathfinding
  • note – shooting one’s way out of being surrounded is nice in this version since the mobs don’t move unless you do so you can blow open a hole and escape even in a crowd… would be interesting to see what adding user-aimed shots to this would be like

8b45d30 (compare) – player/tiles can have a stack of color rather than just 1, mobs can move when player doesn’t

  • Disable mobs cancelling out on their own (need to “shoot” new mobs at old mobs to kill them)
  • Simplify camera movement
  • Allow mobs to move when player waits (unless the player is immediately adjacent)
  • Make player and tiles able to accumulate color – dropping n accumulated color drops it all at once and spawns n mobs
  • Add particle effects to indicate a high stack of color
  • when spawning mobs, if there isn’t room for them then don’t spawn them even though you “spent” color in the process
  • note – it’s too easy to kill endless mobs safely by making sure you’re holding color and cycling pick up and drop until there are none left

3943fc6 (compare) – balance tweaks to fix previous version being too trivial

  • Make player unable to pick up color without moving – prevents pickup/drop cycling to clear nearby enemies trivially
  • Fix a few bugs around particle emitting
  • Make mobs not block mobs/player of the same color
  • Adjust player and mob max move distances for balance
  • Make a separate variable for how far away a mob can be activated by a player from how far they can move (ie, they can now move towards a player even if they can’t quite it reach yet)

d2de1e8 (compare) – Add experimental mouse support

  • Difficult to detect whether the player has a mouse or a finger
  • Types of interface for mouse and finger are very different and it’s a lot of extra maintenance and design to keep them both in-line
  • Eventually removed in a later commit due to new features that were too tedious to make work with a mouse, but sticks around until then

06f3cb4 (compare) – Add color-stacked enemies and a death screen

  • Make 4 different enemies representing color stacks of 1, 2, 3, 4+
  • When shooting out more than 1 color it comes out as a 1 large mob rather than n mobs of size 1
  • Add a “DEAD – click to try again” death screen where the enemies scramble around your dead body aimlessly
  • Target the largest nearby enemy when shooting out mobs so you can kill the biggest one quickly
  • Start the player at 3,3 instead of 0,0
  • note – targeting the biggest enemy ended up making it too tedious and complex to clear groups of enemies

0485c63 (compare) – smarter mobs, more restricted gray movement, dropped color only results in mobs

  • As gray, you can only move onto the edge of a cluster of color – once pathfinding walks over a color tile it stops searching
  • When dropping color it does not turn back into a tile, solving the cycling exploit without the confusion (previously it was solved by not being able to pick up a tile without moving) – also tends to make the total amount of color shift in forms rather than get created or destroyed
  • Mobs now prioritize targets (in descending order of priority – neaby enemy players, nearest enemy mob, larger friendly player, nearest friendly mob larger than us)
  • If a mob has no viable targets, wander aimlessly
  • When a stack of color is held, only fire one color instance each turn rather than a big shot of 4 color
  • Fix death screen not being centered after moving the camera
  • note – at this point I’m starting to try to polish existing behavior to a “local maxima” of good gameplay to wrap up the prototype project

b8bb143 (compare) – Simplify and cleanup code, make mobs prioritize players targets similarly to mob targets, choose which direction to shoot

  • Mobs used to have separate prioritization for targeting mobs vs players but that’s now been flattened to make players treated similarly to other mobs to give more of a “being among equals” feel
  • Direction to “fire” new mobs is now explicit – shows you what color it will be, prioritizes a nearby opposite color, and allows you to change the selection with button 2
  • Mouse support was finally removed to avoid having to support fire-direction with the mouse somehow
  • Lots of code removal and cleanup now that a lot of behavior has been properly retired

74ac27e (compare) – Targeting visual tweaks, go-like capturing, HUD-like indication of color stack or vulnerable (gray), friend-boosting

  • Made targeting graphics a bit clearer about what’s about to happen
  • Enemies can now be not only canceled out by “firing”, but also surrounded like go stones. when surrounded they revert to tiles
  • Visual indicator of how many colors you have or if you’re vulnerable (gray) since it’s way easier to die while gray
  • Now possible to fire at friend mobs (ie, the same color) which makes them bigger. Usually this is undesirable, but I needed to add it to avoid a possible situation where you can land between friendly mobs and not have any possible direction to shoot or move