Cartesian and Polar Co-ordinates

Introduction

I started to talk about Cartesian co-ordinates in a previous blog, and thought I'd better clarify for any non-mathematicians what that is, and then add on the concept of polar co-ordinates, which I started using sporadically from Morpheus onwards, i.e. 1987.

I'd been playing Gyruss in the arcades, and then on the C64. On my trip to Chicago in 1986 to get Uridium started on the 16-bit machines, I met the programmer who wrote the C64 version. I got interested in the circular patterns that Gyruss produced.

That was a real rushed trip as I had to get a passport and a US visa in about a week. This required trips to find the Peterborough passport office and the US embassy in London (without Sat-Nav!). Probably another blog-page could be devoted to Chicago.

 

Cartesian Co-ordinates.

We use Cartesian co-ordinates on maps and screens, amongst other things. In a 2-dimensional system we use 2 co-ordinates, by no small coincidence. Conventionally we use X for the horizontal, and Y for the Vertical. Relating that to the memory in the Commodore 64 that is used to display the screen in 8x8 pixel characters, the top left character is the first byte, the next byte is to its right, for 40 characters. After 40 bytes we get to the second character down, on the left edge, followed by another 39 bytes across.  

 

World and Screen Co-ordinates.

For a 2D scrolling game on the C64 we would have the whole map laid out in characters in a big buffer. This buffer would not be in the 16K video RAM. The map might represent an area of 6 screens wide and 4 screens deep, as a Gribbly's example. That's a buffer 256 characters wide by 80 deep, so some 20K of the available 64K of RAM. That's an estimate, I don't have my listings to hand.

 

We need to know where all of the game objects are on the map, so we need Cartesian world co-ordinates that allow us to index into the map. You might need to do that for background collision detection, and to stop objects from leaving the edges of the map.

 

It makes sense for the world co-ordinates and screen co-ordinates to be the same sign so that you can quickly translate from one to the other. The player's position in the world decides the screen scroll position, then that in turn decides everything's on-screen relative position, by a simple subtraction of their world position from the scroll position. So there's a strict pecking order. Always get the player done first, work out the "camera" position, i.e. the scroll position for the screen, then work out the rest of the objects. 

 

Again for Gribbly's, once you work out the screen relative position you can decide whether another object is on screen or not. If it's off-screen, it doesn't need a sprite. I was running 16 objects maximum, but sharing 5 sprites to display them all, so they had to share. Once an object was on screen it would keep a sprite until it left the screen area or got bubbled. That led to some brutal decisions about what happens to a sixth object trying to enter the screen area.

 

Joysticks and Screens

Non-proportional joysticks use 4 switches to detect Cartesian X and Y movement, or lack of, in 4 directions, giving 9 valid combinations, including centred. Some crude control modes just apply speeds to the player based on the joystick input. I always preferred to apply accelerations  to the speeds before then applying the speeds to the position,  so that the speed is applied gradually. You can also apply a different braking rate if the input direction is opposite the current movement direction.

 

Whilst there have been polar control modes, such as Lunar Lander or Asteroids, these control rotation and speed by button, it is seldom that we saw a circular proportional controller in the early days. Potentially we see those on some modern game controllers, though they might still be square, so need some software modification to the values received to make the control circular.    

 

Polar Speed

In order to get into polar speeds, you have to start manipulating vectors and work out sines and cosines. What we want to achieve is to represent the same overall speed at arbitrary angles, not just up, down, left and right. This involves working out the Cartesian X and Y components, to sub-pixel accuracy, of arbitrary angles and speeds.

 

Now the C64 doesn't have any floating point support, and not even a multiply instruction. Fortunately, I wasn't really thinking mathematics, I was just thinking that I wanted to get some pretty effects  You have to be thinking in hexadecimal for ways to do things. The key is always the Power of Two. I needed some sines and cosines, and a way to multiple them by speeds to get pixel distances.

 

You also need to be able to convert from Cartesian to polar so as to work out in which direction an arbitrary object lies, and how far. We managed to find an approximation routine that was much quicker than doing the big calculation. Also, polar vector addition is easiest carried out by converting to Cartesian, adding, and then converting back to polar. Gravity sometimes needs to be applied to objects that are moving polar. You can choose to switch from Polar to Cartesian once you've started. It's rare that you want to continue with polar movement in an environment with gravity. That's a major difference between a top-down game and a side-on game.

