All posts by Eevee

Cheezball Rising: Maps and sprites

Post Syndicated from Eevee original https://eev.ee/blog/2018/07/15/cheezball-rising-maps-and-sprites/

This is a series about Star Anise Chronicles: Cheezball Rising, an expansive adventure game about my cat for the Game Boy Color. Follow along as I struggle to make something with this bleeding-edge console!

GitHub has intermittent prebuilt ROMs, or you can get them a week early on Patreon if you pledge $4. More details in the README!


In this issue, I get a little asset pipeline working and finally have a real map.

Previously: spring cleaning.
Next: resounding failure.

Recap

The last post only covered some minor problems (including, I grant you, being totally broken), so the current state of the game is basically unchanged from before.

A space cat roams around on a grassy background

That grass pattern, the grass sprite itself, and the color scheme are all hardcoded — written directly into the source code, by hand. If this game is going to get very far at all, I urgently need a better way to inject some art.

Constraints

The Game Boy imposes some fairly harsh constraints on the artwork — which is part of the charm! But now I have to figure out how to work within those constraints most effectively. Here’s what I’ve got to work with.

Bear in mind that I intend for the game to be based around 16×16, um, tiles. Okay, it’s extremely confusing that “tile” might refer either to the base size of the artwork or to the Game Boy’s native 8×8 tiles, so I’m going to call the art tiles and the Game Boy’s basic unit a character (which is what the manual does).

  • The background layer is a grid of 8×8 characters, each of which uses one of eight 4-color background palettes.

  • The object layer is a set of 8×16 character pairs, each of which uses one of eight 3-color object palettes. These palettes are 3-color because color 0 is always transparent.

  • No more than 40 objects can appear on screen at the same time. (There is a way to weasel past this limit, but it requires considerable trickery.)

  • No more than 10 objects can appear in the same row of pixels. (I believe this is a hard limit.)

  • There are three blocks of 256 chars each. I can divide this between the background and objects more or less however I want, though neither can have more than two blocks (= 512 chars).

I’m intending for the game to be based around a 16×16 grid, a fairly common size for the Game Boy. That makes me a little concerned about the per-row object limit — each entity will need to have two Game Boy objects side by side, so I’m really limited to only five entities sharing the same row of pixels. I can’t do much about that quite yet (and only have one entity anyway), but it’s likely to affect how I design maps and draw sprites.

The next biggest problem is colors. Each object palette can only have three colors, which in practice means a shadow/outline color, a highlight color, and a base color. This is why every NPC and overworld critter in Pokémon GSC and the Zeldas is basically monochromatic. They pull it off really well by making very effective use of the highlight and shadow colors.

Since 16×16 sprites are composed of multiple Game Boy objects, it’s possible to overcome this limit by giving each part of the sprite a different palette. Unfortunately, objects being 8×16 means the sprites are split vertically, when it would be most useful to have different colors for e.g. the head and body. I wish the Game Boy supported 16×8 objects! That’d help a ton with the per-row limit, too. Alas, a few decades too late to change it now.


As for the number of chars… well, let’s see. The whole screen is only 160×144, which is 20×18 or 360 chars, so I could allocate two blocks to the background and have 512 — more than enough to cover the entire screen in unique chars! (I expect one block to be more than enough for objects, since I can only show 80 object chars at once anyway.)

On the other hand, I’ll need to reserve some of that space for text and UI and whatnot, and each 16×16 tile is composed of four chars. If I very generously allocate a whole block to window dressing (enough for all of ISO-8859-1?), that leaves 256 chars, which is 64 tiles, which is a tileset that fits in an eight-by-eight square.

For comparison’s sake, even fox flux’s relatively limited tileset is a sixteen-tile square — four times as big. This feels a little dire.

But how can it be dire, when I have enough sprite space to fill the screen and then some?

Let’s see here. A pretty good chunk of the fox flux tileset is unused or outright blank. Some of these tiles are art for moving objects that happened to fit in the grid, and those wouldn’t be in the background tileset. And while all of the tiles are distinct, a lot of the basic terrain has some significant overlap:

A set of dirt tiles from fox flux, colored to indicate where different tiles have identical corners

All of the regions of the same color are identical. These 9 distinct tiles could fit into 20 chars if they shared the common parts, rather than the 36 required to naïvely cutting each one into four dedicated chars.

(The fox flux grid is 32×32, so everything is twice as big as it will be on the Game Boy, but you get the idea.)

I’m feeling a little better about this, especially knowing I do have enough space to cover the whole screen. Worst case, I could draw the map as though it were a single bitmap. I don’t want to have to rely on that if I can get away with it, though — I suspect I’d need to constantly load chars on the fly, and copying stuff around eats into my CPU budget surprisingly quickly.

Research

That does get me wondering: what, exactly, do the Oracle games do? I haven’t done any precise measurements, but I’m pretty sure they have more than sixty-four distinct map tiles throughout their large connected worlds. Let’s have a look!

Oracle of Ages and its live tilemap, in the graveyard, showing the graveyard tileset

Here I am in the graveyard near the start of Oracle of Ages. The “creepy tree” here is distinct and doesn’t really appear anywhere else, so I found it in the tile viewer (lower right) and will be keeping an eye on it. Note that only the left half of the face is visible; the right half is using the same tiles, flipped horizontally. (The colors are different because the tile viewer shows the literal colors, whereas the game itself is being drawn with a shader.)

Let’s walk left one screen.

Oracle of Ages and its live tilemap, outside of the graveyard

Now, this is interesting. The creepy tree is still on the screen here, so its tiles are naturally still loaded. But a bunch of tiles on the left — parts of the dungeon entrance and other graveyard things — have been replaced by town tiles. I’m several screens away from the town!

The next screen up has no creepy trees, but its tiles remain. Of course, they’d have to, since the creepy tree is still visible during a transition. I have to go left from there before the tree disappears:

Oracle of Ages and its live tilemap, with tiles spelling SHOP clearly visible

Wow! At a glance, this looks like enough tiles to draw the entire town.

This is fascinating. The Oracle games have several transitions between major areas, marked by fade-outs or palette changes — the purple-tinted graveyard is an obvious example. But it looks like there are also minor transitions that update the tileset while I’m still several screens away from where those tiles are used. The screens around the transition only use common tiles like grass and regular trees, so I never notice anything is happening.

That’s cute, clever, and an easy way to make screen transitions work without having to figure out what tiles are becoming unused as they slide off the screen!

At this point I realize I may be getting ahead of myself. Screen transitions? I don’t have a map yet! Hell, I don’t even have a camera. Time to back up and make something I can build on.

Designing a tileset

I’m pretty tired of manually translating art into bits. It’s 2018, dammit. I want to use all the regular tools I would use for this, I want the Game Boy’s limitations to be expressed as simply as possible, and I want minimal friction between the source artwork and the game.

Here’s my idea. I know I only have 8 palettes to work with, so I’m decreeing that tilesets will be stored as paletted PNGs. The first four colors in the image palette will become the first Game Boy palette; the next four colors become the second Game Boy palette; and so on. If I then resize Aseprite’s palette panel to be four colors wide, I’ll have an instant view of all my available combinations of colors.

This already has some problems — for starters, if the same color appears in multiple palettes (which will almost certainly happen, for the sake of cohesion), I’m very likely to confuse the hell out of myself. I also have no idea how to extend this into multiple tilesets, but for now I’ll pretend the entire game world only uses a single tileset.

I could instead dynamically infer the palettes based on what combinations of colors are actually used, but after more than a couple tiles, it would be a nightmare for a human to keep track of what those combinations are. With this approach, all a human needs to do is color-drop a pixel from a particular tile and look at what row the color’s in.

After a quick jaunt into the pixel mines, here are some tiles.

A small set of pastel yellow moon tiles

Or, as viewed in Aseprite:

The same set of tiles, as seen in an editor, with the four-color palette visible

That’s only one palette, but hopefully you can see what I’m going for here. It’s enough to get started.

At this point, I started writing a little Python script that used Pillow to inspect the colors and pixels and dump them out to rgbasm-flavored source code. The script itself is not especially interesting: run through each 8×8 block of pixels, look at each pixel’s palette index, mod 4 to get the index within the Game Boy palette, print out as backtick literals. (I could spit out raw binary data, but I wanted to be able to inspect the intermediate form easily. Maybe later.)

The results:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
SECTION "Map dumping test", ROM0
TEST_PALETTES:
    dw %0101011110111101
    dw %0101011100011110
    dw %0100101010111100
    dw %0100011001111000
    ; ... enough zeroes to make eight palettes ...
; sorry, in the script I was calling them "tiles", not "chars"
TEST_TILES:
    ; tile 0 at 0, 0
    dw `00001000
    dw `00000000
    dw `00100000
    dw `00000000
    dw `00000000
    dw `00000000
    dw `20000000
    dw `20000002
    ; ... etc ...

And hey, I already have code that can load palettes and chars, so all I have to do is swap out the old labels for these ones.

Now I have a tileset I can load into the game, which is very exciting, except that I can’t see any of them because I still don’t have a map. I could draw a test map by hand, I suppose, but the whole point of this exercise was to avoid ever doing that again.

Drawing a map

In keeping with the “it’s 2018 dammit” approach, I elect to use Tiled for drawing the maps. I’ve used it for several LÖVE games, and while its general-purposeness makes it a little clumsy at times, it’s flexible enough to express basically anything.

I make a tileset and create a map. I choose 256×256 pixels (16×16 tiles), the same size as the Game Boy screen buffer, and fill it with arbitrary terrain. In retrospect, I probably should’ve made it the size of the screen, since I still don’t have a camera. Oh, well.

Here, I hit a minor roadblock. I want to do as much work as possible upfront, so I want to store the map in the ROM as chars, not tiles. That means I need to know what chars make up each tile, which is determined by the script that converts the image to char data. Multiple maps might use the same tileset, and a map might use multiple tilesets, so it seems like I’ll need some intermediate build assets with this information…

(In retrospect again, I realize that the game may need to know about tiles rather than just chars, since there’ll surely be at least a few map tiles that act like entities — switches and the like — and those need to function as single units. I guess I’ll work that out later.)

This is all looking like an awful lot of messing around (and a lot of potential points of failure) before I can get anything on the dang screen. I waffle for a bit, then decide to start with a single step that simultaneously dumps the tiles and the map. I can split it up when I actually have more than one of either.

You can check out the resulting script if you like, but again, I don’t think it’s particularly interesting. It enforces a few more constraints than before, and adds a TEST_MAP_1 label containing all the char data, row by row. Loading that into VRAM is almost comically simple:

1
2
3
4
5
    ; Read from the test map
    ld hl, $9800
    ld de, TEST_MAP_1
    ld bc, 1024
    call copy16

The screen buffer is 32×32 chars, or 1024 bytes. As you may suspect, copy16 is like copy, but it takes a 16-bit count in bc.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
; copy bc bytes from de to hl
; NOTE: bc must not be zero
copy16:
    ld a, [de]
    inc de
    ld [hl+], a
    dec bc
    ; dec bc doesn't set flags, so gotta check by hand
    ld a, b
    or a, c
    jr nz, copy16
    ret

Hm. It’s a little harder to justify the bc = 0 case as a feature here, since that would try to overwrite every single byte in the entire address space. Don’t do that, then.

Anise, in-game, walking on the moon tiles

Now, at long long last, I have a background with some actual art! It’s starting to feel like something! I’ve even got something resembling a workflow.

My desktop, showing the moon tiles in an image editor, the map put together in Tiled, and the game running in mGBA

All in a day’s work. Good time to call it, right?

Except

I just wrote this char loading code…

And there’s still one thing still hardcoded…

I wonder if I could do something about that…?

Sprites

Above, I conspicuously did not mention how I integrated the Python script into the build system. And, well, I didn’t do that. I ran it manually and put it somewhere and committed it all as-is. You currently (still!) can’t actually build the game without repeating my steps. You can’t even just put the output in the right place, because you also have to delete some debug output from the middle of the file.

It gets worse! Here’s how.

I have some Anise walking sprites, too, drawn in Aseprite. They’re pretty cute and I’d love to have them in the game, now that I have some Real Art™ for the background.

Star Anise, walking forwards

Why not throw these at the same script and hack them into animating?

Unfortunately, this introduces a bit of manual work, as animation often does. (My kingdom for a way to embed a small simple animation in a larger spritesheet in Aseprite!) I’ve typically animated every critter in its own Aseprite file — or stacked several vertically in the same file when their animations are similar enough — and then exported as a sheet with the frames running off horizontally. You can see this at work in fox flux, e.g. on its critter sheet.

But Star Anise introduces a wrinkle that prevents even that slightly clumsy workflow from working.

You may have noticed that the walking sprite above blows the color budget considerably, using a whopping five colors. The secret is that Anise himself fits in a 16×16 square, and then his antenna is a third 8×16 sprite drawn on top. I can’t simply export him as a spritesheet, because the antenna needs to be separate, and it’s not even aligned to the grid. It doesn’t even stay in the same place consistently!

I could maybe hack something together that would automatically pull the incompatible pixels into a separate sprite. I might need to, since — spoiler alert — there are an awful lot of Lunekos in this game. For now, though, I did the dumbest thing that works and copied his frames to their own sheet by hand.

Star Anise's walking frames laid out in a spritesheet

The background is actually cyan, not transparent. I had to do this because my setup expects multiple sets of four colors — the first color in an object palette is still there, even if it’s ignored — and only one color in an indexed PNG can be transparent. (Don’t @ me about PNG pixel formats.) I could’ve adjusted it to work with sets of three colors and put the transparent one at the end so the palette column trick still worked, but… this was easier.

Here’s the best part: I took the main function from my tile loading script, copy-pasted it within the same file, and edited the copy to dump these sprites sans map. So now not only is there no build system, but half of the loading script is inaccessible! Sorry. We’re getting into experiment territory and I am going to start making a lot of messes while I figure out what I actually want.

Using these within the game was just as easy as before — replace some labels with new ones — and the only real change was to use a third OAM slot for the antenna. (The antenna has to appear first; when sprites overlap, the one with the lowest index appears on top.)

That did make updating OAM a little clumsy; you may recall that before, I loaded the x and y positions into b and c, updated them, then wrote them back into OAM:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
    ; set b/c to the y/x coordinates
    ld hl, oam_buffer
    ld b, [hl]
    inc hl
    ld c, [hl]
    bit BUTTON_LEFT, a
    jr z, .skip_left
    dec c
.skip_left:
    bit BUTTON_RIGHT, a
    jr z, .skip_right
    inc c
.skip_right:
    bit BUTTON_UP, a
    jr z, .skip_up
    dec b
.skip_up:
    bit BUTTON_DOWN, a
    jr z, .skip_down
    inc b
.skip_down:
    ld [hl], c
    dec hl
    ld [hl], b
    ld a, c
    add a, 8
    ld hl, oam_buffer + 5
    ld [hl], a
    dec hl
    ld [hl], b

The above approach required that I hardcode the 8-pixel offset between the left and right halves. With the antenna in the mix, I would’ve had to hardcode another more convoluted offset, and I didn’t like the sound of that. So I changed it to inc and dec the OAM coordinates directly and immediately:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
    ; Anise update loop
    ; set b/c to the y/x coordinates
    ld bc, 4
    bit BUTTON_LEFT, a
    jr z, .skip_left
    ld hl, oam_buffer + 1
    dec [hl]
    add hl, bc
    dec [hl]
    add hl, bc
    dec [hl]
.skip_left:
    ; ... etc ...

Eventually I should stop doing this and have an actual canonical x/y position for Anise somewhere. But I didn’t do that yet.

I did also take this opportunity to change my LCDC flags so that object chars start counting from zero at $9000, fixing the misunderstanding I had before. That’s nice.

Anyway, tada, Star Anise can slide around, but now with his antenna.

Not good enough.

Animating

It’s time to animate something. And this time around, all I’ve got are bytes to work with. Oh, boy!

Right out of the gate, I have two options. I could load all of Anise’s sprites into VRAM upfront and change the char numbers in OAM to animate him, or I could reserve some specific chars and overwrite them to animate him.

The first choice makes sense for an entity that might exist multiple times at once, like enemies or… virtually anything in the game world, really. But there’s only ever one player, and he’s likely to have a whole lot of spritework, which I would prefer not to have clogging up my char space for the entire duration of the game. So while I might use the other approach for most other things, I’m going to animate Anise by overwriting the actual graphics. Every frame.

First things first. I’m going to need some state, which I’ve been avoiding by relying on OAM. At the very least, I need to know which way Anise is facing — which isn’t necessarily the direction he’s moving, because he should keep his facing when he stops. I also need to know which animation frame he’s on, and how many LCD frames are left until he should advance to the next one.

Let’s refer to the time between vblanks as a “tic” for now, to avoid the ambiguity of a “frame” when talking about animation.

A good start, then, would be some constants.

1
2
3
4
5
6
FACING_DOWN   EQU 0
FACING_UP     EQU 1
FACING_RIGHT  EQU 2
FACING_LEFT   EQU 3

ANIMATION_LENGTH EQU 5

ANIMATION_LENGTH is the length of every frame. I don’t especially want to give every frame its own distinct duration if I can avoid it; this will be complicated enough as it is. I fiddled with the frame duration in Aseprite for a bit and landed on 83ms as a nice speed, and that’s 5 tics.

I also need a place for this state, so I add some more stuff to my RAM block.

1
2
3
4
5
6
anise_facing:
    db
anise_frame:
    db
anise_frame_countdown:
    db

And initialize it in setup.

1
2
3
4
    ld a, FACING_DOWN
    ld [anise_facing], a
    ld a, ANIMATION_LENGTH
    ld [anise_frame_countdown], a

Presumably, one day, I’ll have multiple entities, and they’ll all share a similar structure, which I’ll have to traverse manually. For now, it’s easier to follow the code if I give every field its own label.

I have four levels of hierarchy here: the spriteset (which for now is always Anise’s), the pose (I only have one: walking), the facing, and the frame. I need to traverse all four, but luckily I can ignore the first two for now.

I don’t want to animate Anise when he’s not moving, so I changed the OAM updating code to also ld d, 1 if there’s any movement at all, and skip over all the animation stuff if d is still zero.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
    ; ... read input ...

    ; This was before I knew the 'or a' trick; these two ops
    ; could be replaced with 'xor a; or d'
    ld a, d
    cp a, 0
    jp z, .no_movement

    ; ... all the animation code will go here ...

.no_movement:
    ; and after this we repeat the main loop

This does have the side effect that Anise will simply freeze in mid-walk when stopped, rather than returning to his standing pose. I still haven’t fixed that; I could special-case it, but I usually treat “standing” as its own one-frame animation, so it feels like something that ought to come when I implement poses.

Next I decrement the countdown, which is the number of tics left until the frame ought to change. If this is nonzero, I don’t need to do anything.

1
2
3
4
5
6
    ld a, [anise_frame_countdown]
    dec a
    ld [anise_frame_countdown], a
    jp nz, .no_movement
    ld a, ANIMATION_LENGTH
    ld [anise_frame_countdown], a

Again, this isn’t actually right. If Anise’s state changes, such as between standing and walking, then this should be ignored because he’s switching to a new animation. But this is a pose thing again, so I’m deferring it until later.

Next I need to advance the current frame. I don’t have modulo on hand and even simple ifs are kind of annoying, so I was naughty here and used bitops to roll from frame 3 to frame 0. This would obviously not work if the number of frames were not a power of two.

1
2
3
4
    ld a, [anise_frame]
    inc a
    and a, 4 - 1
    ld [anise_frame], a

Yet again, if Anise changes direction, the frame should be reset to zero… but it ain’t.

Now, let’s think for a second. I know what frame I want. I have a label for the upper-left corner of the spritesheet, and I want to get to the upper-left corner of the appropriate frame. Each frame has 3 objects; each object has 2 chars; each char is 16 bytes.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
    ld hl, ANISE_TEST_TILES
    ; Skip ahead 3 sprites * the current frame
    ld bc, 3 * 2 * 16
    ; Remember, zero iterations is also possible
    or a
    jr z, .skip_advancing_frame
.advance_frame:    
    add hl, bc
    dec a
    jr nz, .advance_frame
.skip_advancing_frame:
    ; Copy the sprites into VRAM
    ; They're consecutive in both the data and VRAM, so only
    ; one copy is necessary.  And bc is already right!
    ld d, h
    ld e, l
    ld hl, $8000
    call copy16

Hey, look at that!

Star Anise walking around in-game, now animated

Only one small problem: I forgot about facing, so Anise will always face forwards no matter how he moves. Whoops!

Facing

I need to actually track which way Anise is facing, which is a surprisingly subtle question. He might even be facing away from his own direction of movement, if for example he was thrown backwards by some external force.

A decent first approximation is to use the last button that was pressed. (That’s still not quite right — if you hold down, hold down+right, and then release right, he should obviously face down. But it’s a start.)

I don’t yet track which buttons were pressed this frame, but it’s easy enough to add. While I’m at it, I might as well track which buttons were released, too. I amend the input reading code thusly, based on the straightforward insight that a button was pressed this frame iff it is currently 1 and was previously 0.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
    ; a now contains the current buttons
    ld hl, buttons
    ld b, [hl]                  ; b <- previous buttons
    ld [hl], a                  ; a -> current buttons
    cpl
    and a, b
    ld [buttons_released], a    ; a = ~new & old, i.e. released
    ld a, [hl]                  ; a <- current buttons
    cpl
    or a, b
    cpl
    ld [buttons_pressed], a     ; a = ~(~new | old), i.e. pressed

