Object collisions - "grouping" / speed benefit
Moderator: Moderators
Re: Object collisions - "grouping" / speed benefit
Okay - I think my brain needs a bourbon break for a few days........
ME: Man! No matter what I do I can't seem to curb the slowdown problem. I didn't even have this much of an issue with Mystic Origins, and was a much more dense mess of spaghetti code! I've tried bit masking and lists and every other thing I can think of, and it should DEFINITELY be more efficient than this!
...(takes a closer look at my main loop)...
Inside of a loop through all objects, I was handling object collisions (the entire HandleObjectCollisions routine, iterating all over again for every active object). I had an outer loop that loops through all the objects and handles drawing and a few other things, and my collision routine was INSIDE that loop, which was in and of itself a loop through all of the objects for collision detection. I was literally running collision detection squared. I was cycling through ALL objects for EACH object.
Ha. No wonder!
ME: Man! No matter what I do I can't seem to curb the slowdown problem. I didn't even have this much of an issue with Mystic Origins, and was a much more dense mess of spaghetti code! I've tried bit masking and lists and every other thing I can think of, and it should DEFINITELY be more efficient than this!
...(takes a closer look at my main loop)...
Inside of a loop through all objects, I was handling object collisions (the entire HandleObjectCollisions routine, iterating all over again for every active object). I had an outer loop that loops through all the objects and handles drawing and a few other things, and my collision routine was INSIDE that loop, which was in and of itself a loop through all of the objects for collision detection. I was literally running collision detection squared. I was cycling through ALL objects for EACH object.
Ha. No wonder!
Re: Object collisions - "grouping" / speed benefit
Concerning linked lists: it's true that lda NextItem, x + tax is slower than just inx or dex, but if you have an array with gaps in it, when iterating it you have to spend some extra time checking whether each slot is occupied, while in a linked list there are no gaps to test for. For reasons like this, I think things balance out and there's hardly any overhead to linked lists, and obvious benefits for insertion and removal of elements, so I use them whenever I can when dealing with variable amounts of stuff.
I do have a linked list for empty object slots, so new objects can be loaded faster (no need to search for an empty slot, just put new objects in the beginning of the list), but active objects also belong in linked lists, this is how they're put into groups. I use grouping mostly to control the update order, but knowing that some groups never interact with others does prevent some unnecessary iterations. My objects still have a "collision response" field that specifies how they interact with others, the groups by themselves don't define that.
@JoeGtake2: Sounds like you didn't need any major refactoring after all!
I do have a linked list for empty object slots, so new objects can be loaded faster (no need to search for an empty slot, just put new objects in the beginning of the list), but active objects also belong in linked lists, this is how they're put into groups. I use grouping mostly to control the update order, but knowing that some groups never interact with others does prevent some unnecessary iterations. My objects still have a "collision response" field that specifies how they interact with others, the groups by themselves don't define that.
@JoeGtake2: Sounds like you didn't need any major refactoring after all!
-
- Posts: 1565
- Joined: Tue Feb 07, 2017 2:03 am
Re: Object collisions - "grouping" / speed benefit
if your are not concerned with order (and it seems neither of you are) - a collapsed array is simpler, faster and uses less RAM. there will be a point were copying the data stored in the "node" will take longer than the link list relink code and adding the link to the Free list, however. Then you need to factor in the number of additions/removals per run vs the extra cost of iterating.
It seems a Word is being stored in the list?
care needs to be taken when you remove while itterating, either you make a "death list" and delete from lower to upper. or you skip the dex if you delete <= current head, or do an inx to cancel out the eventual dex depending upon your code flow.
It seems a Word is being stored in the list?
Code: Select all
head .byte
Array .block
lo .fill 64 ; or however big you want it to be
hi .fill 64
.bend
init
lda #$ff
sta head ; array is empty
rts
addAY
inc head ; move to next slot
ldx head
sta Array.lo,x ; store data
tya
sta Array.hi,x
rts
removeX
ldy head ; get current head
lda Array.lo,y
sta Array.lo,x ; copy head over item we want to remove
lda Array.hi,y
sta Array.lo,x
dec head ; shrink array
rts
iterate
ldx head ; get head
bmi _empty ; is empty?
- do stuff ; x holds index into array
dex
bpl - ; until done
_empty
Re: Object collisions - "grouping" / speed benefit
We're talking about game objects here though, and most people reserve 16 to 32 bytes of RAM for each active object, and there's no way that moving that many bytes is gonna be faster than re-linking. As for RAM usage, it's usually not hard to dedicate one byte out of the many in each object slot to indicate what the next slot is (specially if the slot is empty!).Oziphantom wrote:if your are not concerned with order (and it seems neither of you are) - a collapsed array is simpler, faster and uses less RAM.
And there goes the simplicity.care needs to be taken when you remove while itterating, either you make a "death list" and delete from lower to upper. or you skip the dex if you delete <= current head, or do an inx to cancel out the eventual dex depending upon your code flow.
Re: Object collisions - "grouping" / speed benefit
When dealing with slots, I use heaps of free slots. I usually start with an array of slots where each index has the index as the value (i.e. 0, 1, 2, 3, 4, 5,...), and set the "top" of the heap to the last index. When I need a free slot, I pick up the number at the top of the heap and use such number as the index to the remaining arrays. When I need to destroy an object, I just copy its index to the top of the heap. Creating / destroying is direct as I don't need to search for empty slots, but of course iterating the arrays need to test if each object instance is active or not.
Re: Object collisions - "grouping" / speed benefit
And there goes the space advantage over singly linked lists!na_th_an wrote:I usually start with an array of slots where each index has the index as the value (i.e. 0, 1, 2, 3, 4, 5,...), and set the "top" of the heap to the last index. When I need a free slot, I pick up the number at the top of the heap and use such number as the index to the remaining arrays. When I need to destroy an object, I just copy its index to the top of the heap.
I'm not judging, everyone is encouraged to do what they feel works best for them, and the idea of managing a list of indices like you described is actually very interesting, although I personally wouldn't want the extra layer of indirection in this particular case, but calling linked lists "complex", "slow" or "wasteful" in this context is just crazy, they're anything but.
Re: Object collisions - "grouping" / speed benefit
I'll try linked lists in my next project, hadn't thought of them in this context and it feels so natural. Thanks for the hint!
Re: Object collisions - "grouping" / speed benefit
I always felt that the amount of active "objects" in an NES game is always so small that linked lists doesn't really serve a purpose. If I have a game with eg. a potential of 10 enemies on screen at the same time, it's extremely fast to iterate through all ten slots.
Is there any advantage to linked lists if the order of the objects doesn't matter?
Or maybe I should ask, why does the order of your objects matter?
Is there any advantage to linked lists if the order of the objects doesn't matter?
Or maybe I should ask, why does the order of your objects matter?
Re: Object collisions - "grouping" / speed benefit
The update order matters a lot when objects can affect the position or the appearance of other objects in any way. Moving platforms, for example. Anything on top of a moving platform has to move along with it, and one way to implement that is to displace the objects by the same distance that the platform moved, but in order to do that the platform has to be moved first, so its displacement it's known to the other objects.
As for the number of active objects in an NES game, it's true that the typical game doesn't have that many, but when you use 8-way scrolling, you should be prepared to deal with a larger number of objects. Ideally you'd avoid situations with many active objects, but you should still be prepared to deal with them depending on your game's design, even if there's slowdown. There are games with tons of projectiles and items, for example, and those can add up fast.
As for the number of active objects in an NES game, it's true that the typical game doesn't have that many, but when you use 8-way scrolling, you should be prepared to deal with a larger number of objects. Ideally you'd avoid situations with many active objects, but you should still be prepared to deal with them depending on your game's design, even if there's slowdown. There are games with tons of projectiles and items, for example, and those can add up fast.
Re: Object collisions - "grouping" / speed benefit
And one way to accomplish proper ordering is to put lifts and simple projectiles in separate object pools, which is what The Curse of Possum Hollow does.tokumaru wrote:Anything on top of a moving platform has to move along with it, and one way to implement that is to displace the objects by the same distance that the platform moved, but in order to do that the platform has to be moved first, so its displacement it's known to the other objects.
Re: Object collisions - "grouping" / speed benefit
Which I accomplish by having separate object groups.
Re: Object collisions - "grouping" / speed benefit
I'm with tepples on that one - for objects where the order matters based on grouping (as opposed to individual sorting), I think it makes perfect sense to treat moving platforms entirely as their own thing. Most likely they don't need more than a few bytes in RAM depending on how dynamic you want them to be, compared to the typical enemy character, etc, and I wouldn't want them to hog up the more "generic" object RAM. I'd treat bullets separately too, but it really depends on the individual game of course.
It's not that I'm opposed to linked lists in NES development, in fact I'm a big fan of them and would really like to employ them effectively, but using them makes more sense to me in something like C code for a PC where I can use the OS to assign memory for me, and I need a list that can be very dynamic in size. For everything I've made on the NES so far, I've always used striped tables, and tried to design my game around the space I've assigned for each type of object.
It's not that I'm opposed to linked lists in NES development, in fact I'm a big fan of them and would really like to employ them effectively, but using them makes more sense to me in something like C code for a PC where I can use the OS to assign memory for me, and I need a list that can be very dynamic in size. For everything I've made on the NES so far, I've always used striped tables, and tried to design my game around the space I've assigned for each type of object.
-
- Posts: 1565
- Joined: Tue Feb 07, 2017 2:03 am
Re: Object collisions - "grouping" / speed benefit
As per the original topic, of keeping "lists" of entities in groups for Collision purposes, I would say LLs holding the actual entity is bad as you, in the generic engine case, may need to put the entity into multiple lists. I.e a thing wants walls and player bullets. A thing want enemies and their bullets.
For a specific game with an engine customised for said game, hardcore your lists and your order
As per LL saving memory from an alloc list if one has
Alloc .fill 256
Data .fill 256
vs
Data .fill 256
Next .fill 256
it's the same RAM usage. One fills the alloc with 0-255, and you need a head variable. You pull the index at head, and inc head to alloc, then to restore you, dec head, store index.
Where the LL approach saves memory is you can put multiple lists into the one larger list memory allocation, i.e you have N heads.
My current trying to pull as much as I can and punch beyond its weight engine is using a lot of specialised DLLs and boy am I sick of debugging them XD they are trivial in C/C++ but making an optimised one in 6502 is pain.. My Kingdom for an extra register...
For a specific game with an engine customised for said game, hardcore your lists and your order
As per LL saving memory from an alloc list if one has
Alloc .fill 256
Data .fill 256
vs
Data .fill 256
Next .fill 256
it's the same RAM usage. One fills the alloc with 0-255, and you need a head variable. You pull the index at head, and inc head to alloc, then to restore you, dec head, store index.
Where the LL approach saves memory is you can put multiple lists into the one larger list memory allocation, i.e you have N heads.
My current trying to pull as much as I can and punch beyond its weight engine is using a lot of specialised DLLs and boy am I sick of debugging them XD they are trivial in C/C++ but making an optimised one in 6502 is pain.. My Kingdom for an extra register...
Re: Object collisions - "grouping" / speed benefit
Your kingdom, eh? Would you give up indexed addressing modes for extra registers that can be paired to hold a whole pointer? If so, welcome to Game Boy.Oziphantom wrote:My current trying to pull as much as I can and punch beyond its weight engine is using a lot of specialised DLLs and boy am I sick of debugging them XD they are trivial in C/C++ but making an optimised one in 6502 is pain.. My Kingdom for an extra register...
-
- Posts: 1565
- Joined: Tue Feb 07, 2017 2:03 am
Re: Object collisions - "grouping" / speed benefit
Well at this point I think just having the Z of the 65CE02/4510 would really help. Also for when doing swaps. At the moment for the 4K compo I'm limited to the 6510. However I plan the make the "enhanced" version for the 128. Which will allow me to run most of the code in 8500, but when it comes to doing things that could really do with extra registers, such as double links patching, swapping data and maybe even hunting for values in the sort, I can switch to a full Z80 giving me IX and IY and EXX