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

Object collisions - "grouping" / speed benefit

Post by JoeGtake2 »

Hey all. So in trying to twist NESmaker to allot for a bunch of different scenarios, we need to bend it to allow for lots of potential collision circumstances. For Mystic Searches, we just did the object compare...cycled each through the array, checking the next through the last, and then increasing the index and repeating until we were at the last monster. This worked ok for *that* engine, but as we progress to more and more possibilities, we start to get slow down pretty quick with not much on the screen.

So I'm considering making some classes, essentially...player class needs to check against all other classes, player projectiles/melee checks against 'lethal' objects (monsters). It seems it would reduce the calls significantly! But...since objects can sort of be invoked in any order, there would have to be either some level of sorting into proper class arrays, or when an object is created, storing it to available spot in class array and dumping it off the array when deactivated. I wonder how hefty that logic will be and how deep it goes before it begins to unravel the benefit. We have the added complication of having to be more malleable than most engines, of course.

Curious as to how some of you handled this and if anyone can attest to notable speed gains.

*EDIT*...actually seems like most of this could be handled with player objects array and monster objects array. And I'd never need to check monsters against anything, because the necessary checks would have already happened in checking player / player object collisions. Hm.
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 »

In my engine I created the concept of object groups. They're basically a set of (4 or 5, can't remember) linked lists. There's one variable for each group, pointing to the object slot that contains the first object of it's respective group, and then one byte in each object's RAM state is used to indicate the next object in the same group. A negative (>$80) value indicates the end of the list. When an object is activated, it adds itself to one of these groups.

The groups don't have hardcoded meanings, the game is free to distribute the different objects across the different groups as it sees fit. This affects the order in which objects are processed (e.g. objects in group 2 are guaranteed to be updated before those in group 3 - very useful for moving platforms, for example), and the functions that deal with objects (physics, collision detection, etc.) can iterate over an entire group, so you can do things like have the player go "test for collisions between me and all objects in group 3", knowing that group 3 is comprised entirely of enemy objects.

Another thing you can do is reserve a group for non-interactive stuff, like level ornaments or visual effects, so that nobody wastes time checking for collisions against those.

It can be a bit of a challenge to select the optimal way to distribute objects across the different groups, so that the update order allows for the necessary object interactions and the smallest number of iterations is done each frame.
User avatar
Kasumi
Posts: 1293
Joined: Wed Apr 02, 2008 2:09 pm

Re: Object collisions - "grouping" / speed benefit

Post by Kasumi »

All my objects have a type byte.

"Object is solid to other objects, object is grab-able, object can be stomped, is player projectile" etc. Those bits can be user defined.

An object that could grab things, but couldn't stomp things and didn't care about solidity could run through the list of objects like this:

Code: Select all

loop:
lda OBJtype,y
and #OBJECTGRABABLE
beq nextcollision
;Code that checks if the object is inside the other here, as well as how to handle it

nextcollision:
dey
bpl loop
To test multiple things, it'd look like this:

Code: Select all

lda OBJtype,y
and #OBJECTGRABBABLE+OBJECTSOLID+OBJECTSTOMPABLE
so it's not any slower.

If the player object didn't need to check collision with its own projectiles, it just wouldn't add the projectile type to the number after the and.

As well before the loop you can only check objects with a lower index, as objects that would have a higher index should have already checked lower index objects.

Code: Select all

txa;If our index is zero, we don't need to check other object
beq skipallcollision
tay
dey
loop:
lda OBJtype,y
;More of the code above.

skipallcollision:
To be malleable, all you need to do is let the user define 8 type of things (one for each bit) and then define which bits an object cares about for collision, which would change the and. (If it cares about nothing, don't loop at all.)

With just this method, I got 14 things actually collision checking each other without slowdown. (That is, object 14 needed to actually compare its position with 13 other objects, then object 13 needed to actually compare its position with 12 other objects etc.)
If some objects didn't need to check each other (the and discarded the needed for the position check), you could push more stuff.

Another simple optimization. Store the player character's index. If there's an object that only cares about the player, it's just ldy #playerindex, jsr collisioncheck. In theory you could have your player not check for collisions with anything and just have the monsters check the player. (Wouldn't work for a two player game, of course.)