It's more useful to know the polar direction to a target than the distance, though the Paradroid 90 robots could only "see" a certain distance. If your polar calculations are accurate rather than fast, then you could use them for collision detection. Our 16-bit algorithm was accurate to about 10%, which is enough for visibility, but we didn't use it for collisions. The algorithm has been published, we didn't invent it, but it was based on making a guess and looping about 3 times improving the guess, which involved a square root calculation, so we didn't want to be doing that too often. Nowadays you can get fast accurate answers in floating point.

 

Sometimes you might not be moving in the same direction as you are facing. Imagine a drift car driving round a track, so you might want to store an object's facing direction separately from the movement. The two will want to align over time, but certain actions might cause them to differ.
  

Morpheus

I had been playing an upwards scrolling top-down shoot-em-up on my Amiga and something caught my eye. In the grand scheme of things it wasn't particularly important, but it irritated me. A ground-based turret fired 8 bullets at once, spaced at 45 degrees, so up, right, down and left and the 4 diagonals. In the real world, the diagonal bullets would come out at the same speed as the others, forming an octagon, but these came out in a square shape.

 

Now I can see that the initialisation would be minutely quicker when setting the 8 bullets' speeds. You just use zero and one value for the various X and Y speeds, either negative or positive. If you just had a lower X and Y speed for the diagonal bullets, which you can work out in advance, you can get a better pattern, and equalise the overall speeds of the diagonal bullets.

 

I got to thinking then, that I'd like to do some pretty patterns with pixels firing from the middle of the screen, This all ended up as the title screen on Morpheus, as well as the background stars for the game, and is all part of the control mode too.

 

I decided that I needed some sine and cosine values to represent a number of angles. Now you might have been told at school that there are 360 degrees in a circle. I am here to tell you that they got that wrong, there are 256. At least there are in the computer world, the Matrix, if you will. Looking up values in a 256 byte table is a nice easy task for the CPU, and I believe I repeated 64 values from the beginning to be able to add a quarter of circle to the sine values to get the matching cosines.

 

I sat there with my hex calculator and worked out the hex values for the 256 direction sines using SOH-CAH-TOA that we had been given at school: Sine equals Opposite over Hypotenuse, Cosine = Adjacent over Hypotenuse and Tangent = Opposite over Adjacent. We know the hypotenuse is a constant sweep of a clock hand round the clock face. Due to the low level of accuracy, some 8-bit values came out the same, but when the sine of two next-door angles came out the same, the cosine would be different, and vice versa, so there was no duplication.

 

I then had to choose a scale for the speed. This is largely arbitrary, but depending on our calculation method we need to work in whatever units make the CPU maths easiest. Again, we want to be working to a few binary places of sub-pixels to get some accuracy. Nothing much is going to be moving more than 8 pixels a frame, bearing in mind that we are moving everything at the magic 50 frames per second. Anything going at that speed will be across the screen in less than a second. 

 

I do recall that for the Amiga polar system I considered increasing the number of possible angles to 1024, another finely-rounded number. The thought of working out that many values and typing them into the assembler put me off, we stayed with 256, which I still re-calculated to higher accuracy. The polar distance of 1 pixel was $0400, and the sine table values were 14-bit signed numbers this time. When the polar speed was multiplied by the appropriate sine value, we got a 32-bit answer with the number of pixels in the top byte, and the part pixels in the rest. We would then have arithmetic-shifted the number 8 bits to the right to give us 16 bits of pixels and 16 bits of sub-pixels. The world and relative co-ordinates would be in that scale, giving 10 screens wide using the positive numbers.

I also remember keying in the original set of 256 8-bit values for the sine table, and testing them all. There were a few typos which showed themselves up when I rigged up a test-bed to fire a group of pixels at slightly different angles at once. 

I think Steve Turner found all this polar nonsense rather bemusing at first. Sure, I could get some pretty explosion effects, but what was the point? Little did we realise that soon enough we'd be doing MotoX on the PlayStation and we'd be needing the polar knowledge.

 

Intensity

The player and drone ships in this game use polar movement. The joystick Cartesian input is converted to a polar desired direction and the player ship swings round to that direction in a smooth curve. I was just trying something different. The drone follows a polar path too, which can be seen if you give it a new destination while it is in flight.

The meanies are all using polar movement to track the crew, though the final fizzing meanies take a zig-zag path to the player ship. They still need to know the polar direction as they are modifying that target direction for their flight.

 

Paradroid 90

