[tokumaru]

Hey everyone. As some of you might remember, I've been working on a Sonic game for the NES (for a long time now, but it's hard to find the time to do it). So, with a decent scrolling/rendering engine capable of displaying large level maps working, it's time to think about programming the Sonic object.

We all know that what makes a Sonic game deserve that title is the physics, not the blue sprite, so I want to code a character that's as fun to control as his MD/GEN counterpart, but the problem is that I don't have the same CPU power as the original games. I don't think this is a reason to be extremely worried about, because the Master System games for example had very different physics but were still enjoyable in their own way (it wasn't frustrating that Sonic didn't move exactly like he did on the 16-bit games, at least not for me).

Recently I've been reading the Sonic Physics Guide, to know the basics about how the 16-bit games work. I found that many of the solutions I had thought of were similar to what was presented in that guide, but there are several details that are hard to figure out without deeper investigation, such as when each type of force is or isn't applied, the exact values of those forces and things like that, so it was a very interesting read.

So after looking at the original physics, my conclusion is that the constant multiplications needed to convert the speed into horizontal and vertical components (and everything else that deals with sines and cosines) are probably the the most CPU-intensive parts. I don't remember if the 68000 has built-in multiplication, but the 6502 (the NES CPU) certainly doesn't, so I'd like to keep multiplications to a minimum.

Anyway, the reason for this thread is asking you guys what kinds of simplifications you think could be done in order to reduce the CPU load while processing the Sonic object, without sacrificing the fun. If anyone knows a bit about how the SMS games work as opposed to the 16-bit ones and wants to share, that would be great. I don't want to copy the 8-bit games exactly though, because I want to do things they don't, like making jumps perpendicular to the floor.

I think I'm going to use the quadrant thing, where different modes (floor, right wall, ceiling, left wall) are used to keep Sonic attached to the "ground" depending on his angle. I'm thinking about not converting the ground speed into horizontal and vertical components though, and just using it directly as fully horizontal or fully vertical, depending on his angle, while the other coordinate just follows the ground. Maybe with careful calibration of the resistance of the slopes it will not feel so different. About the perpendicular jumps, that can possibly be done using look-up tables for each possible angle, since the initial force for the jump should be constant.

If you have any interesting ideas, let me know. Also, if you foresee any problems that these simplifications might generate, that will be nice to read too. Thanks in advance for any suggestions!

[Glitch]

The sms games don't use the inertia/angle system of the megadrive games. Like the 6502, the z80 lacks mul/div ops (the 68k does have mul/div, btw). Sonic's position coordinates are stored as 16.8 fixed point variables, along with horizontal & vertical velocity in 8.8 fixed point. With each iteration of the game loop the velocity variables are added to the respective coordinates. A "slope type" index is encoded in the collision data. When sonic is moving over a slope, the x-velocity is adjusted using a value from a lookup table. Basic, simple stuff. This simplicity means that the loops/quater circles have to be custom coded and triggered when the player reaches a certain point in the level.

I'm still trying to find a nice efficient way of emulating the megadrive physics without resorting to software mult routines.

[tokumaru]

I see... I want to do it kinda like you described, but also applying this basic system to the walls and the ceiling and having Sonic stick to the different types of surfaces based on their angles, so that loops don't have to be scripted.

I'm considering having the ground speed affect Sonic's main axis (X for floors or ceilings, Y for walls) and using the resistance of the slopes to compensate for the ground speed not being divided between both axis, but actually using multiplications for jumps. If it's just a matter of deciding how much of the speed goes to X and how much goes to Y, one multiplication is enough to find one of them, and the other can be calculated by subtracting the calculated speed from the whole speed. One multiplication every once in a while (as opposed to several every frame) doesn't seem so hard to pull off.

I'm still trying to find a nice efficient way of emulating the megadrive physics without resorting to software mult routines.

Are you working on a project that requires this or is it just an exercise? =)

[Glitch]

I'm planning on making some changes to the S2 physics for Sonic 2 LD. Some of the physics from the megadrive version are going to be impossibly hard to emulate with the current system. We need something a bit more flexible without sacrificing too many cpu cycles.

[tokumaru]

