It is currently Thu Jan 17, 2019 6:51 pm

All times are UTC - 7 hours





Post new topic Reply to topic  [ 31 posts ]  Go to page 1, 2, 3  Next
Author Message
PostPosted: Sun Apr 25, 2010 2:47 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 11090
Location: Rio de Janeiro - Brazil
In this post tepples mentioned he was looking for an efficient way to test this kind of collision, and then UncleSporky thought this was worth discussing, so I made this topic to share my findings in this area.

Games objects usually collide with everything else in the game (other objects and surfaces) through the use of a bounding box that represents its solid area. However, when you respect the object's bounding box and put it on a slope, it doesn't look very good:

Image

The object will appear to be standing on air rather than on the ground. Some games compensate that with art, by drawing the ground above the logical collision surface:

Image

This solution is quick but will probably make the levels hard to edit since the art is so different from the collision data. Also, it's not an optimal solution because depending on how wide the objects are they will still look like they are floating (too wide) or sunk into the floor (too narrow):

Image

To fix this, the best solution I found was to use a central point (or a small segment between two points, but one point is simpler and appears to work OK) for collision with the ground:

Image

Now the width of the bounding boxes don't matter, all objects will be adequately positioned on the floor. There is one big problem though: here's what happens when the object walks off a ledge:

Image

Yup, it will fall while half of its body is stuck into the wall. Not good, huh? So you either let that ugly side effect happen or you suddenly push the object away from the wall to fix it, causing jerky movement. Both options suck, so I came up with a 3rd one: When the central point (or line) is not making contact with the floor, then you use the corners of the bounding box to check for collisions:

Image

But the secret is to not allow the bounding box's corners to collide with slopes, they only collide with completely solid blocks (while the central point collides with solid blocks AND slopes). In the image above, it's like the slope has "guided" the game object to land on the solid block, and then it's like the slope doesn't exist anymore, because there's nothing below the central point. If the object keeps moving left, it'll eventually fall, but it won't be stuck into the wall.

To me it seems like this would work perfectly for all kinds of games. There are a few limitations though. For example, the slopes have to start and end connected to solid blocks. I mean, you can't use the side of a slope as a wall, because things like this would happen:

Image

You can't have the end of a slope leading to nowhere like that. If you want your slope to lead to a pit, you have to add some "trimming". Something like this would do the trick:

Image

All sorts of crazy slopes will work fine, as long as long as the complex shapes start and end on solid blocks. I like to think of the slopes as "decoration", something that makes the otherwise blocky areas more interesting, but the basic shape of the levels is still made of solid blocks:

Image