I like that cute trick for getting the pressed buttons. I need a & ~b, but cpl only works on a, so I would’ve had to juggle a bunch of registers. But applying De Morgan’s law produces ~(~a | b), which only requires complementing a. (Full disclosure: I didn’t actually try register juggling, and for all I know it could end up shorter somehow.)

Next I check the just-pressed buttons and updating facing accordingly. It looks a lot like the code for checking the currently-held buttons, except that I only use the first button I find.

1
2
3
4
5
6
7
8
    ld hl, anise_facing
    ld a, [buttons_pressed]
    bit BUTTON_LEFT, a
    jr z, .skip_left2
    ld [hl], FACING_LEFT
    jr .skip_down2
.skip_left2:
    ; ... you get the idea ...

And finally, amend the sprite choosing code to pick the right facing, too.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
    ld hl, ANISE_TEST_TILES

    ; Skip ahead a number of /rows/, corresponding to facing
    ld a, [anise_facing]
    and a, %11                      ; cap to 4, just in case
    jr z, .skip_stride_row
    ; This is like before, but times 4 frames
    ld bc, 4 * 3 * 2 * 16
.stride_row:
    add hl, bc
    dec a
    jr nz, .stride_row
.skip_stride_row:

    ; Bumping the frame here is convenient, since it leaves the
    ; frame in a for the next part
    ld a, [anise_frame]
    inc a
    and a, 4 - 1
    ld [anise_frame], a

    ; ... continue on with picking the frame ...

Hardcoding the number of frames here is… unfortunate. I should probably flip the spritesheet so the frames go down and each column is a facing; then there’ll always be a fixed number of columns to skip over.

But who cares about that? Look at Anise go! Yeah!

Star Anise walking around in-game, now animated in all four directions

Well, yes, there is one final problem, which is that the antenna is misaligned when walking left or right… because its positioning is different than when walking up or down, and I don’t have any easy way to encode that at the moment. It’s still like that, in fact. I’m sure I’ll fix it eventually.

More vblank woes

I didn’t run into this problem until a little while later, but I might as well mention it now. The above code writes into VRAM in the middle of updating entities — updating them very simply, perhaps, but updating nonetheless. If that updating takes longer than vblank, the write will fail.

I expected this, though not quite so soon. It’s a disadvantage of swapping the char data rather than the char references: 32× more writing to do, which will take 32× longer. The solution is similar to what I do for OAM: defer the write until the next vblank. I’m already doing that with Anise’s position, anyway, and it makes no sense to have his position and animation updated on different frames.

I ended up special-casing this for Anise, though it wouldn’t be too hard to extend this into a queue of tiles to copy. It’s nothing too world-shaking; I just store the address of Anise’s current sprite in RAM, then copy it over during vblank, just after the OAM DMA.

I did try doing this with one of the Game Boy Color’s new features, general-purpose DMA, which can copy from basically anywhere in ROM or RAM to basically anywhere in VRAM. It involves five registers: you write the source address in the first two, the destination in the next two, and the length in the fifth, which triggers the copy. The CPU simply freezes until the copy is done, so there are no goofy timing issues here.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
    ld hl, anise_sprites_address
    ld a, [hl+]
    ld [rHDMA1], a
    ld a, [hl]
    ld [rHDMA2], a
    ld a, HIGH($0000)
    ld [rHDMA3], a
    ld a, LOW($0000)
    ld [rHDMA4], a
    ; To copy X bytes, write X / 16 - 1 to this register
    ld a, (32 * 3) / 16 - 1
    ld [rHDMA5], a

General-purpose DMA can copy 16 bytes every 8 cycles, or ½ cycle per byte. The fastest possible manual copy would be an unrolled series of ld a, [hl+]; ld [bc], a; inc bc which takes a whopping 6 cycles per byte — twelve times slower! This is a neat feature.

FYI, it’s also possible to have a copy done piecemeal during hblanks, though that sounds a bit fragile to me.

Future work

I’ve laid some very basic groundwork here, and there’s plenty more to do, which I will get back to later! It’s just me hacking all this together, after all, and I like flitting between different systems.

I will definitely need to figure out how the heck multiple tilesets work and when they get switched out. How do I even use multiple tilesets, each with its own set of palettes? What’s the workflow if I want to use the same tiles with several different palettes, like how the graveyard in Oracle of Ages is tinted purple? And I didn’t even implement character de-duplication yet… which will require some metadata for each tile… aw, geez.

And I still haven’t fixed the build system! Maybe you can understand why I’m hesitant to impose more structure on this idea quite yet.

To be continued

That brings us to commit 59ff18. Except for a commit about the build that I skipped. Whatever. This post has been a little more draining to write, perhaps because it forced me to confront and explain a bunch of hokey decisions.

Next time: resounding failure!

Cheezball Rising: Spring cleaning

Post Syndicated from Eevee original https://eev.ee/blog/2018/07/13/cheezball-rising-spring-cleaning/

This is a series about Star Anise Chronicles: Cheezball Rising, an expansive adventure game about my cat for the Game Boy Color. Follow along as I struggle to make something with this bleeding-edge console!

GitHub has intermittent prebuilt ROMs, or you can get them a week early on Patreon if you pledge $4. More details in the README!


In this issue, I tidy up some of the gigantic mess I’ve made thusfar.

Previously: writing a main loop, and finally getting something game-like.
Next: sprite and map loading.

Recap

After only a few long, winding posts’ worth of effort, I finally have a game, if you define “game” loosely as a thing that reacts when you press buttons.

A space cat roams around on a grassy background

Beautiful. But to make an omelette, you need to break a few eggs, and if it’s your first omelette then you might break some glassware too. As tiny as this game is, a couple things could use improvement.

Also, for narrative purposes, it’s much more interesting to put all these miscellaneous fixes together, rather than interrupting other posts with them. I didn’t actually do all this work in one lump in this order. Apologies to the die-hard non-fiction crowd.

It’s totally broken

Ah, the elephant in the room. The end of the previous post aligned with the first demo build, but if you downloaded it and tried to play it, you may have seen something that looks more like this:

Similar to the previous image, but with obvious graphical corruption

I said in the beginning that I liked mGBA and would be developing against it. That’s still true — it’s open source (and I’ve actually read some of it), it’s cross-platform, and it has some debug tools built in.

I also said that emulators are primarily designed to accept correct games, not necessarily to reject incorrect games. And that’s still very true.

I discovered this problem myself a little later (after the events of the next post), while shopping around a bit for emulators explicitly focused on accuracy. The one I keep being told to use is bgb, but it’s for Windows and Wine is kind of annoying, so I was exploring my other options; I found SameBoy (primarily for Mac, but with Linux and Windows builds sans debug features) and Gambatte (cross-platform, and the core for RetroArch’s Game Boy emulation). All three of them looked like the screenshot above.

Something was going very wrong when writing to VRAM. You can’t write to VRAM while the LCD is redrawing, so the most obvious cause is that… well… maybe the LCD is redrawing during my setup code.

Remember, on an actual Game Boy, the system doesn’t immediately start running what’s on the cartridge — it scrolls in the Nintendo logo first (or on a Color, does a fancier logo with a cool fanfare). That’s done by a tiny internal program called the boot ROM, and the state of the LCD when the boot ROM hands over control is undefined. I’m sure it’s consistent, but it’s not anything in particular, and for all I know it might be when the LCD is halfway through a redraw.

(Side note: I am violating Nintendo’s game submission requirements by consistently referring to it as a “cartridge” when in fact it is properly called a Game Pak. My bad.)

So what we’re seeing above is the result of VRAM becoming locked and unlocked as the LCD draws (remember, after every row is an hblank, during which time VRAM is accessible), while I’m trying to copy blocks of data there. In fact, every emulator I’ve tried shows a slightly different form of corruption, since this problem is very sensitive to timing accuracy. Super interesting!

I could wait for vblank and try to squeeze in all my setup code there, maybe even split across several vblanks. But since this is setup code and doesn’t run during gameplay, there’s a much easier solution: turn the screen off. That’s done with a bit in the LCDC register, which I currently configure at the end of my setup code; all I need to do is move that to the beginning and clear the appropriate bit instead.

1
2
    ld a, %00010111  ; $91 plus bit 2, minus bit 7
    ld [$ff40], a

Then, of course, set it again once I’m done. I did this with a couple macros, since it’s only a few instructions and it seems like the kind of thing I might need again later.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
DisableLCD: MACRO
    ld a, [$ff40]
    and a, %0111111
    ld [$ff40], a
ENDM

EnableLCD: MACRO
    ld a, [$ff40]
    or a, %10000000
    ld [$ff40], a
ENDM

; and, of course, stick an EnableLCD at the end of setup code

Note that when the screen is off, it’s off, and there are no vblank interrupts or anything else that might be triggered by the screen’s behavior. So, you know, don’t wait for vblank while the screen’s off. When the screen turns back on, it immediately starts redrawing from the first row, so don’t try to use VRAM right away either. Finally, on the original Game Boy, do not turn off the screen when it’s not in vblank, or you might physically damage the screen. It’s fine on the Game Boy Color, but… hell, I’m gonna edit this to wait for vblank anyway. Feels kinda inappropriate to abruptly turn off the screen halfway through drawing.

Anyway, that solves my goofy corruption problems, and now the game looks the same on all of these emulators! I also reported this misbehavior, and it’s since been fixed, so recent dev builds of mGBA also correctly render garbage for the first release. See, by not targeting the most accurate emulators, I’ve caused another emulator to become more accurate!

hardware.inc

I mentioned last time that I’d adopted hardware.inc. That’s in large part because I keep producing monstrosities like the previous snippet. Here are those macros with some symbolic constants:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
DisableLCD: MACRO
    ld a, [rLCDC]
    and a, $ff & ~LCDCF_ON
    ld [rLCDC], a
ENDM

EnableLCD: MACRO
    ld a, [rLCDC]
    or a, LCDCF_ON
    ld [rLCDC], a
ENDM

A breath of fresh air!

The $ff & is necessary because the argument needs to fit in a byte, but rgbasm’s integral preprocessor type is wider than a byte. I suppose I could also use LOW() here, or maybe there’s some other more straightforward solution.

Rearranging the buttons

In the previous post, I read the button states and crammed them into a single byte. I had a choice of whether to put the dpad low or the buttons low, but it didn’t seem to matter, so I picked arbitrarily: buttons high, dpad low.

It turns out I chose wrong! Also, it turns out there’s a “wrong” here! I’ve heard two compelling reasons to do it the other way. For one, hardware.inc contains constants for the bit offsets of the buttons, and it assumes the dpad is high. Why is this arbitrary data layout decision embedded in a list of hardware constants? Possibly for the second reason: on the GBA, input is available as a single word, and the lowest byte contains bits for all the buttons on the Game Boy — in the same order, with the dpad high.

So I’m switching this around and using hardware.incs constants. Easy change.

Fixing vblank

My original approach to waiting for vblank seemed simple enough: loop until vblank_flag is set, clear it, then continue on.

I’ve made a slight oversight here: what if the main loop does take longer than a frame? Then a vblank interrupt will fire in the middle of it and harmlessly set vblank_flag. But when the loop finally finishes and goes to wait for vblank again, the flag will already be set, and it’ll continue on immediately — regardless of the state of the screen! Whoops.

Again, the fix is simple: clear the flag before beginning to wait.

And while I’m at it, I see other uses for waiting for vblank in the near future, so I may as well pull this out into a function.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
; idle until next vblank
wait_for_vblank:
    xor a                       ; clear the vblank flag
    ld [vblank_flag], a
.vblank_loop:
    halt                        ; wait for interrupt
    ld a, [vblank_flag]         ; was it a vblank interrupt?
    and a
    jr z, .vblank_loop          ; if not, keep waiting
    ret

Copy function

So far, I’ve done an awful lot of runtime copying by using the preprocessor. Consider the code for copying the DMA routine into HRAM:

1
2
3
4
5
6
7
8
    ; Copy the little DMA routine into high RAM
    ld bc, dma_copy
    ld hl, $ff80
    REPT dma_copy_end - dma_copy
    ld a, [bc]
    inc bc
    ld [hl+], a
    ENDR

This will repeat the ld/inc/ld dance 13 times in the built ROM. Which is fine, except that I’m about to have places where I do much more copying, and there’s only so much space in the ROM, and this is kind of ridiculous. So I guess I will finally write a copy function.

I’m calling it copy, not memcpy. What else am I going to copy, if not memory?

Attempt number 1 looked like this:

1
2
3
4
5
6
7
8
; copy d bytes from bc to hl
copy:
    ld a, [bc]
    inc bc
    ld [hl+], a
    dec d
    jr z, copy
    ret

I was then informed that it’s more idiomatic to use de as the source address and c as the count, possibly for some reason relating to the NES or SNES? I don’t remember. I’m totally on board for using c to mean a count, though, and started doing that elsewhere.

I went to change that, and actually make use of this function, and lo! I discovered a colossal bug. That last line, jr z, copy, will loop only if d was just decremented to zero. So this function will only ever copy one byte, unless you asked to copy only one byte, in which case it copies two.

This is not the first time I’ve gotten a condition backwards. I’ll get used to it eventually, I’m sure.

Oh, one other minor problem: if you ask to copy zero bytes, you’ll actually copy 256, since the zero check only comes after the decrement. (This is a recurring annoyance, actually, and makes while loops surprisingly clumsy to express.) So far I’ve only ever needed to copy a constant amount, so this hasn’t been a problem, but… I’ll just leave a comment pretending it’s a feature.

1
2
3
4
5
6
7
8
9
; copy c bytes from de to hl
; NOTE: c = 0 means to copy 256 bytes!
copy:
    ld a, [de]
    inc de
    ld [hl+], a
    dec c
    jr nz, copy
    ret

And here it is in action:

1
2
3
4
5
    ; Copy the little DMA routine into high RAM
    ld de, dma_copy
    ld hl, $FF80
    ld c, dma_copy_end - dma_copy
    call copy

Cool.

Of course, this is now significantly slower than the original unrolled version. The original took 13 × (2 + 2 + 2) = 78 cycles; the function adds 6 cycles for the call, 4 cycles for the ret, and 13 × (1 + 3) = 52 for the counting and jumping. As c goes to infinity, the function takes about ⅔ longer than unrolling.

If I feel like it, I could mitigate this somewhat by partially unrolling. First I’d mask off some lower bits of c — say, the lowest two — and copy that many bytes. Now the amount of copying left is a multiple of four, so I could shift c right twice and have another loop that copies four bytes at a time, amortizing the cost of the decrement and jump.

It’s not urgent enough for me to want to bother yet, and it’ll make relatively little difference for small copies like this DMA one, but I’m strongly considering it for copying a 16-bit amount.

Reset vectors

Now I have a couple utility functions like copy and wait_for_vblank. I don’t really care where they go, so I put them in their own SECTION and let the linker figure it out.

It took a while for me to notice where, exactly, the linker had put them: at $0000! These functions are small, and I have nothing explicitly placed before the interrupt handlers (which begin at $0040), so rgblink saw some empty space and filled it.

The thing is, the Game Boy has eight instructions of the form rst $xx that act as fast calls — each one jumps to a fixed low address (a “reset vector”), using less time and space than a call would. And those fixed $xx addresses are… $00, and every eight bytes afterwards.

I don’t have any immediate use for these — eight bytes isn’t a lot, though I guess copy could fit in there — but I probably don’t want arbitrary code ending up where they go, so for now I’ll stub them out like I stubbed out the interrupt handlers.

(I have been advised of one very good use for reset vectors: putting a crash handler at $38. Why? Because rst $38 is encoded as $ff, which is a fairly common byte to encounter if you accidentally jump into garbage. A lot of the Game Boy’s RAM is even initialized to $ff at startup.)

Idioms

I’m still discovering what’s considered idiomatic, but here are a couple tidbits.

The set of instructions is a little scattershot as far as arguments go. Several times early on, I wrote stuff like this:

1
2
3
  ld hl, some_address
  ld a, 133
  ld [hl], a

But I overlooked that there are instructions for both ld [hl], n8 and ld [n16], a, so the above can be reduced to two lines. There’s no such thing as ld [n16], n8, though.

A surprising number of instructions can use [hl] directly as an operand — even inc and dec, combining fetch/mutate/store into a single instruction.

xor a is twice as short and twice as fast as ld a, 0. I mean, we’re talking about a single byte and single cycle here, but no reason not to.

(xor a really means xor a, a, but since every boolean op instruction takes a as the first argument anyway, it can be omitted. I don’t like to omit it in most cases, since xor b doesn’t mention a at all and that seems misleading, but it feels appropriate when combining a with itself.)

or a (equivalently, and a) is a quick way to test whether a is zero, since boolean ops set the zero flag.

Color

This is neither here nor there, but since this post began with emulator differences, here’s another one.

The screen you’re reading this on is almost certainly backlit, but the original Game Boy Color screen was not. A fully white pixel on a Game Boy Color is turned off — it’s the color of the screen itself, in which you can probably see your own reflection.

Which raises a tricky question: what color is that? The game thinks it’s pure white, but the screen was a sort of pale yellow. So how should it be rendered in an emulator, on a modern backlit LCD monitor?

Compounding this problem is that Game Boy Color games can also run on the Game Boy Advance, which showed the colors yet slightly differently. And, of course, even monitors may be calibrated differently, in which case it all goes out the window.

It’s interesting to see different emulators’ opinions of how to render color:

The same screenshot, seen in several different emulators with different color schemes

This is exactly the same ROM. The top left is mGBA out of the box, which shows colors completely unaltered — usually fairly saturated. The top right is mGBA with its “gba-colors” shader enabled, which is supposed to replicate how colors appear on a GBA screen, but seems passingly similar to a GBC too. Then on the bottom are two emulators renowned for their accuracy, here wildly disagreeing with each other.

My Game Boy Color is currently in a box somewhere, and until I can find it, I can’t be sure who’s closer. All of these are perfectly fine interpretations of the same art, though.

I may or may not use the “gba-colors” shader, and may or may not fiddle with mGBA’s color settings over time. If the colors vary a bit in future screenshots, that’s probably why.

To be continued

This post doesn’t really correspond to a particular commit very well, since it’s all little stuff I did here and there. I hope you’ve enjoyed the breather, because it’s all downhill from here. In a good way, I mean. Like a rollercoaster.

Next time: map and sprite loading, which will explain how I got from grass to the moon texture in the screenshots above!

Cheezball Rising: Main loop, input, and a game

Post Syndicated from Eevee original https://eev.ee/blog/2018/07/05/cheezball-rising-main-loop-input-and-a-game/

This is a series about Star Anise Chronicles: Cheezball Rising, an expansive adventure game about my cat for the Game Boy Color. Follow along as I struggle to make something with this bleeding-edge console!

GitHub has intermittent prebuilt ROMs, or you can get them a week early on Patreon if you pledge $4. More details in the README!


In this issue, I fill in the remaining bits necessary to have something that looks like a game.

Previously: drawing a sprite.

Recap

So far, I have this.

A very gaudy striped background with half a cat on top

It took unfathomable amounts of effort, but it’s something! Now to improve this from a static image to something a bit more game-like.

Quick note: I’ve been advised to use the de facto standard hardware.inc file, which gives symbolic names to all the registers and some of the flags they use. I hadn’t introduced it yet while doing the work described in this post, but for the sake of readability, I’m going to pretend I did and use that file’s constants in the code snippets here.

Interrupts

To get much further, I need to deal with interrupts. And to explain interrupts, I need to briefly explain calls.

Assembly doesn’t really have functions, only addresses and jumps. That said, the Game Boy does have call and ret instructions. A call will push the PC register (program counter, the address of the current instruction) onto the stack and perform a jump; a ret will pop into the PC register, effectively jumping back to the source of the call.

There are no arguments, return values, or scoping; input and output must be mediated by each function, usually via registers. Of course, since registers are global, a “function” might trample over their values in the course of whatever work it does. A function can manually push and pop 16-bit register pairs to preserve their values, or leave it up to the caller for speed/space reasons. All the conventions are free for me to invent or ignore. A “function” can even jump directly to another function and piggyback on the second function’s ret, kind of like Perl’s goto &sub… which I realize is probably less common knowledge than how call/return work in assembly.

Interrupts, then, are calls that can happen at any time. When one of a handful of conditions occurs, the CPU can immediately (or, rather, just before the next instruction) call an interrupt handler, regardless of what it was already doing. When the handler returns, execution resumes in the interrupted code.

Of course, since they might be called anywhere, interrupt handlers need to be very careful about preserving the CPU state. Pushing af is especially important (and this is the one place where af is used as a pair), because a is necessary for getting almost anything done, and f holds the flags which most instructions will invisibly trample.

Naturally, I completely forgot about this the first time around.

The Game Boy has five interrupts, each with a handler at a fixed address very low in ROM. Each handler only has room for eight bytes’ worth of instructions, which is enough to do a very tiny amount of work — or to just jump elsewhere.

A good start is to populate each one with only the reti instruction, which returns as usual and re-enables interrupts. The CPU disables interrupts when it calls an interrupt handler (so they thankfully can’t interrupt themselves), and returning with only ret will leave them disabled.

