### Bookstore

 Computer Math and Games in Pascal (preview) Lazarus Handbook

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

#### IroncrossBG

• New Member
• Posts: 10
##### Problem with Collision detection
« 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!
« Last Edit: June 15, 2019, 12:49:20 pm by IroncrossBG »

#### jamie

• Hero Member
• Posts: 3640
##### Re: Problem with Collision detection
« Reply #1 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..

The only true wisdom is knowing you know nothing

#### Handoko

• Hero Member
• Posts: 3851
• My goal: build my own game engine using Lazarus
##### Re: Problem with Collision detection
« Reply #2 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?

#### SymbolicFrank

• Hero Member
• Posts: 639
##### Re: Problem with Collision detection
« Reply #3 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.

#### IroncrossBG

• New Member
• Posts: 10
##### Re: Problem with Collision detection
« Reply #4 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

#### IroncrossBG

• New Member
• Posts: 10
##### Re: Problem with Collision detection
« Reply #5 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?

#### jamie

• Hero Member
• Posts: 3640
##### Re: Problem with Collision detection
« Reply #6 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.
The only true wisdom is knowing you know nothing

#### Handoko

• Hero Member
• Posts: 3851
• My goal: build my own game engine using Lazarus
##### Re: Problem with Collision detection
« Reply #7 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.

#### IroncrossBG

• New Member
• Posts: 10
##### Re: Problem with Collision detection
« Reply #8 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.

#### Handoko

• Hero Member
• Posts: 3851
• My goal: build my own game engine using Lazarus
##### Re: Problem with Collision detection
« Reply #9 on: June 15, 2019, 08:01:31 pm »
Maybe you need to set the delta lower.

#### IroncrossBG

• New Member
• Posts: 10
##### Re: Problem with Collision detection
« Reply #10 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;
« Last Edit: June 16, 2019, 12:17:44 am by IroncrossBG »

#### Handoko

• Hero Member
• Posts: 3851
• My goal: build my own game engine using Lazarus
##### Re: Problem with Collision detection
« Reply #11 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.

#### jamie

• Hero Member
• Posts: 3640
##### Re: Problem with Collision detection
« Reply #12 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.
The only true wisdom is knowing you know nothing

#### IroncrossBG

• New Member
• Posts: 10
##### Re: Problem with Collision detection
« Reply #13 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.
« Last Edit: June 16, 2019, 07:20:56 pm by IroncrossBG »

#### Handoko

• Hero Member
• Posts: 3851
• My goal: build my own game engine using Lazarus
##### Re: Problem with Collision detection
« Reply #14 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.