1. Computing

Calculating the relative angle between two points

To speed up collision detection in Asteroids

By

Screenshot of utility

In the Asteroids Tutorials, the precision collision detection needs to find out where two (potentially) colliding objects are located relative to each other in one of 8 orientations.

This is so the collision code can check to see which edges might touch, build an overlap box around the area of touch and see if the edges do inded overlap and touch.

As the largest Asteroids fit it in a 280 x 280 square, then if they collide the centres could be at least 560 pixels apart. To allow for a bit of space, I made this 640 x 640

The method I've chosen for determining orientation is to divide a circle into 8 x 45 degree slices (as in the screenshot above) and see in which slice the centre of one object is, if the other object is located at the centre of the circle.

So what is the quickest way to tell which of 8 orientations two objects at two points (x1,y1) and (x2,y2) are to each other? I decided I wanted to minimize calculations and use a look up table.

This would have added a massive amount of data though so as a small compromise I use Run-Length Encoding to shrink the data. More on that later.

To do this I first need to create a square 640 x 640 (actually I used 641 x 641) then draw a circle in it and divide it into the 8 octants. As it involves graphics, I used C# and Winforms to do it.

The .NET framework has some excellent and fast graphics routines and the Graphics object FillPie method suits admirably.

  • Download the source code (zipped up) juxta.zip. This also contains the binary (compiled on my safe PC) and will output the compressed points in cpoints.csv and all points as graphics in points.txt.

It takes a brush, a rectangle (square in this case) that completely covers the whole circle and two angles. I made it slightly smaller as when I did it to the full rectangle, it went slightly outside. Start angle (relative to the X axis) and how many degrees of sweep.

I picked eight colors from the System.Drawing colors list and put them in an array of Color[8] colors. I also created another 8 element array argbs[8] to hold the argb value of each corresponding color. When doing color comparison, it's much easier and faster to work with the int argb value. It's the 32 bit value derived from AARRGGBB where AA is the 8 bit alpha component (for transparency) and RGB are the Red, Green and Blue color value.

This event handler code draws a circle with a 45 degree slice in each of the eight colors starting with the first slice 22.5 degrees either side of the vertical axis. It creates a Bitmap then gets the Graphics Context, creates a brush with that color and calls FillPie.

The startAngle is relative to the X Axis, So if it was 0 it would draw the first (white) slice below the xa axis, starting at the three o'clock position. It also populates the argbs[8] int array that we'll need shortly.

private void btnDrawCircle_Click(object sender, EventArgs e)
{
    Cursor.Current = Cursors.WaitCursor;
    img = new Bitmap(gridwidth, gridheight);
    gr = Graphics.FromImage(img);

    var startAngle = 270-(45/2);
    const int sweepAngle = 45;
    for (var i = 0; i < 8;i++)
    {
        var brush = new SolidBrush(colors[i]);
        argbs[i] = colors[i].ToArgb();
        gr.FillPie(brush, 0, 0, gridwidth-5, gridheight-5, startAngle, sweepAngle);
        startAngle = startAngle + 45;
    }
    pb.Image = img;
    Cursor.Current = Cursors.Default;
}

Having drawn the 8 slices, the method ExtractPoints is called to find the segment index (0-7) of every point in the 641 x 641 square and put a corresponding character in each cell of a grid of the same dimensions. If the point is outside the circle, i.e. at the corners, a space character is used.

The Graphics.GetPixel(x,y) method is called to retrieve each pixel at x,y from the Bitmap. The alpha value of each pixel (c.A in the code) is 0 for those outside the circle so there's no point (pun intended!) to searching the argbs[] array to see which of the 8 segments is done.

Watching the Pixel Extraction

Just for fun, I have it black the circle pixel by pixel as they are extracted. Because it's taken from the in-memory Bitmap this isn't visible unless the PictureBox control (which is on the form), has its bitmap copied from the in-memory bitmap. That's what pb.Image = img; does.

If this is done for every pixel it's very slow as it can only do about 50 pixels every second on my PC. So in the outside loop there is code to assign the image control once every 64 lines (or once every line if the checkbox is ticked) and then call Application.DoEvents() which refreshes the aplication's display.

The grid is 641 x 641 chars = a whopping 410,881 bytes but if you run it and examine the output file points.txt. You can see it's the kind of data that compresses well using Run Length Encoding.

Each line starts with a number of spaces then is followed by a run of the same digit and so on until it hits spaces again. So it can be turned into a data format where the first number says how many spaces there are then it's followed by a number of pairs (number,character) and repeat for each of the 641 lines.

These are a few of the 641 rows after compression:

188,12,7,240,0,6,1
186,15,7,238,0,9,1
184,17,7,238,0,11,1
182,20,7,236,0,14,1
180,22,7,236,0,17,1
178,24,7,236,0,18,1
176,27,7,234,0,21,1

Looking at the first row the 188 is the number of spaces followed by 12 x 7, 240 x 0 ad 6 x 1. There's no point in storing the spaces on the right hand side.

In the Asteroids game, now the function that returns the value at x,y has to loop through this data but there are only 3-6 pairs at most so it's pretty quick. Of course if you want even faster speed then use the 410K data instead.

  1. About.com
  2. Computing
  3. C / C++ / C#
  4. C# / C Sharp
  5. Learn C Sharp
  6. Calculating the relative angle between two points

©2014 About.com. All rights reserved.