This page is a mirror of Tepples' nesdev forum mirror (URL TBD).
Last updated on Oct-18-2019 Download

Organizing and processing objects.

Organizing and processing objects.
by on (#96540)
I have been thinking over more and more, without much actual coding, on how to handle cycling through objects, collision detection, sprite frames, etc.

I'm looking for discussion of ideas or solutions for these problems. My goal is a good balance of flexibility and speed.

So far I've figured I want to have a 'engine' that can cycle through objects and update everything. So the top level I am thinking about would be that: the code that updates each object. I have a lot of thoughts bouncing around, so maybe start there instead of typing a really long post. What kind of data structure should the object have? I'm thinking about handling everything a player interacts with as an object (platforms and doors too) and I'm imagining a platform/action type of game.

So far I want my object to potentially have (in RAM):

-object number
-object type
-X,Y (screen? world? I guess it doesn't matter)
-deltax,deltay
-pointer to metasprite
-current frame (metasprite)
-direction (metasprite flipping)
-status (attacking, defending, resting, hit points, whatever.. extra data as needed for object type)
-incoming event (set by another function doing something to this object)
-pointers to various function for this object number on events. ( I guess this could be a separate jump table in ROM)

Is something like this normal/good coding?
Issues:
How to allocate and track RAM on creation/destruction of an object?
I think I would like to sort by at least one coordinate for better collision detection, any suggestion how to have a sorted list index the object?

Thanks

Edit: Made this test program last week.. can't get much further yet.. : http://wikisend.com/download/164710/ball.nes
Re: Organizing and processing objects.
by on (#96544)
Movax12 wrote:
-status (attacking, defending, resting, hit points, whatever.. extra data as needed for object type)
-pointers to various function for this object number on events. ( I guess this could be a separate jump table in ROM)

Instead of using codes for status and jump tables (or God forbids, long chains of IFs), I prefer to store the PC of the object's AI, so that it can resume from where it stopped last frame.

That way, to call an object I copy its PC to the stack and RTS. If the state doesn't change, the PC doesn't change (i.e. the same code will be called again), but when it jumps to another state there's a routine they JSR to that saves their PC to their RAM. Something like this:

Code:
CallObject: ;index of object in X
   lda ObjectPCHi, x
   pha
   lda ObjectPCLo, x
   pha
   rts

SaveObject: ;index of object in X
   pla
   sta ObjectPCLo, x
   pla
   sta ObjectPCHi, x
   rts


Quote:
How to allocate and track RAM on creation/destruction of an object?

I have a linked list of free object slots. Since the slots are free, I can use any byte to indicate the next free slot (a negative index indicates that there are no more free slots). A separate variable indicates the first free slot (if this is negative, there are no free slots at all). To allocate/deallocate memory for objects I just remove/add entries at/to the beginning of the linked list. The GetObjectSlot routine returnes the index of the first free slot, and makes the second free slot the new first. The ReturnObjectSlot routine makes the current slot the first free one and makes it point to the old one as the new second.

All my object memory is a series of arrays, which I access using the X register. That way, routines that manipulate the objects using the base addresses of the arrays and the index of the object in X. For example, ldx #$04; dec ObjectHealth, x; would decrase the health of the object in the 5th slot.

The disadvantage is that you don't have any permanent linear memory for the objects, so if you need to use pointers and such (anything requiring consecutive bytes, really) you have to copy them to some scratchpad RAM first.

Quote:
I think I would like to sort by at least one coordinate for better collision detection, any suggestion how to have a sorted list index the object?

Personally I don't bother with sorting, I just try to minimize the number of collision checks. Most objects don't have to collide with each other, and some don't even collide with anything, so most of the time I just make the objects check for collisions with the player and that's it.

If you need objects of different types to collide, you should have a linked list for each type. For example, bullets would have in their AI a loop that only checks for collisions against objects in a list of objects that can be hit by bullets.
Re: Organizing and processing objects.
by on (#96547)
subroutine wrote:
Instead of using codes for status and jump tables (or God forbids, long chains of IFs), I prefer to store the PC of the object's AI, so that it can resume from where it stopped last frame.


I am not sure if understand exactly how you are using that technique. Rather than checking the state and jumping to a subroutine, you just have an address saved that you jump to. I like that, but how to you decide when to change the saved address? Wouldn't it result in the same problem of looking up an address of the appropriate code? Or are you talking about a yield and continue type idea? (I think that is beyond my ability at this point.)


Quote:
How to allocate and track RAM on creation/destruction of an object?

Quote:
I have a linked list of free object slots.

I haven't done linked lists in asm, but seems easy enough and an appropriate use of linked lists. This seems to require an object data structure of fixed length to avoid fragmentation, but a variable size seems overly complicated to track.

Quote:

The disadvantage is that you don't have any permanent linear memory for the objects, so if you need to use pointers and such (anything requiring consecutive bytes, really) you have to copy them to some scratchpad RAM first.


I think you are saying this is a way around the fixed size of object data?

Quote:
Personally I don't bother with sorting, I just try to minimize the number of collision checks. Most objects don't have to collide with each other, and some don't even collide with anything, so most of the time I just make the objects check for collisions with the player and that's it.

If you need objects of different types to collide, you should have a linked list for each type. For example, bullets would have in their AI a loop that only checks for collisions against objects in a list of objects that can be hit by bullets.


Good point... Still thinking about this.

EDIT:

I think I understand your PC saving idea a bit better: There is -no- need to save a list of addresses if your current object code can handle the possible changes in status and decide how to jmp to the new subroutine - which sets itself up as the new default subroutine if it should persist for more than one frame. Correct?
Re: Organizing and processing objects.
by on (#96549)
Movax12 wrote:
Or are you talking about a yield and continue type idea? (I think that is beyond my ability at this point.)

Yeah, something like that. But it's probably not as complicated as you think it is.

Quote:
I think I understand your PC saving idea a bit better: There is need to save a list of addresses if your current object code can handle the possible changes in status and decide how to jmp to the new subroutine - which sets itself up as the new default subroutine if it should persist for more than one frame. Correct?

There's only one list, with pointers to the "reset" address of each object. This is called when objects are first loaded, so they can initialize themselves. After that, objects enter their first state, and you can freely move between states with JMPs. Each object would look something like this:

Code:
Object01:

   ;INITIALIZE THE OBJECT HERE

Object01State0:

   ;HANDLE STATE 0 HERE (can JMP to other states if necessary)

   jsr SaveObjectStateAndReturn ;start from here next time
   jmp Object01State0 ;loop

Object01State1:

   ;HANDLE STATE 1 HERE (can JMP to other states if necessary)

   jsr SaveObjectStateAndReturn ;start from here next time
   jmp Object01State1 ;loop

Object01State2:

   ;HANDLE STATE 2 HERE (can JMP to other states if necessary)

   jsr SaveObjectStateAndReturn ;start from here next time
   jmp Object01State2 ;loop

There's nothing wrong with jump tables though, so if you feel more comfortable with them maybe you should go that way.

Quote:
I haven't done linked lists in asm, but seems easy enough and an appropriate use of linked lists.

They sure make the process of getting and freeing object slots very fast, as there's no need to scan the list looking for free slots.

Quote:
This seems to require an object data structure of fixed length to avoid fragmentation, but a variable size seems overly complicated to track.

True. If you need more memory than a single object slot provides, you can just request another slot and reference it in the first, while using a bogus AI pointer on the second one so that it doesn't do anything when called.

Quote:
I think you are saying this is a way around the fixed size of object data?

The object data remain the same, but while the AI is running it should have a slice of RAM for temporary calculations. I do have some extra RAM for objects which I use to preserve their state when they are unloaded and reloaded again, and there's a pointer to this memory in the object slot when it's active. That kind of circumvents the fixed size of object memory.

by on (#96550)
Thanks for your input.

I have one other question:

Quote:
All my object memory is a series of arrays, which I access using the X register. That way, routines that manipulate the objects using the base addresses of the arrays and the index of the object in X. For example, ldx #$04; dec ObjectHealth, x; would decrase the health of the object in the 5th slot.


I guess this is more a matter of preference, but you are saying your setup your data structures with all the ObjectHealth slots together linearly, rather than all the elements of an object together, then the next object? I suppose it makes for easier coding and I hadn't thought of doing it that way.

by on (#96552)
Movax12 wrote:
I guess this is more a matter of preference, but you are saying your setup your data structures with all the ObjectHealth slots together linearly, rather than all the elements of an object together, then the next object? I suppose it makes for easier coding and I hadn't thought of doing it that way.

Exactly. I prefer to do it like this because you can quickly switch from an object to the next by changing the X register, which is the index of the object slot. If X is 0, you access the object in the first slot, if it's 1, you access the second slot, and so on. If the memory of each object was linear, you'd probably have to use pointers and the ($XX), Y addressing mode to access everything, which would be slow and not as versatile.

The 6502 favors access to structures of arrays rather than arrays of structures, so in many cases it makes sense to store data interleaved like that.

by on (#96554)
If you don't have too many objects and they don't have many variables, you can have linear layout using lda $nnnn,x addressing. Say, you can have 16 objects max, each uses 16 bytes, or 32 objects, 8 bytes each - 256 bytes total. You can use $PP0n offsets to access individual variables of an object (PP is page for the list, n is offset in the object), and X contains object number*size of object.

by on (#96556)
Yeah, if the total memory for objects doesn't exceed 256 bytes, you can do like Shiru said and not give up the benefits of linear memory. 256 bytes is too little for me though (I suppose I could dedicate more than 1 page of memory for this so that each object would have 2 blocks of consecutive bytes that are not consecutive themselves, but this would be kinda confusing...), so I'd rather do it the other way.

by on (#96559)
I was actually thinking of making the objects powers of two - so an object has to use 2,4,8,16, or 32 bytes. Then you could lda an object number, asl a a few times and add to that to the base address, then index it with x.

I think I really like the interleaved method though, it works well with the 6502.

by on (#96563)
Objects occupying different amounts of memory would be too much trouble IMO... Think about it, the memory area dedicated to holding objects would get fragmented really fast, and finding room for the larger objects would get harder and harder, unless you constantly reordered the used memory to keep the unused bytes together, which would be a fairly slow procedure during gameplay.

Object handling is one of the slowest things in games. Just watch how famous games like SMB3, Kirby and Mega Man start lagging terribly when a slightly larger number of enemies are active. You really should do things as optimally as you can in this area, if you expect to have a lot of action going on in your game.

I've come to a few conclusions about processing objects over the last few years. One of them is that I would only loop through the list of objects once, because doing this is slow. This meant that objects would run their AI and draw themselves in one go (scanning the list once for processing and again for drawing would be slow). One consequence of that is that the player object must be processed first, because he dictates how the camera moves, and all objects must know the position of the camera in order to draw themselves.

And this poses another problem, because if the player is processed first and the camera coordinate is decided, what happens if later during object processing some obstacle pushes the player back? This would mean that the data we calculated before (the camera's position, for example) would be wrong, and that some objects were drawn using that wrong data.

My solution was actually to always keep the processing one step ahead of the drawing. Every frame, objects will first draw themselves, using information that is known to be valid (because all objects have been processed last frame, so even if they modified each other somehow by now they would be at their final positions and states), and then they run the AI. Hopefully 1 frame of lag won't be noticeable since there are 60 of them in a second.

Using these rules, I can guarantee that objects are only processed once per frame, meaning that I'm not wasting valuable processing time.

by on (#96564)
I only meant I would have pick one of those - for all objects.. 8 bytes, maybe 16.. so I could use shifts to quickly calculate the address. Variable sizes isn't going to happen. I'm going to go with interleaved and indexed with x anyway.
Re: Organizing and processing objects.
by on (#96571)
tokumaru wrote:
That way, to call an object I copy its PC to the stack and RTS. If the state doesn't change, the PC doesn't change (i.e. the same code will be called again), but when it jumps to another state there's a routine they JSR to that saves their PC to their RAM. Something like this:

Nice idea. Have to consider implementing this when I start needing objects with multiple states.

by on (#96577)
It's funny because in the game I am developing I do it exactly as Tokumaru describes.
That way every object is like a thread, which is created and destroyed, and when active is called once per frame.

I was under the impression that I had a super original idea but maybe it was not the case :lol:

Personally I find it much more intuitive to program "AI" in a linear way, like if it was a program in ifself, than dealing with a finite-state-machine and long chain of ifs.

Otherwise I do it pretty much like you descibed. I have object type, X, Y, current frame and direction variables. The "status", "incoming event" variables are not needed because of what Tokumaru said.

Collision detection is done by the object's AI itself, that is an object that is suppoed to interact with others objects is supposed to have it's AI calling the routine. There is a much standard procedure though.

This is a total pain to code in assembly by the way.

I do not sort the objects for collision detection, this is not necessary. However I sort them to display their sprites, so that the topmost objects are drawn last and looks "behind" the bottom most objects. I use a bubble sort to achieve this.

In my engine I have a limitation that every object is associated with a single meta-sprite. This works well but some times it is limiting, I can't for example have a large boss with two metasprites without having two distinct objects (and in fact I plan to have bosses which are like this).

The metasprites associated with every frame and direction for all objects of the game are hard-coded in a huge table. Not the most flexible solution, I know, a metasprite pointer like you said would be more flexible, BUT every object would have to manually update it's own pointer every frame, while my engine does everything automatically becasue it's hard-wired.

by on (#96724)
Rather than linked lists, wouldn't it be easier/faster to use a few bytes and use one bit per object to indicate if it is available or not. Maybe not faster to find the first free object, but much easier to remove one from the list. You could use 8 bytes to indicate which OAM slot is free as well. Is this too many branches/loops to find the next free?

by on (#96725)
I personally use lists with a 'free' flag. It is not too slow to find first free object, actually - because it is the last one that was removed from the list. It could be slow to find a free object if there were no objects removed since last object addition, though.

by on (#96731)
Movax12 wrote:
Maybe not faster to find the first free object, but much easier to remove one from the list.

I'm not sure you realize how quick it is to manipulate the linked list. For example, this is what you'd do to retrieve the index of a free object slot and remove it from the linked list:

Code:
   ldx FirstFreeSlot ;get the index of the first free slot
   lda NextFreeSlot, x ;get the index of the second free slot
   sta FirstFreeSlot ;make the second free slot the first one

See? Now X holds the index of the slot that the new object can use. Maybe this is even faster than manipulating bits that indicate what's free and what's not, because accessing individual bits in a byte isn't so trivial.

Later, when the object is done, the reverse operations will free the slot and put it back at the start of the linked list:

Code:
   lda FirstFreeSlot ;get the index of the first free slot
   sta NextFreeSlot, x ;save it as the second free slot
   stx FirstFreeSlot ;make the current slot the first free one

BTW, "NextFreeSlot" is just an alias for one of the attributes of the objects. Since the slot is free, the bytes that would otherwise be used for holding the state of the object (health, meta sprite pointer, whatever) are free to be used by the linked list.

Quote:
You could use 8 bytes to indicate which OAM slot is free as well. Is this too many branches/loops to find the next free?

IMO, yes. I avoid "searching" as much as I can in my programs. As for the OAM in particular, there are several good cycling algorithms that don't require slots to be marked as used/free. 64 may not sound like much, but a loop with that many iterations will surely make a difference in CPU usage, so actually filling the slots already takes a significant amount of time, you really don't want to add in the time necessary to manipulate bits with slow masking operations.

by on (#96753)
That's pretty good. I guess that's better than playing with bits.

You would simply have to initialize each NextFreeSlot at the beginning of a game/level which I suppose is trivial.

by on (#96754)
Movax12 wrote:
You would simply have to initialize each NextFreeSlot at the beginning of a game/level which I suppose is trivial.

Exactly. You'd make NextFreeSlot point to slot 0 and then loop through all the slots writing increasing indexes starting from 1 to their NextFreeSlot variables. I use a negative number to indicate the end of the list (since I don't plan on having more than 128 slots!). Like you pointed out, the initialization of the list is only necessary once at the beginning of the level.

by on (#96772)
I set the object AI routine address to $0000 for inactive object slots.

I also have this huge-ass subroutine that I call "physics," and what it does is, apply gravity and calculate BG collision with objects automatically. For if you have a "koopa" ememy, all you have to do is move his x coordinate a pixel to the left, then "jsr physics," and he will fall off a platform when he reaches a ledge, and will stop when he runs into a wall.