Collision in 2D-Game

Heya, i have been making some progress on a 2D-open-world-“game”. So far, you can move into eight directions (thanks to the user @CodeMasterX) on a 200000 by 200000 pixel world and increase your speed by holding the sprint button. The UI so far is a display of your coordinates, and a minimap, which shows everything around you in a certain radius, dependent on the set resolution (effectively the window size). 500 trees and 500 rocks spawn in the boundaries of the world, but you cannot interact with them in any way.

I want to change that by adding collision.
So far (in other projects) i coded collision by giving every object (in this case the rocks and trees) a function that does the following (this is a snippet out of a little game i coded 2 years ago)


void RockExecute() {
  for (int i=0; i<Rocks.size(); i++) {
    Rocks.get(i).RockFallLoop();
  }
}

void RockFallLoop() {
checkCollision();
//other stuff
//more other unimportant stuff
}


void checkCollision() {
if (((PlayerY + 65 > RockY) && (PlayerY < RockY +75)) && ((PlayerX + 115 > RockX) && (PlayerX < RockX + 75))) {
      GameOver = true;
    }

at some point after every object has executed that function, another function is gonna check GameOver and do stuff if it is true.

I have 2 problems with this:

  1. I am 99% sure that this long if-condition with checking the manually written boundaries is unnecessary and inefficient

  2. I want the player to have the collision functions, since i think it will save me a lot of time, as i am going to add WAY more things with collision than just trees and rocks.

(i don’t think it’s necessary to paste my whole code right here, if you need more info on my code, i can paste the section that you need)

I suggest you add a class. It can be either:
obstacle or rock (depends what you want, suggest both)

Preferably they should be rectangular since circular/ellyptical collisions are a pain to code. So just go with rectangular which are way simpler.

I suggest you go with both obstacle and rock classes.
Obstacle will be a list of all obstacles.
Every rock (and every other non passable object) will have an assigned obstacle. It is far easier and faster to run, since you will only go through one list of obstacles instead of all types at the same time.

Unless the player is a point, I recommend you check this:

Besides that, first check if the obstacle is even on the screen. It should save massive amounts of computer resources, since you don’t have to check thousands of hitboxes every move.

Providing that you are looking to handle blocky shapes here is an example that can handle any number of sides.

I have an ellipse collision test somewhere I can share for irregular ellipses, and for completeness you should also add a beziers or curve collision which I do not have examples for but providing that you know how to handle line collisions then it should be pretty straightforward as most curves are really just a series of straight lines. There are lots of examples already on the site for line to point collisions and line to line collisions and the website above should be an excellent guide too. That should handle all cases in 2 dimensions.

This one handles all concave and convex shapes. You’ll have to read through the code and see how you can adapt it for your needs I unfortunately do not have the time right now to adapt it for you.

Please note it is an algorithm that handles closed shapes. It should be able to handle open shapes and I think the easiest way to handle them would be to close them anyway and keep track of the vertices you have added and hide them in code.

Please note I cannot remember if my example provides a midpoint test, I know the shapes have a midpoint but I cannot remember if I specifically added that test.
The midpoint test speeds up collision testing for scenes with a lot of shapes. As it first test whether the mouse is in between the midpoint and the furthest point the shape has from the midpoint. If this test isn’t done it would keep testing all shapes regardless of whether or not it is or not.

Please note however that the algorithm will still cause your program to slow down if you have a lot of shapes with a lot of sides that overlap.

Hi! I thought this was an interesting challenge so I made a simple demo program.
ONLY WATCH IF YOU DON’T WANT TO FIND THE SOLUTION YOURSELF!!!

I posted it in my project library; here is the link to the “solution”