what are common bugs when doing collision detection?

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

User avatar
Banshaku
Posts: 2417
Joined: Tue Jun 24, 2008 8:38 pm
Location: Japan
Contact:

what are common bugs when doing collision detection?

Post by Banshaku »

I rewrote some assembler code I did 10 years ago in C and my collision detection got better but I still have some edge case that I need to figure out. I know without the code it is hard to guess but since the C code and the code that retrieve the metatile data (still in asm) is spread a little bit and mangled with other part of the view, it would be too complicated and long to paste all the code. I will just explain the symptom in the hope to either found the cause or being suggested better way to do it.

For example, let say the actor is walking right then jump on an edge and ends almost on the corner of that edge. The actor ends up inside the block and then gets ejected to the left even though it should have landed on the corner. I usually checks vertical ejection first then sideways so you see it gets pushed up then left. I didn't have time to debug and check the why yet.

Another similar case is let set you are close to an edge when walking right then you quickly go left/right. The actors start to fall because it was too close but for some reason gets ejected hard like if it ended up deeper into the block or something, jerking the camera along with it. I'm not sure if it's the quick movement that cause an issue with the code that checks the location and cause it to be pushed harder than expected. I would expect to slide on the side of the surface, so there must be something going on with the quick movement.

When just colliding with a wall left/right on ending up on a surface while jumping, the ejection is done and not noticeable. Maybe I should try to capture some animated gif that would should the current symptom.

Are those common issue with collision or maybe it is just my code that is still erratic at this point?

edit:

Included an animated gif of one of the bug. The more I look at it, the more I think that it's like the detection ends in the second metatile from the left somehow and it get pushed hard from the second block.
falling_from_edge.gif
falling_from_edge.gif (715.92 KiB) Viewed 4892 times
P.s. Since I didn't write code for 10 years I do not have any new assets so I'm just continuing an engine with my old code/assets. It doesn't means anything about "that" project. It is very useful than restarting something from scratch when you're not an artist.
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: what are common bugs when doing collision detection?

Post by tepples »

You could try reading the map at the blocks at the four corners of the actor and then ejecting toward whatever corner is not solid. If the actor's hitbox is bigger than one metatile, treat a block in the middle of a side as being both corners.

Are you already doing that?
User avatar
Banshaku
Posts: 2417
Joined: Tue Jun 24, 2008 8:38 pm
Location: Japan
Contact:

Re: what are common bugs when doing collision detection?

Post by Banshaku »

My current way is quite primitive ^^;; My sprite origin start at the top/left corner (leftover of my previous effort that I need to change someday) I will check 2 points near the feet but the order of testing is based on the direction walking.

For example, if the user is walking right, I will first check first if the point at the bottom left of the feet is still on a surface. If it is, I'm maybe on a edge or a block and don't need to check the second point and continue to be in walking state. If falling, I check the second point on the bottom right to see if there is contact. If there is, then to some degree I'm on a block and can continue walking. If nothing then the actor is now in falling state. The test is reversed when walking left.

The reason I test that way is because of my concern/obsession about performance and try to avoid testing as much as I can. Since the test must be done on every frame , if walking, it "gives" the impression that it is intensive.

Maybe I'm worrying too much and should change to another way. The one you are mentioning is interesting. Since the code is in C I guess I could test later a temporary function with that logic but right now my logic call almost to no method to avoid unnecessary call to function (again, concern about performance) so it's 1 big function for input checking and collision.
User avatar
dougeff
Posts: 3079
Joined: Fri May 08, 2015 7:17 pm

Re: what are common bugs when doing collision detection?

Post by dougeff »

I just rewrote the collision code in my C project, a few weeks ago, and will post it on my website in the next month or 2 (whenever I get free time). If you don't mind waiting, you could use that.

It's similar to what @tepples said, 4 corners.
nesdoug.com -- blog/tutorial on programming for the NES
User avatar
gauauu
Posts: 779
Joined: Sat Jan 09, 2016 9:21 pm
Location: Central Illinois, USA
Contact:

Re: what are common bugs when doing collision detection?

Post by gauauu »

I've always found this blog post on 2d platforming movement to be a great reference in how to manage collision detection and player physics.
User avatar
Kasumi
Posts: 1293
Joined: Wed Apr 02, 2008 2:09 pm

Re: what are common bugs when doing collision detection?

Post by Kasumi »

Move the object on one axis. Eject the object on that axis. Move the object on the other axis. Eject the object on that axis. And you will not have problems.

That is to say:
1. Move on X.
2. Eject on X.
3. Move on Y.
4. Eject on Y.
Rather than:
1. Move on X.
2. Move on Y.
3. Eject on X.
4. Eject on Y.