I tried looking for existing games that behave like what I just described and the closest thing I found was Mega Man X (SNES). It doesn't have many slopes, and I have no idea of how they are actually implemented, but all the features and limitations I mentioned here seem to apply: After going down a slope that leads to a pit, Mega Man will move horizontally for a few pixels, like he was standing on a flat block, before falling (that's the "objects don't get stuck in the wall" feature). All the rising slopes that lead to pits I could find in that game have a flat area before the pit (that's the "the sides of slopes can't be used as walls" limitation).

Even if this isn't exactly what Mega Man X or any other game does, I still think it's a pretty good solution. I don't think the few limitations are deal breakers by any means, and the whole idea seems very simple to me, and easy to implement on top of an already working "bounding box to solid blocks" solution. Nothing about a working engine like that would have to be changed, only a new collision point and a new type of block (a block with a height map) would have to be added.

Please let me know what everyone thinks, if you have suggestions on how to improve this idea or if you can see potential problems I might have overlooked.


Top
 Profile  
 
 Post subject:
PostPosted: Sun Apr 25, 2010 3:30 pm 
Offline
User avatar

Joined: Wed Nov 10, 2004 6:47 pm
Posts: 1849
I dunno.. having a collision system that explodes if you arrange your map a certain way isn't ideal, IMO.

I'm working on something like this right now, although it's for a PC game and not for the NES, so I don't have to be as limited in my calculations.

One idea I've been kicking around is having a 'V' bottom on the rectangle. So the rect actually has 5 points instead of 4.

My pictures aren't as pretty, but here's the basic idea:

Image

I haven't worked out the details on how to actually make it work, though =x


Top
 Profile  
 
 Post subject:
PostPosted: Sun Apr 25, 2010 3:49 pm 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 21002
Location: NE Indiana, USA (NTSC)
I'm still at the point where I'm trying to decide whether point (x, y) is within the terrain. What's the best way to represent a slope? Sonic 2 uses a set of n pixel heights, one for each column of a metatile. But I think some other games use a more "vector" method: represent it as a height at the left side and a height at the right


Top
 Profile  
 
 Post subject:
PostPosted: Sun Apr 25, 2010 4:20 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 11090
Location: Rio de Janeiro - Brazil
Disch wrote:
I dunno.. having a collision system that explodes if you arrange your map a certain way isn't ideal, IMO.

Yeah, but I couldn't think of a good way to allow the sides of the slopes to be used as walls. If you look around you'll see that several commercial games had problems with this, so they either avoided the situation or left the bugs in. Take a look at what happens in Sonic 1 in a situation like this. Here's Sonic about to walk towards a pointy ledge:

Image

It appears that a collision point close to the tip of his shoes is being used, as you can see as he goes up the slope:

Image

But once that point has no floor below it, Sonic falls, and and a point at the back of his shoes makes contact with the floor and keeps him from falling further:

Image

Now if you keep walking you can make Sonic go up the slope again, now using the other collision point:

Image

When that second collision point is about to go off the ledge Sonic starts his balancing animation:

Image

And after that he falls for real. Now look how Mega Man X 2 appears to avoid situations like this, by putting flat areas at the top of the ramps:

Image

Image

I have the impression that this is a notoriously hard thing to get right, and that programmers have always had problems implementing this on limited hardware. If anyone else can find examples in other games, please post them.

Quote:
I'm working on something like this right now, although it's for a PC game and not for the NES, so I don't have to be as limited in my calculations.

Yeah, you idea is very interesting, and OK for a PC game, but colliding with angled lines is probably too slow for the NES, possibly even for the SNES or the MD/Genesis I think.


Last edited by tokumaru on Sun Apr 25, 2010 8:58 pm, edited 2 times in total.

Top
 Profile  
 
 Post subject:
PostPosted: Sun Apr 25, 2010 4:33 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 11090
Location: Rio de Janeiro - Brazil
tepples wrote:
Sonic 2 uses a set of n pixel heights, one for each column of a metatile.

That is my approach, because it allows for more interesting surfaces than just straight lines.

Quote:
But I think some other games use a more "vector" method: represent it as a height at the left side and a height at the right

This might be doable, but I think it will be kinda slow if you have to trace a line (possibly with bresenham's algorithm) to connect the points. One thing that might be easy to do is specify how much the height changes from column to column using a fixed-point number. That way you can multiply that number by how far into the block your column of interest is to get the height of that column.

I really prefer to simply have a table with all the column heights though. Is it space you are worried about? If instead of hardcoding the height maps to the blocks that use them you make them reusable (have each block indicate what height map it uses), they will not take so much space. And you can probably use a single set of collision maps for the whole game, because different levels usually share many similar slopes.


Top
 Profile  
 
 Post subject:
PostPosted: Sun Apr 25, 2010 5:28 pm 
Offline

Joined: Mon May 25, 2009 2:20 pm
Posts: 65
Image

it's like that on my game too, about how mm and enemies will barly even be standing on the slopes at all, like just a pixel of their feet and no more.
a japanese person named Rock5easily coded the slope mechanics before that i could use in my rom hack well over 2 years ago, but i have no idea how to even modify it cause it's way too complex to me. :(

It sucks that it looks like that ..about barly standing on the edge like that, looks worse when walking though. I can't ever fix it on my own, as well as this very annoying issue when sliding on slopes, there's a small rare chance mm gets stopped immediately only when sliding. It's pretty annoying


Top
 Profile  
 
 Post subject:
PostPosted: Sun Apr 25, 2010 7:23 pm 
Offline
User avatar

Joined: Wed Apr 02, 2008 2:09 pm
Posts: 1268
Here's how my system works.

I have "hard" and "soft" tiles. Hard tiles impede progress (0 your X velocity and eject you from the wall horizontally) when the left/right points are touching them. Soft tiles don't. (so you can move up slope tiles without being ejected horizontally)

You can land on hard tiles with your left/right points. You can't land on soft tiles with your left/right points.

Slope tiles are always soft unless they are VERY steep, so the middle point is used to land on them. They're also used to eject the character vertically. Flat areas are usually hard unless they lie next to slope tiles (for reasons described further below), so you can have your middle point off them and still not fall.

I have a special case where if a soft tile is DIRECTLY above a hard tile you can't land on it with the left/right points. (But it will still impede left/right progress if you run up against it or jump to the left or right of it) This special case is for when a when a slope ends over a pit.

In my diagrams, purple is a hard tile, yellow is a soft tile.

Here is the above special case. You can't land on that hard tile, but it would still eject you horizontally if you were jumping next to it, or falling through it.

Image

Right now my game ejects the character from the wall in the above case if they have no velocity, or velocity that would put them further in the wall. This is so they don't fall halfway through the wall. If they have velocity away from the wall, well... no ejection occurs since they're moving out of it anyway.

That ejection looks kinda silly, but you have to really be trying to trigger it. The plan that I have, though it's not programmed yet, is to just add velocity in that case, so it's like the slope pushes the character out of the wall with the X velocity it gives the player. Actually landing on a slope would give you some horizontal velocity, so it would be like you landed on it for a frame and got its velocity, then started falling.

And it checks the pixel above the tile. So this doesn't trigger that special case. The character would just be ejected horizontally here:

Image

That's the basics of hard and soft tiles. But a tile can be both soft and hard. For instace. What do we do in a case like this?

Image

The character's right point is in a hard tile so by game rules he should be ejected to the left. But... that wouldn't make any sense to the player who thinks he should be able to continue up the slope.

If those tiles were made soft, the player could fall through on the other side with half his body inside.

So the tile is made soft for the right point and hard for the left point. Problem solved.

Even this breaks in this case Tokumaru posted.

Image

But I've yet to come up with anything else this doesn't handle.


Top
 Profile  
 
 Post subject:
PostPosted: Sun Apr 25, 2010 8:54 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 11090
Location: Rio de Janeiro - Brazil
They didn't fix it in Sonic 2:

Image -> Image

I couldn't find places like this in Sonic 3 (& Knuckles), but I didn't look much.

I guess that the only way to fix this is to check all the column heights below the object in case the primary point isn't making contact, as opposed to checking just the secondary points. Not the fastest solution, but it will allow for the sides of slopes to be used as walls.


Top
 Profile  
 
 Post subject:
PostPosted: Sun Apr 25, 2010 9:26 pm 
Offline
User avatar

Joined: Fri Nov 19, 2004 7:35 pm
Posts: 4119
Mr. Gimmick appears to just let you fall off a slope as your midpoint leaves the slope.
Image
Then wall ejection kicks you out of inside the wall.

_________________
Here come the fortune cookies! Here come the fortune cookies! They're wearing paper hats!


Top
 Profile  
 
 Post subject:
PostPosted: Sun Apr 25, 2010 10:01 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 11090
Location: Rio de Janeiro - Brazil
Yeah, I mentioned some games do that. Kasumi seems to handle it like this as well. I don't like it, I think it's a very sudden movement that looks weird.


Top
 Profile  
 
 Post subject:
PostPosted: Sun Apr 25, 2010 10:25 pm 
Offline
User avatar

Joined: Wed Nov 10, 2004 6:47 pm
Posts: 1849
Let's look at this from a different angle.

We know what the problems are, but what would be the desired behavior? Part of the reason why I'm having a hard time visualizing a solution is because I don't know what I'm aiming for.

I think the "top of the slope" desired behavior is pretty straightforward. Once the object gets to the top, he should move horizontally until his hitbox completely clears the topmost point, at which point he falls.

But what about the bottom of the slope behavior? Is it the same? Once you go past the bottom of the slope, we want to move horizontally until the hitbox clears, right?

With that in mind, here's my new idea:

1) Use the center point first and foremost. If the center point is grounded, the object is grounded. If the center point is on a slope, the object is on a slope.

2) If the center point gives the impression that you're going to fall, you instead check the entire lower surface of the rect.