Naturally, I completely forgot about this the first time around.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
; Interrupt handlers
SECTION "Vblank interrupt", ROM0[$0040]
    ; Fires when the screen finishes drawing the last physical
    ; row of pixels
    reti

SECTION "LCD controller status interrupt", ROM0[$0048]
    ; Fires on a handful of selectable LCD conditions, e.g.
    ; after repainting a specific row on the screen
    reti

SECTION "Timer overflow interrupt", ROM0[$0050]
    ; Fires at a configurable fixed interval
    reti

SECTION "Serial transfer completion interrupt", ROM0[$0058]
    ; Fires when the serial cable is done?
    reti

SECTION "P10-P13 signal low edge interrupt", ROM0[$0060]
    ; Fires when a button is released?
    reti

These will do nothing. I mean, obviously, but they’ll do even less than nothing until I enable them. Interrupts are enabled by the dedicated ei instruction, which enables any interrupts whose corresponding bit is set in the IE register ($ffff).

So… which one do I want?

Game loop

To have a game, I need a game loop. The basic structure of pretty much any loop looks like:

  1. Load stuff.
  2. Check for input.
  3. Update the game state.
  4. Draw the game state.
  5. GOTO 2

(If you’ve never seen a real game loop written out before, LÖVE’s default loop is a good example, though even a huge system like Unity follows the same basic structure.)

The Game Boy seems to introduce a wrinkle here. I don’t actually draw anything myself; rather, the hardware does the drawing, and I tell it what to draw by using the palette registers, OAM, and VRAM.

But in fact, this isn’t too far off from how LÖVE (or Unity) works! All the drawing I do is applied to a buffer, not the screen; once the drawing is complete, the main loop calls present(), which waits until vblank and then draws the buffer to the screen. So what you see on the screen is delayed by up to a frame, and the loop really has an extra “wait for vsync” step at 3½. Or, with a little rearrangement:

  1. Load stuff.
  2. Wait for vblank.
  3. Draw the game state.
  4. Check for input.
  5. Update the game state.
  6. GOTO 2

This is approaching something I can implement! It works out especially well because it does all the drawing as early as possible during vblank. That’s good, because the LCD operation looks something like this:

1
2
3
4
5
6
7
LCD redrawing...
LCD redrawing...
LCD redrawing...
LCD redrawing...
VBLANK
LCD idle
LCD idle

While the LCD is refreshing, I can’t (easily) update anything it might read from. I only have free control over VRAM et al. during a short interval after vblank, so I need to do all my drawing work right then to ensure it happens before the LCD starts refreshing again. Then I’m free to update the world while the LCD is busy.

First, right at the entry point, I enable the vblank interrupt. It’s bit 0 of the IE register, but hardware.inc has me covered.

1
2
3
4
5
main:
    ; Enable interrupts
    ld a, IEF_VBLANK
    ldh [rIE], a
    ei

Next I need to make the handler actually do something. The obvious approach is for the handler to call one iteration of the game loop, but there are a couple problems with that. For one, interrupts are disabled when a handler is called, so I would never get any other interrupts. I could explicitly re-enable interrupts, but that raises a bigger question: what happens if the game lags, and updating the world takes longer than a frame? With this approach, the game loop would interrupt itself and then either return back into itself somewhere and cause untold chaos, or take too long again and eventually overflow the stack. Neither is appealing.

An alternative approach, which I found in gb-template but only truly appreciated after some thought, is for the vblank handler to set a flag and immediately return. The game loop can then wait until the flag is set before each iteration, just like LÖVE does. If an update takes longer than a frame, no problem: the loop will always wait until the next vblank, and the game will simply run more slowly.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
SECTION "Vblank interrupt", ROM0[$0040]
    push hl
    ld hl, vblank_flag
    ld [hl], 1
    pop hl
    reti

...

SECTION "Important twiddles", WRAM0[$C000]
; Reserve a byte in working RAM to use as the vblank flag
vblank_flag:
    db

The handler fits in eight bytes — the linker would yell at me if it didn’t, since another section starts at $0048! — and leaves all the registers in their previous states. As I mentioned before, I originally neglected to preserve registers, and some zany things started to happen as a and f were abruptly altered in the middle of other code. Whoops!

Now the main loop can look like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
main:
    ; ... bunch of setup code ...

vblank_loop:
    ; Main loop: halt, wait for a vblank, then do stuff

    ; The halt instruction stops all CPU activity until the
    ; next interrupt, which saves on battery, or at least on
    ; CPU cycles on an emulator's host system.
    halt
    ; The Game Boy has some obscure hardware bug where the
    ; instruction after a halt is occasionally skipped over,
    ; so every halt should be followed by a nop.  This is so
    ; ubiquitous that rgbasm automatically adds a nop after
    ; every halt, so I don't even really need this here!
    nop

    ; Check to see whether that was a vblank interrupt (since
    ; I might later use one of the other interrupts, all of
    ; which would also cancel the halt).
    ld a, [vblank_flag]
    ; This sets the zero flag iff a is zero
    and a
    jr z, vblank_loop
    ; This always sets a to zero, and is shorter (and thus
    ; faster) than ld a, 0
    xor a, a
    ld [vblank_flag], a

    ; Use DMA to update object attribute memory.
    ; Do this FIRST to ensure that it happens before the screen starts to update again.
    call $FF80

    ; ... update everything ...

    jp vblank_loop

It’s looking all the more convenient that I have my own copy of OAM — I can update it whenever I want during this loop! I might need similar facilities later on for editing VRAM or changing palettes.

Doing something and reading input

I have a loop, but since nothing’s happening, that’s not especially obvious. Input would take a little effort, so I’ll try something simpler first: making Anise move around.

I don’t actually track Anise’s position anywhere right now, except for in the OAM buffer. Good enough. In my main loop, I add:

1
2
3
4
    ld hl, oam_buffer + 1
    ld a, [hl]
    inc a
    ld [hl], a

The second byte in each OAM entry is the x-coordinate, and indeed, this causes Anise’s torso to glide rightwards across the screen at 60ish pixels per second. Eventually the x-coordinate overflows, but that’s fine; it wraps back to zero and moves the sprite back on-screen from the left.

The half-cat is now sliding across the screen

Excellent. I mean, sorry, this is extremely hard to look at, but bear with me a second.

This would be a bit more game-like if I could control it with the buttons, so let’s read from them.

There are eight buttons: up, down, left, right, A, B, start, select. There are also eight bits in a byte. You might suspect that I can simply read an I/O register to get the current state of all eight buttons at once.

Ha, ha! You naïve fool. Of course it’s more convoluted than that. That single byte thing is a pretty good idea, though, so what I’ll do is read the input at the start of the frame and coax it into a byte that I can consult more easily later.

Turns out I pretty much have to do that, because button access is slightly flaky. Even the official manual advises reading the buttons several times to get a reliable result. Yikes.

Here’s how to do it. The buttons are wired in two groups of four: the dpad and everything else. Reading them is thus also done in two groups of four. I need to use the P1 register, which I assume is short for “player 1” and is so named because the people who designed this hardware had also designed the two-player NES?

Bits 5 and 6 of P1 determine which set of four buttons I want to read, and then the lower nybble contains the state of those buttons. Note that each bit is set to 1 if the button is released; I think this is a quirk of how they’re wired, and what I’m doing is extremely direct hardware access. Exciting! (Also very confusing on my first try, where Anise’s movement was inverted.)

The code, which is very similar to an example in the official manual, thus looks like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
    ; Poll input
    ; The direct hardware access is nonsense and unreliable, so
    ; just read once per frame and stick all the button states
    ; in a byte

    ; Bit 6 means to read the dpad
    ld a, $20
    ldh [rP1], a
    ; But it's unreliable, so do it twice
    ld a, [rP1]
    ld a, [rP1]
    ; This is 'complement', and flips all the bits in a, so now
    ; set bits will mean a button is held down
    cpl
    ; Store the lower four bits in b
    and a, $0f
    ld b, a

    ; Bit 5 means to read the buttons
    ld a, $10
    ldh [rP1], a
    ; Apparently this is even more unreliable??  No, really, the
    ; manual does this: two reads, then six reads
    ld a, [rP1]
    ld a, [rP1]
    ld a, [rP1]
    ld a, [rP1]
    ld a, [rP1]
    ld a, [rP1]
    ; Again, complement and mask off the lower four bits
    cpl
    and a, $0f
    ; b already contains four bits, so I need to shift something
    ; left by four...  but the shift instructions only go one
    ; bit at a time, ugh!  Luckily there's swap, which swaps the
    ; high and low nybbles in any register
    swap a
    ; Combine b's lower nybble with a's high nybble
    or a, b
    ; And finally store it in RAM
    ld [buttons], a

...

SECTION "Important twiddles", WRAM0[$C000]
vblank_flag:
    db
buttons:
    db

Phew. That was a bit of a journey, but now I have the button state as a single byte. To help with reading the buttons, I’ll also define a few constants labeling the individual bits. (There are instructions for reading a particular bit by number, so I don’t need to mask a single bit out.)

1
2
3
4
5
6
7
8
9
; Constants
BUTTON_RIGHT  EQU 0
BUTTON_LEFT   EQU 1
BUTTON_UP     EQU 2
BUTTON_DOWN   EQU 3
BUTTON_A      EQU 4
BUTTON_B      EQU 5
BUTTON_START  EQU 6
BUTTON_SELECT EQU 7

Now to adjust the sprite position based on what directions are held down. Delete the old code and replace it with:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
    ; Set b/c to the y/x coordinates
    ld hl, oam_buffer
    ld b, [hl]
    inc hl
    ld c, [hl]

    ; This sets the z flag to match a particular bit in a
    bit BUTTON_LEFT, a
    ; If z, the bit is zero, so left isn't held down
    jr z, .skip_left
    ; Otherwise, left is held down, so decrement x
    dec c
.skip_left:

    ; The other three directions work the same way
    bit BUTTON_RIGHT, a
    jr z, .skip_right
    inc c
.skip_right:
    bit BUTTON_UP, a
    jr z, .skip_up
    dec b
.skip_up:
    bit BUTTON_DOWN, a
    jr z, .skip_down
    inc b
.skip_down:

    ; Finally, write the new coordinates back to the OAM
    ; buffer, which hl is still pointing into
    ld [hl], c
    dec hl
    ld [hl], b

Miraculously, Anise’s torso now moves around on command!

The half-cat is now moving according to button presses

Neat! But this still looks really, really, incredibly bad.

Aesthetics

It’s time to do something about this artwork.

First things first: I’m really tired of writing out colors by hand, in binary, so let’s fix that. In reality, I did this bit after adding better art, but doing it first is better for everyone.

I think I’ve mentioned before that rgbasm has (very, very rudimentary) support for macros, and this seems like a perfect use case for one. I’d like to be able to write colors out in typical rrggbb hex fashion, so I need to convert a 24-bit color to a 16-bit one.

1
2
3
4
5
6
dcolor: MACRO  ; $rrggbb -> gbc representation
_r = ((\1) & $ff0000) >> 16 >> 3
_g = ((\1) & $00ff00) >> 8  >> 3
_b = ((\1) & $0000ff) >> 0  >> 3
    dw (_r << 0) | (_g << 5) | (_b << 10)
    ENDM

This is going to need a whole paragraph of caveats.

A macro is contained between MACRO and ENDM. The assembler has a curious sort of universal assignment syntax, where even ephemeral constructs like macros are introduced by labels. Macros can take arguments, but they aren’t declared; they’re passed more like arguments to shell scripts, where the first argument is \1 and so forth. (There’s even a SHIFT command for accessing arguments beyond the ninth.) Also, passing strings to a macro is some kind of byzantine nightmare where you have to slap backslashes in just the right places and I will probably avoid doing it altogether if I can at all help it.

Oh, one other caveat: compile-time assignments like I have above must start in the first column. I believe this is because assignments are also labels, and labels have to start in the first column. It’s a bit weird and apparently rgbasm’s lexer is horrifying, but I’ll take it over writing my own assembler and stretching this project out any further.

Anyway, all of that lets me write dcolor $ff0044 somewhere and have it translated at compile time to the appropriate 16-bit value. (I used dcolor to parallel db and friends, but I’m strongly considering using CamelCase exclusively for macros? Guess it depends how heavily I use them.)

With that on hand, I can now doodle some little sprites in Aseprite and copy them in. This part is not especially interesting and involves a lot of squinting at zoomed-in sprites.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
SECTION "Sprites", ROM0
PALETTE_BG0:
    dcolor $80c870  ; light green
    dcolor $48b038  ; darker green
    dcolor $000000  ; unused
    dcolor $000000  ; unused
PALETTE_ANISE:
    dcolor $000000  ; TODO
    dcolor $204048
    dcolor $20b0b0
    dcolor $f8f8f8
GRASS_SPRITE:
    dw `00000000
    dw `00000000
    dw `01000100
    dw `01010100
    dw `00010000
    dw `00000000
    dw `00000000
    dw `00000000
EMPTY_SPRITE:
    dw `00000000
    dw `00000000
    dw `00000000
    dw `00000000
    dw `00000000
    dw `00000000
    dw `00000000
    dw `00000000
ANISE_SPRITE:
    ; ... I'll revisit this momentarily

Gorgeous. You may notice that I put the colors as data instead of inlining them in code, which incidentally makes the code for setting the palette vastly shorter as well:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
    ; Start setting the first color, and advance the internal
    ; pointer on every write
    ld a, %10000000
    ; BCPS = Background Color Palette Specification
    ldh [rBCPS], a

    ld hl, PALETTE_BG0
    REPT 8
    ld a, [hl+]
    ; Same, but Data
    ld [rBCPD], a
    ENDR

Loading sprites into VRAM also becomes a bit less of a mess:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
    ; Load some basic tiles
    ld hl, $8000

    ; Read the 16-byte empty sprite into tile 0
    ld bc, EMPTY_SPRITE
    REPT 16
    ld a, [bc]
    inc bc
    ld [hl+], a
    ENDR

    ; Read the grass sprite into tile 1, which immediately
    ; follows tile 0, so hl is already in the right place
    ld bc, GRASS_SPRITE
    REPT 16
    ld a, [bc]
    inc bc
    ld [hl+], a
    ENDR

Someday I should write an actual copy function, since at the moment, I’m using an alarming amount of space for pointlessly unrolled loops. Maybe later.

You may notice I now have two tiles, whereas before I was relying on filling the entire screen with one tile, tile 0. I want to dot the landscape with tile 1, which means writing a bit more to the actual background grid, which begins at $9800 and has one byte per tile.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
    ; Fill the screen buffer with a pattern of grass tiles,
    ; where every 2x2 block has a single grass at the top left.
    ; Note that the buffer is 32x32 tiles, and it ends at $9c00
    ld hl, $9800
.screen_fill_loop:
    ; Use tile 1 for every other tile in this row.  Note that
    ; REPTed part increments hl /twice/, thus skipping a tile
    ld a, $01
    REPT 16
    ld [hl+], a
    inc hl
    ENDR
    ; Skip an entire row of 32 tiles, which will remain empty.
    ; There is almost certainly a better way to do this, but I
    ; didn't do it.  (Hint: it's ld bc, $20; add hl, bc)
    REPT 32
    inc hl
    ENDR
    ; If we haven't reached $9c00 yet, continue looping
    ld a, h
    cp a, $9C
    jr c, .screen_fill_loop

Sorry for all these big blocks of code, but check out this payoff!

A very simple grassy background

POW! Gorgeous.

And hey, why stop there? With a little more pixel arting against a very reduced palette…

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
SPRITE_ANISE_FRONT_1:
    dw `00000111
    dw `00001222
    dw `00012222
    dw `00121222
    dw `00121122
    dw `00121111
    dw `00121122
    dw `00121312
    dw `00121313
    dw `00012132
    dw `00001211
    dw `00000123
    dw `00100123
    dw `00011133
    dw `00000131
    dw `00000010
SPRITE_ANISE_FRONT_2:
    dw `11100000
    dw `22210000
    dw `22221000
    dw `22212100
    dw `22112100
    dw `11112100
    dw `22112100
    dw `21312100
    dw `31312100
    dw `23121000
    dw `11210000
    dw `32100000
    dw `32100000
    dw `33100000
    dw `13100000
    dw `01000000

Yes, I am having trouble deciding on a naming convention.

This is now a 16×16 sprite, made out of two 8×16 parts. This post has enough code blocks as it is, and the changes to make this work are relatively minor copy/paste work, so the quick version is:

  1. Set the LCDC flag (bit 2, or LCDCF_OBJ16) that makes objects be 8×16. This mode uses pairs of tiles, so an object that uses either tile 0 or 1 will draw both of them, with tile 0 on top of tile 1.
  2. Extend the code that loads object tiles to load four instead.
  3. Define a second sprite that’s 8 pixels to the right of the first one.
  4. Remove the hard-coded object palette, and instead load the PALETTE_ANISE that I sneakily included above. This time the registers are called rOCPS and rOCPD.

Finally, extend the code that moves the sprite to also move the second half:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
    ; Finally, write the new coordinates back to the OAM
    ; buffer, which hl is still pointing into
    ld [hl], c
    dec hl
    ld [hl], b
    ; This bit is new: copy the x-coord into a so I can add 8
    ; to it, then store both coords into the second sprite's
    ; OAM data
    ld a, c
    add a, 8
    ; I could've written this the other way around, but I did
    ; not, I guess because this structure mirrors the above?
    ld hl, oam_buffer + 5
    ld [hl], a
    dec hl
    ld [hl], b

Cross my fingers, and…

A little cat sprite atop the grassy background

Hey hey hey! That finally looks like something!

To be continued

It was a surprisingly long journey, but this brings us more or less up to commit 313a3e, which happens to be the first commit I made a release of! It’s been more than a week, so you can grab it on Patreon or GitHub. I strongly recommend playing it with a release of mGBA prior to 0.7, for… reasons that will become clear next time.

Next time: I’ll take a breather and clean up a few things.

Cheezball Rising: Drawing a sprite

Post Syndicated from Eevee original https://eev.ee/blog/2018/06/21/cheezball-rising-drawing-a-sprite/

This is a series about Star Anise Chronicles: Cheezball Rising, an expansive adventure game about my cat for the Game Boy Color. Follow along as I struggle to make something with this bleeding-edge console!

source codeprebuilt ROMs (a week early for $4) • works best with mGBA

In this issue, I figure out how to draw a sprite. This part was hard.

Previously: figuring out how to put literally anything on the goddamn screen.

Recap

Welcome back! I’ve started cobbling together a Pygments lexer for RGBDS’s assembly flavor, so hopefully the code blocks are more readable, and will become moreso over time.

When I left off last time, I had… um… this.

Vertical stripes of red, green, blue, and white

This is all on the background layer, which I mentioned before is a fixed grid of 8×8 tiles.

For anything that moves around freely, like the player, I need to use the object layer. So that’s an obvious place to go next.

Now, if you remember, I can define tiles by just writing to video RAM, and I define palettes with a goofy system involving writing them one byte at a time to the same magic address. You might expect defining objects to do some third completely different thing, and you’d be right!

Defining an object

Objects are defined in their own little chunk of RAM called OAM, for object attribute memory. They’re also made up of tiles, but each tile can be positioned at an arbitrary point on the screen.

OAM starts at $fe00 and each object takes four bytes — the y-coordinate, the x-coordinate, the tile number, and some flags — for a total of 160 bytes. There are some curiosities, like how the top left of the screen is (8, 10) rather than (0, 0), but I’ll figure out what’s up with that later. (I suppose if zeroes meant the upper left corner, there’d be a whole stack of tile 0 there all the time.)

Here’s the fun part: I can’t write directly to OAM? I guess??? Come to think of it, I don’t think the manual explicitly says I can’t, but it’s strongly implied. Hmm. I’ll look into that. But I didn’t at the time, so I’ll continue under the assumption that the following nonsense is necessary.

Because I “can’t” write directly, I need to use some shenanigans. First, I need something to write! This is an Anise game, so let’s go for Anise.

I’m on my laptop at this point without access to the source code for the LÖVE Anise game I started, so I have to rustle up a screenshot I took.

Cropped screenshot of Star Anise and some critters, all pixel art

Wait a second.

Even on the Game Boy Color, tiles are defined with two bits per pixel. That means an 8×8 tile has a maximum of four colors. For objects, the first color is transparent, so I really have three colors — which is exactly why most Game Boy Color protagonists have a main color, an outline/shadow color, and a highlight color.

Let’s check out that Anise in more detail.

Star Anise at 8×

Hm yes okay that’s more than three colors. I guess I’m going to need to draw some new sprites from scratch, somehow.

In the meantime, I optimistically notice that Star Anise’s body only uses three colors, and it’s 8×7! I could make a tile out of that! I painstakingly copy the pixels into a block of those backticks, which you can kinda see is his body if you squint a bit:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
SECTION "Sprites", ROM0
ANISE_SPRITE:
    dw `00000000
    dw `00001333
    dw `00001323
    dw `10001233
    dw `01001333
    dw `00113332
    dw `00003002
    dw `00003002

The dw notation isn’t an opcode; it tells the assembler to put two literal bytes of data in the final ROM. A word of data. (Each row of a tile is two bytes, remember.)

If you think about this too hard, you start to realize that both the data and code are just bytes, everything is arbitrary, and true meaning is found only in the way we perceive things rather than in the things themselves.

Note I didn’t specify an exact address for this section, so the linker will figure out somewhere to put it and make sure all the labels are right at the end.