Whether you do Y first or X first depends on what you value.
Edit: If you walk right off an edge, then walk left. This could evaluate to:
1. Move right on X.
2. Eject on X. There's no ejection to be done.
3. Move on Y. (Since you're walking, they won't be any movement.)
4. Eject on Y. (Check for ground underneath, you'll fall.)
Next frame.
1. Move left on X.
2. Eject on X. (If you fell a pixel in the first frame of being airborne, you'll eject, but that's fine since you had to be further out than the wall to fall in the first place. If you didn't fall a pixel, you'll end up back above the ground.)
3. Move on Y. (You might move a bit due to gravity.)
4. Eject on Y. (You'll end up in an identical position to where you were the frame before.)

It's similar for the corner jump case. If you jump at a corner, you'll always get only one ejection. Either one will make sense.

Edit2: The Sequel: This describes separating movement axes with diagrams and such: https://forums.tigsource.com/index.php? ... msg1386874
I do basically that, except I don't check more than two points an axis for objects with a height of width less than the tile size. (Except for slopes...)
User avatar
Banshaku
Posts: 2417
Joined: Tue Jun 24, 2008 8:38 pm
Location: Japan
Contact:

Re: what are common bugs when doing collision detection?

Post by Banshaku »

@dougeff

There is no rush. I put that project on hold for almost 10 years so I will first try to find a solution myself and will be more than happy to look at your code later to see if I can improve based on it. Right now that bug is not a blocker and soon I will be able to achieve a big milestone which will be to switch map based on exit point(s) so many bugs will arise anyway :lol: Will be more than glad to look at it once it is available.

@gauauu

I will give it a look, thanks!

@Kasumi

Right now, if the player is in "JUMPING" state (either going up or down based on velocity) the Y position is calculated and the ejection is done right away. Then if the user is walking, the x position is calculated then the ejection calculated.

One thing I realize is that if I'm not moving left/right I don't do any horizontal ejection which could be one possible cause of it. Unless mistaken I do ejection in the following scenario:

- first when jumping/falling
- when moving left/right I check first the floor then eject if necessary

which means, I never eject horizontally if not moving, which could be an issue, hmm..

(I see you have updated your post while I was writing and did a quick check. Will in details soon about it. )
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: what are common bugs when doing collision detection?

Post by tokumaru »

Kasumi wrote:Move the object on one axis. Eject the object on that axis. Move the object on the other axis. Eject the object on that axis. And you will not have problems.
I second this. If you don't do one axis at a time, you may have problems with corners.

If you don't want to be unfair to the player, you can carry the order in which you check the axes: when falling down, you can do X first and then Y, to increase the chances of the player reaching a ledge. When going up, do Y first, then X, also to help with ledges. But if you're gonna use the same order every time, I suggest X first.

I don't know if you're doing slopes, but if you are, then we have a lot more to discuss!
User avatar
Banshaku
Posts: 2417
Joined: Tue Jun 24, 2008 8:38 pm
Location: Japan
Contact:

Re: what are common bugs when doing collision detection?

Post by Banshaku »

For now the engine in mind is for game similar to mega man, ninja gaiden and the like so slopes are not necessary. I will keep everyone feedback in mind and start debugging the cause of those 2 edge case. Must be just a little something missing.
User avatar
Sumez
Posts: 919
Joined: Thu Sep 15, 2016 6:29 am
Location: Denmark (PAL)

Re: what are common bugs when doing collision detection?

Post by Sumez »

As long as your collision detection is entirely bound to a grid, corner clipping is definitely your worst concern.

Being off by one pixel to one or more edges is another classic one, as collision detection always raises the "philisophical" question of which side of a pixel coordinate the bounding box of your characters actually begins and ends.
Different games might do it in different ways, but it's important to be consistent to avoid bugs.
gauauu wrote:I've always found this blog post on 2d platforming movement to be a great reference in how to manage collision detection and player physics.
I love this article.
It's kind of funny I read through it all before noticing it's written by a guy I used to talk with a lot on IRC during my early game dev days in the late 90s, and when I reconnected with him again later on I made sure to praise him for that article.
In fact, I think it's kind of indirectly a part of what lead me into eventually pursuing development on actual retro hardware. I started replicating "the old way" of doing things in my game engines, and ended up figuring out that since I'm doing that anyway, it would be fun to do it the real way. :)
User avatar
Banshaku
Posts: 2417
Joined: Tue Jun 24, 2008 8:38 pm
Location: Japan
Contact:

Re: what are common bugs when doing collision detection?

Post by Banshaku »

The older code in assembler didn't have those specific issues but had a strange bug that I never found the cause so I decided to try to rewrite in C. Now that bug was fixed but new ones emerged. I think my previous ejection code was unusual, something like if inside a block, go back to previous X position or something like that. Not very good ^^;;;

For now it doesn't prevent to develop other aspects but hope I will find them soon just to feel closure on those bugs :lol: My next concern will be how easy that engine will be to "change" once I develop my real game. For now I'm using an existing game/style as a template which help me to develop the foundations but how hard it will be to change it to something different is a little bit worrisome but 2d are 2d games so the basics (collisions, basic map transition, entity management) should stay similar to some degree.
User avatar
gauauu
Posts: 779
Joined: Sat Jan 09, 2016 9:21 pm
Location: Central Illinois, USA
Contact:

Re: what are common bugs when doing collision detection?

Post by gauauu »

Sumez wrote:
gauauu wrote:I've always found this blog post on 2d platforming movement to be a great reference in how to manage collision detection and player physics.
I love this article.
Yeah, I discovered it after a couple of miserable weekends trying to do ramps. Now I regularly read through it as a refresher before starting any platformer project. I can't recommend it enough.
User avatar
thefox
Posts: 3134
Joined: Mon Jan 03, 2005 10:36 am
Location: 🇫🇮
Contact:

Re: what are common bugs when doing collision detection?

Post by thefox »

Sumez wrote:Being off by one pixel to one or more edges is another classic one, as collision detection always raises the "philisophical" question of which side of a pixel coordinate the bounding box of your characters actually begins and ends.
Different games might do it in different ways, but it's important to be consistent to avoid bugs.
I think it's pretty easy to make the "correct" decisions here if you're careful enough, however they might not always be the most performant ones. Of course there are some even more philosophical questions, like should you handle collisions when your object is 0.1 pixels into the platform :)
Download STREEMERZ for NES from fauxgame.com! — Some other stuff I've done: fo.aspekt.fi
User avatar
Banshaku
Posts: 2417
Joined: Tue Jun 24, 2008 8:38 pm
Location: Japan
Contact:

Re: what are common bugs when doing collision detection?

Post by Banshaku »

Found the cause of the bug. It was a fix for a visual "bug/annoyance" that caused this other bug. In my current test data I'm using mega man for testing. When you check an edge and are falling, the animation was switched to jumping state.

The problem is if you move fast enough, you could go back on the edge since the velocity has not effected you yet. This gives you a chance on edges but the animation went back to running and ended up that you "landed" on a platform, causing a sound to be played (like the original, I'm testing fx these days). The problem with that is if you do a back and fort on a corner the animation/sound was trigged and it was quite annoying. To remove that "bug", when this case occurred I gave the actor an additional push downward and made it fall on purpose, which caused that ejection bug when moving fast backward very fast and because of the way the ejection code was written.

For now I just removed the extra push and will have to clean-up that part which is too messy. If I keep the "give a chance" to come back on the edge, maybe I will delay by a few frame before the animation is switched and sound played.
na_th_an
Posts: 558
Joined: Mon May 27, 2013 9:40 am

Re: what are common bugs when doing collision detection?

Post by na_th_an »

I do as suggested, deal with axes separately. Do everything for one axis, then for the next. When checking for collision, I usually use two points (or three if the collision box is bigger than collidable metatiles), like this:

Code: Select all

// Vertical
// --------

// Make acceleration affect velocity (for example, G)
vy = vy + g; if (vy > max_vy) vy = max_vy;

// Make velocity affect position
y = y + vy;

// Check for collisions
if (vy > 0) {
   // Check the two lower vertices of the collision box, reposition, etc.
} else if (vy < 0) {
   // Check the two upper vertices of the collision box, reposition, etc.
}

// Extra vertical stuff: jump ,etc.

// Horizontal
// ----------

// Make acceleration affect velocity. In side view, accelerate if pressing D-Pad, deccereate when not.
if (pad_left) {
   vx = vx - ax; if (vx < -max_vx) vx = -max_vx;
} else if (pad_right) {
   vx = vx + ax; if (vx > max_vx) vx = max_vx;
} else {
   if (vx > 0) vx = vx - fx; if (vx < 0) vx = 0;
   else if (vx < 0) vx = vx + fx; if (vx > 0) vx = 0;
}

// Make velocity affect position
x = x + vx;

// Check for collisions
if (vx > 0) {
   // Check the two rightmost vertices of the collision box, reposition, etc.
} else if (vx < 0) {
   // Check the two leftmost vertices of the collision box, reposition, etc.
}

// etc...
This is usually pretty strong. I don't do slopes nor anything flashy, tho'.
Post Reply