Amiga Isometric Devlog #3
30 March 2024
SPRITES AND ISOMETRIC SORTING
It's been a busy couple of weeks in real life, but the show goes on! When we last saw the Amiga iso-game I was about to get some objects into the world and implement isometric sorted rendering.
I had studied a disassembly of the Spectrum version of Head over Heels and read some text Jon Ritman had written about it, and felt I had a good handle on how it worked. Still, I decided first to make a prototype in Pygame just to make sure. In this, I used the dumbest possible isometric "is in front" function (DPIFF) I found on a blog post I first read in 2013(!), which just used the sum of an object's x, y, z coordinates as its sort key. To my surprise, it worked!
Pygame Prototype
The first step in the game itself was to tag, in the map editor, the blocks that needed isometric sorted rendering and pipeline that through into the binary map data used by the engine. Most blocks in a room won't need sorted as the player (and other objects) can't pass behind them. 80's isometric games take advantage of this fact to make the floor and walls non-interactive backdrops, and while that's not the case for this game it's still a big performance gain to not sort all the potentially thousands of blocks in a room.
Tagging Blocks
Simply getting sprites rendered on the screen at all took some work. The previous games I'd made with this codebase were 2D and there was some work (and thinkage) required to efficiently introduce a transformation step from 3D world coordinates to the screen.
I also had to create a new background restore system based on saving and restoring chunks of the background with temporary buffers instead of the simpler restores from a pristine buffer I'd used before. Once again the restore blits are run from a copperlist, but for this approach it had to run the restores in reverse order. I figured the most effcient way of doing this was to build the copperlist backwards in memory as the entities were rendered, so the restore blits ran in the reverse order.
First Sprites
All that done, I could finally look at the, extremely core to the game, isometric sorting.
Despite reading a lot of articles featuring clever words like Directed Acyclic Graphs, Topgraphic Sorting and Tarjan's Strongly Connected Components Algorithm, I went with a simple doubly-linked list (like Head over Heels) containing both moving entities and sort-tagged blocks, ordered by each objects DPIFF key.
When an entity moves it is removed from the list and re-added with it's new sort key. Once all entities have moved, any movers are flagged for rendering, and every object in the list after each (ie: in front of it) that also overlaps it in screen space is also flagged for rendering. Finally, the whole list is walked in order and any flagged objects are drawn. Restoring the background with the copperlist means I can use fast copy blits instead of slower cookie-cut blits to draw blocks behind entities.
I think the linked list and render flags are probably doing something like making a DAG and topographic sort, of sorts. Maybe.
It semed to work anyway, just like the prototype. Eventually.
Living in an Isometric World
Living in an Isometric World
Ignore the jerky movment in the video, it's only moving in 8-point steps to speed up testing. It can move about smoothly scrolling at 25fps.
I also implemented optimisations to clip the rendering of iso-sorted blocks to just the words that an entity overlaps. In some cases this is a significant saving. One test case reduced the block blit from 780 cookie-cut words to 230, for example.
I'd also like to see if it's possible to reduce the length of the list walks for each moving entity, perhaps by (somehow) making sublists based on a spatial hash. However, it could easily be the case that maintaining any complicated data structure like this would be less efficient than the simple list walk and AABB testing it's doing now. Always the way. I'l leave this one for now.
What I really need to test is player Z movement; my Spidey-Sense tingles that the DPIFF might be a little too dumb, though it seemed to work well enough for the game in the blog post and in my prototype. I have a fallback clever algorithm based on axis overlaps (it might be a form of the SAT), but it's slower of course.
Next would be controller driven movement, collision detection, and perhaps even some early physics like falling. Then it might even start to look like something that could become a game.
Given time.