# Lazarus

## Programming => General => Topic started by: IroncrossBG on June 15, 2019, 12:13:06 am

Title: Problem with Collision detection
Post by: IroncrossBG on June 15, 2019, 12:13:06 am
Hello everyone, im new to the forum :)

So, im trying to recreate the original Asteroids game and im having a bit of a problem with my collision detection. I have an asteroid polygon made from lines which are made from float TPoint. The way my collision works is every tick, i make a line between the current bullet position and the future bullet position (x + xSpeed, y + ySpeed) and then check if an asteroid line intersects it and then destroy the bullet. But for unknown reasons to me, some of the bullets jump over the asteroid line and no collision occurs. Any ideas? i have attached my project as a zip, it's written in Delphi 10.3.
Im writing here cause most of Delphi/Pascal forums are pretty much dead. :/

Thanks!
Title: Re: Problem with Collision detection
Post by: jamie on June 15, 2019, 03:22:26 am
I down loaded your program, did a little conversion here and there because I am still using Lazarus
2.0.2 with 3.0.4 …

Looking at your methods of detection I would say that you have floating point rounding errors
and you're skipping over a number because you are looking for exact values.. This isn't going
to happen like the way you wish..
What you should be doing is using a 2x2 box test area..

if you use the PtinRect (Point_Int_Rect) you can determine if the current X,Y target is within
the rectangle block

Since you are using floats throughout maybe you could write a PtInRectF function..

Title: Re: Problem with Collision detection
Post by: Handoko on June 15, 2019, 05:56:46 am
@jamie

:'( I failed to convert it, because I'm not familiar with the generics things, can you please share the code you have converted?
Title: Re: Problem with Collision detection
Post by: SymbolicFrank on June 15, 2019, 09:04:45 am
For such collision detection, you should draw a virtual line between the last and the current position of the bullet. And if the asteroid moved, you should first draw a virtual box that encompasses both the old and new position. Then calculate if they overlap.
Title: Re: Problem with Collision detection
Post by: IroncrossBG on June 15, 2019, 12:40:13 pm
Ok, i've managed to convert it to Lazarus. Project is attached. Using Lazarus 2.0.2 64 bit. Generics in Lazarus are a bit trickier ;)
Title: Re: Problem with Collision detection
Post by: IroncrossBG on June 15, 2019, 02:16:22 pm
I down loaded your program, did a little conversion here and there because I am still using Lazarus
2.0.2 with 3.0.4 …

Looking at your methods of detection I would say that you have floating point rounding errors
and you're skipping over a number because you are looking for exact values.. This isn't going
to happen like the way you wish..
What you should be doing is using a 2x2 box test area..

if you use the PtinRect (Point_Int_Rect) you can determine if the current X,Y target is within
the rectangle block

Since you are using floats throughout maybe you could write a PtInRectF function..

Code: Pascal  [Select]
1. function PointWithinLine(const px, py, x1, y1, x2, y2: Double): Boolean;
2. begin
3.         if (px >= Min(x1, x2)) and (px <= Max(x1, x2)) and (py >= Min(y1, y2)) and
4.                 (py <= Max(y1, y2)) then
5.                 Result := True
6.         else
7.                 Result := False
8. end;

I think i alleady have a PtinRectF function, or am i wrong?
Title: Re: Problem with Collision detection
Post by: jamie on June 15, 2019, 05:33:19 pm
That code looks a little fishy because you are using MIN/Max etc..

There will be times that you will have negative numbers that you need to use for example when
a sprite is partially being shown on the edge..
Code: Pascal  [Select]
1. Function FloatPtInSquare(X,Y, X1,Y1,X2,Y2:Double):Boolean;
2.  Begin
3.     Result := false;
4.      If X < X1 Then Exit else
5.       IF X >= X2 Then Exit else
6.        If Y < Y1 then Exit else
7.          Result := Y < Y2;
8.  end;
9.
10. This is what I had in mind, you'll notice that I don't use the edge of X2 and and Y2, this code operates like the integer version of the PtinRect where the inside is not up on the right and bottom of the rectangle..
11.
12.  This reason for this is you can subtract the left/top from the Right/Bottom to get the number of pixels within..
13.
14.
Title: Re: Problem with Collision detection
Post by: Handoko on June 15, 2019, 07:04:21 pm
I think I have solved the problem.

I modified the code to make it compilable on Linux. I also added an autofire checkbox and bullet speed trackbar. Also, TTimer.Interfal lower than 16 usually is useless, so I changed it to 16.

If you want to compare the source codes, I recommend Meld.

The solution for the issue is to use CompareValue and set a tolerance/delta for it:
https://www.freepascal.org/docs-html/rtl/math/comparevalue.html

I use 0.1 for the tolerance.
Title: Re: Problem with Collision detection
Post by: IroncrossBG on June 15, 2019, 07:53:17 pm
I think I have solved the problem.

I modified the code to make it compilable on Linux. I also added an autofire checkbox and bullet speed trackbar. Also, TTimer.Interfal lower than 16 usually is useless, so I changed it to 16.

