Hi everyone ! I'm new on this forum and english is not my native language but i'll do my best to express myself.

Briefly, i'm a 25 years old chemistry student and passionate of programming. I've touched several languages (HTML & CSS, Java, C, C++ and python) and it allowed me to find the best language with the one I've a good feeling and I can quickly understand everything. So, since 2 years I'm programming in Pythont to practice myself but I've been always intrested in making a small cool game (not thoses clone of tetris, snake or whatever arcade game cauz' I never liked them sorry). I'm more intrested in dungeons crawler or Die and retry games in narrow levels. We see a bunch of thoses games on the market (Hotline miami, enter the gungeon or more recently streets of rogue etc...).

I've coded on Python with the Pygame library, a couple of lines that allow me to display images, move them, handle keyboard inputs and sounds. But, I was thinking about trying to handle collisions between entities that are represented as sprites with an ID and coordinates (x and y). There are various possibilities to check collision, but my question is more focused on a global concept.

Imagine we have a large background where there is a blue entity on the left side and a bunch (100 maybe) of red entities on the right side with random moves. If my blue entity start to move to the right, what I want is to determine when this blue entity hit a red one. The first idea that come is to check every step if the blue one collide with the other 100 red ones. In terms of computer calculating it's unforgivable to do that. So how can we optimized the collision detection to reduce this calculation time but without loosing efficiency if multiple things collide at the same time ?

I've try to think by myself and I found that maybe a solution will be to do a coordinates comparison between entities. If the red one is farther than X units then you skip the collision algorithm and you go to the next entities. It's probably faster than the first idea but i'm sure there is a more efficient way to do that, so I'm asking for help with this problem. Thank you in advance for any kind of help that you can bring to me.

One possibility would be to use an existing physics engine, like Box2D. It looks like there's a Python version. I don't know anything about it (other than that it exists), but you could take a look at that.

If you want to do it yourself:

Quote

The first idea that come is to check every step if the blue one collide with the other 100 red ones. In terms of computer calculating it's unforgivable to do that.

Not necessarily unforgivable, generally speaking. With some languages/environments, 100 collision checks per update would probably be fine. I don't know much about Python's performance characteristics, but you could try brute-forcing it, just to see what happens. Even if performance was unacceptable, it might at least give you some idea of how much you'd need to optimize.

Beyond that, a typical solution would be some sort of broad phase step using a spatial partitioning system. Options for spatial partitioning include grids, sort-and-sweep/sweep-and-prune, etc. Different partitioning schemes have different characteristics, and some are much more or less complex to implement than others. A grid might be one of the simpler systems to implement.

There may be other issues to consider as well, such as discrete vs continuous tests and tunneling.

If you need more specific advice, further details would be useful, such as:

- You mentioned an object moving left to right towards a bunch of other objects. Is that specifically part of the design, or is that just an example?

- How much does the size of the objects vary?

- When you say the entities move randomly, do they change velocity, or move with a fixed (but randomized) velocity?

- Is the blue entity in the example player-controlled? Or does it just move left to right automatically?

I'm not saying you need to answer these questions here - these are just things that could be relevant. Depending on the exact circumstances, it's possible you could implement a special-case system that's more efficient than more general alternatives.

I am wondering if it helps to define the coordinate system of the red entities relative to the blue entity. Obviously you have to update the position of all the red entities when the blue entity moves, but you have to go through all of them anyway to move them, as they also move themselves.

A simpler solution could be to keep an absolute coordinate system (like you have now I assume) and compare the position of the red entities with the blue entity while you move the former, and keep a collection of "near enough" red entities that could perhaps soon collide. Again, there is little extra cost if you have to go through all red entities anyway to move their position.

You only have one blue entity?  So, checking all blue entities against all red entities is just 1×100=100 checks?  Why are you even worrying about that?  Sophisticated spatial partitioning systems exist, but they're there to reduce the number of collision checks from the millions to the thousands, not to reduce the number of collision below 100.

I am not an expert but i am not sure if that's true in general. Depending on what the entity holds it might be pretty expensive to load, maintain and check. If they are only coloured boxes you are right, but that's probably not always the case, even if these boxes only bound something more complex inside of them if might be necessary to load, prepare or unload connected data. Trying to keep it as low as possible is generally not a wrong approach, imo :-)

A spatial data structure, like a quad tree for a 2D field for example, can help. One could build a selection of the spatial units to check this frame, in the direction the blue e. moves, and perform only checks against those red e.s that are in the way .... But that, as has been said, depends on the use case. How quick are they, do they move erratically or straight, is there a danger that between frames they have tunnelled through each other ...

Not a trivial field, but nice to implement :-)