Problem with Collision detection

[IroncrossBG]

The reason behind the bug is when the asteroid rotates, sometimes the current and future bullet position end up inside the asteroid. I tried adding LastX and LastY instead of future pos, but the same thing happens.

Then it won't be hard. I simply repeat the collision detection twice, the second one has speed x 2:

Code: Pascal  [Select][+][-]

1.     //COLLISION DETECTION
2.     for I := 0 to EM.Entities.Count - 1 do
3.       for J := Low(A.Polygon) to High(A.Polygon) do
4.         if LinesIntersect(A.Polygon[J].x1, A.Polygon[J].y1, A.Polygon[J].x2,
5.           A.Polygon[J].y2, EM.Entities[I].Pos.X, EM.Entities[I].Pos.Y,
6.           EM.Entities[I].Pos.X + EM.Entities[I].xSpeed, EM.Entities[I].Pos.Y +
7.           EM.Entities[I].ySpeed, Inter) then
8.             EM.Entities[I].Active := False;
9.  
10.     for I := 0 to EM.Entities.Count - 1 do
11.       if not(EM.Entities[I].Active) then
12.         Continue
13.       else
14.         for J := Low(A.Polygon) to High(A.Polygon) do
15.           if LinesIntersect(A.Polygon[J].x1, A.Polygon[J].y1, A.Polygon[J].x2,
16.             A.Polygon[J].y2, EM.Entities[I].Pos.X, EM.Entities[I].Pos.Y,
17.             EM.Entities[I].Pos.X + EM.Entities[I].xSpeed*2, EM.Entities[I].Pos.Y +
18.             EM.Entities[I].ySpeed*2, Inter) then
19.               EM.Entities[I].Active := False;

Almost perfect, still 1 hidden bug.

Download the code below, run it and hold 'F' key. Only 1 missed bullet in a 360 clockwise rotation.

Try with lowest speed on trackbar, still doing it... 

[Handoko]

I'm back and I am sure I have solved the problem. But my solution has a small flaw.

Code: Pascal  [Select][+][-]

1.     //COLLISION DETECTION
2.     for I := 0 to EM.Entities.Count - 1 do
3.       for J := Low(A.Polygon) to High(A.Polygon) do
4.         if LinesIntersect(A.Polygon[J].x1, A.Polygon[J].y1, A.Polygon[J].x2,
5.           A.Polygon[J].y2, EM.Entities[I].Org.X, EM.Entities[I].Org.Y,
6.           EM.Entities[I].Pos.X + EM.Entities[I].xSpeed, EM.Entities[I].Pos.Y +
7.           EM.Entities[I].ySpeed, Inter) then
8.             EM.Entities[I].Active := False;

I added TEntity.Org. Without my explanation, I believe you can guess how it works. But as I already said it has a small flaw.

[engkin]

I am curious to know if the solutions being used here are some of the known ones, as this problem seems to be an age old and must have a big number of solutions. I read the posts, but did not see a hint.

The reason for my question, beside my curiosity, is that I assume there must be a well tested efficient way to solve this problem.

[IroncrossBG]

I'm back and I am sure I have solved the problem. But my solution has a small flaw.

Code: Pascal  [Select][+][-]

1.     //COLLISION DETECTION
2.     for I := 0 to EM.Entities.Count - 1 do
3.       for J := Low(A.Polygon) to High(A.Polygon) do
4.         if LinesIntersect(A.Polygon[J].x1, A.Polygon[J].y1, A.Polygon[J].x2,
5.           A.Polygon[J].y2, EM.Entities[I].Org.X, EM.Entities[I].Org.Y,
6.           EM.Entities[I].Pos.X + EM.Entities[I].xSpeed, EM.Entities[I].Pos.Y +
7.           EM.Entities[I].ySpeed, Inter) then
8.             EM.Entities[I].Active := False;

I added TEntity.Org. Without my explanation, I believe you can guess how it works. But as I already said it has a small flaw.

Just finished my own implementation. First, i find the polygon bounding box, then get the length of the box, then project a line new line Bullet.Angle - 180 with bounding box length. No bugs found. I think your implementation is similar to mine, except you project the line to original pos, i haven't found any bugs in your implementation. Although, i think your code might cause problems if there is more than one asteroid, not sure.



Here is my code:

GetPolygonBoundsFA

Code: Pascal  [Select][+][-]

1. function GetPolygonBoundsFA(const Polygon: TPolygonLinesArr): TLine2D;
2.         var
3.                 I: Integer;
4.                 minX, maxX, minY, maxY: Double;
5.         begin
6.                 minX := High(Integer);
7.                 minY := High(Integer);
8.                 maxX := Low(Integer);
9.                 maxY := Low(Integer);
10.  
11.                 for I := 0 to Length(Polygon) - 1 do
12.                 begin
13.                         if Polygon[I].x1 < minX then
14.                                 minX := Polygon[I].x1;
15.                         if Polygon[I].x2 < minX then
16.                                 minX := Polygon[I].x2;
17.  
18.                         if Polygon[I].x1 > maxX then
19.                                 maxX := Polygon[I].x1;
20.                         if Polygon[I].x2 > maxX then
21.                                 maxX := Polygon[I].x2;
22.  
23.                         if Polygon[I].y1 < minY then
24.                                 minY := Polygon[I].y1;
25.                         if Polygon[I].y2 > maxY then
26.                                 maxY := Polygon[I].y2;
27.  
28.                         if Polygon[I].y1 < minY then
29.                                 minY := Polygon[I].y1;
30.                         if Polygon[I].y2 > maxY then
31.                                 maxY := Polygon[I].y2;
32.                 end;
33.                 Result := Line2D(minX, minY, maxX, maxY);
34.         end;

