2D Collision Detection & Drawing on a Backscreen

After numerous attempts to write some sort of a 2D collision detection using distance and circles I’ve given up. My 2D sprites and strange shapes and I can’t have any overlap in my game. I’ve come up with an idea and I want to run it past the community and maybe get a little advice on a couple of points.

First, here’s what I’m dealing with:

Note how I’ve already created copies of the shapes for the drop shadow. My idea is to draw (using the drop shadow shapes, except 100% black) on a backscreen. It would look like this (except it’s on a back screen):

  1. Then I would count all the black pixels (imagine the gray sprites are black).
  2. Then I would place the shape of the unit I was checking for collision on the backscreen but this time I would draw it in green.
  3. Then I would count the black pixels again. If there was any over lap (green over black) the number of black pixels would be reduced and I know there would be a collision.

This isn’t a RTS, it’s what I call a ‘phased’ game, so time isn’t that crucial. It’s the only way I can think of to solve this problem.

My questions are:

  1. How do I redirect drawing to a back screen?
  2. How do check the RGB values of each pixel on the back screen?

As always, many thanks to the MonoGame Community for getting me this far!

Since this is not an RTS , I think you may not need exact pixel perfect collision, why it didn’t work for you?

In any case, about your new idea, if you want to read in CPU the values of the GPU image, it will be very but very slow!
If you want to draw to another screen you can use render targets, and if you want to read the pixels you can use


but I do not recommend that way. I use boxes and circles for collision detection without problems, what is not working for you? You should have all the x,y coordinates of all your units so using either rectangles or circles should mostly work and would be very fast.

Circles won’t work because units can be right next to each other but cannot touch or overlap:
Overlapping circles

What I want to do is draw to memory. It doesn’t have to be to the GPU. Back in the '80s when I wrote for the Atari ST you could make any address in memory the address of the screen. It was incredibly easy to write to memory and then flip it to the front.

EDIT: I’ve been thinking about ‘rectangles’. The X,Y is not where you think on these icons (and it moves around from line to column formations) but the math is doable. The problem would be calculating intersection after the rotation. This can’t be a simple X1,Y1, X2, Y2 rect.

Your diagram with the circles actually looks acceptable to me. You can tweak the bounding circle accordingly. You can also use bounding rectangles if you want to be more precise. There’s a fairly simple polygon overlapping check algorithm that you can implement.

It’s probably going to be overall easier (and more performant) to implement than a pixel perfect scan over a hit buffer. When you were doing those manual renders on the old atari, the screen resolution was a lot smaller.

But if you want to draw to a screen in this way, you can render to a texture, then check the data for that texture.

