Would love some thoughts on techniques for memory layout and object lifetime appropriate for NES/6502.
So far, I've learned:
-SoA over AoS
-8b members wherever possible
-breaking 16b members to SOA 8b members where speed is most critical
-8b indices over pointers
For lifetime management, I'm currently using two patterns:
-packed array (bubble down last element on remove)
-external singly-linked list
Packed arrays are definitely fastest for iteration, but moving elements invalidates external pointers/indices.
The single list is nice: array of next-indices, free_head and used_head indices. This lets one do the standard trick of having both a free and used list for the cost of one link/item. Downsides: iteration is slower, and (less important to me) frees require traversal to find previous link.
Double-linked lists would make removal constant time, but probably not worth the RAM overhead, given number of used nodes is relatively low.
For an entity system, instead of a list of polymorphic objects, I've been just statically separating and sizing the data (A_SOA_16 A_t; B_SOA_8 B_t; etc). This eliminates dispatch/switch-on-type, and saves some member memory (given I'm not using a general heap), at some costs to free memory efficiency. If I understand correctly, this has been the pattern 8b games were often coded?
Any other good patterns? Special 6502 tricks?
memory and object patterns?
Moderator: Moderators
Re: memory and object patterns?
You are thinking slightly too complex for a typical NES game. No alloc/dealloc is usually necessary, just statically allocate ENEMY_MAX, and when looping over, skip the dead ones.
It's only once the screen is full of enemies that you start to need more efficient approaches.
edit: Or to put it another way, who cares about O(n) when N=4.
It's only once the screen is full of enemies that you start to need more efficient approaches.
edit: Or to put it another way, who cares about O(n) when N=4.
Re: memory and object patterns?
Exactly what calima said!
I've settled with a static list. When iterating through it the logic checks every slot. I don't care about keeping it packed or having other helper variables.
Reasoning: when the screen is full of enemies it has to go through every item anyway.
So when it isn't full of enemies it doesn't matter if it goes through every item because the empty ones have no logic and are quickly skipped. In other words, keeping the list packed would only optimize the game when the screen isn't full of enemies.
I've settled with a static list. When iterating through it the logic checks every slot. I don't care about keeping it packed or having other helper variables.
Reasoning: when the screen is full of enemies it has to go through every item anyway.
So when it isn't full of enemies it doesn't matter if it goes through every item because the empty ones have no logic and are quickly skipped. In other words, keeping the list packed would only optimize the game when the screen isn't full of enemies.
https://twitter.com/bitinkstudios <- Follow me on twitter! Thanks!
https://www.patreon.com/bitinkstudios <- Support me on Patreon!
https://www.patreon.com/bitinkstudios <- Support me on Patreon!
- never-obsolete
- Posts: 411
- Joined: Wed Sep 07, 2005 9:55 am
- Location: Phoenix, AZ
- Contact:
Re: memory and object patterns?
I hard code certain slots to specific types so assumptions can be made when it comes time for collision and other things:
0: Player 1
1: Player 2
2-4: Player 1 projectiles
5-7: Player 2 projectiles
8-31: General use
32-39: Map "doors"
You can also add data fields to certain groups without having to inflate all the groups ram footprint by accessing it using an offset.
0: Player 1
1: Player 2
2-4: Player 1 projectiles
5-7: Player 2 projectiles
8-31: General use
32-39: Map "doors"
You can also add data fields to certain groups without having to inflate all the groups ram footprint by accessing it using an offset.
Re: memory and object patterns?
I used to have several linked lists grouping objects by type and whatnot, but among other things, the complexity of removing elements from singly linked lists made me give up on this idea. Now I have only one linked list, for the free object slots. This list is very quick and easy to manage, since you can always insert to and remove from the beginning, which is much better than scanning all slots looking for a free one.
Now I have each object indicate its type(s) using bit fields, allowing objects to scan the list looking for the types of objects they interact with.
Now I have each object indicate its type(s) using bit fields, allowing objects to scan the list looking for the types of objects they interact with.
Re: memory and object patterns?
Thanks for all the replies!
Some more context driving my thinking:
-I don't have yet an intuitive feel yet for the real complexity bounds of NES games - mostly just informed by what I've played
-I want to push those bounds
-I'm currently prototyping an 8-way scrolling shooter, and want to maximize on-screen complexity
-I want to keep frame rate/avoid lag frames
-I've got (relatively) large levels and want level state to be preserved (i.e. not re-spawning enemies when revisiting parts of the level)
-AFAICT CPU is going to be my limit, rather than RAM. Well, I'm using MM3 and the expansion RAM, so that helps...
On object systems: in general, I'm trying to avoid polymorphic/switch-on-type systems - they can be fundamentally slower by losing compile-time type knowledge, though statically allocating ranges as suggested can avoid that. More of a code style thing, but I dislike union-of-members entity systems because IMO it reduces code clarity, where it's not clear per-type which members are used. And storage efficiencies drive re-use of members. That's second order to me though
Thinking out loud:
The point on optimizing for worst case is key though. For some things, that's going to be go through every item (ex: missiles), whereas for others things I'm going to need to cull to ~screen bounds (ex: turret AI). Maintaining an active list may be the key here.
Given my assumptions above, traversal speed is key, particularly for a few O(n^2) collision detection parts. Dead flags is an interesting one I'd initially rejected. Intuitively 8b index linked-list seems more optimal on 6502 than array indexing and checking a flag?
While insertion/deletion is lower frequency, I've got a few potential gameplay patterns (ex: missile burst launches) that cause this to spike.
I've got another pattern that can drive a different strategy - fixed lifetime (ex: explosions). I made this a FIFO, with head & tail indices (pow2 size for masked wrap).
Some more context driving my thinking:
-I don't have yet an intuitive feel yet for the real complexity bounds of NES games - mostly just informed by what I've played
-I want to push those bounds
-I'm currently prototyping an 8-way scrolling shooter, and want to maximize on-screen complexity
-I want to keep frame rate/avoid lag frames
-I've got (relatively) large levels and want level state to be preserved (i.e. not re-spawning enemies when revisiting parts of the level)
-AFAICT CPU is going to be my limit, rather than RAM. Well, I'm using MM3 and the expansion RAM, so that helps...
On object systems: in general, I'm trying to avoid polymorphic/switch-on-type systems - they can be fundamentally slower by losing compile-time type knowledge, though statically allocating ranges as suggested can avoid that. More of a code style thing, but I dislike union-of-members entity systems because IMO it reduces code clarity, where it's not clear per-type which members are used. And storage efficiencies drive re-use of members. That's second order to me though
Thinking out loud:
The point on optimizing for worst case is key though. For some things, that's going to be go through every item (ex: missiles), whereas for others things I'm going to need to cull to ~screen bounds (ex: turret AI). Maintaining an active list may be the key here.
Given my assumptions above, traversal speed is key, particularly for a few O(n^2) collision detection parts. Dead flags is an interesting one I'd initially rejected. Intuitively 8b index linked-list seems more optimal on 6502 than array indexing and checking a flag?
While insertion/deletion is lower frequency, I've got a few potential gameplay patterns (ex: missile burst launches) that cause this to spike.
I've got another pattern that can drive a different strategy - fixed lifetime (ex: explosions). I made this a FIFO, with head & tail indices (pow2 size for masked wrap).