•    Free Pascal
• Website
• Downloads
• Wiki
• Bugtracker
• Mailing List
•    Lazarus
• Website
• Downloads (Laz+FPC)
• Packages (OPM)
• FAQ
• Wiki
• Bugtracker
• IRC channel
• Follow us on Twitter
• Latest SVN
• Mailing List
• Other languages
•    Foundation
• Website
• Project Roadmap
• Getting the Source
• Screenshots

### Author Topic: Problem with Collision detection  (Read 2965 times)

#### IroncrossBG ##### Re: Problem with Collision detection
« Reply #15 on: June 16, 2019, 07:34:02 pm »
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 ##### Re: Problem with Collision detection
« Reply #16 on: June 16, 2019, 09:31:46 pm »
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

• Hero Member
•     • Posts: 2513 ##### Re: Problem with Collision detection
« Reply #17 on: June 16, 2019, 09:57:03 pm »
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 ##### Re: Problem with Collision detection
« Reply #18 on: June 16, 2019, 10:03:02 pm »
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.x1, A.Polygon.y1),
5.                                 PointF(A.Polygon.x1, A.Polygon.y1),
6.                                 PointF(A.Polygon.x1, A.Polygon.y1),
7.                                 PointF(A.Polygon.x1, A.Polygon.y1),
8.                                 PointF(A.Polygon.x1, A.Polygon.y1),
9.                                 PointF(A.Polygon.x1, A.Polygon.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;
« Last Edit: June 16, 2019, 10:07:52 pm by IroncrossBG »

#### IroncrossBG ##### Re: Problem with Collision detection
« Reply #19 on: June 16, 2019, 10:27:52 pm »
Ok, here is the project with my implementation. Did some changes here and there.

#### jamie ##### Re: Problem with Collision detection
« Reply #20 on: June 17, 2019, 12:32:18 am »
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.
The only true wisdom is knowing you know nothing

#### SymbolicFrank

• Hero Member
•     • Posts: 639 ##### Re: Problem with Collision detection
« Reply #21 on: June 18, 2019, 01:23:14 pm »
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

• Hero Member
•     • Posts: 2513 ##### Re: Problem with Collision detection
« Reply #22 on: June 18, 2019, 02:43:59 pm »
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.
« Last Edit: June 18, 2019, 06:17:45 pm by engkin »

#### SymbolicFrank

• Hero Member
•     • Posts: 639 ##### Re: Problem with Collision detection
« Reply #23 on: June 18, 2019, 03:34:04 pm »
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.
« Last Edit: June 18, 2019, 03:43:33 pm by SymbolicFrank » ##### Re: Problem with Collision detection
« Reply #24 on: June 18, 2019, 06:28:34 pm »
Note that in the math unit there are optimized pure pascal functions for the issue at hand.
I am more like donkey than shrek

#### eny

• Hero Member
•     • Posts: 1593 ##### Re: Problem with Collision detection
« Reply #25 on: June 18, 2019, 09:50:52 pm »
Interesting topic.
Was just working on an SDL2 version to develop a little framework All posts based on: Win10 (Win64); Lazarus 1.8.0 'stable' (#56594 win64) unless specified otherwise...

#### SymbolicFrank

• Hero Member
•     • Posts: 639 ##### Re: Problem with Collision detection
« Reply #26 on: June 19, 2019, 09:17:11 am »
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 ##### Re: Problem with Collision detection
« Reply #27 on: June 19, 2019, 12:07:19 pm »
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.
« Last Edit: June 19, 2019, 12:11:26 pm by IroncrossBG »