Here’s another example of how rects aren’t going to work (and even calculating the X1,Y1,X2,Y2 for these rects, I think, would be a daunting task (I don’t even know where to start on the math for that).
The real problem isn’t what we consider acceptable, it’s what wargamers want. And they want units in column formation next to each other. Circles won’t work. Rects won’t work. The only thing I can think of is what I outlined above. I’m seriously open to any other suggestions.

You are also 100% correct. The old Atari ST had a resolution of 640 x 400 (in black and white, 640 x 200 in 16 color). It was also using a Motorola 68000 chip, which was easy to work with.

How would I draw on a back screen? Or just draw to a hunk of memory? Or even draw to a 2D array (that would be great if I could do that).

That would work fine if you didn’t let the units collide. They’ll just be a bit further apart. That’s not quite what I meant though. Imagine that rectangle is around the unrotated sprite, then rotates with the sprite. Then test to see if the two rectangles overlap. Either line segments will intersect, or a line from any given point to infinity will intersect with a segment an odd number of times.

Now you can make the bounding rectangles as tight or as loose as you want. Remember though, it’s not going to be perfect, just close enough… but nothing I see from your example images suggests just using unrotated rectangles (or circles) would break it. Your units would be a little further apart and that’s it. Rotated rectangles is still a lot less computational complexity than a pixel perfect scan over an HD texture though :smiley:

Look into render target usage. I can’t remember the exact syntax offhand, but you want to use a RenderTarget2D (which extends from Texture2D). You create a new one, then set it as the target on your graphics device. Render as you would normally but everything is sent to that texture. One of the initialization constructors lets you initialize it to be a transparent image. Then you can do GetData on the RenderTarget2D. Something like…

Color[] data = myRenderTarget.GetData<Color[]>();

… I think?

The Atari ST used a different architecture , today we put all graphics assets into the video card which has its own GPU so all textures are not in you main CPU and the graphics card also has its own memory to store all the graphics, so that’s why pulling data from the graphics card is slow compared to the Atari ST. Still the resolution was way smaller than current graphics, so I think is not fair to compare both.

In one of my games I put 1000s of units on screen in real time like this, and I used circle collision though it was not perfect it was ok, and all enemies had different shapes

I saw your rectangle image example, you can actually rotate every single rectangle to fit the shape to your units, then rotate them to check collision , that should do the job. Though it will be a little bit slow but given the number of units you have you can optimize it easily, I don’t think you will be drawing more than 1000 units in one map so it will still be fast.

Anyway, I haven’t tested this but it should be something like this:

public static bool CheckCollision(Rectangle rect1, float angle1, Rectangle rect2, float angle2)
    // Calculate the four corners of each rectangle
    Vector2[] corners1 = CalculateCorners(rect1, angle1);
    Vector2[] corners2 = CalculateCorners(rect2, angle2);

    // Check if any of the corners of rectangle 1 are inside rectangle 2
    for (int i = 0; i < corners1.Length; i++)
        if (IsPointInsidePolygon(corners1[i], corners2))
            return true;

    // Check if any of the corners of rectangle 2 are inside rectangle 1
    for (int i = 0; i < corners2.Length; i++)
        if (IsPointInsidePolygon(corners2[i], corners1))
            return true;

    // If none of the corners are inside the other rectangle, there is no collision
    return false;

private static Vector2[] CalculateCorners(Rectangle rect, float angle)
    // Calculate the four corners of the rectangle
    Vector2[] corners = new Vector2[4];
    corners[0] = new Vector2(rect.Left, rect.Top);
    corners[1] = new Vector2(rect.Right, rect.Top);
    corners[2] = new Vector2(rect.Right, rect.Bottom);
    corners[3] = new Vector2(rect.Left, rect.Bottom);

    // Rotate the corners around the center of the rectangle
    Vector2 center = new Vector2(rect.Center.X, rect.Center.Y);
    for (int i = 0; i < corners.Length; i++)
        corners[i] = RotatePoint(corners[i], center, angle);

    return corners;

private static Vector2 RotatePoint(Vector2 point, Vector2 center, float angle)
    // Rotate a point around another point by a given angle
    float sin = (float)Math.Sin(angle);
    float cos = (float)Math.Cos(angle);
    Vector2 translated = new Vector2(point.X - center.X, point.Y - center.Y);
    Vector2 rotated = new Vector2(
        translated.X * cos - translated.Y * sin,
        translated.X * sin + translated.Y * cos);
    return new Vector2(rotated.X + center.X, rotated.Y + center.Y);

private static bool IsPointInsidePolygon(Vector2 point, Vector2[] polygon)
    // Check if a point is inside a polygon using the ray casting algorithm
    bool inside = false;
    for (int i = 0, j = polygon.Length - 1; i < polygon.Length; j = i++)
        if (((polygon[i].Y > point.Y) != (polygon[j].Y > point.Y)) &&
            (point.X < (polygon[j].X - polygon[i].X) * (point.Y - polygon[i].Y) / (polygon[j].Y - polygon[i].Y) + polygon[i].X))
            inside = !inside;
    return inside;

I think this may work, test it and let me know.

First of all, I can’t thank you (and the MonoGame Community) enough! There’s no way I would have got this far without your help! I really appreciate it!

Here’s the absolute worst case with circles:
Worst Case
So, for wargamers (my target demographic) this is a non-starter because they’re going to want ‘blocks’ of units stacked behind each other or in columns like this.

So, next I’ll try your code. I’ll be able to create rects that exactly match the units (for strange wargaming reasons, sometimes X,Y is the front center of the unit, sometimes it’s the front of the column) but I can calculate the correct offsets.

Again, thanks for all the help and, either way, I’ll report my results back here for the next guy stuck with this problem.

Im not sure if you have used chatgtp but it is amazing

Ask it to write you a rotated rectangle collision method for monogame with collision resolution and it will make you an algorithm using Seperation Axis Thereom

I did it a couple weeks ago and it made one that worked. I had to tell it to modify a few things and it did. Tell it you need to store a rotation float etc

In case you havent used chatgtp when it stops writing code halfway just write continue. If somethings not quite working or you want it to add things tell it, and it will apologise and try to fix it, or rewrite methods for you

I think you’re not getting what I mean about things being spaced further apart, as you keep drawing the circles with the spacing as it is now, with no collision, instead of as it would be if you just used those circles for collision.

Still, it sounds like tight packing is what you want, so my suggestion to use rotated bounding boxes is what you need. I described the algorithm, but MysticRiverGames straight up gave you an awesome implementation that you should be able to just go ahead and use.

At the end of the day, whatever works for you, but that algorithm will do much better for you than using a rasterized hit detection layer. There is absolutely a tradeoff in precision, but it comes with a massive performance gain.

I don’t think you need to worry about it for your case, but keep in mind you can actually use both approaches. Use the circle method as you’ve demonstrated to check if you should even bother using the rotated bounding box method.

Good luck! I’m looking forward to seeing your progress, Ezra :slight_smile:

Yes, I think MysticRiverGames solution is optimal. And, yes, I have to really pack these units together (again, this is a 19th century wargame and that’s how the battles were fought).

Interestingly, the solution that I came up with is a typical computer science grad school solution. I remember trying to convince the dept. chair that A* was superior to Kruskel’s algorithm for least-weighted path work. Yes, Kruskal’s is guaranteed to give the optimal solution, but it’s slooooooow where as A* is fast.

I am a retired comp sci prof and I hearby give you an A+++++++ and will be glad to write you a letter of recommendation. After some slight mods (the unit icons don’t rotate from the center, they rotate from the front of the icon) and some visual debugging (I’m drawing red rects around the units to make sure the rotations are correct) we got this:

I think it’s a winner! You rock @MysticRiverGames! I’ll probably make the bounding rects a little bigger, but this looks good. I’m not seeing any real overlap (I don’t care about the arrows).
Again, thanks a million! The MonoGame Community is the best!

Good to hear that it is working for you now!
Hopefully we will see your finished product some day :slight_smile:
You can post it this forum too! it is nice to see more people finishing their games and see the results.

The Steam Store: General Staff: Black Powder on Steam

1 Like

Mate your game is looking amazing

Im very impressed with the large list of choices the ai was calculating.

Games looking very polished. Would love to watch a full video on a scenario

Edit: Just watched your video on your map editor. Very impressive. I loved the way you could draw your shapes for citys and forest etc.

The maths look strong on the road building with integrating that in with your pathfinding

I hope to be in beta in a month.

1 Like

I just saw your steam page, your game idea looks pretty interesting, I remember I use to play strategy games similar to this in the Atari ST time, like Empire? was it called like that? anyway, but it was more like Civilization but on military scale, and many others somehow similar to your game idea but not as advanced. I remember in the Atari 8 bit there was a couple of games like this, though it was quite difficult to play them since at that time I preferred more action games. Keep up the good work!

I prefer like RTS type of games, which are not that common anymore.

My first wargame, UMS: Universal Military Simulator, was on the Atari ST, . Empire, by Mark Baldwin, was actually a port of an early mainframe wargame! I, too, played Empire a lot. Very fun skittles & beer game.

Wow! , I never had the chance to play UMS, I searched for it and found some videos on YouTube, missed the chance to play it.
Hopefully I will be able to play your next one :slight_smile:

Shoot me your email and I’ll make sure you get a key. I’m Ezra [at] RiverviewAI.com

1 Like