Hey Glitch, I've been thinking about this, and maybe the original physics isn't as CPU intensive as we might think at first. I guess that what scared me was the fact that the Physics Guide is written with high-level languages in mind (because that's what most people use to recreate Sonic), but when you think of the optimizations that can be done in assembly, it's not so bad.

There are very few multiplications, that are only needed to split the angular speed into vertical and horizontal components. Two multiplications (one for each axis) are needed per frame when Sonic is on the ground, and two multiplications are needed far starting jumps. Since each pair of multiplications consists in multiplying the angular speed by the sine and cosine of the angle, we can do both multiplications at once, using the bits of the angular speed to decide when to add. Doing that once per frame shouldn't be that bad, specially if you use an unrolled multiplication routine.

From what I remember of the rest of the guide there are no more multiplications, only additions and shifts. So I think I just might be able to stay true to the original engine. Of course that our problems are completely different, and modifying an existing engine is more difficult than making one from scratch. I can optimize other things so that Sonic gets a little extra time, for example, but that would be hard to do when hacking a game (and I seen to remember there are several things in the SMS games that are not very optimized).

[sonicblur]

You can pull it off without any multiplication or division, with some assumptions and a carefully created lookup table. (Warning: This is purely untested theory.)

Considering the limitations of the NES, I assume you might use an 8-bit signed byte to represent the ground speed on a scale of -128 to 127. Let's say that the maximum speed you want to move in either direction would be 15 pixels per frame, thus if you were just moving on flat ground you'd end up with (gndSpd>>3) as your X speed. Let us also assume that your possible angles of rotation are limited to 5 degree increments. (5, 10, 15, 20, etc)

If we were just considering the X and Y speeds at a full ground velocity of 127, you'd only need 18 entries in your lookup table because you can stop right before 90 degrees and handle the mirroring in code. And you don't need separate lookup tables for X and Y since Y speed = gndSpd - X speed.
Now if we consider again that we wanted our maximum speed to be 15 pixels per frame in either direction and ignore 0 that leaves only 270 entries needed for a lookup table to cover every possible outcome of 5-degree increments up to 15 pixels a second. Since you can't move a fraction of a pixel, I don't think there's any harm in shifting that precision away to calculate how far you move horizontally and vertically. And besides, you still have 127 distinct speeds to travel at, allowing you to provide smooth acceleration and slowdown.

What do you think about this? It's the closest to the methodology described in the Wiki that I can think of.


Alternatively, there might some way to adapt Bresenham's circle algorithm to be useful here. I'm not even sure if it would be feasible, but I figured it wouldn't hurt to suggest it. You'd probably need to choose a radius that provides the appropriate number of steps you need to make it around the circle based on the number of angles you want, and set aside a few bytes of memory to keep everything around. Every time you want to switch angles, run an iteration of the algorithm in the appropriate direction. I think you'd want to move based on your X and Y in the virtual circle, but that doesn't take velocity into account. The idea sounds promising though, maybe now that I've mentioned it someone could think up how to apply it.

Figuring out how to do this with integer math has been on my list of things I've wanted to do for some time now, maybe I'll look into it more if nobody comes up with a solution before then. (Although my own agenda would be to do it in 16-bit integer math which would provide a bit more precision.)

[nineko]

Y speed = gndSpd - X speed.

Actually, X² + Y² = gndSpd². But I get your point and it makes perfect sense. Lookup tables might save a lot of processing time. And by reducing the allowed angles this might really be feasible.

[tokumaru]

Considering the limitations of the NES, I assume you might use an 8-bit signed byte to represent the ground speed on a scale of -128 to 127.

I'm considering using 8.8 precision for the speeds, because I fear that anything less will feel very different from the original.

Let's say that the maximum speed you want to move in either direction would be 15 pixels per frame, thus if you were just moving on flat ground you'd end up with (gndSpd>>3) as your X speed.

I think that using only 3 bits for the fractional part might be too little.

Let us also assume that your possible angles of rotation are limited to 5 degree increments. (5, 10, 15, 20, etc)

It would probably be better to use something more computer-friendly, such as dividing the whole circle in 64 or 128 units. I think that the 256 units of the original is overkill though.

And you don't need separate lookup tables for X and Y since Y speed = gndSpd - X speed.

I though so too at first, but after some calculations that doesn't seem to be the case. EDIT: Like nineko just said. =)

Since you can't move a fraction of a pixel, I don't think there's any harm in shifting that precision away to calculate how far you move horizontally and vertically.

Even though the sprite can only move whole pixels at a time, internally the Sonic object does move fractions of pixels.

What do you think about this? It's the closest to the methodology described in the Wiki that I can think of.

I think that the use of look-up tables is something to think about, but I don't think the tables will be as small as you might think. I could probably get the space for some big tables, but I'd probably need bankswitching to access them, and then in the end this approach might not be so much faster than just doing the multiplication, and considering the space needed by the tables, using a few extra CPU cycles and just doing the multiplication could be worth it. Let's see.

Alternatively, there might some way to adapt Bresenham's circle algorithm to be useful here.

Now that' a bit too experimental, don't you think? =) I wouldn't like to try such a radically different approach without being sure that it looks promising. So far the original approach doesn't sound so complicated, at least not as much as I first though it was, so I'll try to be as faithful to it as possible.

