How to handle object collision?

Question

Programming

So I'm going to write my game in SDL. The actual action will take place on the game plane, on which objects will move, consisting of coordinates and a 2-dimensional array, in which values ​​can take on the values ​​0 or 1. 0 - empty, 1 - busy. And, in fact, the question is: how to check 2 objects for collisions and determine which parts of the arrays the collision occurred?
I myself came up with 2 options, but they are resource-intensive:
1) "on the forehead": Compare each point of the 1st array with each point of the second, if the coordinates are the same -> collision.
2) "on the forehead": create another two-dimensional array "game plane". Copy the 2nd object onto it. Then iterate over all points of the 1st object, if both the 1st object and the plane have a point occupied -> collision.
Are there any less costly ways? What can you say about the 2nd?

Answer 1

Judging by the emphasis on any configuration of objects, you need to correctly handle even such cases when the coordinate objects pass through each other, but due to the peculiarities of their configuration matrices, they do not collide.
A universal solution is only the storage of additional cache matrices, a reduced scale of objects. The number and configuration of caches depends on the complexity of these matrices. There can be several matrices for one object, sequentially decreasing the scale (for example, with a factor of 4 - 128x128 -> 32x32 -> 8x8 -> 2x2), then when a collision of rectangular areas of objects is detected, the intersections of points are sequentially checked first on the object configuration matrices with low resolution, with If an intersection is detected, the check is repeated for the corresponding points already from the matrix with a higher resolution.
The algorithm is very efficient, especially for complex objects that take up little space in the matrix.
ps fragmentation of an object into components can also be a good help (i.e. represent an object as several objects at once, the parameters of which are calculated right there, it is not even necessary to physically store and move these objects synchronously)

Answer 2

noregret.org/tutor/n/grid/
noregret.org/tutor/n/collision/
www.gamedev.ru/code/articles/?id=4194
Sorry if this is off topic :)

Answer 3

If the point is already occupied, increase the Plane[x coordinate of the point][y coordinate of the point] by one.
Then check: if (Plane[x][y] > 0) a collision has occurred.

Answer 4

Recalculate the coordinates of a moving object and compare with the rest.
Tip: if you want to understand, then write your own Tetris - this is a great example of collision handling.

Answer 5

Start with objects colliding with surfaces.
Further, it is possible to discretize the shape of an object with a decrease in accuracy (say, the contour of an object is 1000 points, construct derived objects with 100 points, with 10). Calculate completely only the rough model. At the output, you will not know whether the objects will collide or not (that's why it is rough), but you can roughly estimate the probability (the coefficients depend on the shape of the model) and the nodes that are closest to each other and potentially participate in the collision.
If the probability of a collision based on a rough model is high, calculate this area in a higher resolution, etc.

Answer 6

It all depends on the situation, but in most cases the playing space is divided into zones (the zone is larger than the largest object). And then as the inner voice decides. As a result, it was necessary to check a maximum of 4 zones for a collision. There were many zones. In fact, nothing slowed down. Again, another option where there is a raster field and each object behind it marked that it had already taken its place, as a result there was only a small array with quick access to elements, but if the object fell into the area marked occupied, then more accurate checks were carried out.

Answer 7

With a very high probability, you do not need such accuracy.
Outline with vectors, or even easier, close the object with a set of rectangles and circles, and compare them already.

Answer 8

Why don't you use game SDKs with a built-in (or easily screwed) collision sensor?
pygame, moai, LÖVE and others.

Answer 9

described for pygame, but it will also be relevant for you:
https://youtu.be/FxInYJC2LD4