3) If no point on the lower surface finds any floor, you fall

4) Otherwise, you remain grounded as if you were on a flat surface (no slope).

It'd work like this:

Image

The problem is this only works if you're grounded. If you're falling, this poses a problem:

Image

The same problem persists if you walk from a flat surface to a downward slope (or from a downward slope to a steeper slope):

Image

So what's the solution here?

My first incling is to check a few pixels beneath the center point. If the center point is "almost" grounded:

- "snap" to the floor if you're already grounded
- or resume falling and ignore the floor overlap if you're airborne


This logic seems to cover every angle I can think of. What do you guys think?


Top
 Profile  
 
 Post subject:
PostPosted: Sun Apr 25, 2010 10:47 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 11090
Location: Rio de Janeiro - Brazil
Disch wrote:
1) Use the center point first and foremost. If the center point is grounded, the object is grounded. If the center point is on a slope, the object is on a slope.

Yeah, that's how the idea I presented in the first post works.

Quote:
2) If the center point gives the impression that you're going to fall, you instead check the entire lower surface of the rect.

Yup, instead of using a secondary collision point you have to check the whole width of the object.

Quote:
This logic seems to cover every angle I can think of. What do you guys think?

What about ejection from the side of a slope?

Image

Do you think it can work the same way it does with regular walls?


Top
 Profile  
 
 Post subject:
PostPosted: Sun Apr 25, 2010 10:53 pm 
Offline
User avatar

Joined: Wed Nov 10, 2004 6:47 pm
Posts: 1849
Quote:
What about ejection from the side of a slope?


Well I'm doing X and Y movement seperately, so that's not really a problem for me.

