Slope Detection Methods

[Kain]

This topic is about various Slope Detection Methods for 360 degree Sonic engines, how they can be implemented, how they can be improved, and how they can be utilized. But this intro post will be presented tutorial-style as somewhat of an overview of the two methods of Slope Detection I'm aware of. I've rarely see slope detection methods differ from engine to engine, but the fact is there are tons of ways to go about it, each having their own benefits and fallbacks.

Intro

Dynamic Slope Detection is an essential process in creating 360 engines without pre-defining the slopes of wall objects on an individual basis. The basic idea behind slope detection is that if you have two points, seperated by a reasonable distance on the surface of the wall/ground, then you can easily mathematically measure the angle from one of the points to another (see diagram bellow). (usually there is an arctan2 or similar function for this).

(note: depending on your scale, you want the points to be a certain distance apart. Too close could highlight the roughness of pixel-based sprites; too far could round off things you don't want to round off.)

Traditional Method (Method 1)

The way this concept is generally implemented in 360 engines is that points are taken to the left and right of Sonic (still inside the main collision sensor to play nice with running into walls) and they are moved down until they collide with the ground and the angle is measured from them (see diagram bellow). "Left", "right", and "down" are all, of course, defined in terms of the angle Sonic is currently moving in. Assuming the ground doesn't change dramatically over the last 5 or so pixels you moved, you expect that Sonic's going to reach the ground moving in the same direction there was ground before (cliffs and such are handled other ways). That way, you get pretty reliable estimations of a contiguous ground . There are problems with this method, but for the most part, it's great for detection of continuous on-the-ground slope checking.

The way this is performed is you define sensors left and right of Sonic, a certain distance (say, horrizontal_separation). After than, you move them one pixel down (a maximum of some number of pixels to prevent infinite loops, say max_vertical_distance) until they collide with the wall. Once they both collided with the wall, get the angle between the left and right sensors. Here's the psuedocode sans error checking:

// set the left sensor's position to a certain distance left of Sonic
Set Left Sensor's X Position to  Sonic's X position - Cos( angle ) * horizontal_separation
Set Left Sensor's Y Position to  Sonic's Y position + Sin( angle ) * horizontal_separation
// set the right sensor's position to a certain distance right of Sonic
Set Right Sensor's X Position to  Sonic's X position + Cos( angle ) * horizontal_separation
Set Right Sensor's Y Position to  Sonic's Y position - Sin( angle ) * horizontal_separation

Loop the following max_vertical_distance times {
    if the Left Sensor isn't colliding with the wall {
        // move the Left Sensor down 1 pixel
        Add Cos( angle + 90) to Left Sensor's X
        Subtract Sin( angle + 90) from Left Sensor's Y
    }
    if the Right Sensor isn't colliding with the wall {
        // move the Right Sensor down 1 pixel
        Add Cos( angle + 90) to Right Sensor's X
        Subtract Sin( angle + 90) from Right Sensor's Y
    }
}

Set Sonic's angle to the angle from the Left Sensor to the Right Sensor

Now, there are a number of ways you can optimize it. For example, you could do it in a modified binary-search type method to reduce the number of collision checks. And you could make if work better in certain situations by adding more points or extra conditions, but that's the core idea.

This slope detection method, as mentioned, is very good for on ground use. It has a few problems with sharp angle changes (nonconvergence, oversmoothing), but those are only real issues in extreme cases. The real problem with this slope detection method is that it requires a good estimate for what the angle of the slope should be (usually, the angle of the slope from the previous step is used, but when landing, 0 is used). Particularly for landing, this can be a big issue because if you're landing on a slope of, say, 75 degrees, it's going to have a lot of trouble finding it. Usually this leads to a great deal more momentum lost in landing through a quarter-pipe than you expect. In addition, if you want it to detect the angle of a wall you collided with in air, that you are not sure which direction is in, you're pretty much out of luck.

Alternative Method (Method 2)

That's where another angle detection method comes in. This method uses the same concept of determining the angle (from two points on the floor), but goes about it a different way. Instead of taking two points and moving them in one direction, you take two points and circle them arround Sonic (with a constant radius slightly bigger than Sonic's mask and an angle that changes a certain number of degrees each step) to find the two points. This method is a good deal less straightforward than the other. There are lots of ways to go about it and no obvious best way. The simplest way is to take an angle (usually the direction you are going in, but it could be completely arbitrary and still work), and follow two cases: in the case that that original angle collides with the wall, move the left sensor counterclockwise and the right sensor clockwise until, individually, they get out of the wall; in the case that the original angle doesn't collide with the wall, move the left sensor clockwise and the right sensor counterclockwise til they collide with the wall:

One major problem with this method is with the second case. If you start outside the wall and move your points in two seperate directions, there's no garentee you're going to get points from the same wall. It may be an extreme case, but you can end up with potentially disasterous results such as this:

To fix this, I implemented it so that, if it's the non-colliding case, each sensor moves in their direction until either one colides with a wall. Then whenever they colide with the wall, they fix a point to that position and have the other one move in the direction of the one that collided with the wall until if gets out of a wall. It's a little complicated to understand, so here is an animation:

It can be a tad problematic keeping track of which sensor is the left sensor and which is the right and what state they are in. For simplicity, say that the left sensor is always moving counterclockwise and the right sensor is moving clockwise. Each sensor has a variable to keep track of its state:

• If state = 0, that sensor is done checking
  
• If state = -1, then both sensors are done checking; set the new angle to the angle from Sensor Left to Sensor Right.
  
• If both states are 2, both sensors are in the ground and moving; once one gets out of the ground, you set its state to 0 and the other's state to 1.
  
• If both states are 1, both sensors are in the air and moving; once one gets into the ground, you change the other's angle to the angle you're currently at (or for consistancy, the angle from the step before), then set is state to 0 (you state stays 1).
  
• If one sensor is 1 and the other 0, this sensor is in the ground and moving; once it moves out of the ground, set both states to -1.

There's also a little bit of error checking: if one angle ever gets 360 degrees away from the other, then you have made a complete circle without changing state and the slope detection has failed.

Sample Implementations :

GM 6+ (unregisterred or registerred)

MMF 1.5

Controls:

Mouse controls where the object you're checking angles on is. Method 1 keeps track of the angle from the previous step for testing in the next step. Even if you're in the air and/or fail to detect, it'll keep it til you're back on ground or press Space.

Enter: Switch Between Methods

Left/Right: Decrease/Increase Horizontal_Distance for Method 1 and Degrees per Step for Method 2

Up/Down: Decrease/Increase max_vertical_distance for Method 1 and Radius for Method 2

Space (Method 1): Reset Angle to 0

Space (Method 2): Estimate angle based on movement (not in MMF)

(Note: I learned MMF while I made this, so my example probably isn't nearly as efficient or well-made as it could be)

Things I'm particularly interested in discussing:

• Lowering Collision Tests.
  
• Dealing with trouble spots such as sharp corners ruged terrain.
  
• Using slope detection to in an engine with arbitrary gravity direction
  
• Walking all the way up to and jumping on the very edge of a cliff.
  
• Slope detection methods I never even thought of.

[Godmaster]

Pretty useful, Kain!

But in GM6 360 engine, if Sonic is rolling/ crouching down, his main mask changes to a lower one, so the normal mask (main mask) must be bigger than 32x32.

I have already tested the mask change using a cylindric one for the main mask, and a circle for the crouch/ rolling mask. So I had problems with this, the ground collision was screwed up

How we make a perfect rolling collision?

[LarkSS]

I have another way.

Store Sonic's X and Y position into two values. After he moves a certain amount of pixels ( preferably 8 ), get the angle from Sonic's stored position to his current position and set Sonic's current position into the stored position so it can reoccur.

The advantage of this is no loop is required for sensor positioning and the angle retrieving is all based on your movement so strange sensor movement can't cause problems.

The disadvantage is that since you have to move a few pixels before the slope is detected, Sonic won't have the ability to rotate smoothly unless an interpolation technique is used.

I used this method to create slope detection in my MMF2 Sonic engine ( sig ) as I wanted to see if it was possible without sensors. Take a look if you'd like.

[Kain]

Pretty useful, Kain!

But in GM6 360 engine, if Sonic is rolling/ crouching down, his main mask changes to a lower one, so the normal mask (main mask) must be bigger than 32x32.

I have already tested the mask change using a cylindric one for the main mask, and a circle for the crouch/ rolling mask. So I had problems with this, the ground collision was screwed up

How we make a perfect rolling collision?

As mentioned, the circular slope detection method isn't really intended for ground use. It can cause distances to be too high and get weird angle detections for corners and such. It's intended for use when you have abslolutely (or little) idea what the slope is. Such as landing in extreme cases and jumping into a wall (if you wish to correctly deflect the speed). Anyway you kindof need the origin for the sprite to be about the center, and you set the radius so that a circle that size contains the entire mask (i.e. no parts or pixels are outside of it).

@LarkSS: I forgot about this method. That's actually the method I used when I was just starting out (after I tried hard-coded with poor results), before I looked at and adopted Dami's/Paradox's method (which was similar to a method I was testing with full Masks to the left/right of Sonic, but significantly better). It's not a bad method but absolutely useless for getting the slopes from landing and such. The problem is sometimes it can lead to more slope detections with the Main sensor (probably only in extreme rare cases if you code it right) and that's just as bad if not worse than a few loops of slope detections with the small sensors. However, if you regulate the distance you have to travel before calculating the slope, it can be very smooth and accurate.

[sonikku x]

Once again, posting here just so that I can view my recent viewed threads. Probably is a feature here, but I can't be bothered.

[Serephim]

the bookmark feature on your web browser works too

[StealthyMC]

I think favoriting/bookmarking would have been better than bumping a six year old thread

[Light The Hedgehog]

I think favoriting/bookmarking would have been better than bumping a six year old thread

Oh the irony... guess its not as bad though. Also can this be ported into a game engine? Or is it more just the detection part that it pertains to? No laptop access as of now.

If anyone still checks this thread.

Edited December 12, 2013 by LightTheHedgehogInSnowZone