The robots in this game are using polar movement and firing. The heads of some robots swing round too, and line-of-sight is used by most robots. Hence you can sneak up behind many of them. Since many also have hearing, if you fire then they will turn to face you, and fire back, of course. The polar routines are used all over the place to allow the robots to fire at any angle to hit the player. They rarely miss.

 

Fire and Ice

Polar movement is used for the various ice weapons, but then Cartesian gravity is also applied. You can see the multiple ice bullets fire in a neat spray but get distorted by gravity. There was a lot of simulated physics going on in this one as I encoded the ground characters with slopes and allowed the ice to roll down the slopes.

The trickiest bit was stopping the ice still when it rolled slowly into a valley, as the small accelerations due to the two adjacent opposite-slope pieces kept the ice oscillating.  The puppies also apply a bit of physics to be able to jump to another platform. It's the same physics equation that the Gribblets use, which also make an appearance here.

If you know what gravity acceleration you have, and you know you want to jump to another height in 16 moves, then you can work out what initial velocity you need. I worked this out at run-time every time, but actually in Gribbly's there are quite a limited number of possibilities so I'd have been smarter to store the limited number of answers in a look-up table. I still think it looks really clever when the Gribblets or puppies jump upwards or downwards.

 

Uridium 2

The homing missiles all use a polar homing algorithm, the Uridimines do not. I'd seen the homing missiles of the arcade game SlapFight, and thought that they take a lot of the hassle out of the game, but then noted their cheeky nod to the plight of polar homing. Since they can only turn at a certain rate, then if they skim past a target they have to go round again, and can quite easily miss again. They seem to let the homing missiles come out straight a fair way before chasing the target. They may be including a minimum distance from the target before going into chase mode. 

My solution was slightly different: initially the homing missiles come out of the Manta forwards, and then select a target. If there isn't one they'll go forwards until there is a target, or they leave the screen, this doesn't usually happen as there are nearly always plenty of targets. If the homing missile manages to go round 360 degrees on full lock it knows it must be going round the target, so it goes into enforced straight flight for a couple of cycles and then starts homing again. You might only see that happen once a game, it happens real fast, and you're probably too busy to notice, but you would notice a homing missile going round and round not hitting the target.

 

I did one time get interrupted at work by a guy's email asking how the Uridimine algorithm worked. The email came to me via the managing director and HR, so that got rather embarrassing. Please don't do that to people.

 

Just for the record then: the Uridimines simply accelerate by, say, 1 pixel per cycle in the X direction towards the player, and do the same in the Y. The X and Y speeds are then capped to within, say, 5 pixels a cycle. It's really dirty, and rather embarrassingly means they move diagonally faster than horizontally or vertically, where they oscillate.  Fortunately you have nothing to compare them with because the Uridimines all chase the player from the off! The top speed has to be less than the Manta's top speed, as they are intended to tempt the player to rush off at high speed, or loop to height to avoid a collision. I wish I'd done an enemy ship that released a whole swathe of them. Maybe next time... I can't think of a reason why they shouldn't go high and be able to take out the Manta in a loop either.

 

3D Cartesian Co-ordinates.

All 3D games that allow flight will be using some kind of 3D polar system, along with their 3D Cartesian co-ordinate system. As well as an X and Y co-ordinate, we add a Z. Conventionally the X and Y usually go across the ground surface, and Z is the height.

 

There are 2 different ways that have been used to do that, wouldn't you know it?  They call then left and right-handed systems. If you keep X going left to right and Z going up, in a left-handed system the Y comes towards you, in right-handed it goes away. DirectX uses a left-handed world. I'm fine with that; it's about time us left-handers had a say.

Then there's the screen pixel layout. Traditionally we managed with X going left to right, and Y going top to bottom. You can use the X and Y co-ordinates to simply and quickly (thanks for the catchphrase, Rich) calculate the address and pixel position for plotting. This all changes on the PC, but that's another story, for another blog. Also maybe the story of how we can simply build a ladder to the moon (out of matchsticks). Easy to ask...

My issue with 3D is that everything has to be done properly. Uridium cheated in that the Manta bullets could go high to hit the enemy ships that flew over the player, and could go low to hit ground targets. Viewed directly from above you can't tell that's ambiguous. Maybe the Manta is firing two bullets, one high and one low, with Bluetooth so that if one detonates, so does the other? Hey, if one photon can pass through two slits then anything's possible! 

If we ever get a 3D Uridium then there will need to be some extra guns on the Manta, and the control mode is going to be more extra-dimensional. Lucky there are more controls on a game controller these days.