Also, here's actual code of tokumaru's linked list thing: https://forums.nesdev.com/viewtopic.php ... st#p152230
And though it's linked in the post above, here is tokumaru's original post where I learned the method from: viewtopic.php?p=96731#p96731

14 things all colliding with each other is a lot of collisions in one frame, so I've never really thought about grouping in any other way. (The game in question has RAM reserved for 42 objects. Shrinking this number gets a few more collisions out of the frame, but eh.)

I might make a run and gun soon, and I'll see if I need to group differently for that. If so, I might make different groups of objects, each with its own linked list as tokumaru described above.
Last edited by Kasumi on Thu Apr 26, 2018 10:04 pm, edited 1 time in total.
Oziphantom
Posts: 1565
Joined: Tue Feb 07, 2017 2:03 am

Re: Object collisions - "grouping" / speed benefit

Post by Oziphantom »

The traditional method and name is "collision flags".
So given

Code: Select all

kCollisionFlags .block
    Player       = 1 << 0
    PlayerBullet = 1 << 1
    Enemy        = 1 << 2
    EnemyBullet  = 1 << 3
    Door         = 1 << 4
    Fire         = 1 << 5
.bend
Then you set the player Type to kCollisionFlags.Player and Collides with to kCollisionFlags.(Enemy,EnemyBullet,Door,Fire)
Then you set the enemy Type to kCollisionFlags.Enemy and Collides with to kCollisionFlags.(Player,PlayerBullet,Door)
Then when you come to do your "should I collide this with"

Code: Select all

lda A.Type
and B.Collides
beq _noCollision
...handle collision based upon flags here
A way to speed this up is, as tokumaru says, you can make a prebuilt lists, so you do less compares per frame. I would not store them as a Linked List although their ability to grow might be better for a generic system, as the over head of walking and keeping the list is higher than a array. Typically the order in which you do the collision is not important, if its is better to make different lists to force the order, or to collapse the array with a shift rather than copy last to hole method.

I also trust you are already caching collision results so you don't do things twice, or adjusting your starting indexes to be A vs [A+1.....A+n], A+1 vs [A+2....A+n] etc

ninja'd by Kasumi;)
User avatar
Kasumi
Posts: 1293
Joined: Wed Apr 02, 2008 2:09 pm

Re: Object collisions - "grouping" / speed benefit

Post by Kasumi »

