Sonic the Hedgehog movement algorithm

Are you aiming to replicate the Genesis games?

Cause downloading the disassemblies and reverse engineering the code would probably be the best bet for doing that.

As for this, some important variables that I didn't notice in your explanation was the orientation of the character and the angle of a given piece of terrain. I think that would be helpful in developing a good algorithm :P

 

If you're worried about the angle being too precise, could you not use a function like floor/round?

 

Cyberblade,

What you have described is essentially the way that it works in the original engine. However, in the real engine, instead of always moving the player directly up, left, right or down according to path velocity -- the "movement" of the player (deltas across both axes) will be adjusted so that the velocity is applied according to the ANGLE of the current block at the original point where movement began. After this, the player sprite is adjusted so that it adheres to the "edge" of the height map for the destination "tile."

In other words, just replace the green straight lines in your diagram that are the result of player velocity (but leave the straight red lines that are part of player->edge adjustment.) Replace those green lines with angled lines of the same effective magnitude, but with an angle equal to the "slope" of the original point.

You have one "point of Sonic collision" listed. In the original engine, when Sonic is moving, there are multiple points of collision. There are always at least two that are sensitive to "vertical" collision, and one that is sensitive to "horizontal" collision, respective to Sonics orientation. These points will be adjusted (flipped/mirrored) based on the angle value of the ground tile upon which Sonic is currently traversing.

There are obviously plenty of details that I've glossed over, but this information should get you going in the right direction.

 

Dr. Ivo: The wrinkle is that Cyberblade wants his movement engine to function without the need of specifying terrain angles manually.

 

While we're at it, let's try our hand at a sprite collision detection algorithm, except we won't involve any "extra" properties of the object that we "don't want to 'manually' store" like height and width. Let's just compute those on the fly, based on a live pixel-by-pixel evaluation of the object. That should work out perfectly from the standpoint of efficiency and sensibility.


Hell, why are we even storing height maps for playfield solidity? We can rely on graphical data for everything! Who needs an extra layer of abstraction? That never solved anything in the field of computer science.

 

Yeah, real-time angle finding is a hefty processor rape. But it isn't like I can't see why he would want to do it that way. It does save a significant amount of time for putting most tiles together. If he were designing for the least amount of processing it would be another story.

 

There is never any one perfect implementation for anything in computer science, and if he thinks there's a use in developing an algorithm that doesn't need that layer of abstraction then so be it. I don't think it's a good idea personally, but I find it interesting if only for academic purposes.

Also keep in mind that while we look at the Genesis Sonic physics as the "right" way of doing things, many of things they did probably weren't provoked by preference, but rather by need; the Genesis isn't exactly cutting-edge hardware after all. If there are ways that produce better results, I see no reason why they must be shied away from. On the other hand, it's not easy to think of something that produces better results because the original programming really did do a lot of things right.

Regardless, that's what he wants to do. I don't think a discussion of whether his method is worthwhile if he's dead set on removing angle data. Of course, since he hasn't replied in a while, I'm not sure if that's the case.

 

Okay, question time.

I have, in the past, attempted to make a pixel-perfect angle-detection algorithm (given 64x64 tiles which are defined by a few basic math functions; ie: "if pixel being checked is in this tile, return true, return false, return true if under line y=x, return true if under line y=-x", etc). It didn't really work out. As such, I'm interested in setting the angles directly into the tiles themselves (and probably breaking them down into smaller tiles, like the Sonic engine does). However, I've noticed one unusual discrepancy.

First off, here's the basic gist of what I'm trying to do. In picture form!



Hopefully that's a sufficient explanation, but if you still don't get it: think of what Sonic Xtreme was being billed as. Namely, the whole "level rotates as you start walking on walls" aspect (and less the "first 3D Sonic ever" aspect). That's what I'm shooting for.

Now, obviously, this looks and probably feels a lot like Sonic's engine, albeit gravity is now the normal of the surface you're walking on, and not constantly down (and as such, you don't experience deceleration/acceleration on curves and such - but this isn't going to be a Sonic game, so that alteration is more forgivable). Thus, the more I yank from that design, the better - and the tile-based angles, while born from necessity in the Genesis games (because the Genesis isn't using a dual core processor like I am), is still probably the most efficient way to go. But this is where I encounter the problem I mentioned earlier.

Namely, tiles you can stand on from various angles. Observe!



Notice how, for this one tile, you can, according to the game concept, legally walk on both the left side and the top side of this tile. And yet, I can only assign one angle to this block. This tile is actually used all around the sides, too, so there are no less than four distinct angles that can be considered "correct" here (0, 90, 180, 270), and, depending on the level design, a single tile of this sort can be used for all four at once (ie: a single tile floating out in space, which allows you to walk on all sides of it depending on the angle you came at it from).

Any ideas on how to handle a situation like that? I'm sure the answer is staring me in the face, but I'm not sure what it is.

 

Sorry this is so late in coming (I haven't checked the forums regularly for a while), but the answer is pretty simple, and you'll probably kick yourself when you think of it.
Just add the player's current angle to the angle of the block and subtract 360 if the result is greater. Or, depending on exactly what the terrain angle represents, subtract the player's angle, and add 360 if the result is negative.

 

Since this topic is somewhat focused on the original solution to these problems...

In the original Sonic engine, there are four "all solid" tiles, each of which have a different angle asssigned to them (0, 90, 180, 270.) As a general rule, there aren't any game paths that are less than two 16x16 tiles thick. If there's something small that you can stand on, it is probably an "object." The engine is actually very limited. The best solution to problems within a game engine whose solution would reqire large amounts of code or processing time is to prevent that situation from happening by enforcing a "design rule."

 

So in other words, the desired behavior isn't even possible. Right, then I guess I'll have to take the slow, "calculate your angle every frame" route, then. Bleh.

Also, Upthorn... huh? Why are you subtracting/adding 360? The question was what constant value to give a tile that could have four separate, distinct values. I appreciate your attempt to help, but what you've got sounds more like a way to find an angle difference between the player and a tile, which wouldn't be a hassle.

 

To add to the original topic, aside from the technical issues, graphics-based collision detection is also a bad idea for Sonic games because it just means ground-level effects like grass and railings won't work unless you spend that same effort you would've saved not marking collision masks on separating out graphical flourishes into noncolliding objects instead. Better to just make a collision editing tool that lets you mark a few points and be done.

 

The point is that you can give the blocks one static angle, if the collision calculation "rotates" by the current gravity angle (which is also the current player angle). The adding/subtracting 360 is so that the angle doesn't go below 0 or above 360 degrees.
Take for instance a block with an angle of 0. If the current gravity angle is 90, you subtract 90, getting -90, then add 360 (cause it's below 0) getting 270. The block has gone from acting as a flat walkable surface to acting as a wall. Meanwhile a block with the angle of 90 would go to 0, changing from a wall into a flat walkable surface. In this way a square 16x16 block could placed hanging in the air, and each side become walkable or non-walkable as needed by gravity.