Collision Examples

[Guilty]

I don't know if this is the best place to put this, but I'm looking for examples on how to handle collision, and maybe we can start a broader discussion on different techniques in general as well as the way they can be set up on the NES. I've seen a few threads on this forum discussing collision before but most of them have handled the issue of sprites interacting with static background elements, not many people seem to talk about sprites interacting with sprites.

Of course, when I talk about sprites I'm referring to the object that's represented by a sprite; an entity that is not affixed to the nametable grid. Mario and the Goombas, not the Question Blocks or Pipes.

So... What are some opinions on collision?

I started programming with MUGEN, so I'm used to thinking of collision in terms of red and blue hitboxes, aggressive rectangles that trigger code when they overlap with inert rectangles and the inert rectangles themselves. In most fighting games I've picked at, objects are all handled first, then collision is done afterwards. That is to say, the player's and every enemy's movements/state changes are calculated and applied before any collision is done at all. An object logic loop before the hitbox logic loop. I find this to be an ideal way of doing things, since processing any object's collision before all other objects are handled might lead to a single frame of latency (bullet moves into corner, finds no victim, player moves into corner, finds no wall, end tick. next frame, bullet moves again and finds the player that it should have collided with last frame).

However I can't find a generalized way of doing this without using a ton of memory for each collision box. Every hitbox would need many bytes in ram: x, y, width, height, the ram offset to find the object that created this hitbox, whether its a 'hit' box or a 'hurt' box, and the low/high bytes of the address to run code from when it interacts. Even if you compress width and height into a single byte, you're still looking at about six bytes per hitbox; which is an issue for bullet hells and similar collision-heavy genres. You would need about two pages of ram for hitboxes for a single page of simple objects.

What, when you go about your platformers/beat-em-ups/shmups/grid-movers/thwaites, do you do for collision? How do you stuff it into your RAM?
And have you looked into the collision systems for other games? How does Ninja Gaiden/Mega Man/Gimmick/Battletoads/Other handle their invisible object interaction detection?

[Kasumi]

Simply put: It doesn't have to be RAM.

Say I create four bytes in ROM. X offset, Y offset, Width, Height. I can load and pass those to a function.
Say I create an array for all four. If I want any hitbox's information, I can do

Code: Select all

ldy hitboxnum
lda xoffset,y
sta temp1
lda yoffset,y
sta temp2
lda width,y
sta temp3
lda height,y
sta temp4
jsr checkbox

Now say I create 4 more bytes. The first is a byte with the value of 3. The number of hitboxes in the structure. Each following byte is a hitboxnum referring to the first four arrays (xoffset, yoffset etc).
I can now pass the address of those four bytes (And an address to a similar structure), and check all hitboxes for one against all hitboxes from the other using practically no RAM.

It's very similar to a lot of the other things you'd do on NES. Like... the levels aren't usually the tile numbers. They're structures that refer to smaller structures that refer to tile numbers. You can go a lot of layers deep, or not. Depends on what you need. This also allows you to reuse stuff. Like... same hitbox across frames or enemies or whatever.