Oziphantom wrote: I would not store them as a Linked List although their ability to grow might be better for a generic system, as the over head of walking and keeping the list is higher than a array.
From what I understand, tokumaru mixes the methods. (If not, it's what I do.) Use the linked list to avoid a seek while creating an object, but since all possible entries for the linked list are still an array, you can walk the array instead of the linked list any time you need to do a "seek" of the objects that are already there.

You only need to discard objects which don't exist, which can be done with the and is no slower than the array. (In fact, the code to do the two would be identical.) (Essentially just ensure a destroyed object has its type bits all cleared.)

Edit: Hmm. Walking the array is

Code: Select all

dey
bpl
Walking the linked list is

Code: Select all

lda OBJlist,y
tay
bpl
So four cycles slower. Not too bad as far as things go.
Oziphantom
Posts: 1565
Joined: Tue Feb 07, 2017 2:03 am

Re: Object collisions - "grouping" / speed benefit

Post by Oziphantom »

A linked list implies you have a link, so you have at min a value and nextObject right? Where as an array you just have the value.

Now you can put an linked list into an array, so you have 2 arrays, 1 values, 1 next. So to walk though the linked list you do to read value and get next

Code: Select all

txa
tay
lda Value,x
ldx next,y
right?
And then when you want to remove an object you then have to patch the Next, for the one before it, with the your next. So you need to walk through the list keep the previous index, until you find the one you want to remove, then patch up the prev/next. Unless you go double linked list, to which you now use 3 bytes per value, but it allows for faster insertions and removals. You could keep going until you reach the end, and then move the last node back into the node you just removed, and then patch the next for the 2nd last next to point to the new location. Then dec your allocator index to point to the next free slot. The benefit of this is you can just add a pool and have multiple lists in a pool and not have to fixed alloc any arrays, however adding and removing is expensive, if you don't care about having it in order you can still do a cheap walk thought the "values" array(if you only have one LL in the array).

vs An Array where you have an array of Values, and a byte that holds the "head"
so to add an item

Code: Select all

ldx head
inc Head
sta Array,x
to remove an item, where x is the item you want to remove

Code: Select all

ldy head
beq +
lda Array-1,y
sta Array,x
+
dec head
or if you need it to be "in order" you copy the loop items down. I would think that for the number of items you have on a a NES, ie. a handful, that doing a simple copy down loop would be faster than the search and re link of a linked list.
User avatar
Kasumi
Posts: 1293
Joined: Wed Apr 02, 2008 2:09 pm

Re: Object collisions - "grouping" / speed benefit

Post by Kasumi »

All I can say is read this post I linked: viewtopic.php?p=96731#p96731
You remove and add items in fixed time (unless creating the object is not possible), you can go iterate through the list by loading a single byte of RAM that holds the first index and then using the method I described in the last post.

I guess, put another way, you don't need next plus value because next is also the value. So if the current object's index is in y

Code: Select all

lda next,y
tay
Now the next object's index is in y. Which is only 4 cycles slower than just the dey needed for an array walk.

Edit: Maybe destruction/creation does get more complicated if you walk actively walk it, but then walking it would still be the above method. I admit I've only used it for destruction/creation. I don't walk the list.

Edit2: I guess I need to write code to test this. Design wise, my object's can only destroy themselves. (If an object wants to destroy another, it request that object destroy itself) Knowing this, I guess I'd just store the previous index in the list to temp RAM, and if an object needed to destroy itself it would use that and still be fixed time without the RAM hit of a "previous" list.
Oziphantom
Posts: 1565
Joined: Tue Feb 07, 2017 2:03 am

Re: Object collisions - "grouping" / speed benefit

Post by Oziphantom »

WAIT - so you are only using a linked list to hold the "free" list and not your data?
If your data is in a Linked List then you have to walk it to get your data right? And to destroy a thing you have to unlink it from somewhere in the list right?
User avatar
Kasumi
Posts: 1293
Joined: Wed Apr 02, 2008 2:09 pm

Re: Object collisions - "grouping" / speed benefit

Post by Kasumi »

You have to go through the object list in order regardless just to get the object data. (For the array, it's dey to get to the next object. For ... whatever this post describes, it's lda OBJnextline,x tay). What the list(s?) stores is an object index you can use to allocate an object OR access its data through.

Knowing you may need to relink, it's easy to store the previous index that was run. Before the object loop runs, set the previous index RAM to $FF. During the loop, store the current index before retrieving the index of the next object. (This is needed to easily relink for destruction, but not for collision, so it's done once per object per frame regardless of how many times you walk the list in other ways.)

OBJnext is the next free slot. OBJnextline is the next allocated object. The main loop looks like this:

Code: Select all

	lda #$FF
	sta <lastrun
	
	ldx <firstobject;If no objects have been created
	bmi nothing;We shouldn't do anything
spritestart:	
	;Run object
spriteend:
	stx <lastrun;Store previous index for easy relinking in case of destruction
	lda OBJnextline,x
	tax
	bpl spritestart
nothing:
To initialize the object list:

Code: Select all

initializeobjectlist:;{
	lda #$FF
	sta <firstobject
	sta <lastobject
	ldx #objectnum-1
	stx <OBJfreeslot
	ldy #objectnum-2
iol.loop:
	tya
	sta OBJnext,x;the next available slot is one index below the current to start
	
	jsr zeroobject
	
	lda #$FF;Unless otherwise stated, there are no objects following us
	sta OBJnextline,x
	
	dey
	dex
	bpl iol.loop
	
	rts;}