Now I load this into tilespace, back in my main code:

1
2
3
4
5
6
7
8
    ; Define an object
    ld hl, $8800
    ld bc, ANISE_SPRITE
    REPT 16
    ld a, [bc]
    ld [hl+], a
    inc bc
    ENDR

This copies 16 bytes, starting from the ANISE_SPRITE label, to $8800.


Why $8800, not $8000? I’m so glad you asked!

There are actually three blocks of tile space, each with enough room for 128 tiles: one at $8000, one at $8800, and one at $9000. Object tiles always use the $8000 block followed by the $8800 block, whereas background tiles can use either $8000 + $8800 or $9000 + $8800. By default, background tiles use $8000 + $8800.

All of which is to say that I got very confused reading the manual (which spends like five pages explaining the above paragraph) and put the object tiles in the wrong place. Whoops. It’s fine; this just ends up being tile 128.

In my partial defense, looking at it now, I see the manual is wrong! Bit 4 of the LCD controller register ($ff40) controls whether the background uses tiles from $8000 + $8800 (1) or $9000 + $8800 (0). The manual says that this register defaults to $83, which has bit 4 off, suggesting that background tiles use $9000 + $8800 (i.e. start at $8800), but disassembly of the boot ROM shows that it actually defaults to $91, which has bit 4 on. Thanks a lot, Nintendo!

That was quite a diversion. Here’s a chart of where the dang tiles live. Note that the block at $8800 is always shared between objects and background tiles. Oh, and on the Game Boy Color, all three blocks are twice as big thanks to the magic of banking. I’ll get to banking… much later.

1
2
3
4
5
                            bit 4 ON (default)  bit 4 OFF
                            ------------------  ---------
$8000   obj tiles 0-127     bg tiles 0-127
$8800   obj tiles 128-255   bg tiles 128-255    bg tiles 128-255
$9000                                           bg tiles 0-127

Hokay. What else? I’m going to need a palette for this, and I don’t want to use that gaudy background palette. Actually, I can’t — the background and object layers have two completely separate sets of palettes.

Writing an object palette is exactly the same as writing a background palette, except with different registers.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
    ; This should look pretty familiar
    ld a, %10000000
    ld [$ff6a], a

    ld bc, %0000000000000000  ; transparent
    ld a, c
    ld [$ff6b], a
    ld a, b
    ld [$ff6b], a
    ld bc, %0010110100100101  ; dark
    ld a, c
    ld [$ff6b], a
    ld a, b
    ld [$ff6b], a
    ld bc, %0100000111001101  ; med
    ld a, c
    ld [$ff6b], a
    ld a, b
    ld [$ff6b], a
    ld bc, %0100001000010001  ; white
    ld a, c
    ld [$ff6b], a
    ld a, b
    ld [$ff6b], a

Riveting!

I wrote out those colors by hand. The original dark color, for example, was #264a59. That uses eight bits per channel, but the Game Boy Color only supports five (a factor of 8 difference), so first I rounded each channel to the nearest 8 and got #284858. Swap the channels to get 58 48 28 and convert to binary (sans the trailing zeroes) to get 01011 01001 00101.

Note to self: probably write a macro or whatever so I can define colors like a goddamn human being. Also why am I not putting the colors in a ROM section too?

Almost there. I still need to write out those four bytes that specify the tile and where it goes. I can’t actually write them to OAM yet, so I need some scratch space in regular RAMworking RAM.

1
2
3
SECTION "OAM Buffer", WRAM0[$C100]
oam_buffer:
    ds 4 * 40

The ds notation is another “data” variant, except it can take a size and reserves space for a whole string of data. Note that I didn’t put any actual data here — this section is in RAM, which only exists while the game is running, so there’d be nowhere to put data.

Also note that I gave an explicit address this time. The buffer has to start at an address ending in 00, for reasons that will become clear momentarily. The space from $c000 to $dfff is available as working RAM, and I chose $c100 for… reasons that will also become clear momentarily.

Now to write four bytes to it at runtime:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
    ; Put an object on the screen
    ld hl, oam_buffer
    ; y-coord
    ld a, 64
    ld [hl+], a
    ; x-coord
    ld [hl+], a
    ; tile index
    ld a, 128
    ld [hl+], a
    ; attributes, including palette, which are all zero
    ld a, %00000000
    ld [hl+], a

(I tried writing directly to OAM on my first attempt. Nothing happened! Very exciting.)

But how to get this into OAM so it’ll actually show on-screen? For that, I need to do a DMA transfer.

DMA

DMA, or direct memory access, is one of those things the Game Boy programming manual seems to think everyone is already familiar with. It refers generally to features that allow some other hardware to access memory, without going through the CPU. In the case of the Game Boy, it’s used to copy data from working RAM to OAM. Only to OAM. It’s very specific.

Performing a DMA transfer is super easy! I write the high byte of the source address to the DMA register ($ff46), and then some magic happens, and 160 bytes from the source address appear in OAM. In other words:

1
2
3
    ld a, $c1       ; copy from $c100
    ld [$ff46], a   ; perform DMA transfer
    ; now $c000 through $c09f have been copied into OAM!

It’s almost too good to be true! And it is. There are some wrinkles.

First, the transfer takes some time, during which I almost certainly don’t want to be doing anything else.

Second, during the transfer, the CPU can only read from “high RAM” — $ff80 and higher. Wait, uh oh.

The usual workaround here is to copy a very short function into high RAM to perform the actual transfer and wait for it to finish, then call that instead of starting a transfer directly. Well, that sounds like a pain, so I break my rule of accounting for every byte and find someone else who’s done it. Conveniently enough, that post is by the author of the small template project I’ve been glancing at.

I end up with something like the following.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
    ; Copy the little DMA routine into high RAM
    ld bc, DMA_BYTECODE
    ld hl, $ff80
    ; DMA routine is 13 bytes long
    REPT 13
    ld a, [bc]
    inc bc
    ld [hl+], a
    ENDR

; ...

SECTION "DMA Bytecode", ROM0
DMA_BYTECODE:
    db $F5, $3E, $C1, $EA, $46, $FF, $3E, $28, $3D, $20, $FD, $F1, $D9

That’s compiled assembly, written inline as bytes. Oh boy. The original code looks like:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
    ; start the transfer, as shown above
    ld a, $c1
    ld [$ff46], a

    ; wait 160 cycles/microseconds, the time it takes for the
    ; transfer to finish; this works because 'dec' is 1 cycle
    ; and 'jr' is 3, for 4 cycles done 40 times
    ld      a, 40
loop:
    dec     a
    jr      nz, loop

    ; return
    ret

Now you can see why I used $c100 for my OAM buffer: because it’s the address this person used.

(Hm, the opcode reference I usually use seems to have all the timings multiplied by a factor of 4 without comment? Odd. The rgbds reference is correct.)

(Also, here’s a fun fact: the stack starts at $fffe and grows backwards. If it grows too big, the very first thing it’ll overwrite is this DMA routine! I bet that’ll have some fun effects.)

At this point I have a thought. (Okay, I had the thought a bit later, but it works better narratively if I have it now.) I’ve already demonstrated that the line between code and data is a bit fuzzy here. So why does this code need to be pre-assembled?

And a similar thought: why is the length hardcoded? Surely, we can do a little better. What if we shuffle things around a bit…

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
SECTION "init", ROM0[$0100]
    nop
    ; Jump to a named label instead of an address
    jp main

SECTION "main", ROM0[$0150]
; DMA copy routine, copied into high RAM at startup.
; Never actually called where it is.
dma_copy:
    ld a, $c1
    ld [$ff46], a
    ld a, 40
.loop:
    dec a
    jr nz, .loop
    ret
dma_copy_end:
    nop

main:
    ; ... all previous code is here now ...

    ; Copy the little DMA routine into high RAM
    ld bc, dma_copy
    ld hl, $ff80
    ; DMA routine is 13 bytes long
    REPT dma_copy_end - dma_copy
    ld a, [bc]
    inc bc
    ld [hl+], a
    ENDR

This is very similar to what I just had, except that the code is left as code, and its length is computed by having another label at the end — so I’m free to edit it later if I want to. It all ends up as bytes in the ROM, so the code ends up exactly the same as writing out the bytes with db. Come to think of it, I don’t even need to hardcode the $c1 there; I could replace it with oam_buffer >> 8 and avoid repeating myself.

(I put the code at $0150 because rgbasm is very picky about subtracting labels, and will only do it if they both have fixed positions. These two labels would be the same distance apart no matter where I put the section, but I guess rgbasm isn’t smart enough to realize that.)

I’m actually surprised that the author of the above post didn’t think to do this? Maybe it’s dirty even by assembly standards.

Timing, vblank, and some cool trickery

Okay, so, as I was writing that last section, I got really curious about whether and when I’m actually allowed to write to OAM. Or tile RAM, for that matter.

I found/consulted the Game Boy dev wiki, and the rules match what’s in the manual, albeit with a chart that makes things a little more clear.

My understanding is as follows. The LCD draws the screen one row of pixels at a time, and each row has the following steps:

  1. Look through OAM to see if any sprites are on this row. OAM is inaccessible to the CPU.

  2. Draw the row. OAM, VRAM, and palettes are all inaccessible.

  3. Finish the row and continue on to the beginning of the next row. This takes a nonzero amount of time, called the horizontal blanking period, during which the CPU can access everything freely.

Once the LCD reaches the bottom, it continues to “draw” a number of faux rows below the bottom of the visible screen (vertical blanking), and the CPU can again do whatever it wants. Eventually it returns to the top-left corner to draw again, concluding a single frame. The entire process happens 59.7 times per second.

There’s one exception: DMA transfers can happen any time, but the LCD will simply not draw sprites during the transfer.

So I probably shouldn’t be writing to tiles and palettes willy-nilly. I suspect I got away with it because it happened in that first OAM-searching stage… and/or because I did it on emulators which are a bit more flexible than the original hardware.

In fact…

Same screenshot as above, but the first row of pixels is corrupt

I took this screenshot by loading the ROM I have so far, pausing it, resetting it, and then advancing a single frame. This is the very first frame my game shows. If you look closely at the first row of pixels, you can see they’re actually corrupt — they’re being drawn before I’ve set up the palette! You can even see each palette entry taking effect along the row.

This is very cool. It also means my current code would not work at all on actual hardware. I should probably just turn the screen off while I’m doing setup like this.

It’s interesting that only OAM gets a special workaround in the form of a DMA transfer — I imagine because sprites move around much more often than the tileset changes — but having the LCD stop drawing sprites in the meantime is quite a limitation. Surely, you’d only want to do a DMA transfer during vblank anyway? It is much faster than copying by hand, so I’ll still take it.

All of this is to say: I’m gonna need to care about vblanks.


Incidentally, the presence of hblank is very cool and can be used for a number of neat effects, especially when combined with the Game Boy’s ability to call back into user code when the LCD reaches a specific row:

  • The GBC Zelda games use it for map scrolling. The status bar at the top is in one of the two background maps, and as soon as that finishes drawing, the game switches to the other one, which contains the world.

  • Those same games also use it for a horizontal wavy effect, both when warping around and when underwater — all they need to do is change the background layer’s x offset during each hblank!

  • The wiki points out that OAM could be written to in the middle of a screen update, thus bypassing the 40-object restriction: draw 40 objects on the top half of the screen, swap out OAM midway, and then the LCD will draw a different 40 on the bottom half!

  • I imagine you could also change palettes midway through a redraw and exceed the usual limit of 56 colors on screen at a time! No telling whether this sort of trick would work on an emulator, though.

I am very excited at the prospects here.

I’m also slightly terrified. I have a fixed amount of time between frames, and with the LCD as separate hardware, there’s no such thing as a slow frame. If I don’t finish, things go bad. And that time is measured in instructions — an ld always takes the same number of cycles! There’s no faster computer or reducing GC pressure. There’s just me. Yikes.

Back to drawing a sprite

I haven’t had a single new screenshot this entire post! This is ridiculous. All I want is to draw a thing to the screen.

I have some data in my OAM buffer. I have DMA set up. All I should need to do now is start a transfer.

1
    call $ff80

And… nothing. mGBA’s memory viewer confirms everything’s in the right place, but nothing’s on the screen.

Whoops! Remember that LCD controller register, and how it defaults to $91? Well, bit 1 is whether to show objects at all, and it defaults to off. So let’s fix that.

1
2
    ld a, %10010011  ; $91 plus bit 2
    ld [$ff40], a
The same gaudy background, but now with a partial Anise sprite on top

SUCCESS!

It doesn’t look like much, but it took a lot of flailing to get here, and I was overjoyed when I first saw it. The rest should be a breeze! Right?

To be continued

That doesn’t even get us all the way through commit 1b17c7, but this is already more than enough.

Next time: input, and moderately less eye-searing art!

Cheezball Rising: A new Game Boy Color game

Post Syndicated from Eevee original https://eev.ee/blog/2018/06/19/cheezball-rising-a-new-game-boy-color-game/

This is a series about Star Anise Chronicles: Cheezball Rising, an expansive adventure game about my cat for the Game Boy Color. Follow along as I struggle to make something with this bleeding-edge console!

source codeprebuilt ROMs (a week early for $4) • works best with mGBA

In this issue, I figure out how to put literally anything on the goddamn screen, then add a splash of color.

The plan

I’m making a Game Boy Color game!

I have no— okay, not much idea what I’m doing, so I’m going to document my progress as I try to forge a 90s handheld game out of nothing.

I do usually try to keep tech stuff accessible, but this is going to get so arcane that that might be a fool’s errand. Think of this as less of an extended tutorial, more of a long-form Twitter.

Also, I’ll be posting regular builds on Patreon for $4 supporters, which will be available a week later for everyone else. I imagine they’ll generally stay in lockstep with the posts, unless I fall behind on the writing part. But when has that ever happened?

Your very own gamedev legend is about to unfold! A world of dreams and adventures with gbz80 assembly awaits! Let’s go!

Prerequisites

First things first. I have a teeny bit of experience with Game Boy hacking, so I know I need:

  • An emulator. I have no way to run arbitrary code on an actual Game Boy Color, after all. I like mGBA, which strives for accuracy and has some debug tools built in.

    There’s already a serious pitfall here: emulators are generally designed to run games that would work correctly on the actual hardware, but they won’t necessarily reject games that wouldn’t work on actual hardware. In other words, something that works in an emulator might still not work on a real GBC. I would of course prefer that this game work on the actual console it’s built for, but I’ll worry about that later.

  • An assembler, which can build Game Boy assembly code into a ROM. I pretty much wrote one of these myself already for the Pokémon shenanigans, but let’s go with something a little more robust here. I’m using RGBDS, which has a couple nice features like macros and a separate linking step. It compiles super easily, too.

    I also hunted down a vim syntax file, uh, somewhere. I can’t remember which one it was now, and it’s kind of glitchy anyway.

  • Some documentation. I don’t know exactly how this surfaced, but the actual official Game Boy programming manual is on archive.org. It glosses over some things and assumes some existing low-level knowledge, but for the most part it’s a very solid reference.

For everything else, there’s Google, and also the curated awesome-gbdev list of resources.

That list includes several skeleton projects for getting started, but I’m not going to use them. I want to be able to account for every byte of whatever I create. I will, however, refer to them if I get stuck early on. (Spoilers: I get stuck early on.)

And that’s it! The rest is up to me.

Making nothing from nothing

Might as well start with a Makefile. The rgbds root documentation leads me to the following incantation:

1
2
3
4
all:
        rgbasm -o main.o main.rgbasm
        rgblink -o gamegirl.gb main.o
        rgbfix -v -p 0 gamegirl.gb

(I, uh, named this project “gamegirl” before I figured out what it was going to be. It’s a sort of witticism, you see.)

This works basically like every C compiler under the sun, as you might expect: every source file compiles to an object file, then a linker bundles all the object files into a ROM. If I only change one source file, I only have to rebuild one object file.

Of course, this Makefile is terrible garbage and will rebuild the entire project unconditionally every time, but at the moment that takes a fraction of a second so I don’t care.

The extra rgbfix step is new, though — it adds the Nintendo logo (the one you see when you start up a Game Boy) to the header at the beginning of the ROM. Without this, the console will assume the cartridge is dirty or missing or otherwise unreadable, and will refuse to do anything at all. (I could also bake the logo into the source itself, but given that it’s just a fixed block of bytes and rgbfix is bundled with the assembler, I see no reason to bother with that.)

All I need now is a source file, main.rgbasm, which I populate with:

1

Nothing! I don’t know what I expect from this, but I’m curious to see what comes out. And what comes out is a working ROM!

A completely blank screen

Maybe “working” is a strong choice of word, given that it doesn’t actually do anything.

Doing something

It would be fantastic to put something on the screen. This turned out to be harder than expected.

First attempt. I know that the Game Boy starts running code at $0150, immediately after the end of the header. So I’ll put some code there.

A brief Game Boy graphics primer: there are two layers, the background and objects. (There’s also a third layer, the window, which I don’t entirely understand yet.) The background is a grid of 8×8 tiles, two bits per pixel, for a total of four shades of gray. Objects can move around freely, but they lose color 0 to transparency, so they can only use three colors.

There are lots more interesting details and restrictions, which I will think about more later.

Drawing objects is complicated, and all I want to do right now is get something. I’m pretty sure the background defaults to showing all tile 0, so I’ll try replacing tile 0 with a gradient and see what happens.

Tiles are 8×8 and two bits per pixel, which means each row takes two bytes, and the whole tile is 16 bytes. Tiles are defined in one big contiguous block starting at $8000 — or, maybe $8800, sometimes — so all I need to do is:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
SECTION "main", ROM0[$0150]
    ld hl, $8000
    ld a, %00011011
    REPT 16
    ld [hl+], a
    ENDR

_halt:
    ; Do nothing, forever
    halt
    nop
    jr _halt

If you are not familiar with assembly, this series is going to be a wild ride. But here’s a very very brief primer.

Assembly language — really, an assembly language — is little more than a set of human-readable names for the primitive operations a CPU knows how to do. And those operations, by and large, consist of moving bytes around. The names tend to be very short, because you end up typing them a lot.

Most of the work is done in registers, which are a handful of spaces for storing bytes right on the CPU. At this level, RAM is relatively slow — it’s further away, outside the chip — so you want to do as much work as possible in registers. Indeed, most operations can only be done on registers, so there’s a lot of fetching stuff from RAM and operating on it and then putting it back in RAM.

The Game Boy CPU, a modified Z80, has eight byte-sized registers. They’re often referred to in pairs, because they can be paired up to make a 16-bit values (giving you access to a full 64KB address space). And they are: af, bc, de, hl.

The af pair is special. The f register is used for flags, such as whether the last instruction caused an overflow, so it’s not generally touched directly. The a register is called the accumulator and is most commonly used for math operations — in fact, a lot of math operations can only be done on a. The hl register is most often used for addresses, and there are a couple instructions specific to hl that are convenient for memory access. (The h and l even refer to the high and low byte of an address.) The other two pairs aren’t especially noteworthy.

Also! Not every address is actually RAM; the address space ($0000 through $ffff) is carved into several distinct areas, which we will see as I go along. $8000 is the beginning of display RAM, which the screen reads from asynchronously. Also, a lot of addresses above $ff00 (also called “registers”) are special and control hardware in some way, or even perform some action when written to.

With that in mind, here’s the above code with explanatory comments:

TODO need to change this to write a single byte

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
; This is a directive for the assembler to put the following
; code at $0150 in the final ROM.
SECTION "main", ROM0[$0150]
    ; Put the hex value $8000 into registers hl.  Really, that
    ; means put $80 into h and $00 into l.
    ld hl, $8000

    ; Put this binary value into registers a.
    ; It's just 0 1 2 3, a color gradient.
    ld a, %00011011

    ; This is actually a macro this particular assembler
    ; understands, which will repeat the following code 16
    ; times, exactly as if I'd copy-pasted it.
    REPT 16

    ; The brackets (sometimes written as parens) mean to use hl
    ; as a position in RAM, rather than operating on hl itself.
    ; So this copies a into the position in RAM given by
    ; hl (initially $8000), and the + adds 1 to hl afterwards.
    ; This is one reason hl is nice for storing addresses: the +
    ; variant is handy for writing a sequence of bytes to RAM,
    ; and it only exists for hl.
    ld [hl+], a

    ; End the REPT block
    ENDR

; This is a label, used to refer to some position in the code.
; It only exists in the source file.
_halt:
    ; Stop all CPU activity until there's an interrupt.  I
    ; haven't turned any interrupts on, so this stops forever.
    halt

    ; The Game Boy hardware has a bug where, under rare and
    ; unspecified conditions, the instruction after a halt will
    ; be skipped.  So every halt should be followed by a nop,
    ; "no operation", which does nothing.
    nop

    ; This jumps back up to the label.  It's short for "jump
    ; relative", and will end up as an instruction saying
    ; something like "jump backwards five bytes", or however far
    ; back _halt is.  (Different instructions can be different
    ; lengths.)
    jr _halt

Okay! Glad you’re all caught up. The rgbds documentation includes a list of all the available operations (as well as assembler syntax), and once you get used to the short names, I also like this very compact chart of all the instructions and how they compile to machine code. (Note that that chart spells [hl+] as (HLI), for “increment” — the human-readable names are somewhat arbitrary and can sometimes vary between assemblers.)

Now, let’s see what this does!


A completely blank screen, still

Wow! It’s… still nothing. Hang on.

