KICK C and the 65C02 CPU - A double linked list without pointers.

svenvandevelde · Post by **svenvandevelde** » Thu May 11, 2023 6:10 am

So as you've seen in the previous articles, developing in C using pointers have the risk to produce code that is not well tuned for the 65C02 processor. The 65C02 is an 8 bit processor. Where possible, try to write code that produces code using absolute indexed addressing. To achieve this, use structures applying the method Structures of Arrays (SoA). Stick to the byte size boundaries.

So in this article we will show a concrete example of C code that produces a double linked list capability for the CX16, following the above design principles. You can find the code and executable attached, but let's walk through the code and with a few screenshots of debug output we can have a look how this works.

The double linked list has a concrete use case in my equinoxe game. I needed a capability to administer various lists for the various types of objects flying around on the screen, this frame per frame. And this frame aspect requires me to squeeze every cycle out of the CPU where I can. The equinoxe game has various types of objects, like a player space ship and later player controlled objects, various enemy ships, scenery objects, ground objects, bullets, explosions, engine exhausts, etc ... Each of these objects have code that models the moving and AI behaviour and have data properties attached. The generated code to administer all this logic, is deployed in banked memory, so each type of object code is located at a different RAM bank between A000 and BFFF on the CX16. Using kernal routine JSRFAR I'm calling for each type of object an "update" routine that calculates for each frame the new positions and actions of the object type.

By using the RAM banking, I have lot's of code space to model the behaviour of these objects and i'm not bound to the $0800 till $9F00 address range in low memory. In fact, I started my game like this and quickly realized that the low memory address space is rather limited. Unlike the C64 and C128, the upper memory address spaces cannot be "deactivated", especially the ROMs between $C000 and $FFFF. There is no shadow RAM underneath ROM address space, so hence RAM banking was the solution! Together with Jesper we developed a nice RAM banking capability in kickc, that allows you to compile your code banked and deploy it banked, but that explanation will come later how to use it.

The consequence of the RAM banking is that FAR calls need to be made to administer the positions of each object type. Imagine I have 1 player ship, but 32 enemies and 25 bullets in the air. The equinoxe game logic calls a dedicated update routine first for the player ship, then it calls the update routine for the enemy ships and then it calls the update routine for the bullets using JSRFAR kernal routine. So, instead of doing for each object a JSRFAR routine, i'm doing for each object type a JSRFAR call that then in encapsulation mode performs its logic. This saves me a lot of CPU expensive JSRFAR calls, however, that requires some mechanism to quickly be able to loop through the entries that describe the object types, and ONLY those object types.

Simply said, the CX16 has 128 sprites, of which 127 are usable for equinoxe (the sprite 0 is the mouse). Imagine I would use a simple array (been there....), that would be used by each update routine for each object type, which would simply loop through the array, validating if the object underneath is of the same type, and then perform the update logic. That means, that for players i would need to loop 127 times, for enemy ships i would need to loop 127 times and for bullets i would need to loop 127 times. Add to that equation object types for ground installations, explostions, scenary and the like, and you see quickly that the looping would cause a significant overhead to the game logic. It really counts, loop overheads are killing the frame per frame performance of the game engine. So it is important to have a design that minimizes such loop overheads!

I reworked the engine to use a simple double linked lists (plural), mapped on a SoA, with multiple root positions for each object type, having it's own linked list within the SoA. That allows me for each object type to simply iterate through the list of each object type, avoiding the problematic loop overhead!

Remember, we declare a structure that contains multiple arrays of maximum one byte length! We use where possible for each field a data type that is one byte large! This will result in absolute indexed addressing and will produce minimal code size and fast and functional code!

So below you find an example how such a list can be designed. I'm not showing the actual equinoxe game engine solution because that would really bring us too far. Let's first talk about the setup of the data structures and types.

We declare ELEMENTS, which denote a maximum of 64 elements within the SoA. Note that I've decided to use #defines instead of const as the const keyword is not the same as #define in C.