Better collision detection techniques...

Better collision detection techniques...
by Sivak on 2010-07-16 (#64365)

Okay, so I'm trying to do the collision more efficiently than how I did it in the first game. The first game's approach was rather... well... silly and very assumption-based. Timmy would ALWAYS move at a speed of 2, so this worked. I'm still amazed that it did work to be honest.

The problem with BK2 is I want the complicated tiles that could move you at speeds that are not 2, so I need something better. Anyway...

What I'm basically doing is this:
-There's a hitbox naturally. 4 points which basically constitute top, bottom, left, right. These points are combined these into a value to lookup the tile on the grid. So if you were at left $7F and top $40, for instance, that'd be tile number $47 to look at.
-If you request to move horizontally, you are permitted to do so and the box updates with the acceleration you move in. Then comes a series of checks if the box is within something solid...
-What I do is see if either your top left or bottom left points is within something solid and if so, "push the player right" so that you are touching the solid object to your left. Similar behavior of course happens for the right points and "pushing left" in that case.

The main problems I am seeing with this are what'll happen for disappearing blocks? Something could instantly become solid and push you away. I've done memory altering tests and you do get pushed out, but that may not be the desired effect... Interestingly, if all 4 points are in the box, you don't get pushed.

Another issue I'm seeing would be with jumping or falling and trying to "squeeze into" something that's only 1 tile high. Your jump height is variable and if you get "pushed out" then going into something 1 unit high might not work as easily. I remember doing what felt like VERY hackish code to make this work in BK1.

I don't know. Is there a better way?

Re: Better collision detection techniques...
by tokumaru on 2010-07-16 (#64367)

Sivak wrote:

The main problems I am seeing with this are what'll happen for disappearing blocks? Something could instantly become solid and push you away. I've done memory altering tests and you do get pushed out, but that may not be the desired effect...

What would the desired effect be then? The player and a solid block can not occupy the same space, so you have to eject the player in some direction. For the player it would be easier if you ejected upwards, so he'd stand on the block that just appeared.

Quote:

Interestingly, if all 4 points are in the box, you don't get pushed.

Yeah, since traditional collision with the background consists of checking points around the object, if the block is completely inside the object's hit box it will go undetected.

I'd solve this problem by treating disappearing blocks as actual objects (like enemies or items) instead of simply another block type. That will allow you to check for collisions with the player using two hit boxes (object-to-object collision), which gives better results than traditional background collision, so you'll be able to take special measures if they do collide, and do some consistent ejecting rather than rely on your map collision engine to do the right thing for that block. After ejecting the player, if necessary, the block object can modify the RAM map to put a solid block in its location.

Things that are too dynamic (such as disappearing blocks and conveyor belts) should be given more attention, and have their own AI routines. Since their behavior is so specialized, coding them as part of the general collision routine will introduce unneeded complexity and possibly waste CPU time with the checking of unnecessary things since most rooms don't even have any of these special blocks.

Quote:

Another issue I'm seeing would be with jumping or falling and trying to "squeeze into" something that's only 1 tile high. Your jump height is variable and if you get "pushed out" then going into something 1 unit high might not work as easily.

I'm not seeing the problem.

The correct thing to do is handle horizontal and vertical motion separately. First you update the object's X coordinate, check for horizontal collisions and eject left or right when necessary. Once you have the final X coordinate, you do the same for Y, which handles jumping and falling.

Also, when checking for collisions you must check as many blocks as necessary to make sure nothing is blocking the way in the whole width or height of the hit box, so objects will not squeeze in narrow spaces.

by Celius on 2010-07-19 (#64459)

In the event of blocks inside of objects going undetected, I actually came up with a very simple solution. I understand some people wouldn't like this, but for my game, the solution helps with a lot of things. I just made the maximum speed of moving objects 8 pixels per frame. Since tiles are 16x16 pixels, an object would never have the chance to move their collision points past the other side of a solid tile. They would always be rejected <=8 pixels into the tile. This also greatly simplifies my scrolling code. Since objects can only move at 8 pixels a frame at max, I only need to decode/update one row/column of tiles per frame to have the camera follow those objects. This saves A LOT of cycles, and also a lot of cycles for collision detection code.

Of course, in a game like Sonic, this wouldn't work, because we want Sonic to move faster than 8 pixels a frame .

EDIT: I previously had said 8 pixels a "second" instead of "frame", and that's just plain wrong. I fixed that just now.

by tokumaru on 2010-07-19 (#64460)

Celius wrote:
Of course, in a game like Sonic, this wouldn't work, because we want Sonic to move faster than 8 pixels a frame .

I believe that the maximum an object can move per frame is the size of the smallest block (metatile). If your blocks are 16x16 pixels, characters can move up to 16 pixels per frame and never miss a block. That's enough even for Sonic, but the rendering engine must draw whole blocks to the name tables, not single tile columns/rows.

But Celius, when he talked about undetected blocks he didn't mean common blocks that the characters run into, but appearing/disappearing blocks. Look at this:
Code:
+------+
| |
| | +----+
| | | |
| | | |
| | +----+
| |
+------+--------------

The big rectangle is the character, the small square is a disappearing block. If the character tries to walk right, the block will stop him:
Code:
+------+
| |
| +----+
| | |
| | |
| +----+
| |
----+------+----------

A collision point at the right edge of the character will detect the block. But once the block disappears, the character is free to move:
Code:
+------+
| |
|......|
|: :|
|: :|
|:....:|
| |
----------+------+----

But when the block appears again it will not be detected, because none of the edges of the character are touching it:
Code:
+------+
| |
|+----+|
|| ||
|| ||
|+----+|
| |
----------+------+----

Which is why I suggested that these special blocks be objects, as object-to-object (bounding box against bounding box) collisions can detect this type of collision.

by Sivak on 2010-07-21 (#64571)

OK, so I want to get into this finally. I have an image here showing my old method and a possible new one, but I see problems with both methods. Also a 3rd approach I thought of...

With the old method, which is what I'm currently doing, I can keep you out of the walls when walking. The problem lies when a vertical movement is happening.

If a point enters a solid surface, you are pushed to the side. But what if you jump and the surface is above you? The point would enter a solid surface and you'd get pushed aside instead of down because the point is in a solid surface. It's almost as if you need a lot more points for this.

The way I handled all this in BK1 was complex, messy, but it did work. Basically, you are ALWAYS moving at a fixed speed of 2. Therefore, the game sees if your box is on the right or left edge of a tile and if what's to your immediate side is solid, you don't move. For verticals, it moves you 1 unit each time and keeps checking for solids above/below. If any solids happen within these checks, you stop.

Doing this the "right" way is complicated...

by tokumaru on 2010-07-21 (#64576)

Sivak wrote:
If a point enters a solid surface, you are pushed to the side. But what if you jump and the surface is above you? The point would enter a solid surface and you'd get pushed aside instead of down because the point is in a solid surface.

This can easily be solved by handling vertical and horizontal motion separately, like I said before. First move horizontally, check for walls, eject horizontally if necessary. Then move vertically, check for floor/ceiling, eject vertically if necessary. If you move in both axis at once and check for collisions later it really will be hard to find a good solution.

by Sivak on 2010-07-21 (#64578)

tokumaru wrote:
Sivak wrote:
If a point enters a solid surface, you are pushed to the side. But what if you jump and the surface is above you? The point would enter a solid surface and you'd get pushed aside instead of down because the point is in a solid surface.

This can easily be solved by handling vertical and horizontal motion separately, like I said before. First move horizontally, check for walls, eject horizontally if necessary. Then move vertically, check for floor/ceiling, eject vertically if necessary. If you move in both axis at once and check for collisions later it really will be hard to find a good solution.

Hm.... It sounds like with your method, I should ONLY check if your acceleration for the frame is a non-zero number. Naturally if you don't move, you don't check. That is making sense. Thanks. I'll play with this.

by tokumaru on 2010-07-21 (#64579)

Sivak wrote:
It sounds like with your method, I should ONLY check if your acceleration for the frame is a non-zero number.

Depends on what you call "acceleration". In my engines I have both "speed" and "acceleration". Since "speed" is what I add to the object's coordinate every frame and "acceleration" is how much I modify the speed each frame, what you said above might not be true in my engines. But you got the right idea, if the character doesn't move, there is no need to check for collisions.

Quote:
Naturally if you don't move, you don't check.

Yup. And if you move right, you only have to check the right edge, because there's no way you'd run into something on the left. Something might run into you, but if something moves I strongly believe it should be treated as an object, not part of the map. I think the same about the disappearing blocks, it's better to make them smart objects.

I've been using this kind of collision detection for a while and it worked great so far. I used it in the engine shown in this video, for example.

What really complicates things are slopes. With slopes there are a million ways to program physics and collisions and none of them are perfect!

by Sivak on 2010-07-21 (#64580)

I'm not doing slopes. Slanted surfaces scare me. Heh.

What do you think about the approach of having 2 boxes on the player, one for horizontal and the other for vertical? Does it make sense or would I most likely be able to get away with the one box?

After I get my meal, I'm going to try the new approach to this. Thanks again.

by tokumaru on 2010-07-21 (#64583)

Sivak wrote:
I'm not doing slopes. Slanted surfaces scare me. Heh.

They scare everybody. But I've been thinking about them for over a year, and I think I got all the aspects covered, so I think my game will be fine.

Quote:
What do you think about the approach of having 2 boxes on the player, one for horizontal and the other for vertical?

I think they might conflict with each other in certain situations... Say that the horizontal box lets you get inside a narrow tunnel but then you jump inside it and the vertical collision detection will probably screw up with the ejection (possibly sinking the sprite into the floor).

I think it's better to use 1 box, but use different sides of it depending on the direction of the movement.

by Sivak on 2010-07-21 (#64591)

OK, I have just foreseen an issue with this method.... If you jump AND move right (or fall too), then the top right point could conceivably be inside a solid surface and you'd be ejected to the left accordingly...

I guess it'd seem to me one would have to do something along these lines for handling collision detections:

-If right, check both top right and lower right points.
-If up, check both top right and top left points.
-If up and right, first check lower right for ejection to the left, then the 2 top points??? Although if you are above a block and your top right point is hitting a wall, but the lower right is not, then what?

Code:
XXXX
XXXX
XXXX
PPP*XXX
PPPP
PPPP
PPPP
;I'm jumping and my top right point is in a block... what would happen?

by tokumaru on 2010-07-21 (#64598)

Sivak wrote:
-If up and right, first check lower right for ejection to the left, then the 2 top points???

Do exactly as if it was just up or just right, but one at a time. Once X is done, do Y.

Quote:
;I'm jumping and my top right point is in a block... what would happen?

The idea behind the separation of vertical and horizontal movement is that you know which of them got the character stuck in the wall.

Move horizontally first, don't touch Y. If that got the character into a wall, eject him (you know you have to eject horizontally). At this point the X coordinate is ready you will not modify it anymore. Now you move the character vertically, if it got inside a ceiling or floor, eject him (now you know to eject vertically). The ejection is handled separately for each axis, so you always know in which direction you should eject.

Of course that if a character touches the block exactly at the corner, the order in which you update the axis (first X or first Y) makes a difference. I chose to do X first because it makes landing on blocks easier when you hit it close to the corner. If Y was done first, the character would hit the side of the block and fall.

by Sivak on 2010-07-23 (#64725)

I actually have been giving some thought to your mention on the disappearing blocks scenario as well...

I'll definitely have something check if they are overlapping you, you get ejected in some direction by the block. After that, the tile the block occupies is then made into a solid tile and will stay that way until the block goes away. This seems like a pretty straightforward method.

by tokumaru on 2010-07-23 (#64726)

Yeah, that's exactly what I had in mind.

by Sivak on 2010-09-09 (#67407)

I've been pondering the disappearing block routine again and think it'll become very complicated as the enemies are only updated once per frame and a dilemma can conceivably occur...

If you had some blocks adjacent to each other and you were inside both, what would happen if you got ejected but then were inside another that had already been updated? You'd get ejected twice, most likely, but over 2 frames and not one.

So.... I have come up with this solution that doesn't seem optimal, but would work and would even be similar to how BK1 works: Don't eject at all. Have the block remain a passable tile, maybe have it flicker to demonstrate this, and if you walk off, then and only then does it turn solid.

This would simplify matters. Plus, I'm not really going to be designing the rooms in such a way that'd have this be so noticeable.

What do you think?