One of my games just has a hitbox (character's extent where they can get hurt) per object. Just Width, Height, since there's no offset from position. As needed, objects can also create boxes to check, because the function that checks the positions doesn't care where the numbers came from. (Like storing to the temps above) So one of my characters creates a box for his grab range ahead of his body. (And this is compatible with the latency issue you describe, you just go through the object list more than once and check if two things tried to grab each other in the same frame which my game does do.)

You could dedicate a box for where you can be hurt, and a box for your attack, and that's not even a lot of memory per object. For things like platformers, it's not as important to have a million boxes like fighting games need. I'm working on a game right now where I'm using one per attack, and it's fine.

But if you DO want a fighting game like system, just create references to references as described above. Have two bytes for the address of the current frame's hitbox structure for all objects, and then your collision routine can resolve collisions afterwards.

As far as what happens when the boxes touch... your collision checker doesn't need to handle that. In my games, objects can only really talk to each other through some specified bits. So... say in my example above that's checking a million boxes, Object Y got hit with Object X's attacks. The function would set Object Y's "You got hit" bit, it would set a bit that tells the direction it got hit in, and maybe some properties about what it got hit with (fire, normal, electric). It would also tell Object X "You hit something". And then when Object Y is next run, it would read that it got hit and do the stuff that happens when it gets hit. And when Object X is next run, it would know it hit something. (For things like cancel on hit.)

You can read more about that system here: viewtopic.php?p=151952#p151952 (ctrl+F "Stuff like:" for the relative bits, but you might find the whole topic interesting.) Stomping is one way my game lets objects "talk" to each other through collision. It checks their boxes, it sets "You got stomped", and "You're bouncing.", but it's up to individual object code to decide how to handle the information that is passed. An object could be destroyed on stomp, or just be sent downward and the thing that stomped it doesn't care either way.

Not having objects touch each other's RAM/update each other is a stable way to do things. Functions can request that an object does something, but it doesn't have to honor it. I've found it to be very stable.

I have no idea how commercial games do this stuff, but I'd probably just have two bytes that point to a hitbox structure for every object if I needed like... five per frame. But... I'd also seriously consider if I really needed five per frame.

[tokumaru]

So... What are some opinions on collision?

Detecting collisions between 2 objects is a fairly simple process, mainly because both entities use the same positioning system, so no coordinate conversions are necessary (as is the case with background collisions). One way to do it is to compare the edges of an object against the edges of another, looking for the cases that make a collision impossible:

• Object0Right < Object1Left
• Object0Left > Object1Right
• Object0Bottom < Object1Top
• Object0Top > Object1Bottom

A collision only happens if all of these are false.

Another approach (which might be faster and use less memory depending on how you implement it) is to calculate the distance between the objects' hotspots and test whether it's smaller than both radiuses added together, on each axis: (the following assumes that the hotspot is at the center of the objects, but if that's not the case in your game you can simply have more than 1 "radius" per object and select the appropriate one for each test)

• ABS(Object0X - Object1X) > (Object0Radius + Object1Radius)
• ABS(Object0Y - Object1Y) > (Object0Radius + Object1Radius)

If both of these are false, you have a collision.

That is to say, the player's and every enemy's movements/state changes are calculated and applied before any collision is done at all. An object logic loop before the hitbox logic loop. I find this to be an ideal way of doing things, since processing any object's collision before all other objects are handled might lead to a single frame of latency (bullet moves into corner, finds no victim, player moves into corner, finds no wall, end tick. next frame, bullet moves again and finds the player that it should have collided with last frame).

Indeed, but an 8-bit CPU running at 1.79MHz might have trouble visiting object routines multiple times per frame.

However I can't find a generalized way of doing this without using a ton of memory for each collision box. Every hitbox would need many bytes in ram: x, y, width, height, the ram offset to find the object that created this hitbox, whether its a 'hit' box or a 'hurt' box, and the low/high bytes of the address to run code from when it interacts. Even if you compress width and height into a single byte, you're still looking at about six bytes per hitbox; which is an issue for bullet hells and similar collision-heavy genres. You would need about two pages of ram for hitboxes for a single page of simple objects.

That's if you treat the hitboxes as separate entities, but if you treat them as part of the object, things aren't nearly as bad. In my game, the hitbox is defined as a single byte in each object's RAM slot. This byte is used as an index into a table that contains 4 byte values, which represent the distances from the center of the object to the 4 sides of the box. This allows me to call a subroutine, passing the index of one object slot in the X register and the other in the Y register, that will calculate the distance between the objects and will then use both hitbox indices to subtract the appropriate sides from this distance (i.e. the second method I mentioned above). All I need is 1 byte of RAM per object, plus the temporary space for calculations.

Anyway, I consider this to be the simple part... handling the collision responses is the part that worries me! Specially considering we don't always have the CPU power to do things "the proper way", iterating over all objects multiple times to guarantee that all states are consistent and there are no delayed reactions.

[Kasumi]

This is a fast, fast way to check collisions (and it is easily extendable to 16bit, as well as to objects that aren't fixed width): http://atariage.com/forums/topic/71120- ... try1054049

[tokumaru]

http://atariage.com/forums/topic/71120- ... try1054049

I really like how it automatically handles the relative positioning of the objects (it doesn't matter which object is on the left/top and which is on the right/bottom)! I'm currently testing each case separately, depending on whether the distance between the objects is positive or negative.

[pubby]

This is a fast, fast way to check collisions (and it is easily extendable to 16bit, as well as to objects that aren't fixed width): http://atariage.com/forums/topic/71120- ... try1054049

This is really cool.

I'm guessing that many games with 16 bit coordinates use their 8 bit screen coordinates for doing collision checks instead their 16 bit absolute coordinates. I'm sure you know this; I'm just thinking out loud.

[Guilty]

Now this is the kind of thread I was hoping to start.

This is a fast, fast way to check collisions (and it is easily extendable to 16bit, as well as to objects that aren't fixed width): http://atariage.com/forums/topic/71120- ... try1054049

That method is radically different from the traditional four checks for box sides. That's awesome. Obviously, that method only works for one dimensional checks though so you'd need to run it twice and make sure that carry is set both times for a two dimensional check of x and y positioning.

@Kasumi: Correct me if I'm wrong, but simply loading the values of xoffset, yoffset, width and height are more or less meaningless on their own, and they'd all need to be applied to the object's coordinates for the checking to matter. To that effect, you'd need to reference the x and y coordinates of each object as they're checked. So in the simplest case, each hitbox in ram would need a byte to look up the hitbox's dimensions from, a byte to reference the ram offset of the object this box belongs to, and optionally a byte to signify whether the hitbox is 'red' or 'blue' (single bit, anyways, so this could be jammed into the hitbox lookup byte).

Again, all of that assumes you're doing a hitbox checking loop after the object handling loop, and not all at once. If you wanted to handle collisions within the object logic you'd need less information... probably.

While I recognize and respect your 'mailbox' bytes for each object, I'm not convinced that's the best way to do things. For instance, say you're recreating the dragon boss at the end of Wily Stage 1 in Megaman 2. (I don't actually remember if the boss works as I'm about to describe, so if it doesn't then we're talking about the green secret miniboss in Sting Chameleon's stage in Megaman X; same principle) The boss needs to respond to bullets in two different ways; if the megalemons hit his belly, they should just bounce away, but if they land on his face, it should do damage. If the dragon has only an inbox byte that tells him he got hit, he'd have no idea whether the bullet landed on his weakspot or no. You might decide from there to make his face a separate object from the rest of his body so that they have different inboxes, but now you need to coordinate the two to make sure they both maintain similar coordinates and the like.

I think a better solution might be to have the bullet run code when it hits something. To that effect, an agressive ('red') hitbox would need a byte in ram to lookup what code to jsr to upon overlap with inert ('blue') hitboxes. This way, whenever a bullet overlaps a hurtbox, it would do a glorified switch statement to identify which type of enemy it just hit, and then depending on that result it would either jsr to the 'tell the victim its been hurt' routine or set its own variables to say 'bounce away' or however else the bullets may respond. When the bullets see that they've hit the dragon, they can do whatever comparisons they need to see if its a hit or no. That check would be pretty simple too; you could just test the distance between the bullet's y coordinate and the dragon's y coordinate to see if it was high enough to hit the face.

Even better, the hitbox lookup tables can have an additional 'attributes' byte in rom that includes flags such as 'invulnerable', which the bullet could then check and decide whether to bounce.

That is to say, the player's and every enemy's movements/state changes are calculated and applied before any collision is done at all. An object logic loop before the hitbox logic loop. I find this to be an ideal way of doing things, since processing any object's collision before all other objects are handled might lead to a single frame of latency (bullet moves into corner, finds no victim, player moves into corner, finds no wall, end tick. next frame, bullet moves again and finds the player that it should have collided with last frame).

Indeed, but an 8-bit CPU running at 1.79MHz might have trouble visiting object routines multiple times per frame.

Such is the woeful discrepancy between the ideal way of handling code and the reality... I haven't done any stress tests or anything, but I feel like running the object logic and hitbox logic separately wouldn't be too stressful as long as hitbox reactions are kept brief. Going back to the Megaman example, handling all the objects would involve moving the bullet to its new location and moving all enemies to their new locations (plus AI routines, etc). That, I hope, would be the bulk of the processing time right there. Then when collision is handled, any overlaps would trigger the bare minimum code needed to update the graphics and get the objects set up to execute their overlapped code on the next frame. In this example, after the objects are handled, a bullet colliding with an enemy would merely update the enemy's current metasprite (visual feedback on this frame) and set his state variable to make sure he does his appropriate 'ouch' motions starting next logic tick. That way there's no perceived frame of latency, even if the baddie's 'ouch' routine hasn't been run at all yet.

I should disclaimer all of this though with my usual message: never finished a NES game before, my ideas are suggestions not solutions, newbies don't take this post for gospel.

[Kasumi]

So in the simplest case, each hitbox in ram would need a byte to look up the hitbox's dimensions from, a byte to reference the ram offset of the object this box belongs to, and optionally a byte to signify whether the hitbox is 'red' or 'blue' (single bit, anyways, so this could be jammed into the hitbox lookup byte).

So what? Say each hitbox needed 40 bytes. I think you're missing that RAM used for hitboxes doesn't need to be persistent. You only ever need to check two hitboxes against each other at a time. So if I have 80 bytes reserved for hitboxes, I can have thousands of hitboxes checking each other in a frame, and it will never use more RAM than 80 bytes. (It would, of course, be CPU intensive, but this is an extreme example.)

So yeah... you need the X pos of the object because you need to add the offset to that, but once you add the offset you no longer need the offset in RAM, just the resulting position. So you've got two bytes for X and Y (for a 16bit game), you've got a byte width and a byte height (assuming no object is more than 256 pixels thick). Maybe you need three bytes to describe all the types of hitboxes, and that's probably two bytes more than you need.

And that's still just 18 bytes you'll need for all of the hitboxes that frame. AND those 18 bytes can be used for other things when you're not checking hitboxes.

Again, all of that assumes you're doing a hitbox checking loop after the object handling loop, and not all at once. If you wanted to handle collisions within the object logic you'd need less information... probably.

That makes zero difference. Consider how you have to get which boxes to check in the first place. From the objects... So... if you already know where an object's RAM is, it's not too much of a stretch to assume you can add offsets or whatever.

You can just go through the object list twice. Once to move everything, once to check hitboxes with everything. This is no less safe than checking everything in some generic routine, because no effects from hits will happen until the next run of the "move everything" run through the object loop. The "hitboxes check" can set requests that the "move everything" loop will honor (or not).

One game I have runs through the object list three times, for reasons I won't get into. What I gather you're looking for is that if something gets hit, you want the hit reaction displayed THE VERY FRAME THAT CHECK WAS TRUE. If you wait until the next frame (i.e. honor the request on the next "move everything" loop), it allows the players to see what the screen looked like when they got hit. (i.e. which attack they had out themselves, rather than just seeing the hurt frame.) Even moreso with hitstop. But if it's a thing you want, you have another loop through the object list after hits are resolved that renders the objects and potentially changes their frames to hit frames. (or have have rendering done with hitbox checking.)

Edit2: And note that because you're running through an object loop again, objects can have unique logic that may do other things. You can use running through the object loop multiple times for all sorts of hacky things.

My game that supports grabbing has a logic loop, grab loop, and render loop. An object could report itself as grabbable, but really act as a switch when grabbed. The player tries to grab it. The grab loop repositions the object to the player's position (even though the switch shouldn't move.) During the render loop, the switch moves itself back to its starting position and requests that the thing that grabbed it drops it. Then renders itself.

So the player will never see that they grabbed it, but the switch during its render loop can use the fact that it was grabbed to activate something, then move itself back. There are all kinds of things you can do, based on need. (I probabaly wouldn't do... this particular thing on a not NES game. But there's a lot of ways to be creative is what I'm getting at.)

Edit: The game that goes through the object list three times supports 20 objects. Which... is more than there will be enough sprites to draw, usually. Going through the list itself is really not that expensive. It's having a lot of object logic that makes stuff slow, regardless of if its split between three loops or one.

While I recognize and respect your 'mailbox' bytes for each object, I'm not convinced that's the best way to do things. For instance, say you're recreating the dragon boss at the end of Wily Stage 1 in Megaman 2. (I don't actually remember if the boss works as I'm about to describe, so if it doesn't then we're talking about the green secret miniboss in Sting Chameleon's stage in Megaman X; same principle) The boss needs to respond to bullets in two different ways; if the megalemons hit his belly, they should just bounce away, but if they land on his face, it should do damage. If the dragon has only an inbox byte that tells him he got hit, he'd have no idea whether the bullet landed on his weakspot or no. You might decide from there to make his face a separate object from the rest of his body so that they have different inboxes, but now you need to coordinate the two to make sure they both maintain similar coordinates and the like.

I don't see why that would be a problem with the system at all. It's pretty much exactly like the stomp stuff I described that the game handles. This is kind of a general thing and not you specifically. But... it just... makes me wonder when people try to come up with ways it can't work... As a programmer, if you need the thing, you just... add it. I harp on this a bit in the engine topic I linked previously.

"Oh no, we need more information than just that he got hit!"

"So... add it?"

I even alluded to this when I said you could have bits for what he got by. And if a box knows what it got hit by, it can also tell what "hit" it stuff. Like to bounce away or whatever. Because what hit it identifies its type by another bit. If the box itself has properties (and it obviously already needs them. Hurt/Hit/Type of attack), the same object could have weak point hitboxes and not, and everything would still work.

This way, whenever a bullet overlaps a hurtbox, it would do a glorified switch statement to identify which type of enemy it just hit, and then depending on that result it would either jsr to the 'tell the victim its been hurt' routine or set its own variables to say 'bounce away' or however else the bullets may respond.

That doesn't handle the case you described either. The bullet knows what type of enemy it hit, but the Dragon boss's type alone doesn't do it. You also need to know where it hit, otherwise you still don't know if it was a weak point or not. Now... you could just... add what you need. But a switch is sure a lot more complicated than adding another bit to describe the object or hitbox.

Even better, the hitbox lookup tables can have an additional 'attributes' byte in rom that includes flags such as 'invulnerable', which the bullet could then check and decide whether to bounce.

Well yeah. That was implied from being able to tell what type of thing you got hit by.

There are lots of reasons why I think my request system is good. A lot are covered in that other topic. Say an object needs to move another object. If one object sets another's position, the second object may end up inside a wall. If an object simply requests that it move, the second object can update itself with that request using its own logic that presumably has been tested to keep it outside of walls. Objects run themselves, objects run themselves, objects run themselves. I believe objects messing with each other directly too much is the cause of many bugs.

Another reason to NEVER do things based off enemy type. (At least how I think you're describing it.) I want to create a new object. I want it to be shootable. I have to update my bullet routine with code to handle this new object. EVERY TIME. Even if it will react to getting shot the same way as everything else. If you have the object just report itself as shootable, it's handled and I have to update no other object to make hitting it work.

I can create a new object, set its type bits correctly and it immediately works. I can have objects hit objects where I haven't coded anything specific and it just works.

I'm not saying my solution is perfect, but the problems you're describing for it aren't really problems. I would still use a system like this if I had all the RAM in the world.

Simply: When I'm programming a new object, I have to change no other object's code and my new object will interact with all existing things just fine. Unless it needs some new behavior. In which case... I just... add a bit for it, and for that I do need to update all existing objects that I want to use this bit. But chances are there aren't many, or I'd have added the bit already.