I'm confident that it can be done on the NES without problems, and I'm sure there's enough CPU power for Sonic to move around without any slowdown. My fear is that there might not be enough time left for the remaining game objects. If that's the case, then I'll have to simplify Sonic.

(Although my own agenda would be to do it in 16-bit integer math which would provide a bit more precision.)

Working with 16 bit values on the 6502 is not such a difficult thing, it's just a bit slower. I plan to stick to the precisions used by the original engine (16.8 for coordinates and 8.8 for speeds).

This post has been edited by tokumaru: 04 February 2010 - 05:12 AM

[Mercury]

I find this a very interesting subject. Two things:

I think I'm going to use the quadrant thing, where different modes (floor, right wall, ceiling, left wall) are used to keep Sonic attached to the "ground" depending on his angle. I'm thinking about not converting the ground speed into horizontal and vertical components though, and just using it directly as fully horizontal or fully vertical, depending on his angle, while the other coordinate just follows the ground. Maybe with careful calibration of the resistance of the slopes it will not feel so different.

If you use resistance values (found in a look-up table based on the angle of ground tile, I'm assuming) to attenuate the main axis, and just have the secondary axis follow the ground, how will you maintain Sonic's velocity when he leaves the ground? The main axis would already be correct, as it would have been affected by the resistance. The secondary axis could be determined by subtracting Sonic's previous position from his current one, I guess?

Sonic doesn't stop when he jumps (ie the jump velocity is added to his currently velocity, it doesn't replace it), so his velocity needs to be maintained when he a) runs off a cliff (though there aren't many slanted cliffs); b) jumps while on a slant; and c) comes detached from the ground while in the lower angles of the Wall quadrants because his speed is too low. (Though I've always wondered why he doesn't only do so if his angle is >= 90 or <= 270, so he wouldn't "fall" with ground still beneath him, and land again so soon because of it.)

About the perpendicular jumps, that can possibly be done using look-up tables for each possible angle, since the initial force for the jump should be constant.

Frankly, it's kind of annoying to jump at an angle when the slant you're on is so shallow. In Sonic 1, the slanted platforms (like the ones that catch fire in MZ) keep Sonic's angle at 0, so he jumps straight up even when he's on a slanted surface. What I'm saying is, the look-up table doesn't need to be very large, because his perpendicular jump angle doesn't need to be that precise. You might subdivide the circle into 64 or 32 parts (as opposed to the 256 of the original), but he might only need about 16 different jumps to feel okay.

Good luck!

[tokumaru]

