I'm in my first year of Game Dev. and I'm just getting into programming for sprites. When I sat down and started thinking about how to move a sprite in circles and ellipses, things got a bit tricky. I found some equations, but it got me to thinking:
How'd they ever manage to do this stuff on the NES? I mean, I'm guessing there's no opcode for sin or cos functions in 6502 assembly... So what did they do?
Lookup tables: they had pre-generated tables for sines, cosines and tangents of several angles and looked up in those tables when needed. Intermediate angles could get rounded up, rounded down or interpolated. Similarly, they also had tables to calculate the arcsine, arccosine and arctangent when they were needed.
Besides interpolating values in lookup tables, there are also tons of clever algorithms to calculate circular and other types of spline paths by using additions and subtractions only (or at most a few multiplications per path). These were quite popular in the days when every single clock cycle mattered (modern game programmers have it really easy).
Well, almost. In fact, some of the algorithms are still pertinent even today. For example, OpenGL has no direct support for drawing circles, but it has support for drawing a bunch of individual pixels very efficiently. If you needed to draw tons of circles as fast as possible, even on a modern computer, you could go the lazy way of using sin/cos or the sqrt methods, but that would be needlessly wasteful. In fact, it's possible to draw a circumference of pixels using integer additions and subtractions only (something like 3 or 4 of them per pixel; I don't remember the exact algorithm right now) and a couple of conditionals (per pixel). (If you need to draw a filled circle, it's simply a matter of drawing horizontal lines from edge to edge, which is something that hardware also supports.)
Most opengl circle drawing tutorials you find out there will use the lazy way of drawing lines using sin/cos, but as said, that's the inefficient (and inexact) way of doing it (it's inexact because you are not going to calculate the coordinates of every single pixel with sin/cos, only a few of them). However, as said, it's possible to do this without having to resort to those heavy-duty functions, restricting yourself to a few integer additions/subtractions per pixel, which is really efficient.
(OTOH, nowadays you often would want to draw an antialiased circle, which is quite a lot more complicated than drawing just a circumference of pixels. If the hardware line drawing supports antialiasing, at least you get that for free if you use the sin/cos + line drawing method.)
Joined: 11/22/2004
Posts: 1468
Location: Rotterdam, The Netherlands
Yeah, it only really needs to look like a circle. I've never actually programmed a "pseudo circle" like that before but I imagine there should be plenty of information out there on how to achieve this.
Think of circular movement, but without the y axis. That looks a lot more simple and attainable without using sin/cos, right? If you manage to make a simple algorithm that can make something move slowly at the start and end, and fast in the middle, you could use that on both the x and y axes and you'd have something that, with some tweaking, would look a lot like a circle.
Warp:
Ya, I've been thinking there had to be something like that. I mean, quadratic motion can be done with only addition by calling a function that adds one vector X, Y (acceleration) to another (velocity) which is in turn added to a final one (position) every frame. And if a parabola can be made like that, why not any conic section?
I'm dealing with cyclical motion rather than drawings of circles but it seems like the same algorithm should be able to work if the "pixel" is used as the sprite's X, Y position instead (given some tweaking to account for the speed of the orbit). Do you remember if the algorithm had a proper name I could try googling?
Cyclical motion -- do you mean just motion in a cycle? Like, f(t) = position, and f(t + k) = position, and f(t + 2k) = position, etc.? Depends on the kind of motion you want in that cycle, of course. :)
Or maybe you mean sinusoidal motion, like the medusa heads in Castlevania? In that case, x_t = x_(t-1) + k, and y = sin(t). In other words, x position advances by a constant each frame, and y position is determined by a sine function (or approximation thereof).
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
The function sqrt(r^2 - x^1) gives you a nice half circle. So, if you want to draw a circle at point (x,y) with a radius of r, you could do so using something like:
for (i == x - r + 1; i < x + r; i++)
{
draw_point(y - sqrt(r^2 - (i - x)^2));
draw_point(y + sqrt(r^2 - (i - x)^2));
}
Now, I'm not sure how well you can approximate square roots in 6502, but this should be a lot more useful than sine/cosine stuff.
Derakon: I mean cyclical motion of the kind used by the Rotodiscs in Mario 3 (The glowing balls with the grid pattern that orbit around certain blocks).
I figure that if I can get that straightened out there ought to be a fairly straight-forward way to derive more complex patterns like ellipses, hypotrochoids, hypocycloids, etc. Or, then, I suppose that if I had a decent approximation of sinsoidal motion I could derive a circle from that.
Derakon: I mean cyclical motion of the kind used by the Rotodiscs in Mario 3 (The glowing balls with the grid pattern that orbit around certain blocks).
I figure that if I can get that straightened out there ought to be a fairly straight-forward way to derive more complex patterns like ellipses, hypotrochoids, hypocycloids, etc. Or, then, I suppose that if I had a decent approximation of sinsoidal motion I could derive a circle from that.
The fire bars in SMB1 just used a pre-built lookup table for the offsets to place the fireballs at.
The function sqrt(r^2 - x^1) gives you a nice half circle. So, if you want to draw a circle at point (x,y) with a radius of r, you could do so using something like:
for (i == x - r + 1; i < x + r; i++)
{
draw_point(y - sqrt(r^2 - (i - x)^2));
draw_point(y + sqrt(r^2 - (i - x)^2));
}
Now, I'm not sure how well you can approximate square roots in 6502, but this should be a lot more useful than sine/cosine stuff.
If you read what I posted, you'll see that it's not necessary to resort to such a heavy-duty function as sqrt in order to draw a circumference of pixels. A few integer additions and subtractions per pixel is enough, using a clever algorithm.
As for a cyclic motion, if it doesn't have to be exactly a sine wave, it can be perfectly well and efficiently approximated with a parabola (in other words, the x2 function) which you mirror and repeat (which, like the circle, can be created with just a few additions and subtractions per point, but the algorithm is even simpler than with the circle drawing).
Joined: 11/22/2004
Posts: 1468
Location: Rotterdam, The Netherlands
Warp wrote:
If you read what I posted, you'll see that it's not necessary to resort to such a heavy-duty function as sqrt in order to draw a circumference of pixels. A few integer additions and subtractions per pixel is enough, using a clever algorithm.
Do you have an example of such a simple/optimized algorithm? Would love to see how they did this sort of thing in practice.
Actually the circle-drawing algorithm given there is not completely optimal because it draws some pixels twice, and uses a needless multiplication by 4 (even though you can optimize it to a left-shift which, in fact, can be slower in some architectures than an integer addition).
I actually once deduced the circle-drawing algorithm all by myself, just for the fun of it.
The basic idea is that you start from one of the points where the circle intersects the main axis (we can assume the circle is centered on the origin, as translating the pixels to their actual location can be trivially done when drawing the pixels), eg. from x=0, y=radius, and then start moving to the right one pixel at a time and keep updating the distance of the new pixel from the origin at each step. If this distance becomes larger than the radius, you decrement y by one (and update the distance variables, of course). While not immediately obvious, it is possible to keep this distance updated using a few integer additions. When you reach the point where x==y, you are done. (You have calculated an eighth of the circle, but the other eighths can be trivially drawn because of symmetry.)
I actually dug up an implementation I once made. It's very optimized in that it never draws the same pixel twice (as is extremely common in implementations you find on the net), and uses only integer additions and subtractions for each pixel, nothing else. (Note that the majority of the code below is the pixel drawing. Each calculated pixel must be duplicated 8 times on each symmetry axis, plus the first and possibly last four pixels have to be drawn separately if we want to avoid duplicated pixels.) Have fun trying to figure out why the algorithm works.
Language: cpp
void drawCircle(int cx, int cy, int radius)
{
int f = 1 - radius;
int ddF_x = 1;
int ddF_y = -2 * radius;
int x = 0;
int y = radius;
drawPixel(cx, cy + radius);
drawPixel(cx, cy - radius);
drawPixel(cx + radius, cy);
drawPixel(cx - radius, cy);
while(true)
{
if(f >= 0)
{
y--;
ddF_y += 2;
f += ddF_y;
}
x++;
ddF_x += 2;
f += ddF_x;
if(x >= y) break;
drawPixel(cx + x, cy + y);
drawPixel(cx - x, cy + y);
drawPixel(cx + x, cy - y);
drawPixel(cx - x, cy - y);
drawPixel(cx + y, cy + x);
drawPixel(cx - y, cy + x);
drawPixel(cx + y, cy - x);
drawPixel(cx - y, cy - x);
}
if(x == y)
{
drawPixel(cx + x, cy + y);
drawPixel(cx - x, cy + y);
drawPixel(cx + x, cy - y);
drawPixel(cx - x, cy - y);
}
}
Let's see.
ddF_x starts at 1 and becomes 3, 5, 7 and so on. These are the differences between consecutive squares - e.g. 4 - 1 = 3, 9 - 4 = 5, 16 - 9 = 7...
f is the residual, the amount of un-sqrted distance that is left over. Every time x is incremented by one, it's updated by the new amount of un-sqrted x distance that it has. Similarly, every time y is decremented the amount of un-sqrted distance lost is added to f.
The only thing I can't figure out is why f is set to 1 - radius in particular, but I get the principle.
The only thing I can't figure out is why f is set to 1 - radius in particular, but I get the principle.
Note that if you started with a distance of exactly radius, the distance of the next pixel would immediately be too large and hence the y coordinate would be decremented immediately. This would cause all circles to have ugly single pixels poking out of each four main directions. To alleviate this problem the radius is effectively incremented by a half pixel. IIRC correctly the initialization is related to that (it has been so long since I figured out and understood the exact algorithm that I don't remember it precisely right now).
Btw, just clear up possible confusion, I would like to point out that the code I posted is not originally mine (although I wasn't sure when I posted it because I couldn't remember). I did figure out the algorithm (or something very similar) all by myself many years ago, and implemented it. However, for this particular implementation I looked up an existing algorithm called midpoint circle algorithm. (You'll probably recognize the variable names in that wikipedia article.) The only thing I did was to modify it slightly so that no repeated pixels would be drawn.
Joined: 5/1/2004
Posts: 4096
Location: Rio, Brazil
I was wondering how did they manage to do some of the apparently complex collision detection. Take Double Dragon 2 for example, how did they calculate where you can walk and where you can't? I mean, right on the first screen you can walk on a rectangular floor, but on the next screen the floor grows diagonally, and the collision there seems pixel perfect. I think the same goes for games like mac kids, super mario 3 or kirby's adventure where there are ramps. How do they calculate that?
I was wondering how did they manage to do some of the apparently complex collision detection. Take Double Dragon 2 for example, how did they calculate where you can walk and where you can't? I mean, right on the first screen you can walk on a rectangular floor, but on the next screen the floor grows diagonally, and the collision there seems pixel perfect. I think the same goes for games like mac kids, super mario 3 or kirby's adventure where there are ramps. How do they calculate that?
Note that these games only use "45 degrees" ramps. Those 45-degrees slopes don't even need to have lookup tables because y(x+1) = y(x) + 1. It's easy to code such collisions with only addition/subtraction operations.
BTW, there's great article from the programmer of MC Kids: http://games.greggman.com/game/programming_m_c__kids/
Note that these games only use "45 degrees" ramps. Those 45-degrees slopes don't even need to have lookup tables because y(x+1) = y(x) + 1. It's easy to code such collisions with only addition/subtraction operations.
The same goes for further bisections, which are just y = x >> level, where "level" how many times the angle has been halved (45 = 1, 22.5=2, etc).
Joined: 5/1/2004
Posts: 4096
Location: Rio, Brazil
AnS wrote:
FODA wrote:
I was wondering how did they manage to do some of the apparently complex collision detection. Take Double Dragon 2 for example, how did they calculate where you can walk and where you can't? I mean, right on the first screen you can walk on a rectangular floor, but on the next screen the floor grows diagonally, and the collision there seems pixel perfect. I think the same goes for games like mac kids, super mario 3 or kirby's adventure where there are ramps. How do they calculate that?
Note that these games only use "45 degrees" ramps. Those 45-degrees slopes don't even need to have lookup tables because y(x+1) = y(x) + 1. It's easy to code such collisions with only addition/subtraction operations.
BTW, there's great article from the programmer of MC Kids: http://games.greggman.com/game/programming_m_c__kids/
Wow that article is gold. I once found a discussion about people liking or disliking m.c kids and one of the developers humbly jumped in to say that he was amused people were talking about the game.
The fire bars in SMB1 just used a pre-built lookup table for the offsets to place the fireballs at.
I doubt SMB3 would be much different.
Nah, I've compared the way the fire chains chunk along into 1/32nds of a circle, and rotodiscs don't do that. Their movement is much smoother, changing position every single frame.
put yourself in my rocketpack if that poochie is one outrageous dude
struct point{int x; int y;}
class rotator()
{
point center;
point pos;
int xvel; int yvel;
void move()
{
if (pos.x < center.x) {xvel += 1;}
if (pos.x > center.x) {xvel -= 1;}
if (pos.y < center.y) {yvel += 1;}
if (pos.y > center.y) {yvel -= 1;}
pos.x += xvel; pos.y += yvel;
}
}
It's something I just quickly wrote, but isn't this a way you could approximate a circular path without having to worry about sin/cos code?
I used structs and classes for readability sake, but all you need are the six variables: 3 x,y pairs for the position, center, and velocity.
Basically, all it does is orbit the center by accelerating towards it. You could use similar code for a wave by just making the horizontal a constant speed.
That won't trace a circular path, though.
At any point on a circular orbit, your acceleration is a constant value. If you're constantly changing both dimensions of that acceleration by the same linear rate, it's going to be taking on different values (because, if you think about it, the net acceleration would trace out a line not a circular arc).
Joined: 11/30/2008
Posts: 650
Location: a little city in the middle of nowhere
I was about to say the same thing. Anyway, if you have a point exactly on the circle, you can find the velocity without calculating acceleration first, because it will be a tangent to the circle. Say the centre of the circle is the origin, the gradient of the tangent will be -x/y.
Note that these games only use "45 degrees" ramps. Those 45-degrees slopes don't even need to have lookup tables because y(x+1) = y(x) + 1. It's easy to code such collisions with only addition/subtraction operations.
How they managed to implement the game engine for NES Solstice is much more impressive (given that the NES is tile-based and has one single tile layer). Most people don't realize it, not even those who have played the game, but quite some ingenuity had to be put into it.
