Dynamic Memory Allocation

[ManicGenius]

I'm curious why you asked. Do you have a use-case for a generic memory allocator? If so, please share. I'm really curious now on how a NES game might benefit form one.

Pretty much just general curiosity really. Old-school ASM programming is really kind've a lost art and thinking about high-level stuff in low-level terms on a limited instruction set is a fun thought game.

A lot of the people on this forum are really knowledgable about things, and just trolling posts here helps a lot. This is just one thing I don't think I've seen a post on so I figured I'd ask.

[ManicGenius]

From most posts so far it seems most people just use a set of fixed variables that they let objects utilize at a given time... Which definitely makes sense, cause like clueless said, on a system like this fragmentation and allocation management is a bitch.

Though I kinda like tokumaru's singly-linked list deal.

[tokumaru]

Each object accesses its own bytes with indirect addressing through a single pointer variable that gets updated after each object is done being processed.

That's the reason why I don't use linear blocks of memory for my objects. Having to modify Y in order to access any byte would be a pain in the ass. I figured that having the object memory interleaved would be more efficient. Loads and stores are 1 cycle faster than in indirect addressing, and there's no need to modify an index register to access different object properties, you just use labels. Also, modifying only the index register to access different object slots is quicker than modifying a 16-bit pointer. I took all that into consideration before deciding to go with the interleaved way. It just happens that, on the 6502, 99% of the time it's easier/faster to handle interleaved data than linear data.

I'm not sure what sort of other techniques are used in other projects. I do speed a lot of things up by copying object coordinates and velocity values into ZP before handling those objects.

I do most of these calculations in place, unless I need both index registers, in which case I have to copy the data to temporary locations.

[frantik]

not sure if this is what you mean, but i created ways to make functions which dynamically allocate memory for their local variables on a stack

http://nesdev.com/bbs/viewtopic.php?t=5 ... =functions

it's more a proof of concept than anything i've used in a program though

[tepples]

Putting local variables on the stack means you can't easily use the X register, as you need to TSX to get your frame pointer.

[Celius]

Each object accesses its own bytes with indirect addressing through a single pointer variable that gets updated after each object is done being processed.

That's the reason why I don't use linear blocks of memory for my objects. Having to modify Y in order to access any byte would be a pain in the ass. I figured that having the object memory interleaved would be more efficient. Loads and stores are 1 cycle faster than in indirect addressing, and there's no need to modify an index register to access different object properties, you just use labels. Also, modifying only the index register to access different object slots is quicker than modifying a 16-bit pointer. I took all that into consideration before deciding to go with the interleaved way. It just happens that, on the 6502, 99% of the time it's easier/faster to handle interleaved data than linear data.

That's a really great idea! So if I'm understanding correctly, you'll have something like this in RAM:

Code: Select all

ObjectXL: .ds 8
ObjectXH: .ds 8
ObjectYL: .ds 8
ObjectYH: .ds 8
ObjectHealth: .ds 8
...

Then in your AI code, you'll have something like X loaded with the object number, so in your code you can do:

Code: Select all

ldx ObjectNumber
lda ObjectXL,x
sta Var
lda ObjectXH,x
sta Var2

instead of the slower:

Code: Select all

ldy #CoordXL
lda (pointer),y
sta Var
iny
lda (pointer),y
sta Var2

If I'm understanding that correctly, that is way more efficient than the way I'm doing it now. From what I see, going interleaved is almost always faster! I interleave a lot of my data, like tile definitions, but for some reason I never thought to interleave variables.

If only I'd thought about doing this earlier! I could save hundreds of bytes and cycles...

[frantik]

Putting local variables on the stack means you can't easily use the X register, as you need to TSX to get your frame pointer.

the code i created doesn't use "the" stack for variables, it uses "a" stack.. a separate one. you still have to use x or y to indirectly access the data though

[tokumaru]

Code: Select all

ObjectXL: .ds 8
ObjectXH: .ds 8
ObjectYL: .ds 8
ObjectYH: .ds 8
ObjectHealth: .ds 8
...

That's exactly it! Only I don't use such specific names in the declaration, I use "ObjectByte00", "ObjectByte01", etc., and near the object routines I use more significant names, like this:

Code: Select all

ObjectXLo = ObjectByte00
ObjectXHi = ObjectByte01
(...)

I do this because not all objects use the same bytes for the same purposes, although a lot of them do.

[Bregalad]

I do it exactly like Celius described. It works fairly well but it's still a pain in the *** to write AI code.

By the way it's possible to use the same variable for different uses in function of the object. For example a projectile can't have an health variable, so instead the damage amount the projectile does is stored here instead (for an example).

[MetalSlime]

I interleave my object data like Tokumaru, except that I give them specific labels from the start. The objects (enemies) in my current project don't vary much so I haven't needed to re-label fields for different uses.

I like declaring the object data in interleaved blocks because it's really easy to loop through all objects with field labels + the X register. I also like the convenience of being able to add and remove fields from my objects without messing up my object handling code too much.

For example a projectile can't have an health variable, so instead the damage amount the projectile does is stored here instead (for an example).

In another project I was working on I treated projectiles exactly the same as other enemies. Their health would get set to 1 and there was a separate field for damage, since regular enemies would damage the hero on collision too. The only real difference was how they were created in-game. Normal enemies were spawned by the level data, and projectile enemies were spawned by other enemies. Under the hood they were the same.

[Celius]

For example a projectile can't have an health variable, so instead the damage amount the projectile does is stored here instead (for an example).

In another project I was working on I treated projectiles exactly the same as other enemies. Their health would get set to 1 and there was a separate field for damage, since regular enemies would damage the hero on collision too. The only real difference was how they were created in-game. Normal enemies were spawned by the level data, and projectile enemies were spawned by other enemies. Under the hood they were the same.

I actually just ran into a dilemma with my project's set up where I was having enemies/objects handle their own projectile weapons with their own RAM. A couple problems concerned speed and space consumption, but another problem arose that I'd never even thought about. When an enemy was deactivated, it's projectiles were deactivated also. That's why I completely redesigned things and separated the two. Now, there are 8 available slots for intelligent objects, and 8 available slots for "spontaneous" objects. Spontaneous objects include projectile weapons and powerups. They don't need as much RAM as enemies and generally deactivate when the player touches them. Separating the two also made the weapon independent of the enemy that instantiated it, so it wouldn't disappear when you killed the enemy.