If you want to compare the source codes, I recommend Meld.

The solution for the issue is to use CompareValue and set a tolerance/delta for it:
https://www.freepascal.org/docs-html/rtl/math/comparevalue.html

I use 0.1 for the tolerance.

It's still doing it. I think am getting close to fixing it. From my tests, i think bullet position or future bullet position sometimes is actually on the line itself and can't do a proper Line Intersect check.
Title: Re: Problem with Collision detection
Post by: Handoko on June 15, 2019, 08:01:31 pm
Maybe you need to set the delta lower.
Title: Re: Problem with Collision detection
Post by: IroncrossBG on June 16, 2019, 12:15:42 am
Ok, i give up. Decided to just use Point in Polygon function and be done with this.

Code: Pascal  [Select]
1. function PNPoly(X, Y: Double; Polygon: array of TPointF): Boolean;
2. var
3.         I, J, pLength: Integer;
4.         C: Boolean;
5. begin
6.         pLength := Length(Polygon) - 1;
7.         J := pLength;
8.         C := False;
9.         for I := 0 to pLength do
10.         begin
11.                 if ((((Polygon[I].Y <= Y) and (Y < Polygon[J].Y)) or
12.                         ((Polygon[J].Y <= Y) and (Y < Polygon[I].Y))) and
13.                         (X > (Polygon[J].X - Polygon[I].X) * (Y - Polygon[I].Y) /
14.                         (Polygon[J].Y - Polygon[I].Y) + Polygon[I].X)) then
15.                         C := not C;
16.                 J := I;
17.         end;
18.         Result := C;
19. end;
Title: Re: Problem with Collision detection
Post by: Handoko on June 16, 2019, 04:34:25 pm
Ok, i give up.

Don't give up easily friend.

I'm still inspecting your (previous) code. And I found some interesting things about the bug:
- The bullet jump over issue won't happen if the asteroid is not rotating
- Clockwise and anticlockwise rotation give different results

Press 'F' to have clockwise rotation and you will see the bullets jump over issue. But if you release the 'F' key then you can see the collision detection works correctly.

Now try to press 'R' to have anticlockwise rotation. If you pay attention you will notice the condition to make the issue appears is different for clockwise and anticlockwise rotation.
Title: Re: Problem with Collision detection
Post by: jamie on June 16, 2019, 04:41:20 pm
Some code should be rewritten to take advantage of readable code and efficiency..

For example

for I := 0 to pLength do with Polygon[ I ] do
begin
// Then address the members directly...

End;

also, as soon as the Result is true a BREAK should be executed to get out of the remaining loop,
this will speed up things.
Title: Re: Problem with Collision detection
Post by: IroncrossBG on June 16, 2019, 06:52:53 pm
Ok, i give up.

Don't give up easily friend.

I'm still inspecting your (previous) code. And I found some interesting things about the bug:
- The bullet jump over issue won't happen if the asteroid is not rotating
- Clockwise and anticlockwise rotation give different results

Press 'F' to have clockwise rotation and you will see the bullets jump over issue. But if you release the 'F' key then you can see the collision detection works correctly.

Now try to press 'R' to have anticlockwise rotation. If you pay attention you will notice the condition to make the issue appears is different for clockwise and anticlockwise rotation.

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.

Some code should be rewritten to take advantage of readable code and efficiency..

For example

for I := 0 to pLength do with Polygon[ I ] do
begin
// Then address the members directly...

End;

also, as soon as the Result is true a BREAK should be executed to get out of the remaining loop,
this will speed up things.

Will try to optimize it. Any ideas on how the find the collision point using PNPoly? I think i have an idea... the bullet has angle and maybe raycast a line at that angle - 180 and check intersect point? will this work? Or maybe check if future Pos is inside the asteroid and then check intersect between future pos and current pos, thus, finding collision point.
Title: Re: Problem with Collision detection
Post by: Handoko on June 16, 2019, 07:27:24 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.
Title: Re: Problem with Collision detection
Post by: IroncrossBG 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...  %)
Title: Re: Problem with Collision detection
Post by: Handoko 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.
Title: Re: Problem with Collision detection
Post by: engkin 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.
Title: Re: Problem with Collision detection
Post by: IroncrossBG 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;
Title: Re: Problem with Collision detection
Post by: IroncrossBG on June 16, 2019, 10:27:52 pm
Ok, here is the project with my implementation. Did some changes here and there.
Title: Re: Problem with Collision detection
Post by: jamie 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.
Title: Re: Problem with Collision detection
Post by: SymbolicFrank 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.

Title: Re: Problem with Collision detection
Post by: engkin 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.
Title: Re: Problem with Collision detection
Post by: SymbolicFrank 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.
Title: Re: Problem with Collision detection
Post by: Thaddy 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.
Title: Re: Problem with Collision detection
Post by: eny on June 18, 2019, 09:50:52 pm
Interesting topic.
Was just working on an SDL2 version to develop a little framework  :D
Title: Re: Problem with Collision detection
Post by: SymbolicFrank 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.
Title: Re: Problem with Collision detection
Post by: IroncrossBG 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.