If you use resistance values (found in a look-up table based on the angle of ground tile, I'm assuming) to attenuate the main axis, and just have the secondary axis follow the ground, how will you maintain Sonic's velocity when he leaves the ground?

Exactly! That's the problem that made me change my mind after the first post. Right now I'm optimistic about doing the multiplication, I'll optimize the hell out of it and hopefully it will not use so much of the available time.

The secondary axis could be determined by subtracting Sonic's previous position from his current one, I guess?

While on the ground I guess I wouldn't even worry about the secondary axis, I'd just keep him stuck to the ground. When I actually needed the secondary axis I first though that I could find it using a subtraction like this, but turns out this isn't mathematically correct at all, as pointed by nineko.

So instead I have decided to do both multiplications at once. The common way to do multiplications in assembly when the CPU doesn't have built-in support for them is checking every bit of one of the factors and adding the other factor to an accumulator when the bits are set (shift-and-add method). Since both multiplications have a common factor (the ground/jump speed), we can speed things up by checking the bits of this common factor, and adding the other two factors to their respective accumulators when bits are set. This is slightly faster than doing the multiplications independently from each other.

What I'm saying is, the look-up table doesn't need to be very large, because his perpendicular jump angle doesn't need to be that precise. You might subdivide the circle into 64 or 32 parts (as opposed to the 256 of the original), but he might only need about 16 different jumps to feel okay.

I agree with you there. Thanks for your input!

[Mercury]

So instead I have decided to do both multiplications at once. The common way to do multiplications in assembly when the CPU doesn't have built-in support for them is checking every bit of one of the factors and adding the other factor to an accumulator when the bits are set (shift-and-add method). Since both multiplications have a common factor (the ground/jump speed), we can speed things up by checking the bits of this common factor, and adding the other two factors to their respective accumulators when bits are set. This is slightly faster than doing the multiplications independently from each other.

Hey, that's cool that you found a way to optimise things, but I still have a question (even though it might now be irrelevant):

The secondary axis could be determined by subtracting Sonic's previous position from his current one, I guess?

While on the ground I guess I wouldn't even worry about the secondary axis, I'd just keep him stuck to the ground. When I actually needed the secondary axis I first though that I could find it using a subtraction like this, but turns out this isn't mathematically correct at all, as pointed by nineko.

nineko pointed out that Yspeed != gndSpeed - Xspeed. I was talking about about using Yspeed = Y - Yprevious. Since it's the vertical distance Sonic's moved in the last step, it kind of has to be accurate (or at least accurate enough), right? Or is there something I'm missing?

[tokumaru]

Hey, that's cool that you found a way to optimise things

I just tried coding the multiplications, and ironically enough they were easier to optimize when done independently from each other. Depending on the speed (that varies from 0.0 to 16.0), I need between 2.5 and 3.5 scanlines worth of time (out of the 224 of the visible frame) to do both multiplications, I think that's OK.

To keep things quick I have used only 7 bits for the fractional part of the sin/cos values... Does anyone know how many the original engine uses (I'm pretty sure it's more)? From the perspective of the player, I think 7 will be indistinguishable from more than that.

nineko pointed out that Yspeed != gndSpeed - Xspeed. I was talking about about using Yspeed = Y - Yprevious. Since it's the vertical distance Sonic's moved in the last step, it kind of has to be accurate (or at least accurate enough), right?

Oh, sorry I missed that! This is an interesting idea. Whenever Sonic leaves the ground we use the difference between the 2 previous positions on the secondary axis as the speed in that axis. Yeah, I guess that should work well to keep Sonic moving at the same angle when he leaves the ground. We can only be sure if we try to actually code it that way, of course. Thanks for the idea, I'll keep it in mind in case I need it. Maybe we would still have to think of something when Sonic returns to the ground (the original seems to use a very strange logic for that).

[Mercury]

To keep things quick I have used only 7 bits for the fractional part of the sin/cos values... Does anyone know how many the original engine uses (I'm pretty sure it's more)? From the perspective of the player, I think 7 will be indistinguishable from more than that.

I'm pretty sure the table of values is in "misc\sinewave.bin" in the Sonic 1 disassembly. It looks like each value uses 2 bytes, but the first is only ever 00 or FF. This tells you the precision of the stored values, but I don't know enough ASM to be able to tell if Sonic's move code uses all their bits when referencing them.

(I'm not sure why the table repeats the first set of values, you'd think there'd only need to be 256 entries. Oh, well, I don't pretend to understand it.)

[tokumaru]

I'm pretty sure the table of values is in "misc\sinewave.bin" in the Sonic 1 disassembly.

Thanks. I'm trying to make some sense out of the length of that table. It's 640 bytes long, and since the game divides the circle in 256 units, it's weird that the size of the table is not a multiple of 256.

Oh I got it! They have values for an extra 90 degrees so that the same table can be used for sines and cosines. I used a similar trick on my NES raycaster.

So this table starts from 0 degrees, goes around the full circle and then repeats the first 90 degrees. Each value is multiplied by 256, which means they use 8 bits for the fractional part, so I guess I can sacrifice one bit for all the extra speed I'll get. =)

It looks like each value uses 2 bytes, but the first is only ever 00 or FF.

The ones starting with 00 are positive values, and the ones starting with FF are negative values. There is one value that starts with the byte 01 though, it's the one that corresponds to 90 degrees (since sin(90) = 1.0, 1.0 * 256 = 256, which is $0100 in hex).

This tells you the precision of the stored values, but I don't know enough ASM to be able to tell if Sonic's move code uses all their bits when referencing them.

Since there are only 8 fractional bits I guess it's safe to say the engine uses them all, specially on a 16-bit CPU.

(I'm not sure why the table repeats the first set of values, you'd think there'd only need to be 256 entries. Oh, well, I don't pretend to understand it.)

Heh, at first I was confused too. But like I said, my guess is that since the cosine values are the same as the sine values only shifted by 90 degrees, they overlapped the sine and cosine tables (I.e. the first 90 degrees are only used for sine and the last 90 are only used for cosine, but everything in between is shared).

This post has been edited by tokumaru: 08 February 2010 - 09:09 AM

[Master Emerald]

I forgot to say! While I was browsing the forums in the DS Browser I saw your avatar! It looked really sexy because it appeared bigger, after the NES version is ready, make a GBC counterpart so I can play it in lameboy :3.