For example, Y movement is done first, and since the rect was originally outside the wall, it would fall as normal.

Then when you try to move left, the side of the slope would appear as a solid wall.


Top
 Profile  
 
 Post subject:
PostPosted: Mon Apr 26, 2010 5:14 am 
Offline
User avatar

Joined: Wed Apr 02, 2008 2:09 pm
Posts: 1268
tokumaru wrote:
Yeah, I mentioned some games do that. Kasumi seems to handle it like this as well. I don't like it, I think it's a very sudden movement that looks weird.

The insta ejection is only how my game works for now. The plan should be easy to implement, I just can't say I have it working right this second. I've got something bigger to solve that factors into this.

In Sonic, jump over a sort of steep slope, then try to 0 out your horizontal velocity before landing. (How about trying on the first slope going down to the right |\ in angel island act 1?) Upon landing, some of Sonic's vertical momentum becomes momentum to the right. My game will do that sort of thing in that case. Character has "landed" his left point in a slope pit. Character should fall because his middle point is not in a wall, and his left point is in a hard wall, but there is a soft wall above it.

But... because it's a hard wall with a soft wall above it... character gains some momentum to the right, so he's moving outside the wall, that would match the momentum he'd gain from landing on the slope with his middle point. No insta ejection occurs. It's like he landed on the slope for a frame, but was unable to jump on this frame. I might prohibit increasing movement to the left until he's safely out of the wall, but I don't think it will look too strange. Maybe on really shallow slopes, but I think I can compensate that somehow. Or... just design my maps around that. I'll need to get it working before I know how bad they'll look. If 30 degree slopes and below look strange, I'd take care not to put those next to pits. If I only have to avoid that and the rising slope ending in pit case, I'm not too worried.

Disch wrote:
2) If the center point gives the impression that you're going to fall, you instead check the entire lower surface of the rect.


You check 15 points for collision if your character is 16 pixels wide? (You already checked one, of course) If that's what you're describing, I definitely can't check that many points quickly enough to not lose frames, considering I also multidirectional scroll and such. My game does not store an array of bytes for each slope, so it's not a simple lda slopetilenumber,x compare for me.

Disch wrote:
4) Otherwise, you remain grounded as if you were on a flat surface (no slope).

This would then allow you to stand like this?

Image

I don't like that. My game uses slopes to add momentum, so being able to land on a slope with a left/right point with no effect to your horizontal velocity is strange behavior compared to landing on one with your middle point and having it add some.

Disch wrote:

My first incling is to check a few pixels beneath the center point. If the center point is "almost" grounded:

- "snap" to the floor if you're already grounded
- or resume falling and ignore the floor overlap if you're airborne


This logic seems to cover every angle I can think of. What do you guys think?


Here's a problem my own game has. How many pixels is a few? I think it runs into a "what's the difference" sort of thing. Green is where the sprite was horizontally last frame. Blue is where it is now.

Image

Can the program tell the difference between the left and right case? How? Granted that's an extreme case, but if your character can move fast enough that his center point might move far enough along for a steep slope below him to be confused for a vertical drop, it can be a problem.

Of course... something moving that fast would probably fall instead of going down the slope anyway. But this sort of thing is another problem for people dealing with slopes to solve. Any input on this one? Right now I've got my max speed capped a tad lower than I want it to be because the character can "unstick" from a slope if he's going fast enough.

My first idea is to just adjust the characters height based on how steep the slope is, rather than "move X pixels", "adjust y position to top of slope at X location". If there was some vertical pixel movement in between those two steps it would keep the character close enough to the slope for this case to be a non issue even at the highest speeds. It may work, but I've yet to really stress test the idea. Any input on this one?

And one more case while I'm at it. How about floating slopes?

Image

The issue is, gravity has pulled your character through a slope, and neither of the y positions register a "hit" on the left/right points so the player keeps falling.

Disch's method would handle the exact case above well, but checking all the bottom points is too CPU intensive for me. I already find how far a floor is beneath a point by checking two tiles, but I haven't tested quite how that works with this case. I need to update my map editor a bit before I do.

Feel free to discuss that or not. I may already have it solved. I like this topic 8)


Top
 Profile  
 
 Post subject:
PostPosted: Mon Apr 26, 2010 5:25 am 
Offline
Formerly 65024U

Joined: Sat Mar 27, 2010 12:57 pm
Posts: 2268
I'm just going to throw my 2 cents into here, it probably won't matter but here it goes....



It's apparent that other games ran into the same problem and solved it different ways, I'm sure they did their homework, too. Since they all used a semi different way to "fix" (or avoid) it, it's clear that we'll just have to pick one of these methods and run with it.....


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 31 posts ]  Go to page 1, 2, 3  Next

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 5 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group