To create and destroy objects, you have to be aware of the first and last object created (they are special cases), but otherwise don't need to walk the list.

Code: Select all

createobject:;{
   ;JSR here with the high byte of the object's address in <reserved0 and the low byte of the object's address in <reserved1
   ;If the object creation was successful, it the negative bit will be clear
   ldx <OBJfreeslot;If there's not a free object
   bmi co.fail;We can't do anything
   
   lda <firstobject;If there are no objects in the list
   bpl nochangefirst
   stx <firstobject;We're the first
nochangefirst:
   
   lda OBJnext,x;Next free slot
   sta <OBJfreeslot
   
   ldy <lastobject;If there are no objects existing
   bmi nofixlast;We can't link a previously created object to ourselves
   txa;Otherwise, link our index
   sta OBJnextline,y
   
nofixlast:
   stx <lastobject;And claim our spot as the object more things need to link to
   
   lda #$FF;Nothing follows us
   sta OBJnextline,x
   
   lda <reserved1;Address to run our code
   sta OBJaddrlow,x
   
   lda <reserved0
   and #%01111111
   sta OBJaddrhigh,x
   
co.fail:
   
   rts;}
And to destroy an object:

Code: Select all

destroyobject:;{
;Destroy the object in X
	lda <OBJfreeslot;Freeing our slot
	sta OBJnext,x
	stx <OBJfreeslot
	
	ldy <lastrun;If this is positive, we're not first in the list
	bpl do.notfirst;
	;If here, we're the first object
	;But we're getting destroyed, so now the next object is the new first object
	ldy OBJnextline,x
	sty <firstobject
	cpx <lastobject
	bne do.return
	;If we're also the last object
	lda #$FF;And we're getting destroyed, so let's reset it
	sta <lastobject
	
do.return:
	rts
	
do.notfirst:
	lda OBJnextline,x;So we only need to relink the object ahead of use to the object behind us
	sta OBJnextline,y
	bpl do.nofix;If there's an object after us
	sty <lastobject;If we are, the object behind us becomes the last object
do.nofix:;We're not the object
	
	jsr zeroobject
	ldx <lastrun
	rts
The collision loop looks like this:

Code: Select all

object.collisionloop:
	ldy OBJnextline,x
	bmi object.skipcollision
object.collision.start:
;You'd do the and type here if you wanted.
	
	jsr generalspritecollision
	bcc object.nextcollision
	
	jsr destroyobject
	jmp spriteend

object.nextcollision:
	lda OBJnextline,y
	tay
	bpl object.collision.start
object.skipcollision:
One of the tricks of this is you can (probably) use OBJnext as a RAM for the object after its created. (Because the data one needs from it gets stored into OBJfreeslot on creation, and restored on destruction.) (I say probably because it was true, but I stopped it from being re-used when I hacked all this list walking stuff in.)

Edit 2: So as far as RAM usage, this (probably) just needs objectnum bytes of RAM for OBJnextline. Which is 1 byte per value rather than three. (If I understand how you're measuring.) The head trick you used for the array also works here, but only one byte copy is needed to do the equivalent of "copy down". (Granted, there's extra logic for the special cases, but a lot of things can probably be optimized. I threw this together.)

The above code IS tested, but not thoroughly tested, so I don't guarantee yet that there aren't fragmentation issues here! I wrote this because I was pretty sure the concept I was suggesting would work, but hadn't actually done it!

Another note: I definitely don't guarantee destroying the first object works properly, the thing I hacked this into makes it somewhat hard to test that without also removing the ability to test the rest of the collisions.

Final verdict: It is ever so slightly faster when you're not maxing out your available objects and have room for more objects than you will probably need. Whether that's worth objectnum bytes of RAM, I don't know. Edit: Maybe I'm not going to bed. If you use the linked list concept in the tokumaru post I linked for object creation and destruction, but then go through the array the normal way you don't need an extra objectnum bytes of RAM. Which... is what I was doing before I tried this. It's neat in that you can create and destroy things without needing to seek and it only costs a byte of RAM. (Because the RAM for the rest of the list can be used by an object once instantiated. That said, in the context of this topic, it's not really any faster unless LOTS of objects are being created in a single frame or something.)

If the concepts here aren't clear, let me know. Also let me know if it you find a logic error! I still recommend that if anyone reading wants to do something like that, they steal from this linked post: https://forums.nesdev.com/viewtopic.php ... st#p152230
Rather than this post. Edit3: As far as object creation without a seek, I truly believe the tokumaru approach is better (It's very similar to the head code for the array, and costs one byte of RAM when you're not trying to maintain a thing to walk through.) As far as if walking a linked list is better than the array approach, I'd have to think more about it, I dunno. This code gave me a decent amount of trouble. I'll probably continue doing what I did before I wrote this post: Linked list for object creation/destruction, walk the array for everything else until some project requires more.

I'm now going to bed. :? I hope I don't wake up and find 1,000 errors in this post >_>
JoeGtake2
Posts: 333
Joined: Tue Jul 01, 2014 4:02 pm

Re: Object collisions - "grouping" / speed benefit

Post by JoeGtake2 »

I had a the slot solution sort of conceptualized, but I wonder - how much time would it actually take to process these lists in a frame? If it's just a bit mask read to put an object into the correct list, and object number is always fairly small (sixteen or so), it seems that would be pretty quick. LDA Object_type,x AND #HARMFUL_TO_PLAYERS puts it in the next slot in "harmful" objects, AND #HARMFUL_TO_MONSTERS puts it into next slot in "weapon" objects. Could use a pair (or more, if you needed more 'types') of RAM variables to keep track of offset as it loops. Seems that would be super quick to sort out just prior to collision routine, no?

And then handle collisions accordingly?

Might even be able to alternate frames without noticing - handle harmful to player even, harmful to monster odd. Obviously it adds some time to every frame, but it seems pretty light, so long as you didn't have continue to reiterate through the list, and just did one pass to sort?

I think I'll try this and report back.
User avatar
Kasumi
Posts: 1293
Joined: Wed Apr 02, 2008 2:09 pm

Re: Object collisions - "grouping" / speed benefit

Post by Kasumi »

LDA Object_type,x AND #HARMFUL_TO_PLAYERS puts it in the next slot in "harmful" objects, AND #HARMFUL_TO_MONSTERS puts it into next slot in "weapon" objects. Could use a pair (or more, if you needed more 'types') of RAM variables to keep track of offset as it loops. Seems that would be super quick to sort out just prior to collision routine, no?
Do you mean sort before collision every frame? Because if you need to AND #HARMFUL_TO_MONSTERS to sort, you may as well just do the collision right then. I think you're misunderstanding. You don't do the bitmask to put it into a list, you do the bitmask to decide if a collision check between the objects is wanted. And if you don't mean sort before collision every frame, you can just add things to proper groups when they're created and still not sort.

Doing only some collisions every frame can be good.

You can also possibly make your collision routine itself faster: http://atariage.com/forums/topic/71120- ... try1054049
That looks a bit faster than what you're doing. You have to do some setup for it instead of the constants, but you're already doing some similar setup in the code that's there.

And you're counting up, not down which means a compare every loop.

Code: Select all

LDY #$00
;stuff
INY
CPY #TOTAL_MAX_OBJECTS
BNE DO_COLLISION_LOOP
vs

Code: Select all

LDY #TOTAL_MAX_OBJECTS-1
;stuff
dey
bpl DO_COLLISION_LOOP
Saves you a compare for every iteration.
JoeGtake2
Posts: 333
Joined: Tue Jul 01, 2014 4:02 pm

Re: Object collisions - "grouping" / speed benefit

Post by JoeGtake2 »

Good notes. I meant effectively creating tables every frame.

Rather than cycling through, seeing "yes, this should hurt monsters", and then evaluating every object to see if it's a monster, start by creating a table of weapons and a table of monsters, and then just comparing them against each other. This seems that it would be faster, but I'm not sure how much.

The other method is what I was working on yesterday - having arrays that fill with FF to designate an empty spot, and when an object is created, it finds an empty spot (otherwise, it can not be created) in a "monster object" table, or a "weapon object" table. When it's destroyed, its position in the monster object table reverts to FF. And then every frame, comparing the weapons and monsters against each other.

The former seems cleaner and easier, albeit slower. The question is, HOW much slower, and would it be passably so? That's sort of what I'm looking at.
User avatar
Kasumi
Posts: 1293
Joined: Wed Apr 02, 2008 2:09 pm

Re: Object collisions - "grouping" / speed benefit

Post by Kasumi »

As far as creating the tables every frame: You're going through object list an extra time.

Cycle through once to create the lists, cycle through again to run the object logic (and cycle through the list that was created to collide for each object)
Vs.
Cycle through once, (and cycle through again to collide for each object).

I don't think you'd win with the top method. You're loading, then storing the result of the and, only to load it and still branch later on the second go around. Vs. Loading and checking the result of the AND on the first go around, and not going through again.

The second thing (separate lists managed at creation) will likely beat both soundly.
JoeGtake2
Posts: 333
Joined: Tue Jul 01, 2014 4:02 pm

Re: Object collisions - "grouping" / speed benefit

Post by JoeGtake2 »

Yeah - I see the logic in what you're saying.

But I guess what I'm thinking is...rather than checking every object against every object (16*15, 15*14, 14*13...etc), instead I'd be doing a quick run through a single time to see where to put the objects, and then running them against each other (monObjectx*weaponObjectx), which would be significantly less than 16, for both, so the one time through to do the sorting into groups would be significantly less than going through, finding it does collide with monster objects, then looking at every object to see if it's a monster object, and if it is, then fire the collision routine. Now, I'd already have a list of monsters from that one pass.

But I do see how lists being populated on creation/destruction would be even more efficient still than that! Hm. Maybe I'll go back to that method.
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 »

At some level, the problem involves defining what are your hitboxes, what are your hurtboxes, and what is your terrain. A "hitbox" deals damage when it collides with a "hurtbox".

I'll give an example based on a game I've worked on a couple years ago. The Curse of Possum Hollow puts objects into several pools:
  • Player (1)
    Move routine is most complex. Hurtbox is body. Hitbox is outside body during attacks.
  • Party members (up to 2)
    The only thing saved is HP. No collision.
  • Enemies (up to 5)
    Move routine can be complex. Hitbox is body, checked against player hurtbox. Hurtbox is body, checked against player attack hitbox and player bullets.
  • Bullets (up to 12)
    Move routine is hardcoded. Hitbox is small, checked against player, enemy, or neither depending on bullet type. Each can be associated with a hardcoded CHR window or with the window of a particular enemy to disappear once the enemy disappears. Weapon hitboxes are represented as invisible bullets. Environmental effects (rain, leaves, splashes) are also bullets, but their collision is skipped.
  • Enemies ready to spawn (up to 8)
    Enemy waiting for there to be fewer than 5 enemies on the screen, an available CHR window, or the camera to proceed to a given point. These collide with nothing.
  • Terrain rectangles (no hardcoded limit)
    To save memory and make collision maps fine down to the 8x4-pixel level, Curse and its predecessor HH85 represent terrain as a list of horizontally sorted rectangles in ROM. But unlike the object-based levels in Super Mario Bros., Super Mario Bros. 3, and Super Mario World, the rectangles are never expanded into a sliding window bitmap. Instead, the collision routine checks them against the rectangles in ROM.
The following loops check collision:
  • Player against floor heightmap and terrain rectangle list: O(t)
  • Player attack hitbox against all enemies: O(n)
  • Enemy hitboxes against player: O(n)
  • Walking enemies against terrain rectangle list: O(t*n)
  • Player bullets against enemies O(b*n)
  • Enemy bullets against player: O(b)
  • Environmental bullets against floor heightmap: O(b)
Post Reply