Collision detection:

Code: Pascal  [Select][+][-]

1. for I := 0 to EM.Entities.Count - 1 do
2.                 begin
3.                         //Just converting the line2D to PointF, will fix later and remove this
4.                         Arr := [PointF(A.Polygon[0].x1, A.Polygon[0].y1),
5.                                 PointF(A.Polygon[1].x1, A.Polygon[1].y1),
6.                                 PointF(A.Polygon[2].x1, A.Polygon[2].y1),
7.                                 PointF(A.Polygon[3].x1, A.Polygon[3].y1),
8.                                 PointF(A.Polygon[4].x1, A.Polygon[4].y1),
9.                                 PointF(A.Polygon[0].x1, A.Polygon[0].y1)];
10.  
11.                         if PNPoly(EM.Entities[I].Pos.x, EM.Entities[I].Pos.y, Arr) then
12.                         begin
13.                                 L := GetPolygonBoundsFA(A.Polygon);
14.                                 P := PointOfAngle(EM.Entities[I].Pos.x  + EM.Entities[I].xSpeed, EM.Entities[I].Pos.y
15.          + EM.Entities[I].ySpeed, DistancePointsF(l.x1, l.y1, l.x2, l.y2),
16.                                         EM.Entities[I].Angle - 180);
17.                                 for J := Low(A.Polygon) to High(A.Polygon) do
18.                                         if LinesIntersect(A.Polygon[J].x1, A.Polygon[J].y1, A.Polygon[J].x2,
19.                                                 A.Polygon[J].y2, EM.Entities[I].Pos.x + EM.Entities[I].xSpeed,
20.                                                 EM.Entities[I].Pos.y + EM.Entities[I].ySpeed, P.x, P.y, Inter) then
21.                                         begin
22.                                                 EM.Entities[I].Pos := Inter;
23.                                                 EM.Entities[I].Target := Inter;
24.                                         end;
25.                         end;
26.                 end;

[IroncrossBG]

Ok, here is the project with my implementation. Did some changes here and there.

[jamie]

I suppose you could draw the object in it's future position on a scratch surface equal to that of the
actual displaying surface, use a flood Fill of a specific color. Calculate the future location of the
intersection and then Read a Pixel from it. test the color, if you are getting the color then you are inside the object.

The other way would be to draw it on a small bitmap and scan from inside out looking for the walls
Account for the offsets of where the image was be in real life.
 if any of those values match the target while scanning then that means there will be a collision.

[SymbolicFrank]

I am curious to know if the solutions being used here are some of the known ones, as this problem seems to be an age old and must have a big number of solutions. I read the posts, but did not see a hint.

The reason for my question, beside my curiosity, is that I assume there must be a well tested efficient way to solve this problem.

There are multiple, but there are also multiple, different implementations of the drawing.

Simply put, you can either draw sprites in layers and see if the pixels painted already have a color (this only works if everything moves at most one pixel per frame), or you draw lines (2D/3D vectors/polygons, optionally filled) and you calculate everything.

Here lines are drawn, so you have to calculate the polygons / volumes.

[engkin]

Thank you. I was referring to the calculation. My assumption is there must be a very efficient and accurate way to find the intersection of one line segment with multiple other segments.

Now I am under the impression that the problem of this thread is solved.

[SymbolicFrank]

Yes/no to both. Depending on how you store your data, you have to come up with a way to calculate the polygon / volume that encompasses the volume of space where the object has been in the time in between the two frames.

First, many game engines run the rendering at a different clock than the physics calculation: the latter is most often fixed, while the first runs as often as possible. So, the time slices have no direct relation to the intervals where the position is recalculated. And objects can change form and rotate...

So, it's not that easy. For sprites, the locations in between frames are often ignored, so you can shoot through an object without hitting it. And the 3D calculations are quite complex, so most of the time one or more rough, squarish, bounding boxes ("hitboxes") are calculated somewhat around the path of the object.

Edit: and to do it right, you should check that at the time the bullet hits the bounding box, the object was at that location and not at the other side.

[Thaddy]

Note that in the math unit there are optimized pure pascal functions for the issue at hand.

[eny]

Interesting topic.
Was just working on an SDL2 version to develop a little framework 

[SymbolicFrank]

For an asteroids game, I would simply calculate for each bullet if they are within the radius of the center of each asteroid. And create an explosion, to mask the inaccuracy.

[IroncrossBG]

I did solve my problem.

A possible optimization would be to put the update/tick function in a Thread timer or a QueryPerformanceCounter timer and have updates/s property and then divide x, y speed by the updates/s. This would give you alot more accuracy with really fast moving objects, the more updates/s, the more accuracy at the expense of CPU calculations. Also, this will reduce the possibility of the bullet jumping over the entire asteroid if the asteroid diameter is smaller than the bullet speed.