If I open the debugger and hit Break, I find out that the CPU is at address $0120 — before my code — and is on an instruction DD. What’s DD? Well, according to this convenient chart, it’s… nothing. That’s not an instruction.

Hmm.

Problem solving

Maybe it’s time to look at one of those skeleton projects after all. I crack open the smallest one, gb-template, and it seems to be doing the same thing: its code istarts at $0150.

It takes me a bit to realize my mistake here. Practically every Game Boy game starts its code at $0150, but that’s not what the actual hardware specifies. The real start point is $0100, which is immediately before the header! There are only four bytes before the header, just enough for… a jump instruction.

Okay! No problem.

1
2
3
SECTION "entry point", ROM0[$0100]
    nop
    jp $0150

Why the nop? I have no idea, but all of these boilerplate projects do it.

Black screen with repeating columns of white

Uhh.

Well, that’s weird. Not only is the result black and white when I definitely used all four shades, but the whites aren’t even next to each other. (I also had a strange effect where the screen reverted to all white after a few seconds, but can’t reproduce it now; it was fixed by the same steps, though, so it may have been a quirk of a particular mGBA build.)

I’ll save you my head-scratching. I made two mistakes here. Arguably, three!

First: believe it or not, I have to specify the palette. Even in original uncolored Game Boy mode! I can see how that’s nice for doing simple fade effects or flashing colors, but I didn’t suspect it would be necessary. The monochrome palette lives at $ff47 (one of those special high addresses), so I do this before anything else:

1
2
    ld a, %11100100         ; 3 2 1 0
    ld [$ff47], a

I should really give names to some of these special addresses, but for now I’m more interested in something that works than something that’s nice to read.

Second: I specified the colors wrong. I assumed that eight pixels would fit into two bytes as AaBbCcDd EeFfGgHh, perhaps with some rearrangement, but a closer look at Nintendo’s manual reveals that they need to be ABCDEFGH abcdefgh, with the two bits for each pixel split across each byte! Wild.

Handily, rgbds has syntax for writing out pixel values directly: a backtick followed by eight of 0, 1, 2, and 3. I just have to change my code a bit to write two bytes, eight times each. By putting a 16-bit value in a register pair like bc, I can read its high and low bytes out individually via the b and c registers.

