Object collisions - "grouping" / speed benefit

Are you new to 6502, NES, or even programming in general? Post any of your questions here. Remember - the only dumb question is the question that remains unasked.

Moderator: Moderators

JoeGtake2
Posts: 333
Joined: Tue Jul 01, 2014 4:02 pm

Re: Object collisions - "grouping" / speed benefit

Post by JoeGtake2 »

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!
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Object collisions - "grouping" / speed benefit

Post by tokumaru »

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!
Oziphantom
Posts: 1565
Joined: Tue Feb 07, 2017 2:03 am

Re: Object collisions - "grouping" / speed benefit

Post by Oziphantom »

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?

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
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.
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Object collisions - "grouping" / speed benefit

Post by tokumaru »

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.
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!).
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.
And there goes the simplicity.
na_th_an
Posts: 558
Joined: Mon May 27, 2013 9:40 am

Re: Object collisions - "grouping" / speed benefit

Post by na_th_an »

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.
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Object collisions - "grouping" / speed benefit

Post by tokumaru »

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.
And there goes the space advantage over singly linked lists! :wink:

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.
na_th_an
Posts: 558
Joined: Mon May 27, 2013 9:40 am

Re: Object collisions - "grouping" / speed benefit

Post by na_th_an »

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!
User avatar
Sumez
Posts: 919
Joined: Thu Sep 15, 2016 6:29 am
Location: Denmark (PAL)

Re: Object collisions - "grouping" / speed benefit

Post by Sumez »

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?
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Object collisions - "grouping" / speed benefit

Post by tokumaru »

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.
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Object collisions - "grouping" / speed benefit

Post by tepples »

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.
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.
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Object collisions - "grouping" / speed benefit

Post by tokumaru »

Which I accomplish by having separate object groups.
User avatar
Sumez
Posts: 919
Joined: Thu Sep 15, 2016 6:29 am
Location: Denmark (PAL)

Re: Object collisions - "grouping" / speed benefit

Post by Sumez »

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.
Oziphantom
Posts: 1565
Joined: Tue Feb 07, 2017 2:03 am

Re: Object collisions - "grouping" / speed benefit

Post by Oziphantom »

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...
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Object collisions - "grouping" / speed benefit

Post by tepples »

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...
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
Posts: 1565
Joined: Tue Feb 07, 2017 2:03 am

Re: Object collisions - "grouping" / speed benefit

Post by Oziphantom »

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 ;)
Post Reply