1
2
3
4
5
6
7
8
    ld hl, $8000
    ld bc, `00112233
    REPT 8
    ld a, b
    ld [hl+], a
    ld a, c
    ld [hl+], a
    ENDR

Third: strictly speaking, I don’t think I should be writing to $8000 while the screen is on, because the screen may be trying to read from it at the same time. It does happen to work in this emulator, but I have no idea whether it would work on actual hardware. I’m not going to worry too much about this test code; most likely, tile loading will happen all in one place in the real game, and I can figure out any issues then.

This is one of those places where the manual is oddly vague. It dedicates two whole pages to diagrams of how sprites are drawn when they overlap, yet when I can write to display RAM is left implicit.

Well, whatever. It works on my machine.

Stripes of varying shades of gray

Success! I made a thing for the Game Boy.

Ah, but what I wanted was a thing for the Game Boy Color. That shouldn’t be too much harder.

Now in Technicolor

First I update my Makefile to pass the -C flag to rgbfix. That tells it to set a flag in the ROM header to indicate that this game is only intended for the Game Boy Color, and won’t work on the original Game Boy. (In order to pass Nintendo certification, I’ll need an error screen when the game is run on a non-Color Game Boy, but that can come later. Also, I don’t actually know how to do that.)

Oh, and I’ll change the file extension from .gb to .gbc. And while I’m in here, I might as well repeat myself slightly less in this bad, bad Makefile.

1
2
3
4
5
6
7
8
TARGET := gamegirl.gbc

all: $(TARGET)

$(TARGET):
        rgbasm -o main.o main.rgbasm
        rgblink -o $(TARGET) main.o
        rgbfix -C -v -p 0 $(TARGET)

I think := is the one I want, right? Christ, who can remember how this syntax works.

Next I need to define a palette. Again, everything defaults to palette zero, so I’ll update that and not have to worry about specifying a palette for every tile.

This part is a bit weird. Unlike tiles, there’s not a block of addresses somewhere that contains all the palettes. Instead, I have to write the palette to a single address one byte at a time, and the CPU will put it… um… somewhere.

(I think this is because the entire address space was already carved up for the original Game Boy, and they just didn’t have room to expose palettes, but they still had a few spare high addresses they could use for new registers.)

Two registers are involved here. The first, $ff68, specifies which palette I’m writing to. It has a bunch of parts, but since I’m writing to the first color of palette zero, I can leave it all zeroes. The one exception is the high bit, which I’ll explain in just a moment.

1
2
    ld a, %10000000
    ld [$ff68], a

The other, $ff69, does the actual writing. Each color in a palette is two bytes, and a palette contains four colors, so I need to write eight bytes to this same address. The high bit in $ff68 is helpful here: it means that every time I write to $ff69, it should increment its internal position by one. This is kind of like the [hl+] I used above: after every write, the address increases, so I can just write all the data in sequence.

But first I need some colors! Game Boy Color colors are RGB555, which means each color is five bits (0–31) and a full color fits in two bytes: 0bbbbbgg gggrrrrr.

(I got this backwards initially and thought the left bits were red and the right bits were blue.)

Thus, I present, palette loading by hand. Like before, I put the 16-bit color in bc and then write out the contents of b and c. (Before, the backtick syntax put the bytes in the right order; colors are little-endian, hence why I write c before b.)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
    ld bc, %0111110000000000  ; blue
    ld a, c
    ld [$ff69], a
    ld a, b
    ld [$ff69], a
    ld bc, %0000001111100000  ; green
    ld a, c
    ld [$ff69], a
    ld a, b
    ld [$ff69], a
    ld bc, %0000000000011111  ; red
    ld a, c
    ld [$ff69], a
    ld a, b
    ld [$ff69], a
    ld bc, %0111111111111111  ; white
    ld a, c
    ld [$ff69], a
    ld a, b
    ld [$ff69], a

Rebuild, and:

Same as before, but now the stripes are colored

What a glorious eyesore!

To be continued

That brings us up to commit 212344 and works as a good stopping point.

Next time: sprites! Maybe even some real art?

Weekly roundup: Fortnite

Post Syndicated from Eevee original https://eev.ee/dev/2018/04/02/weekly-roundup-fortnite/

I skipped a week again because, surprise, I’ve been mostly working on the same game…

  • art: Actually been doing a bit of it! I painted a thing on a whim, and some misc sketches, a few of which I even felt like posting.

  • alice: Finally kind of hit my stride here and wrote, um, a pretty good chunk of stuff. Also played with extending the syntax a bit, and came up with a choice menu that hangs around while the dialogue continues. Kinda cool, though I’m not totally sure what we’ll use it for yet.

    Even with my figuring out how to accelerate, it’s looking like we’ll have to rush if we want to hit our promised date of June 9. So we might delay that a little… maybe even Kickstart some stretch goals? I dunno, I’m leaving that all up to glip and just writing stuff.

  • writing: While I’m at it, I actually picked up and worked on a Twine from ages ago. Cool.

  • idchoppers: Holy moly, it actually works. The basics actually work, at least. I can’t believe how much effort this hecking took.

    I also tried to start putting together an actual map API, with mixed results. And tried to figure out the maximum distance you can jump in Doom, which is surprisingly tricky? Doom physics are super goofy.

  • blog: I actually published a post, which is even tangentially about that idchoppers stuff! Wow! Maybe I’ll do it again, even!

Huh, that almost makes it sound like I’ve been busy.

A geometric Rust adventure

Post Syndicated from Eevee original https://eev.ee/blog/2018/03/30/a-geometric-rust-adventure/

Hi. Yes. Sorry. I’ve been trying to write this post for ages, but I’ve also been working on a huge writing project, and apparently I have a very limited amount of writing mana at my disposal. I think this is supposed to be a Patreon reward from January. My bad. I hope it’s super great to make up for the wait!

I recently ported some math code from C++ to Rust in an attempt to do a cool thing with Doom. Here is my story.

The problem

I presented it recently as a conundrum (spoilers: I solved it!), but most of those details are unimportant.

The short version is: I have some shapes. I want to find their intersection.

Really, I want more than that: I want to drop them all on a canvas, intersect everything with everything, and pluck out all the resulting polygons. The input is a set of cookie cutters, and I want to press them all down on the same sheet of dough and figure out what all the resulting contiguous pieces are. And I want to know which cookie cutter(s) each piece came from.

But intersection is a good start.

Example of the goal.  Given two squares that overlap at their corners, I want to find the small overlap piece, plus the two L-shaped pieces left over from each square

I’m carefully referring to the input as shapes rather than polygons, because each one could be a completely arbitrary collection of lines. Obviously there’s not much you can do with shapes that aren’t even closed, but at the very least, I need to handle concavity and multiple disconnected polygons that together are considered a single input.

This is a non-trivial problem with a lot of edge cases, and offhand I don’t know how to solve it robustly. I’m not too eager to go figure it out from scratch, so I went hunting for something I could build from.

(Infuriatingly enough, I can just dump all the shapes out in an SVG file and any SVG viewer can immediately solve the problem, but that doesn’t quite help me. Though I have had a few people suggest I just rasterize the whole damn problem, and after all this, I’m starting to think they may have a point.)

Alas, I couldn’t find a Rust library for doing this. I had a hard time finding any library for doing this that wasn’t a massive fully-featured geometry engine. (I could’ve used that, but I wanted to avoid non-Rust dependencies if possible, since distributing software is already enough of a nightmare.)

A Twitter follower directed me towards a paper that described how to do very nearly what I wanted and nothing else: “A simple algorithm for Boolean operations on polygons” by F. Martínez (2013). Being an academic paper, it’s trapped in paywall hell; sorry about that. (And as I understand it, none of the money you’d pay to get the paper would even go to the authors? Is that right? What a horrible and predatory system for discovering and disseminating knowledge.)

The paper isn’t especially long, but it does describe an awful lot of subtle details and is mostly written in terms of its own reference implementation. Rather than write my own implementation based solely on the paper, I decided to try porting the reference implementation from C++ to Rust.

And so I fell down the rabbit hole.

The basic algorithm

Thankfully, the author has published the sample code on his own website, if you want to follow along. (It’s the bottom link; the same author has, confusingly, published two papers on the same topic with similar titles, four years apart.)

If not, let me describe the algorithm and how the code is generally laid out. The algorithm itself is based on a sweep line, where a vertical line passes across the plane and ✨ does stuff ✨ as it encounters various objects. This implementation has no physical line; instead, it keeps track of which segments from the original polygon would be intersecting the sweep line, which is all we really care about.

A vertical line is passing rightwards over a couple intersecting shapes.  The line current intersects two of the shapes' sides, and these two sides are the "sweep list"

The code is all bundled inside a class with only a single public method, run, because… that’s… more object-oriented, I guess. There are several helper methods, and state is stored in some attributes. A rough outline of run is:

  1. Run through all the line segments in both input polygons. For each one, generate two SweepEvents (one for each endpoint) and add them to a std::deque for storage.

    Add pointers to the two SweepEvents to a std::priority_queue, the event queue. This queue uses a custom comparator to order the events from left to right, so the top element is always the leftmost endpoint.

  2. Loop over the event queue (where an “event” means the sweep line passed over the left or right end of a segment). Encountering a left endpoint means the sweep line is newly touching that segment, so add it to a std::set called the sweep list. An important point is that std::set is ordered, and the sweep list uses a comparator that keeps segments in order vertically.

    Encountering a right endpoint means the sweep line is leaving a segment, so that segment is removed from the sweep list.

  3. When a segment is added to the sweep list, it may have up to two neighbors: the segment above it and the segment below it. Call possibleIntersection to check whether it intersects either of those neighbors. (This is nearly sufficient to find all intersections, which is neat.)

  4. If possibleIntersection detects an intersection, it will split each segment into two pieces then and there. The old segment is shortened in-place to become the left part, and a new segment is created for the right part. The new endpoints at the point of intersection are added to the event queue.

  5. Some bookkeeping is done along the way to track which original polygons each segment is inside, and eventually the segments are reconstructed into new polygons.

Hopefully that’s enough to follow along. It took me an inordinately long time to tease this out. The comments aren’t especially helpful.

1
    std::deque<SweepEvent> eventHolder;    // It holds the events generated during the computation of the boolean operation

Syntax and basic semantics

The first step was to get something that rustc could at least parse, which meant translating C++ syntax to Rust syntax.

This was surprisingly straightforward! C++ classes become Rust structs. (There was no inheritance here, thankfully.) All the method declarations go away. Method implementations only need to be indented and wrapped in impl.

I did encounter some unnecessarily obtuse uses of the ternary operator:

1
(prevprev != sl.begin()) ? --prevprev : prevprev = sl.end();

Rust doesn’t have a ternary — you can use a regular if block as an expression — so I expanded these out.

C++ switch blocks become Rust match blocks, but otherwise function basically the same. Rust’s enums are scoped (hallelujah), so I had to explicitly spell out where enum values came from.

The only really annoying part was changing function signatures; C++ types don’t look much at all like Rust types, save for the use of angle brackets. Rust also doesn’t pass by implicit reference, so I needed to sprinkle a few &s around.

I would’ve had a much harder time here if this code had relied on any remotely esoteric C++ functionality, but thankfully it stuck to pretty vanilla features.

Language conventions

This is a geometry problem, so the sample code unsurprisingly has its own home-grown point type. Rather than port that type to Rust, I opted to use the popular euclid crate. Not only is it code I didn’t have to write, but it already does several things that the C++ code was doing by hand inline, like dot products and cross products. And all I had to do was add one line to Cargo.toml to use it! I have no idea how anyone writes C or C++ without a package manager.

The C++ code used getters, i.e. point.x (). I’m not a huge fan of getters, though I do still appreciate the need for them in lowish-level systems languages where you want to future-proof your API and the language wants to keep a clear distinction between attribute access and method calls. But this is a point, which is nothing more than two of the same numeric type glued together; what possible future logic might you add to an accessor? The euclid authors appear to side with me and leave the coordinates as public fields, so I took great joy in removing all the superfluous parentheses.

Polygons are represented with a Polygon class, which has some number of Contours. A contour is a single contiguous loop. Something you’d usually think of as a polygon would only have one, but a shape with a hole would have two: one for the outside, one for the inside. The weird part of this arrangement was that Polygon implemented nearly the entire STL container interface, then waffled between using it and not using it throughout the rest of the code. Rust lets anything in the same module access non-public fields, so I just skipped all that and used polygon.contours directly. Hell, I think I made contours public.

Finally, the SweepEvent type has a pol field that’s declared as an enum PolygonType (either SUBJECT or CLIPPING, to indicate which of the two inputs it is), but then some other code uses the same field as a numeric index into a polygon’s contours. Boy I sure do love static typing where everything’s a goddamn integer. I wanted to extend the algorithm to work on arbitrarily many input polygons anyway, so I scrapped the enum and this became a usize.


Then I got to all the uses of STL. I have only a passing familiarity with the C++ standard library, and this code actually made modest use of it, which caused some fun days-long misunderstandings.

As mentioned, the SweepEvents are stored in a std::deque, which is never read from. It took me a little thinking to realize that the deque was being used as an arena: it’s the canonical home for the structs so pointers to them can be tossed around freely. (It can’t be a std::vector, because that could reallocate and invalidate all the pointers; std::deque is probably a doubly-linked list, and guarantees no reallocation.)

Rust’s standard library does have a doubly-linked list type, but I knew I’d run into ownership hell here later anyway, so I think I replaced it with a Rust Vec to start with. It won’t compile either way, so whatever. We’ll get back to this in a moment.

The list of segments currently intersecting the sweep line is stored in a std::set. That type is explicitly ordered, which I’m very glad I knew already. Rust has two set types, HashSet and BTreeSet; unsurprisingly, the former is unordered and the latter is ordered. Dropping in BTreeSet and fixing some method names got me 90% of the way there.

Which brought me to the other 90%. See, the C++ code also relies on finding nodes adjacent to the node that was just inserted, via STL iterators.

1
2
3
next = prev = se->posSL = it = sl.insert(se).first;
(prev != sl.begin()) ? --prev : prev = sl.end();
++next;

I freely admit I’m bad at C++, but this seems like something that could’ve used… I don’t know, 1 comment. Or variable names more than two letters long. What it actually does is:

  1. Add the current sweep event (se) to the sweep list (sl), which returns a pair whose first element is an iterator pointing at the just-inserted event.

  2. Copies that iterator to several other variables, including prev and next.

  3. If the event was inserted at the beginning of the sweep list, set prev to the sweep list’s end iterator, which in C++ is a legal-but-invalid iterator meaning “the space after the end” or something. This is checked for in later code, to see if there is a previous event to look at. Otherwise, decrement prev, so it’s now pointing at the event immediately before the inserted one.

  4. Increment next normally. If the inserted event is last, then this will bump next to the end iterator anyway.

In other words, I need to get the previous and next elements from a BTreeSet. Rust does have bidirectional iterators, which BTreeSet supports… but BTreeSet::insert only returns a bool telling me whether or not anything was inserted, not the position. I came up with this:

1
2
3
let mut maybe_below = active_segments.range(..segment).last().map(|v| *v);
let mut maybe_above = active_segments.range(segment..).next().map(|v| *v);
active_segments.insert(segment);

The range method returns an iterator over a subset of the tree. The .. syntax makes a range (where the right endpoint is exclusive), so ..segment finds the part of the tree before the new segment, and segment.. finds the part of the tree after it. (The latter would start with the segment itself, except I haven’t inserted it yet, so it’s not actually there.)

Then the standard next() and last() methods on bidirectional iterators find me the element I actually want. But the iterator might be empty, so they both return an Option. Also, iterators tend to return references to their contents, but in this case the contents are already references, and I don’t want a double reference, so the map call dereferences one layer — but only if the Option contains a value. Phew!

This is slightly less efficient than the C++ code, since it has to look up where segment goes three times rather than just one. I might be able to get it down to two with some more clever finagling of the iterator, but microsopic performance considerations were a low priority here.

Finally, the event queue uses a std::priority_queue to keep events in a desired order and efficiently pop the next one off the top.

Except priority queues act like heaps, where the greatest (i.e., last) item is made accessible.

Sorting out sorting

C++ comparison functions return true to indicate that the first argument is less than the second argument. Sweep events occur from left to right. You generally implement sorts so that the first thing comes, erm, first.

But sweep events go in a priority queue, and priority queues surface the last item, not the first. This C++ code handled this minor wrinkle by implementing its comparison backwards.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
struct SweepEventComp : public std::binary_function<SweepEvent, SweepEvent, bool> { // for sorting sweep events
// Compare two sweep events
// Return true means that e1 is placed at the event queue after e2, i.e,, e1 is processed by the algorithm after e2
bool operator() (const SweepEvent* e1, const SweepEvent* e2)
{
    if (e1->point.x () > e2->point.x ()) // Different x-coordinate
        return true;
    if (e2->point.x () > e1->point.x ()) // Different x-coordinate
        return false;
    if (e1->point.y () != e2->point.y ()) // Different points, but same x-coordinate. The event with lower y-coordinate is processed first
        return e1->point.y () > e2->point.y ();
    if (e1->left != e2->left) // Same point, but one is a left endpoint and the other a right endpoint. The right endpoint is processed first
        return e1->left;
    // Same point, both events are left endpoints or both are right endpoints.
    if (signedArea (e1->point, e1->otherEvent->point, e2->otherEvent->point) != 0) // not collinear
        return e1->above (e2->otherEvent->point); // the event associate to the bottom segment is processed first
    return e1->pol > e2->pol;
}
};

Maybe it’s just me, but I had a hell of a time just figuring out what problem this was even trying to solve. I still have to reread it several times whenever I look at it, to make sure I’m getting the right things backwards.

Making this even more ridiculous is that there’s a second implementation of this same sort, with the same name, in another file — and that one’s implemented forwards. And doesn’t use a tiebreaker. I don’t entirely understand how this even compiles, but it does!

I painstakingly translated this forwards to Rust. Unlike the STL, Rust doesn’t take custom comparators for its containers, so I had to implement ordering on the types themselves (which makes sense, anyway). I wrapped everything in the priority queue in a Reverse, which does what it sounds like.

I’m fairly pleased with Rust’s ordering model. Most of the work is done in Ord, a trait with a cmp() method returning an Ordering (one of Less, Equal, and Greater). No magic numbers, no need to implement all six ordering methods! It’s incredible. Ordering even has some handy methods on it, so the usual case of “order by this, then by this” can be written as:

1
2
return self.point().x.cmp(&other.point().x)
    .then(self.point().y.cmp(&other.point().y));

Well. Just kidding! It’s not quite that easy. You see, the points here are composed of floats, and floats have the fun property that not all of them are comparable. Specifically, NaN is not less than, greater than, or equal to anything else, including itself. So IEEE 754 float ordering cannot be expressed with Ord. Unless you want to just make up an answer for NaN, but Rust doesn’t tend to do that.

Rust’s float types thus implement the weaker PartialOrd, whose method returns an Option<Ordering> instead. That makes the above example slightly uglier:

1
2
return self.point().x.partial_cmp(&other.point().x).unwrap()
    .then(self.point().y.partial_cmp(&other.point().y).unwrap())

Also, since I use unwrap() here, this code will panic and take the whole program down if the points are infinite or NaN. Don’t do that.

This caused some minor inconveniences in other places; for example, the general-purpose cmp::min() doesn’t work on floats, because it requires an Ord-erable type. Thankfully there’s a f64::min(), which handles a NaN by returning the other argument.

(Cool story: for the longest time I had this code using f32s. I’m used to translating int to “32 bits”, and apparently that instinct kicked in for floats as well, even floats spelled double.)

The only other sorting adventure was this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
// Due to overlapping edges the resultEvents array can be not wholly sorted
bool sorted = false;
while (!sorted) {
    sorted = true;
    for (unsigned int i = 0; i < resultEvents.size (); ++i) {
        if (i + 1 < resultEvents.size () && sec (resultEvents[i], resultEvents[i+1])) {
            std::swap (resultEvents[i], resultEvents[i+1]);
            sorted = false;
        }
    }
}

(I originally misread this comment as saying “the array cannot be wholly sorted” and had no idea why that would be the case, or why the author would then immediately attempt to bubble sort it.)

I’m still not sure why this uses an ad-hoc sort instead of std::sort. But I’m used to taking for granted that general-purpose sorting implementations are tuned to work well for almost-sorted data, like Python’s. Maybe C++ is untrustworthy here, for some reason. I replaced it with a call to .sort() and all seemed fine.

Phew! We’re getting there. Finally, my code appears to type-check.

But now I see storm clouds gathering on the horizon.

Ownership hell

I have a problem. I somehow run into this problem every single time I use Rust. The solutions are never especially satisfying, and all the hacks I might use if forced to write C++ turn out to be unsound, which is even more annoying because rustc is just sitting there with this smug “I told you so expression” and—

The problem is ownership, which Rust is fundamentally built on. Any given value must have exactly one owner, and Rust must be able to statically convince itself that:

  1. No reference to a value outlives that value.
  2. If a mutable reference to a value exists, no other references to that value exist at the same time.

This is the core of Rust. It guarantees at compile time that you cannot lose pointers to allocated memory, you cannot double-free, you cannot have dangling pointers.

It also completely thwarts a lot of approaches you might be inclined to take if you come from managed languages (where who cares, the GC will take care of it) or C++ (where you just throw pointers everywhere and hope for the best apparently).

For example, pointer loops are impossible. Rust’s understanding of ownership and lifetimes is hierarchical, and it simply cannot express loops. (Rust’s own doubly-linked list type uses raw pointers and unsafe code under the hood, where “unsafe” is an escape hatch for the usual ownership rules. Since I only recently realized that pointers to the inside of a mutable Vec are a bad idea, I figure I should probably not be writing unsafe code myself.)

This throws a few wrenches in the works.

Problem the first: pointer loops

I immediately ran into trouble with the SweepEvent struct itself. A SweepEvent pulls double duty: it represents one endpoint of a segment, but each left endpoint also handles bookkeeping for the segment itself — which means that most of the fields on a right endpoint are unused. Also, and more importantly, each SweepEvent has a pointer to the corresponding SweepEvent at the other end of the same segment. So a pair of SweepEvents point to each other.

Rust frowns upon this. In retrospect, I think I could’ve kept it working, but I also think I’m wrong about that.

My first step was to wrench SweepEvent apart. I moved all of the segment-stuff (which is virtually all of it) into a single SweepSegment type, and then populated the event queue with a SweepEndpoint tuple struct, similar to:

1
2
3
4
5
6
enum SegmentEnd {
    Left,
    Right,
}

struct SweepEndpoint<'a>(&'a SweepSegment, SegmentEnd);

This makes SweepEndpoint essentially a tuple with a name. The 'a is a lifetime and says, more or less, that a SweepEndpoint cannot outlive the SweepSegment it references. Makes sense.

Problem solved! I no longer have mutually referential pointers. But I do still have pointers (well, references), and they have to point to something.

Problem the second: where’s all the data

Which brings me to the problem I always run into with Rust. I have a bucket of things, and I need to refer to some of them multiple times.

I tried half a dozen different approaches here and don’t clearly remember all of them, but I think my core problem went as follows. I translated the C++ class to a Rust struct with some methods hanging off of it. A simplified version might look like this.

1
2
3
4
struct Algorithm {
    arena: LinkedList<SweepSegment>,
    event_queue: BinaryHeap<SweepEndpoint>,
}

Ah, hang on — SweepEndpoint needs to be annotated with a lifetime, so Rust can enforce that those endpoints don’t live longer than the segments they refer to. No problem?

1
2
3
4
struct Algorithm<'a> {
    arena: LinkedList<SweepSegment>,
    event_queue: BinaryHeap<SweepEndpoint<'a>>,
}

Okay! Now for some methods.

1
2
3
4
5
6
7
8
fn run(&mut self) {
    self.arena.push_back(SweepSegment{ data: 5 });
    self.event_queue.push(SweepEndpoint(self.arena.back().unwrap(), SegmentEnd::Left));
    self.event_queue.push(SweepEndpoint(self.arena.back().unwrap(), SegmentEnd::Right));
    for event in &self.event_queue {
        println!("{:?}", event)
    }
}

Aaand… this doesn’t work. Rust “cannot infer an appropriate lifetime for autoref due to conflicting requirements”. The trouble is that self.arena.back() takes a reference to self.arena, and then I put that reference in the event queue. But I promised that everything in the event queue has lifetime 'a, and I don’t actually know how long self lives here; I only know that it can’t outlive 'a, because that would invalidate the references it holds.

A little random guessing let me to change &mut self to &'a mut self — which is fine because the entire impl block this lives in is already parameterized by 'a — and that makes this compile! Hooray! I think that’s because I’m saying self itself has exactly the same lifetime as the references it holds onto, which is true, since it’s referring to itself.

Let’s get a little more ambitious and try having two segments.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
fn run(&'a mut self) {
    self.arena.push_back(SweepSegment{ data: 5 });
    self.event_queue.push(SweepEndpoint(self.arena.back().unwrap(), SegmentEnd::Left));
    self.event_queue.push(SweepEndpoint(self.arena.back().unwrap(), SegmentEnd::Right));
    self.arena.push_back(SweepSegment{ data: 17 });
    self.event_queue.push(SweepEndpoint(self.arena.back().unwrap(), SegmentEnd::Left));
    self.event_queue.push(SweepEndpoint(self.arena.back().unwrap(), SegmentEnd::Right));
    for event in &self.event_queue {
        println!("{:?}", event)
    }
}

Whoops! Rust complains that I’m trying to mutate self.arena while other stuff is referring to it. And, yes, that’s true — I have references to it in the event queue, and Rust is preventing me from potentially deleting everything from the queue when references to it still exist. I’m not actually deleting anything here, of course (though I could be if this were a Vec!), but Rust’s type system can’t encode that (and I dread the thought of a type system that can).

I struggled with this for a while, and rapidly encountered another complete showstopper:

1
2
3
4
5
6
fn run(&'a mut self) {
    self.mutate_something();
    self.mutate_something();
}

fn mutate_something(&'a mut self) {}

Rust objects that I’m trying to borrow self mutably, twice — once for the first call, once for the second.

But why? A borrow is supposed to end automatically once it’s no longer used, right? Maybe if I throw some braces around it for scope… nope, that doesn’t help either.

It’s true that borrows usually end automatically, but here I have explicitly told Rust that mutate_something() should borrow with the lifetime 'a, which is the same as the lifetime in run(). So the first call explicitly borrows self for at least the rest of the method. Removing the lifetime from mutate_something() does fix this error, but if that method tries to add new segments, I’m back to the original problem.

Oh no. The mutation in the C++ code is several calls deep. Porting it directly seems nearly impossible.

The typical solution here — at least, the first thing people suggest to me on Twitter — is to wrap basically everything everywhere in Rc<RefCell<T>>, which gives you something that’s reference-counted (avoiding questions of ownership) and defers borrow checks until runtime (avoiding questions of mutable borrows). But that seems pretty heavy-handed here — not only does RefCell add .borrow() noise anywhere you actually want to interact with the underlying value, but do I really need to refcount these tiny structs that only hold a handful of floats each?

I set out to find a middle ground.

Solution, kind of

I really, really didn’t want to perform serious surgery on this code just to get it to build. I still didn’t know if it worked at all, and now I had to rearrange it without being able to check if I was breaking it further. (This isn’t Rust’s fault; it’s a natural problem with porting between fairly different paradigms.)

So I kind of hacked it into working with minimal changes, producing a grotesque abomination which I’m ashamed to link to. Here’s how!

First, I got rid of the class. It turns out this makes lifetime juggling much easier right off the bat. I’m pretty sure Rust considers everything in a struct to be destroyed simultaneously (though in practice it guarantees it’ll destroy fields in order), which doesn’t leave much wiggle room. Locals within a function, on the other hand, can each have their own distinct lifetimes, which solves the problem of expressing that the borrows won’t outlive the arena.

Speaking of the arena, I solved the mutability problem there by switching to… an arena! The typed-arena crate (a port of a type used within Rust itself, I think) is an allocator — you give it a value, and it gives you back a reference, and the reference is guaranteed to be valid for as long as the arena exists. The method that does this is sneaky and takes &self rather than &mut self, so Rust doesn’t know you’re mutating the arena and won’t complain. (One drawback is that the arena will never free anything you give to it, but that’s not a big problem here.)


My next problem was with mutation. The main loop repeatedly calls possibleIntersection with pairs of segments, which can split either or both segment. Rust definitely doesn’t like that — I’d have to pass in two &muts, both of which are mutable references into the same arena, and I’d have a bunch of immutable references into that arena in the sweep list and elsewhere. This isn’t going to fly.

This is kind of a shame, and is one place where Rust seems a little overzealous. Something like this seems like it ought to be perfectly valid:

1
2
3
4
let mut v = vec![1u32, 2u32];
let a = &mut v[0];
let b = &mut v[1];
// do stuff with a, b

The trouble is, Rust only knows the type signature, which here is something like index_mut(&'a mut self, index: usize) -> &'a T. Nothing about that says that you’re borrowing distinct elements rather than some core part of the type — and, in fact, the above code is only safe because you’re borrowing distinct elements. In the general case, Rust can’t possibly know that. It seems obvious enough from the different indexes, but nothing about the type system even says that different indexes have to return different values. And what if one were borrowed as &mut v[1] and the other were borrowed with v.iter_mut().next().unwrap()?

Anyway, this is exactly where people start to turn to RefCell — if you’re very sure you know better than Rust, then a RefCell will skirt the borrow checker while still enforcing at runtime that you don’t have more than one mutable borrow at a time.

But half the lines in this algorithm examine the endpoints of a segment! I don’t want to wrap the whole thing in a RefCell, or I’ll have to say this everywhere:

1
if segment1.borrow().point.x < segment2.borrow().point.x { ... }

Gross.

But wait — this code only mutates the points themselves in one place. When a segment is split, the original segment becomes the left half, and a new segment is created to be the right half. There’s no compelling need for this; it saves an allocation for the left half, but it’s not critical to the algorithm.

Thus, I settled on a compromise. My segment type now looks like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
struct SegmentPacket {
    // a bunch of flags and whatnot used in the algorithm
}
struct SweepSegment {
    left_point: MapPoint,
    right_point: MapPoint,
    faces_outwards: bool,
    index: usize,
    order: usize,
    packet: RefCell<SegmentPacket>,
}

I do still need to call .borrow() or .borrow_mut() to get at the stuff in the “packet”, but that’s far less common, so there’s less noise overall. And I don’t need to wrap it in Rc because it’s part of a type that’s allocated in the arena and passed around only via references.


This still leaves me with the problem of how to actually perform the splits.

I’m not especially happy with what I came up with, I don’t know if I can defend it, and I suspect I could do much better. I changed possibleIntersection so that rather than performing splits, it returns the points at which each segment needs splitting, in the form (usize, Option<MapPoint>, Option<MapPoint>). (The usize is used as a flag for calling code and oughta be an enum, but, isn’t yet.)

Now the top-level function is responsible for all arena management, and all is well.

Except, er. possibleIntersection is called multiple times, and I don’t want to copy-paste a dozen lines of split code after each call. I tried putting just that code in its own function, which had the world’s most godawful signature, and that didn’t work because… uh… hm. I can’t remember why, exactly! Should’ve written that down.

I tried a local closure next, but closures capture their environment by reference, so now I had references to a bunch of locals for as long as the closure existed, which meant I couldn’t mutate those locals. Argh. (This seems a little silly to me, since the closure’s references cannot possibly be used for anything if the closure isn’t being called, but maybe I’m missing something. Or maybe this is just a limitation of lifetimes.)

Increasingly desperate, I tried using a macro. But… macros are hygienic, which means that any new name you use inside a macro is different from any name outside that macro. The macro thus could not see any of my locals. Usually that’s good, but here I explicitly wanted the macro to mess with my locals.

I was just about to give up and go live as a hermit in a cabin in the woods, when I discovered something quite incredible. You can define local macros! If you define a macro inside a function, then it can see any locals defined earlier in that function. Perfect!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
macro_rules! _split_segment (
    ($seg:expr, $pt:expr) => (
        {
            let pt = $pt;
            let seg = $seg;
            // ... waaay too much code ...
        }
    );
);

loop {
    // ...
    // This is possibleIntersection, renamed because Rust rightfully complains about camelCase
    let cross = handle_intersections(Some(segment), maybe_above);
    if let Some(pt) = cross.1 {
        segment = _split_segment!(segment, pt);
    }
    if let Some(pt) = cross.2 {
        maybe_above = Some(_split_segment!(maybe_above.unwrap(), pt));
    }
    // ...
}

(This doesn’t actually quite match the original algorithm, which has one case where a segment can be split twice. I realized that I could just do the left-most split, and a later iteration would perform the other split. I sure hope that’s right, anyway.)

It’s a bit ugly, and I ran into a whole lot of implicit behavior from the C++ code that I had to fix — for example, the segment is sometimes mutated just before it’s split, purely as a shortcut for mutating the left part of the split. But it finally compiles! And runs! And kinda worked, a bit!

Aftermath

I still had a lot of work to do.

For one, this code was designed for intersecting two shapes, not mass-intersecting a big pile of shapes. The basic algorithm doesn’t care about how many polygons you start with — all it sees is segments — but the code for constructing the return value needed some heavy modification.

The biggest change by far? The original code traced each segment once, expecting the result to be only a single shape. I had to change that to trace each side of each segment once, since the vast bulk of the output consists of shapes which share a side. This violated a few assumptions, which I had to hack around.

I also ran into a couple very bad edge cases, spent ages debugging them, then found out that the original algorithm had a subtle workaround that I’d commented out because it was awkward to port but didn’t seem to do anything. Whoops!

The worst was a precision error, where a vertical line could be split on a point not quite actually on the line, which wreaked all kinds of havoc. I worked around that with some tasteful rounding, which is highly dubious but makes the output more appealing to my squishy human brain. (I might switch to the original workaround, but I really dislike that even simple cases can spit out points at 1500.0000000000003. The whole thing is parameterized over the coordinate type, so maybe I could throw a rational type in there and cross my fingers?)

All that done, I finally, finally, after a couple months of intermittent progress, got what I wanted!

This is Doom 2’s MAP01. The black area to the left of center is where the player starts. Gray areas indicate where the player can walk from there, with lighter shades indicating more distant areas, where “distance” is measured by the minimum number of line crossings. Red areas can’t be reached at all.

(Note: large playable chunks of the map, including the exit room, are red. That’s because those areas are behind doors, and this code doesn’t understand doors yet.)

(Also note: The big crescent in the lower-right is also black because I was lazy and looked for the player’s starting sector by checking the bbox, and that sector’s bbox happens to match.)

The code that generated this had to go out of its way to delete all the unreachable zones around solid walls. I think I could modify the algorithm to do that on the fly pretty easily, which would probably speed it up a bit too. Downside is that the algorithm would then be pretty specifically tied to this problem, and not usable for any other kind of polygon intersection, which I would think could come up elsewhere? The modifications would be pretty minor, though, so maybe I could confine them to a closure or something.

Some final observations

It runs surprisingly slowly. Like, multiple seconds. Unless I add --release, which speeds it up by a factor of… some number with multiple digits. Wahoo. Debug mode has a high price, especially with a lot of calls in play.

The current state of this code is on GitHub. Please don’t look at it. I’m very sorry.

Honestly, most of my anguish came not from Rust, but from the original code relying on lots of fairly subtle behavior without bothering to explain what it was doing or even hint that anything unusual was going on. God, I hate C++.

I don’t know if the Rust community can learn from this. I don’t know if I even learned from this. Let’s all just quietly forget about it.

Now I just need to figure this one out…

Conundrum

Post Syndicated from Eevee original https://eev.ee/blog/2018/03/20/conundrum/

Here’s a problem I’m having. Or, rather, a problem I’m solving, but so slowly that I wonder if I’m going about it very inefficiently.

I intended to just make a huge image out of this and tweet it, but it takes so much text to explain that I might as well put it on my internet website.

The setup

I want to do pathfinding through a Doom map. The ultimate goal is to be able to automatically determine the path the player needs to take to reach the exit — what switches to hit in what order, what keys to get, etc.

Doom maps are 2D planes cut into arbitrary shapes. Everything outside a shape is the void, which we don’t care about. Here are some shapes.

The shapes are defined implicitly by their edges. All of the edges touching the red area, for example, say that they’re red on one side.

That’s very nice, because it means I don’t have to do any geometry to detect which areas touch each other. I can tell at a glance that the red and blue areas touch, because the line between them says it’s red on one side and blue on the other.

Unfortunately, this doesn’t seem to be all that useful. The player can’t necessarily move from the red area to the blue area, because there’s a skinny bottleneck. If the yellow area were a raised platform, the player couldn’t fit through the gap. Worse, if there’s a switch somewhere that lowers that platform, then the gap is conditionally passable.

I thought this would be uncommon enough that I could get started only looking at neighbors and do actual geometry later, but that “conditionally passable” pattern shows up all the time in the form of locked “bars” that let you peek between or around them. So I might as well just do the dang geometry.


The player is a 32×32 square and always axis-aligned (i.e., the hitbox doesn’t actually rotate). That’s very convenient, because it means I can “dilate the world” — expand all the walls by 16 units in both directions, while shrinking the player to a single point. That expansion eliminates narrow gaps and leaves a map of everywhere the player’s center is allowed to be. Allegedly this is how Quake did collision detection — but in 3D! How hard can it be in 2D?

The plan, then, is to do this:

This creates a bit of an unholy mess. (I could avoid some of the overlap by being clever at points where exactly two lines touch, but I have to deal with a ton of overlap anyway so I’m not sure if that buys anything.)

The gray outlines are dilations of inner walls, where both sides touch a shape. The black outlines are dilations of outer walls, touching the void on one side. This map tells me that the player’s center can never go within 16 units of an outer wall, which checks out — their hitbox would get in the way! So I can delete all that stuff completely.

Consider that bottom-left outline, where red and yellow touch horizontally. If the player is in the red area, they can only enter that outlined part if they’re also allowed to be in the yellow area. Once they’re inside it, though, they can move around freely. I’ll color that piece orange, and similarly blend colors for the other outlines. (A small sliver at the top requires access to all three areas, so I colored it gray, because I can’t be bothered to figure out how to do a stripe pattern in Inkscape.)

This is the final map, and it’s easy to traverse because it works like a graph! Each contiguous region is a node, and each border is an edge. Some of the edges are one-way (falling off a ledge) or conditional (walking through a door), but the player can move freely within a region, so I don’t need to care about world geometry any more.

The problem

I’m having a hell of a time doing this mass-intersection of a big pile of shapes.

I’m writing this in Rust, and I would very very very strongly prefer not to wrap a C library (or, god forbid, a C++ library), because that will considerably complicate actually releasing this dang software. Unfortunately, that also limits my options rather a lot.

I was referred to a paper (A simple algorithm for Boolean operations on polygons, Martínez et al, 2013) that describes doing a Boolean operation (union, intersection, difference, xor) on two shapes, and works even with self-intersections and holes and whatnot.

I spent an inordinate amount of time porting its reference implementation from very bad C++ to moderately bad Rust, and I extended it to work with an arbitrary number of polygons and to spit out all resulting shapes. It has been a very bumpy ride, and I keep hitting walls — the latest is that it panics when intersecting everything results in two distinct but exactly coincident edges, which obviously happens a lot with this approach.

So the question is: is there some better way to do this that I’m overlooking, or should I just keep fiddling with this algorithm and hope I come out the other side with something that works?


Bear in mind, the input shapes are not necessarily convex, and quite frequently aren’t. Also, they can have holes, and quite frequently do. That rules out most common algorithms. It’s probably possible to triangulate everything, but I’m a little wary of cutting the map into even more microscopic shards; feel free to convince me otherwise.

Also, the map format technically allows absolutely any arbitrary combination of lines, so all of these are possible:

It would be nice to handle these gracefully somehow, or at least not crash on them. But they’re usually total nonsense as far as the game is concerned. But also that middle one does show up in the original stock maps a couple times.

Another common trick is that lines might be part of the same shape on both sides:

The left example suggests that such a line is redundant and can simply be ignored without changing anything. The right example shows why this is a problem.

A common trick in vanilla Doom is the so-called self-referencing sector. Here, the edges of the inner yellow square all claim to be yellow — on both sides. The outer edges all claim to be blue only on the inside, as normal. The yellow square therefore doesn’t neighbor the blue square at all, because no edges that are yellow on one side and blue on the other. The effect in-game is that the yellow area is invisible, but still solid, so it can be used as an invisible bridge or invisible pit for various effects.

This does raise the question of exactly how Doom itself handles all these edge cases. Vanilla maps are preprocessed by a node builder and split into subsectors, which are all convex polygons. So for any given weird trick or broken geometry, the answer to “how does this behave” is: however the node builder deals with it.

Subsectors are built right into vanilla maps, so I could use those. The drawback is that they’re optional for maps targeting ZDoom (and maybe other ports as well?), because ZDoom has its own internal node builder. Also, relying on built nodes in general would make this code less useful for map editing, or generating, or whatever.

ZDoom’s node builder is open source, so I could bake it in? Or port it to Rust? (It’s only, ah, ten times bigger than the shape algorithm I ported.) It’d be interesting to have a fairly-correct reflection of how the game sees broken geometry, which is something no map editor really tries to do. Is it fast enough? Running it on the largest map I know to exist (MAP14 of Sunder) takes 1.4 seconds, which seems like a long time, but also that’s from scratch, and maybe it could be adapted to work incrementally…? Christ.

I’m not sure I have the time to dedicate to flesh this out beyond a proof of concept anyway, so maybe this is all moot. But all the more reason to avoid spending a lot of time on dead ends.

Weekly roundup: Visual novelty

Post Syndicated from Eevee original https://eev.ee/dev/2018/03/20/weekly-roundup-visual-novelty/

Doin’ game stuff. Probably going to be quiet for a few weeks still.

  • alice: Actually wrote a decent amount of stuff, though fairly haphazardly. Finally kind of getting into the groove here. Still contemplating more interesting ways to offer choices, without turning the game into a combinatorial explosion.

  • art: Did some doodles. Not as frequently as I’d like, and mostly not published, but I did some, and that’s nice.

  • fox flux: Revisited the parallax forest background briefly. Made some progress, but talked to glip and maybe it’s not the right approach in the first place? Not thinking about it too seriously right now, regardless.

  • idchoppers: Miraculously, I got multi-polygon splitting finally working… and then hit a panic when there are coincident segments, which offhand I’m not sure how to fix. Sigh.

Way behind on blogging, I know, sorry.

Weekly roundup: Forwards

Post Syndicated from Eevee original https://eev.ee/dev/2018/03/14/weekly-roundup-forwards/

  • art: Did some doodles. Not as frequently as I’d like, and mostly not published, but I did some, and that’s nice.

  • alice: Continuin’ on, though mostly planning and tech stuff this week, not so much writing.

  • irl: I did my taxes oh boy!

  • blog: I made decent progress on last month’s posts, but, am still not done yet. Sorry. I only have so much energy I can pour into writing at a time, apparently, and working on a visual novel is eating up tons of it.

  • anise: We picked up progress on this game again, came up with a bunch more things to populate the world, and both did some sketches of them! Also I did some basic tile collision merging, which I’d been meaning to do for a while, and which had promising results.

  • idchoppers: I got arbitrary poly splitting mostly working, finally…! I can’t believe how much effort this is taking, but it doesn’t help that I’m only dedicating a couple hours at a time to it completely sporadically. Maybe I’ll have something to show for it soon.

The visual novel is eating most of my time lately, and I’m struggling to get back that writing momentum, and in the meantime it feels like it’s consuming all my time and not letting me do anything else! I’m getting there, though.

Weekly roundup: Re-emerging

Post Syndicated from Eevee original https://eev.ee/dev/2018/03/03/weekly-roundup-re-emerging/

Hi! It’s been three weeks again. But this time it’s because I was up to my eyeballs in making a video game, and I generally don’t have much to say during those spans beyond “I’m making a video game”.

  • alice: We made a video game! Or, at least, a demo. Note: extremely NSFW (although that link is fine; it’s just a release post).

    I hadn’t used Ren’Py a month ago, so there was a lot of scurrying around trying to figure out how to make it do what I want, and then there was a lot of fiction-writing which I have a tough time getting into, but I’m pretty happy with how it came out. Now we just need to make the other 80% of it.

  • idchoppers: Oh, yeah, I got the geometry thing I was doing basically working. Next I gotta adjust the algorithm to work with an arbitrary number of input shapes, which is slightly more complicated.

  • blog: Wrote about some tech wishes for 2018. Wrote a decent chunk of a post about my experience with idchoppers and Rust and porting weird C++ code, but it had to wait until I’d actually gotten the thing working, and then I just didn’t finish it yet haha.

Yep, that’s it, really busy, bye

Alice’s Day Off demo

Post Syndicated from Eevee original https://eev.ee/release/2018/03/02/alices-day-off-demo/

🔗 Alice’s Day Off demo on itch

🚨🔞 HEADS UP: This game is super duper NSFW. It contains explicit cartoon porn. You have been warned! 🔞🚨

This is the game glip and I (and a co-writer) made for my horny game jam, Strawberry Jam 2. It’s a goofy visual novel about, well… sex, mostly. A few folks with no interest in the subject matter have played it and still enjoyed it, which seems like a great sign.

(Oh, right, and the jam is over, and has 63 entries! Like last year, they run the gamut from “highly abstract and thoughtful” to “let’s put porn in a game”.)

Some lingering thoughts about the process itself:


Visual novels combine narrative prose with the interaction of games, but the two forces are somewhat at odds: the more interaction you add, the more prose you have to write, with the worst case being a combinatoric explosion (which won’t even be appreciated by players who run through only once). And there’s a subtle tension between the design of those decisions and replay value, which… I maybe ought to go on about some other time.

Anyway, this is all really a distilled form of the problem of offering narrative choice in games in general, which I find fascinating, so I really wanted to play around with it. I have a few ideas for experimenting with what player choice even looks like in a visual novel, and we have thoughts about narrative variety at all levels so there’s something to appreciate no matter how much or little you replay the game.

Alas! We had to drastically cut down what we wanted to do due to time constraints, hence calling this a “demo”; it’s a sample of ten (mostly linear) routes. It’s good stuff, I’m happy with how it came out, and there’s a pretty decent chunk of it — I think a straight read in one sitting takes about an hour — but I naturally compare it to everything I know isn’t there.


This was my first time using Ren’Py, and it defied my assumptions so utterly that I have to go write a separate post about it now. I think it came out pretty well, considering I’d never touched the engine before three weeks ago.

The touch I like the most is the custom title screen, seen above. I think it’s fairly important to hide obvious traces of the engine you’re using, when feasible; otherwise the end result is covered in someone else’s (generic) fingerprints, not yours. So we added a splash, added a title screen, and completely changed the in-game interface. (The in-game menu is basically the same, but it’s general-purpose enough that I’m not sure it’s really worth changing. Maybe?)


Part of the point of this exercise was to force me to actually sit down and write a story, an activity I often attempt to do and then awkwardly shy away from. It feels like pushing against a river of molasses: it takes me so long just to get started at all, and if I stumble even slightly, I lose my momentum completely and have to start all over. It’s my ADD final boss.

Suffice to say, I spent a good chunk of the month mostly not-writing, which was frustrating and didn’t get us very far. It wasn’t until the final week that I felt like I really hit my stride and started churning out big chunks of prose at a time. I don’t have any inspirational tale about how this happened; I just kept trying to do it and failing to do it until I finally did it. Hopefully it’ll be easier to get into from now on!

I did half the writing, and it’s endlessly hilarious to me that my co-writer and I both looked at each other’s prose and came away thinking “damn, I need to do it more like that!” Probably a good sign.

That’s all I’ve got; back to work!

Tech wishes for 2018

Post Syndicated from Eevee original https://eev.ee/blog/2018/02/18/tech-wishes-for-2018/

Anonymous asks, via money:

What would you like to see happen in tech in 2018?

(answer can be technical, social, political, combination, whatever)

Hmm.

Less of this

I’m not really qualified to speak in depth about either of these things, but let me put my foot in my mouth anyway:

The Blockchain™

Bitcoin was a neat idea. No, really! Decentralization is cool. Overhauling our terrible financial infrastructure is cool. Hash functions are cool.

Unfortunately, it seems to have devolved into mostly a get-rich-quick scheme for nerds, and by nearly any measure it’s turning into a spectacular catastrophe. Its “success” is measured in how much a bitcoin is worth in US dollars, which is pretty close to an admission from its own investors that its only value is in converting back to “real” money — all while that same “success” is making it less useful as a distinct currency.

Blah, blah, everyone already knows this.

What concerns me slightly more is the gold rush hype cycle, which is putting cryptocurrency and “blockchain” in the news and lending it all legitimacy. People have raked in millions of dollars on ICOs of novel coins I’ve never heard mentioned again. (Note: again, that value is measured in dollars.) Most likely, none of the investors will see any return whatsoever on that money. They can’t, really, unless a coin actually takes off as a currency, and that seems at odds with speculative investing since everyone either wants to hoard or ditch their coins. When the coins have no value themselves, the money can only come from other investors, and eventually the hype winds down and you run out of other investors.

I fear this will hurt a lot of people before it’s over, so I’d like for it to be over as soon as possible.


That said, the hype itself has gotten way out of hand too. First it was the obsession with “blockchain” like it’s a revolutionary technology, but hey, Git is a fucking blockchain. The novel part is the way it handles distributed consensus (which in Git is basically left for you to figure out), and that’s uniquely important to currency because you want to be pretty sure that money doesn’t get duplicated or lost when moved around.

But now we have startups trying to use blockchains for website backends and file storage and who knows what else? Why? What advantage does this have? When you say “blockchain”, I hear “single Git repository” — so when you say “email on the blockchain”, I have an aneurysm.

Bitcoin seems to have sparked imagination in large part because it’s decentralized, but I’d argue it’s actually a pretty bad example of a decentralized network, since people keep forking it. The ability to fork is a feature, sure, but the trouble here is that the Bitcoin family has no notion of federation — there is one canonical Bitcoin ledger and it has no notion of communication with any other. That’s what you want for currency, not necessarily other applications. (Bitcoin also incentivizes frivolous forking by giving the creator an initial pile of coins to keep and sell.)

And federation is much more interesting than decentralization! Federation gives us email and the web. Federation means I can set up my own instance with my own rules and still be able to meaningfully communicate with the rest of the network. Federation has some amount of tolerance for changes to the protocol, so such changes are more flexible and rely more heavily on consensus.

Federation is fantastic, and it feels like a massive tragedy that this rekindled interest in decentralization is mostly focused on peer-to-peer networks, which do little to address our current problems with centralized platforms.

And hey, you know what else is federated? Banks.

AI

Again, the tech is cool and all, but the marketing hype is getting way out of hand.

Maybe what I really want from 2018 is less marketing?

For one, I’ve seen a huge uptick in uncritically referring to any software that creates or classifies creative work as “AI”. Can we… can we not. It’s not AI. Yes, yes, nerds, I don’t care about the hair-splitting about the nature of intelligence — you know that when we hear “AI” we think of a human-like self-aware intelligence. But we’re applying it to stuff like a weird dog generator. Or to whatever neural network a website threw into production this week.

And this is dangerously misleading — we already had massive tech companies scapegoating The Algorithm™ for the poor behavior of their software, and now we’re talking about those algorithms as though they were self-aware, untouchable, untameable, unknowable entities of pure chaos whose decisions we are arbitrarily bound to. Ancient, powerful gods who exist just outside human comprehension or law.

It’s weird to see this stuff appear in consumer products so quickly, too. It feels quick, anyway. The latest iPhone can unlock via facial recognition, right? I’m sure a lot of effort was put into ensuring that the same person’s face would always be recognized… but how confident are we that other faces won’t be recognized? I admit I don’t follow all this super closely, so I may be imagining a non-problem, but I do know that humans are remarkably bad at checking for negative cases.

Hell, take the recurring problem of major platforms like Twitter and YouTube classifying anything mentioning “bisexual” as pornographic — because the word is also used as a porn genre, and someone threw a list of porn terms into a filter without thinking too hard about it. That’s just a word list, a fairly simple thing that any human can review; but suddenly we’re confident in opaque networks of inferred details?

I don’t know. “Traditional” classification and generation are much more comforting, since they’re a set of fairly abstract rules that can be examined and followed. Machine learning, as I understand it, is less about rules and much more about pattern-matching; it’s built out of the fingerprints of the stuff it’s trained on. Surely that’s just begging for tons of edge cases. They’re practically made of edge cases.


I’m reminded of a point I saw made a few days ago on Twitter, something I’d never thought about but should have. TurnItIn is a service for universities that checks whether students’ papers match any others, in order to detect cheating. But this is a paid service, one that fundamentally hinges on its corpus: a large collection of existing student papers. So students pay money to attend school, where they’re required to let their work be given to a third-party company, which then profits off of it? What kind of a goofy business model is this?

And my thoughts turn to machine learning, which is fundamentally different from an algorithm you can simply copy from a paper, because it’s all about the training data. And to get good results, you need a lot of training data. Where is that all coming from? How many for-profit companies are setting a neural network loose on the web — on millions of people’s work — and then turning around and selling the result as a product?

This is really a question of how intellectual property works in the internet era, and it continues our proud decades-long tradition of just kinda doing whatever we want without thinking about it too much. Nothing if not consistent.

More of this

A bit tougher, since computers are pretty alright now and everything continues to chug along. Maybe we should just quit while we’re ahead. There’s some real pie-in-the-sky stuff that would be nice, but it certainly won’t happen within a year, and may never happen except in some horrific Algorithmic™ form designed by people that don’t know anything about the problem space and only works 60% of the time but is treated as though it were bulletproof.

Federation

The giants are getting more giant. Maybe too giant? Granted, it could be much worse than Google and Amazon — it could be Apple!

Amazon has its own delivery service and brick-and-mortar stores now, as well as providing the plumbing for vast amounts of the web. They’re not doing anything particularly outrageous, but they kind of loom.

Ad company Google just put ad blocking in its majority-share browser — albeit for the ambiguously-noble goal of only blocking obnoxious ads so that people will be less inclined to install a blanket ad blocker.

Twitter is kind of a nightmare but no one wants to leave. I keep trying to use Mastodon as well, but I always forget about it after a day, whoops.

Facebook sounds like a total nightmare but no one wants to leave that either, because normies don’t use anything else, which is itself direly concerning.

IRC is rapidly bleeding mindshare to Slack and Discord, both of which are far better at the things IRC sadly never tried to do and absolutely terrible at the exact things IRC excels at.

The problem is the same as ever: there’s no incentive to interoperate. There’s no fundamental technical reason why Twitter and Tumblr and MySpace and Facebook can’t intermingle their posts; they just don’t, because why would they bother? It’s extra work that makes it easier for people to not use your ecosystem.

I don’t know what can be done about that, except that hope for a really big player to decide to play nice out of the kindness of their heart. The really big federated success stories — say, the web — mostly won out because they came along first. At this point, how does a federated social network take over? I don’t know.

Social progress

I… don’t really have a solid grasp on what’s happening in tech socially at the moment. I’ve drifted a bit away from the industry part, which is where that all tends to come up. I have the vague sense that things are improving, but that might just be because the Rust community is the one I hear the most about, and it puts a lot of effort into being inclusive and welcoming.

So… more projects should be like Rust? Do whatever Rust is doing? And not so much what Linus is doing.

Open source funding

I haven’t heard this brought up much lately, but it would still be nice to see. The Bay Area runs on open source and is raking in zillions of dollars on its back; pump some of that cash back into the ecosystem, somehow.

I’ve seen a couple open source projects on Patreon, which is fantastic, but feels like a very small solution given how much money is flowing through the commercial tech industry.

Ad blocking

Nice. Fuck ads.

One might wonder where the money to host a website comes from, then? I don’t know. Maybe we should loop this in with the above thing and find a more informal way to pay people for the stuff they make when we find it useful, without the financial and cognitive overhead of A Transaction or Giving Someone My Damn Credit Card Number. You know, something like Bitco— ah, fuck.

Year of the Linux Desktop

I don’t know. What are we working on at the moment? Wayland? Do Wayland, I guess. Oh, and hi-DPI, which I hear sucks. And please fix my sound drivers so PulseAudio stops blaming them when it fucks up.

Weekly roundup: Lost time

Post Syndicated from Eevee original https://eev.ee/dev/2018/02/13/weekly-roundup-lost-time/

I ran out of brain pills near the end of January due to some regulatory kerfuffle, and spent something like a week and a half basically in a daze. I have incredibly a lot of stuff to do right now, too, so not great timing… but, well, I guess no time would be especially good. Oh well. I got a forced vacation and played some Avernum.

Anyway, in the last three weeks, the longest span I’ve ever gone without writing one of these:

  • anise: I added a ✨ completely new menu feature ✨ that looks super cool and amazing and will vastly improve the game.

  • blog: I wrote SUPER game night 3, featuring a bunch of games from GAMES MADE QUICK??? 2.0! It’s only a third of them though, oh my god, there were just so many.

    I also backfilled some release posts, including one for Strawberry Jam 2 — more on that momentarily.

  • ???: Figured out a little roadmap and started on an ???.

  • idchoppers: Went down a whole rabbit hole trying to port some academic C++ to Rust, ultimately so I could intersect arbitrary shapes, all so I could try out this ridiculous idea to infer the progression through a Doom map. This was kind of painful, and is basically the only useful thing I did while unmedicated. I might write about it.

  • misc: I threw together a little PICO-8 prime sieve inspired by this video. It’s surprisingly satisfying.

    (Hmm, does this deserve a release post? Where should its permanent home be? Argh.)

  • art: I started to draw my Avernum party but only finished one of them. I did finish a comic celebrating the return of my brain pills.

  • neon vn: I contributed some UI and bugfixing to a visual novel that’ll be released on Floraverse tomorrow.

  • alice vn: For Strawberry Jam 2, glip and I are making a ludicrously ambitious horny visual novel in Ren’Py. Turns out Ren’Py is impressively powerful, and I’ve been having a blast messing with it. But also our idea requires me to write about sixty zillion words by the end of the month. I guess we’ll see how that goes.

    I have a (NSFW) progress thread going on my smut alt, but honestly, most of the progress for the next week will be “did more writing”.

I’m behind again! Sorry. I still owe a blog post for last month, and a small project for last month, and now blog posts for this month, and Anise game is kinda in limbo, and I don’t know how any of this will happen with this huge jam game taking priority over basically everything else. I’ll see if I can squeeze other stuff in here and there. I intended to draw more regularly this month, too, but wow I don’t think I can even spare an hour a day.

The jam game is forcing me to do a lot of writing that I’d usually dance around and avoid, though, so I think I’ll come out the other side of it much better and faster and more confident.

Welp. Back to writing!

Strawberry Jam 2 🍓

Post Syndicated from Eevee original https://eev.ee/release/2018/01/24/strawberry-jam-2/

🔗 Strawberry Jam 2 on itch

I’m running a game jam, and this announcement is before the jam starts! What a concept!

The idea is simple: you have all of February to make a horny game.

(This jam is, as you may have guessed, NSFW. 🔞)


I think there’s a lot of interesting potential at the intersection of sex and games, but we see very little exploration of it — in large part because mega-platforms like Steam (and its predecessor, Walmart) have historically been really squeamish about anything sexual. Unless it’s scantily-clad women draped over everything, that’s fine. But un-clad women are right out. Also gratuitous high-definition gore is cool. But no nipples!!

The result is a paltry cultural volume of games about sex, but as boundaries continue to be pushed without really being broken, we get more and more blockbuster games with sex awkwardly tacked on top as lazy titillation. “Ah, it’s a story-driven role-playing shooter, but in this one part you can have sex, which will affect nothing and never come up again, but you can see a butt!” Truly revolutionary.

The opposite end of the spectrum also exists, in the form of porn games where the game part is tacked on to make something interactive — you know, click really fast to make clothes fall off or whatever. It’s not especially engaging, but it’s more compelling than staring at a JPEG.

So my secret motive here is to encourage people to explore the vast gulf in the middle — to make games that are interesting as games and that feature sexuality as a fundamental part of the game. Something where both parts could stand alone, yet are so intertwined as to be inseparable.

The one genre that is seeing a lot of experimentation is the raunchy visual novel, which is a great example: they tend to tell stories where sexuality plays a heavy part, but they’re still compelling interactive stories and hold up on those grounds just as well. What, I wonder, would this same sort of harmony look like for other genres, other kinds of interaction? What does a horny racing game look like, or a horny inventory-horror game, or a horny brawler? Hell, why are there no horny co-op games to speak of? That seems obvious, right?

I haven’t said all this on the jam page because it would add half a dozen paragraphs to what is already a lengthy document. I also suspect that I’ll sound like I’m suggesting “a racing game but all the cars are dicks,” which isn’t quite right, and I’d need to blather even more to clarify. Anyway, it seems vaguely improper as the jam organizer to be telling people what kind of games not to make; last year I just tried to lead by example by making fox flux.


If exploring this design space seems interesting to you, please do join in! If you’ve never made a game before, this might be a great opportunity to give it a try — everything is going to be embarrassing and personal regardless. Maybe hop on Discord if you need help or want a teammate. Feel free to flip through last year’s entries, too, or my (super nsfw) thread where I played some and talked about them. Some of them are even open source, cough, cough.

Previously:

GDQ schedule dimmer

Post Syndicated from Eevee original https://eev.ee/release/2018/01/23/gdq-schedule-dimmer/

🔗 Source code on GitHub
🔗 Install, maybe

Does this ever happen to you?

[TODO: insert black and white gif of someone struggling to read the GDQ schedule because it’s a single long table and it’s hard to even keep track of what day you’re looking at, let alone find out what’s going on right now]

Well, no more! Thanks to the power of IavaScript, now it’s like the picture above, which I guess gave it away huh.

Not very useful now, since I forgot to even post about it here before AGDQ ended, but presumably useful in SGDQ since they never seem to change this page at all.

Wait! Before you click on the “install” link above. Firefox users will need Greasemonkey. Chrome used to support user scripts natively, and legends say it still does, but there are so many walls around extensions now that I couldn’t figure out how to make it work, so just get Tampermonkey, which is also available for most other browsers.

GAMES MADE QUICK??? 2.0

Post Syndicated from Eevee original https://eev.ee/release/2018/01/23/games-made-quick-2-0/

🔗 GAMES MADE QUICK??? 2.0 on itch

I realize, with all the cognitive speed and grace of a cat falling out of a chair, that I have my own website where I can announce things that I am doing.

Here is a thing that I am having done: it’s GAMES MADE QUICK??? 2.0, a game jam that runs concurrently with Games Done Quick. The inspiration was that I once spent the entire week of AGDQ doing nothing but watching the stream, which completely ruined my momentum and cost me the following week as well while I struggled to get back up to speed. What a catastrophe!

So my solution was to spend the week making a game instead, which prompted someone to suggest that I make a jam out of it, and so I did. The results were NEON PHASE and also the original GAMES MADE QUICK???.

It’s a bit late to join now, but look forward to the jam during SGDQ, which runs the last week of June! In the meantime, perhaps peruse the fruits of this season’s labor, or at least glance over my thoughts on some of them.

Previously:

SUPER game night 3: GAMES MADE QUICK??? 2.0

Post Syndicated from Eevee original https://eev.ee/blog/2018/01/23/super-game-night-3-games-made-quick-2-0/

Game night continues with a smorgasbord of games from my recent game jam, GAMES MADE QUICK??? 2.0!

The idea was to make a game in only a week while watching AGDQ, as an alternative to doing absolutely nothing for a week while watching AGDQ. (I didn’t submit a game myself; I was chugging along on my Anise game, which isn’t finished yet.)

I can’t very well run a game jam and not play any of the games, so here’s some of them in no particular order! Enjoy!

These are impressions, not reviews. I try to avoid major/ending spoilers, but big plot points do tend to leave impressions.

Weather Quest, by timlmul

short · rpg · jan 2017 · (lin)/mac/win · free on itch · jam entry

Weather Quest is its author’s first shipped game, written completely from scratch (the only vendored code is a micro OO base). It’s very short, but as someone who has also written LÖVE games completely from scratch, I can attest that producing something this game-like in a week is a fucking miracle. Bravo!

For reference, a week into my first foray, I think I was probably still writing my own Tiled importer like an idiot.

Only Mac and Windows builds are on itch, but it’s a LÖVE game, so Linux folks can just grab a zip from GitHub and throw that at love.

FINAL SCORE: ⛅☔☀

Pancake Numbers Simulator, by AnorakThePrimordial

short · sim · jan 2017 · lin/mac/win · free on itch · jam entry

Given a stack of N pancakes (of all different sizes and in no particular order), the Nth pancake number is the most flips you could possibly need to sort the pancakes in order with the smallest on top. A “flip” is sticking a spatula under one of the pancakes and flipping the whole sub-stack over. There’s, ah, a video embedded on the game page with some visuals.

Anyway, this game lets you simulate sorting a stack via pancake flipping, which is surprisingly satisfying! I enjoy cleaning up little simulated messes, such as… incorrectly-sorted pancakes, I guess?

This probably doesn’t work too well as a simulator for solving the general problem — you’d have to find an optimal solution for every permutation of N pancakes to be sure you were right. But it’s a nice interactive illustration of the problem, and if you know the pancake number for your stack size of choice (which I wish the game told you — for seven pancakes, it’s 8), then trying to restore a stack in that many moves makes for a nice quick puzzle.

FINAL SCORE: \(\frac{18}{11}\)

Framed Animals, by chridd

short · metroidvania · jan 2017 · web/win · free on itch · jam entry

The concept here was to kill the frames, save the animals, which is a delightfully literal riff on a long-running AGDQ/SGDQ donation incentive — people vote with their dollars to decide whether Super Metroid speedrunners go out of their way to free the critters who show you how to walljump and shinespark. Super Metroid didn’t have a showing at this year’s AGDQ, and so we have this game instead.

It’s rough, but clever, and I got really into it pretty quickly — each animal you save gives you a new ability (in true Metroid style), and you get to test that ability out by playing as the animal, with only that ability and no others, to get yourself back to the most recent save point.

I did, tragically, manage to get myself stuck near what I think was about to be the end of the game, so some of the animals will remain framed forever. What an unsatisfying conclusion.

Gravity feels a little high given the size of the screen, and like most tile-less platformers, there’s not really any way to gauge how high or long your jump is before you leap. But I’m only even nitpicking because I think this is a great idea and I hope the author really does keep working on it.

FINAL SCORE: $136,596.69

Battle 4 Glory, by Storyteller Games

short · fighter · jan 2017 · win · free on itch · jam entry

This is a Smash Bros-style brawler, complete with the four players, the 2D play area in a 3D world, and the random stage obstacles showing up. I do like the Smash style, despite not otherwise being a fan of fighting games, so it’s nice to see another game chase that aesthetic.

Alas, that’s about as far as it got — which is pretty far for a week of work! I don’t know what more to say, though. The environments are neat, but unless I’m missing something, the only actions at your disposal are jumping and very weak melee attacks. I did have a good few minutes of fun fruitlessly mashing myself against the bumbling bots, as you can see.

FINAL SCORE: 300%

Icnaluferu Guild, Year Sixteen, by CHz

short · adventure · jan 2017 · web · free on itch · jam entry

Here we have the first of several games made with bitsy, a micro game making tool that basically only supports walking around, talking to people, and picking up items.

I tell you this because I think half of my appreciation for this game is in the ways it wriggled against those limits to emulate a Zelda-like dungeon crawler. Everything in here is totally fake, and you can’t really understand just how fake unless you’ve tried to make something complicated with bitsy.

It’s pretty good. The dialogue is entertaining (the rest of your party develops distinct personalities solely through oneliners, somehow), the riffs on standard dungeon fare are charming, and the Link’s Awakening-esque perspective walls around the edges of each room are fucking glorious.

FINAL SCORE: 2 bits

The Lonely Tapes, by JTHomeslice

short · rpg · jan 2017 · web · free on itch · jam entry

Another bitsy entry, this one sees you play as a Wal— sorry, a JogDawg, which has lost its cassette tapes and needs to go recover them!

(A cassette tape is like a VHS, but for music.)

(A VHS is—)

I have the sneaking suspicion that I missed out on some musical in-jokes, due to being uncultured swine. I still enjoyed the game — it’s always clear when someone is passionate about the thing they’re writing about, and I could tell I was awash in that aura even if some of it went over my head. You know you’ve done good if someone from way outside your sphere shows up and still has a good time.

FINAL SCORE: Nine… Inch Nails? They’re a band, right? God I don’t know write your own damn joke

Pirate Kitty-Quest, by TheKoolestKid

short · adventure · jan 2017 · win · free on itch · jam entry

I completely forgot I’d even given “my birthday” and “my cat” as mostly-joking jam themes until I stumbled upon this incredible gem. I don’t think — let me just check here and — yeah no this person doesn’t even follow me on Twitter. I have no idea who they are?

BUT THEY MADE A GAME ABOUT ANISE AS A PIRATE, LOOKING FOR TREASURE

PIRATE. ANISE

PIRATE ANISE!!!

This game wins the jam, hands down. 🏆

FINAL SCORE: Yarr, eight pieces o’ eight

CHIPS Mario, by NovaSquirrel

short · platformer · jan 2017 · (lin/mac)/win · free on itch · jam entry

You see this? This is fucking witchcraft.

This game is made with MegaZeux. MegaZeux games look like THIS. Text-mode, bound to a grid, with two colors per cell. That’s all you get.

Until now, apparently?? The game is a tech demo of “unbound” sprites, which can be drawn on top of the character grid without being aligned to it. And apparently have looser color restrictions.

The collision is a little glitchy, which isn’t surprising for a MegaZeux platformer; I had some fun interactions with platforms a couple times. But hey, goddamn, it’s free-moving Mario, in MegaZeux, what the hell.

(I’m looking at the most recently added games on DigitalMZX now, and I notice that not only is this game in the first slot, but NovaSquirrel’s MegaZeux entry for Strawberry Jam last February is still in the seventh slot. RIP, MegaZeux. I’m surprised a major feature like this was even added if the community has largely evaporated?)

FINAL SCORE: n/a, disqualified for being probably summoned from the depths of Hell

d!¢< pic, by 573 Games

short · story · jan 2017 · web · free on itch · jam entry

This is a short story about not sending dick pics. It’s very short, so I can’t say much without spoiling it, but: you are generally prompted to either text something reasonable, or send a dick pic. You should not send a dick pic.

It’s a fascinating artifact, not because of the work itself, but because it’s so terse that I genuinely can’t tell what the author was even going for. And this is the kind of subject where the author was, surely, going for something. Right? But was it genuinely intended to be educational, or was it tongue-in-cheek about how some dudes still don’t get it? Or is it side-eying the player who clicks the obviously wrong option just for kicks, which is the same reason people do it for real? Or is it commentary on how “send a dick pic” is a literal option for every response in a real conversation, too, and it’s not that hard to just not do it — unless you are one of the kinds of people who just feels a compulsion to try everything, anything, just because you can? Or is it just a quick Twine and I am way too deep in this? God, just play the thing, it’s shorter than this paragraph.

I’m also left wondering when it is appropriate to send a dick pic. Presumably there is a correct time? Hopefully the author will enter Strawberry Jam 2 to expound upon this.

FINAL SCORE: 3½” 😉

Marble maze, by Shtille

short · arcade · jan 2017 · win · free on itch · jam entry

Ah, hm. So this is a maze navigated by rolling a marble around. You use WASD to move the marble, and you can also turn the camera with the arrow keys.

The trouble is… the marble’s movement is always relative to the world, not the camera. That means if you turn the camera 30° and then try to move the marble, it’ll move at a 30° angle from your point of view.

That makes navigating a maze, er, difficult.

Camera-relative movement is the kind of thing I take so much for granted that I wouldn’t even think to do otherwise, and I think it’s valuable to look at surprising choices that violate fundamental conventions, so I’m trying to take this as a nudge out of my comfort zone. What could you design in an interesting way that used world-relative movement? Probably not the player, but maybe something else in the world, as long as you had strong landmarks? Hmm.

FINAL SCORE: ᘔ

Refactor: flight, by fluffy

short · arcade · jan 2017 · lin/mac/win · free on itch · jam entry

Refactor is a game album, which is rather a lot what it sounds like, and Flight is one of the tracks. Which makes this a single, I suppose.

It’s one of those games where you move down an oddly-shaped tunnel trying not to hit the walls, but with some cute twists. Coins and gems hop up from the bottom of the screen in time with the music, and collecting them gives you points. Hitting a wall costs you some points and kills your momentum, but I don’t think outright losing is possible, which is great for me!

Also, the monk cycles through several animal faces. I don’t know why, and it’s very good. One of those odd but memorable details that sits squarely on the intersection of abstract, mysterious, and a bit weird, and refuses to budge from that spot.

The music is great too? Really chill all around.

FINAL SCORE: 🎵🎵🎵🎵

The Adventures of Klyde

short · adventure · jan 2017 · web · free on itch · jam entry

Another bitsy game, this one starring a pig (humorously symbolized by a giant pig nose with ears) who must collect fruit and solve some puzzles.

This is charmingly nostalgic for me — it reminds me of some standard fare in engines like MegaZeux, where the obvious things to do when presented with tiles and pickups were to make mazes. I don’t mean that in a bad way; the maze is the fundamental environmental obstacle.

A couple places in here felt like invisible teleport mazes I had to brute-force, but I might have been missing a hint somewhere. I did make it through with only a little trouble, but alas — I stepped in a bad warp somewhere and got sent to the upper left corner of the starting screen, which is surrounded by walls. So Klyde’s new life is being trapped eternally in a nowhere space.

FINAL SCORE: 19/20 apples

And more

That was only a third of the games, and I don’t think even half of the ones I’ve played. I’ll have to do a second post covering the rest of them? Maybe a third?

Or maybe this is a ludicrous format for commenting on several dozen games and I should try to narrow it down to the ones that resonated the most for Strawberry Jam 2? Maybe??

Weekly roundup: Potpourri 2

Post Syndicated from Eevee original https://eev.ee/dev/2018/01/23/weekly-roundup-potpourri-2/

  • blog: I wrote a birthday post, as is tradition. I finally finished writing Game Night 2, a full month after we actually played those games.

  • art: I put together an art improvement chart for last year, after skipping doing it in July, tut tut. Kind of a weird rollercoaster!

    I worked a teeny bit on two one-off comics I guess but they aren’t reeeally getting anywhere fast. Comics are hard.

    I made a banner for Strawberry Jam 2 which I think came out fantastically!

  • games: I launched Strawberry Jam 2, a month-long February game jam about making horny games. I will probably be making a horny game for it.

  • idchoppers: I took another crack at dilation. Some meager progress, maybe. I think I’m now porting bad academic C++ to Rust to get the algorithm I want, and I can’t help but wonder if I could just make up something of my own faster than this.

  • fox flux: I did a bunch of brainstorming and consolidated a bunch of notes from like four different places, which feels like work but also feels like it doesn’t actually move the project forward.

  • anise!!: Ah, yes, this fell a bit by the wayside. Some map work, some attempts at a 3D effect for a particular thing without much luck (though I found a workaround in the last couple days).

  • computers: I relieved myself of some 200 browser tabs, which feels fantastic, though I’ve since opened like 80 more. Alas. I also tried to put together a firejail profile for running mystery games from the internet, and I got like 90% of the way there, but it turns out there’s basically no way to stop an X application from reading all keyboard input.

    (Yes, I know about that, and I tried it. Yes, that too.)

I’ve got a small pile of little projects that are vaguely urgent, so as much as I’d love to bash my head against idchoppers for a solid week, I’m gonna try to focus on getting a couple half-done things full-done. And maybe try to find time for art regularly so I don’t fall out of practice? Huff puff.

Game night 2: Detention, Viatoree, Paletta

Post Syndicated from Eevee original https://eev.ee/blog/2018/01/16/game-night-2-detention-viatoree-paletta/

Game night continues with:

  • Detention
  • Viatoree
  • Paletta

These are impressions, not reviews. I try to avoid major/ending spoilers, but big plot points do tend to leave impressions.

Detention

longish · inventory horror · jan 2017 · lin/mac/win · $12 on steam · website

Inventory horror” is a hell of a genre.

I think this one came from a Twitter thread where glip asked for indie horror recommendations. It’s apparently well-known enough to have a Wikipedia article, but I hadn’t heard of it before.

I love love love the aesthetic here. It’s obviously 2Dish from a side view (though there’s plenty of parallax in a lot of places), and it’s all done with… papercraft? I think of it as papercraft. Everything is built out of painted chunks that look like they were cut out of paper. It’s most obvious when watching the protagonist move around; her legs and skirt swivel as she walks.

Less obvious are the occasional places where tiny details repeat in the background because a paper cutout was reused. I don’t bring that up as a dig on the art; on the contrary, I really liked noticing that once or twice. It made the world feel like it was made with a tileset (albeit with very large chunky tiles), like it’s slightly artificial. I’m used to seeing sidescrollers made from tiles, of course, but the tiles are usually colorful and cartoony pixel art; big gritty full-color tiles are unusual and eerie.

And that’s a good thing in a horror game! Detention’s setting is already slightly unreal, and it’s made all the moreso by my Western perspective: it takes place in a Taiwanese school in the 60’s, a time when Taiwan was apparently under martial law. The Steam page tells you this, but I didn’t even know that much when we started playing, so I’d effectively been dropped somewhere on the globe and left to collect the details myself. Even figuring out we were in Taiwan (rather than mainland China) felt like an insight.

Thinking back, it was kind of a breath of fresh air. Games can be pretty heavy-handed about explaining the setting, but I never got that feeling from Detention. There’s more than enough context to get what’s going on, but there are no “stop and look at the camera while monologuing some exposition” moments. The developers are based in Taiwan, so it’s possible the setting is plenty familiar to them, and my perception of it is a complete accident. Either way, it certainly made an impact. Death of the author and whatnot, I suppose.

One thing in particular that stood out: none of the Chinese text in the environment is directly translated. The protagonist’s thoughts still give away what it says — “this is the nurse’s office” and the like — but that struck me as pretty different from simply repeating the text in English as though I were reading a sign in an RPG. The text is there, perfectly legible, but I can’t read it; I can only ask the protagonist to read it and offer her thoughts. It drives home that I’m experiencing the world through the eyes of the protagonist, who is their own person with their own impression of everything. Again, this is largely an emergent property of the game’s being designed in a culture that is not mine, but I’m left wondering how much thought went into this style of localization.

The game itself sees you wandering through a dark and twisted version of the protagonist’s school, collecting items and solving puzzles with them. There’s no direct combat, though some places feature a couple varieties of spirits called lingered which you have to carefully avoid. As the game progresses, the world starts to break down, alternating between increasingly abstract and increasingly concrete as we find out who the protagonist is and why she’s here.

The payoff is very personal and left a lasting impression… though as I look at the Wikipedia page now, it looks like the ending we got was the non-canon bad ending?! Well, hell. The bad ending is still great, then.

The whole game has a huge Silent Hill vibe, only without the combat and fog. Frankly, the genre might work better without combat; personal demons are more intimidating and meaningful when you can’t literally shoot them with a gun until they’re dead.

FINAL SCORE: 拾

Viatoree

short · platformer · sep 2013 · win · free on itch

I found this because @itchio tweeted about it, and the phrase “atmospheric platform exploration game” is the second most beautiful sequence of words in the English language.

The first paragraph on the itch.io page tells you the setup. That paragraph also contains more text than the entire game. In short: there are five things, and you need to find them. You can walk, jump, and extend your arms straight up to lift yourself to the ceiling. That’s it. No enemies, no shooting, no NPCs (more or less).

The result is, indeed, an atmospheric platform exploration game. The foreground is entirely 1-bit pixel art, save for the occasional white pixel to indicate someone’s eyes, and the background is only a few shades of the same purple hue. The game becomes less about playing and more about just looking at the environmental detail, appreciating how much texture the game manages to squeeze out of chunky colorless pixels. The world is still alive, too, much moreso than most platformers; tiny critters appear here and there, doing some wandering of their own, completely oblivious to you.

The game is really short, but it… just… makes me happy. I’m happy that this can exist, that not only is it okay for someone to make a very compact and short game, but that the result can still resonate with me. Not everything needs to be a sprawling epic or ask me to dedicate hours of time. It takes a few tiny ideas, runs with them, does what it came to do, and ends there. I love games like this.

That sounds silly to write out, but it’s been hard to get into my head! I do like experimenting, but I also feel compelled to reach for the grandiose, and grandiose experiment sounds more like mad science than creative exploration. For whatever reason, Viatoree convinced me that it’s okay to do a small thing, in a way that no other jam game has. It was probably the catalyst that led me to make Roguelike Simulator, and I thank it for that.

Unfortunately, we collected four of the five macguffins before hitting upon on a puzzle we couldn’t make heads or tails of. After about ten minutes of fruitless searching, I decided to abandon this one unfinished, rather than bore my couch partner to tears. Maybe I’ll go take another stab at it after I post this.

FINAL SCORE: ●●●●○

Paletta

medium · puzzle story · nov 2017 · win · free on itch

Paletta, another RPG Maker work, won second place in the month-long Indie Game Maker Contest 2017. Nice! Apparently MOOP came in fourth in the same jam; also nice! I guess that’s why both of them ended up on the itch front page.

The game is set in a world drained of color, and you have to go restore it. Each land contains one lost color, and each color gives you a corresponding spell, which is generally used for some light puzzle-solving in further lands. It’s a very cute and light-hearted game, and it actually does an impressive job of obscuring its RPG Maker roots.

The world feels a little small to me, despite having fairly spacious maps. The progression is pretty linear: you enter one land, talk to a small handful of NPCs, solve the one puzzle, get the color, and move on. I think all the areas were continuously connected, too, which may have thrown me off a bit — these areas are described as though they were vast regions, but they’re all a hundred feet wide and nestled right next to each other.

I love playing with color as a concept, and I wish the game had run further with it somehow. Rescuing a color does add some color back to the world, but at times it seemed like the color that reappeared was somewhat arbitrary? It’s not like you rescue green and now all the green is back. Thinking back on it now, I wonder if each rescued color actually changed a fixed set of sprites from gray to colorized? But it’s been a month (oops) and now I’m not sure.

I’m not trying to pick on the authors for the brevity of their jam game and also first game they’ve ever finished. I enjoyed playing it and found it plenty charming! It just happens that this time, what left the biggest impression on me was a nebulous feeling that something was missing. I think that’s still plenty important to ponder.

FINAL SCORE: ❤️💛💚💙💜