Optimized the collision detection logic behind the `clipline` function #4054

Sheepfan0828 · 2023-10-20T04:12:53Z

Contributor

Name: Yilun Fan (u7277320)

Issue Addressed

PR Summary

The issue i am fixing now is about the bug occurs in Rect.clipline() function dealing with the collision between lines of different angles, and 4 or more than 4 rectangles. For dealing with this, i have reproduced the problem at first, by creating 4 rectangles and lines of the angle within 0-180 degrees inclusive so that we can use Rect.clipline function to check whether a collision has been occured. The result is shown below and we supposed line has the red color if a collision has benn dectected and green color otherwise.

We can observe that most of the lines are still green although the line is actually colliding with the other rectangles.
And then, according to the issue description, we have two tasks to deal with:

Add a small test case proving the issue in test/rect.py
The code for Rect.clipline is in src_c/rect.c@pg_rect_clipline

For task 1, I have added the unittest for Rect.clipline() in test/test_rect.py file (i cannot find rect.py in test folder and only find this). This unittest is mainly testing the case of the collision with 4 or more rectangles using the function Rect.clipline() and get the following failure:

For task 2, I have modified the code in rect.c@pg_rect_clipline to optimize the Intersection collision detection logic with the basic argument analysis unchanged. I have created my own IntersectRectAndLine function so that it will be integrated intp the pg_rect_clipline function to improve the accuracy of the collision dectection between the line and the rectangles.

…ions in rect.c file to fix the problem of the rays colliding with 4 or more rectangles

illume · 2023-10-20T20:03:32Z

Hey hey.

Thanks for this :)

There's some warnings different compilers spotted. You can see them in the failed checks if you search for rect.c.

Pasted here for your convenience.

src_c/rect.c(1177): error C2220: warning treated as error - no 'object' file generated
src_c/rect.c(1177): warning C4013: 'direction' undefined; assuming extern returning int
src_c/rect.c(1188): warning C4244: '=': conversion from 'int' to 'float', possible loss of data
src_c/rect.c(1190): warning C4244: '=': conversion from 'int' to 'float', possible loss of data

  src_c/rect.c: In function ‘line_intersects_line’:
  src_c/rect.c:1177:10: warning: implicit declaration of function ‘direction’ [-Wimplicit-function-declaration]
   1177 |     d1 = direction(l1_x1, l1_y1, l1_x2, l1_y2, l2_x1, l2_y1);
        |          ^~~~~~~~~
  src_c/rect.c:1186:15: warning: variable ‘s’ set but not used [-Wunused-but-set-variable]
   1186 |         float s, t;
        |               ^
  src_c/rect.c: In function ‘pg_rect_clipline’:
  src_c/rect.c:1221:15: warning: variable ‘rect’ set but not used [-Wunused-but-set-variable]
   1221 |     SDL_Rect *rect = &self->r, *rect_copy = NULL;
        |               ^~~~
  In file included from /opt/hostedtoolcache/Python/3.10.13/x64/include/python3.10/Python.h:126,
                   from src_c/_pygame.h:35,
                   from src_c/pygame.h:30,
                   from src_c/rect.c:27:
  /opt/hostedtoolcache/Python/3.10.13/x64/include/python3.10/modsupport.h:20:41: warning: ‘int_y1’ may be used uninitialized in this function [-Wmaybe-uninitialized]
     20 | #define Py_BuildValue                   _Py_BuildValue_SizeT
        |                                         ^~~~~~~~~~~~~~~~~~~~
  src_c/rect.c:1367:17: note: ‘int_y1’ was declared here
   1367 |     int int_x1, int_y1, int_x2, int_y2;
        |                 ^~~~~~
  In file included from /opt/hostedtoolcache/Python/3.10.13/x64/include/python3.10/Python.h:126,
                   from src_c/_pygame.h:35,
                   from src_c/pygame.h:30,
                   from src_c/rect.c:27:
  /opt/hostedtoolcache/Python/3.10.13/x64/include/python3.10/modsupport.h:20:41: warning: ‘int_x1’ may be used uninitialized in this function [-Wmaybe-uninitialized]
     20 | #define Py_BuildValue                   _Py_BuildValue_SizeT
        |                                         ^~~~~~~~~~~~~~~~~~~~
  src_c/rect.c:1367:9: note: ‘int_x1’ was declared here
   1367 |     int int_x1, int_y1, int_x2, int_y2;
        |         ^~~~~~

… IntersectRectAndLine'

Sheepfan0828 · 2023-10-21T15:02:53Z

Hey hey.

Thanks for this :)

There's some warnings different compilers spotted. You can see them in the failed checks if you search for rect.c.

Pasted here for your convenience.

src_c/rect.c(1177): error C2220: warning treated as error - no 'object' file generated
src_c/rect.c(1177): warning C4013: 'direction' undefined; assuming extern returning int
src_c/rect.c(1188): warning C4244: '=': conversion from 'int' to 'float', possible loss of data
src_c/rect.c(1190): warning C4244: '=': conversion from 'int' to 'float', possible loss of data

  src_c/rect.c: In function ‘line_intersects_line’:
  src_c/rect.c:1177:10: warning: implicit declaration of function ‘direction’ [-Wimplicit-function-declaration]
   1177 |     d1 = direction(l1_x1, l1_y1, l1_x2, l1_y2, l2_x1, l2_y1);
        |          ^~~~~~~~~
  src_c/rect.c:1186:15: warning: variable ‘s’ set but not used [-Wunused-but-set-variable]
   1186 |         float s, t;
        |               ^
  src_c/rect.c: In function ‘pg_rect_clipline’:
  src_c/rect.c:1221:15: warning: variable ‘rect’ set but not used [-Wunused-but-set-variable]
   1221 |     SDL_Rect *rect = &self->r, *rect_copy = NULL;
        |               ^~~~
  In file included from /opt/hostedtoolcache/Python/3.10.13/x64/include/python3.10/Python.h:126,
                   from src_c/_pygame.h:35,
                   from src_c/pygame.h:30,
                   from src_c/rect.c:27:
  /opt/hostedtoolcache/Python/3.10.13/x64/include/python3.10/modsupport.h:20:41: warning: ‘int_y1’ may be used uninitialized in this function [-Wmaybe-uninitialized]
     20 | #define Py_BuildValue                   _Py_BuildValue_SizeT
        |                                         ^~~~~~~~~~~~~~~~~~~~
  src_c/rect.c:1367:17: note: ‘int_y1’ was declared here
   1367 |     int int_x1, int_y1, int_x2, int_y2;
        |                 ^~~~~~
  In file included from /opt/hostedtoolcache/Python/3.10.13/x64/include/python3.10/Python.h:126,
                   from src_c/_pygame.h:35,
                   from src_c/pygame.h:30,
                   from src_c/rect.c:27:
  /opt/hostedtoolcache/Python/3.10.13/x64/include/python3.10/modsupport.h:20:41: warning: ‘int_x1’ may be used uninitialized in this function [-Wmaybe-uninitialized]
     20 | #define Py_BuildValue                   _Py_BuildValue_SizeT
        |                                         ^~~~~~~~~~~~~~~~~~~~
  src_c/rect.c:1367:9: note: ‘int_x1’ was declared here
   1367 |     int int_x1, int_y1, int_x2, int_y2;
        |         ^~~~~~

I have roll back the code into the original to tackle this problem. And for fixing the collision detecting bugs, i have just optimized the code for dealing with the intection between the line and rectangles, create a new function Accurate_IntersectRectAndLine. If CI still not passed, i am wondering how pg_rect_clipline actually works to check my understanding so that i can try my best to fix the bug and ensure CI will pass.

illume · 2023-10-23T06:42:10Z

Sheepfan0828 Great. Now it seems to be compiling and running the tests :)

Now the next step is seeing why these tests are failing?

Sheepfan0828 · 2023-10-24T12:08:39Z

Sheepfan0828 Great. Now it seems to be compiling and running the tests :)

Now the next step is seeing why these tests are failing?

Thanks for your responding! I have just reviewed some of error messages from failed checks in CI, it says the problem also exist in existing files in src_c, which are not affected by the issue i am addressing. And i only file i have changed is just rect.c from src_c. I have taken a screenshot of the error message that related to a file that i haven't changed as an example:

I am now get confused with how should that happen. Hope someone can help me tackle this.

illume · 2023-10-27T06:37:55Z

hi.

It looks like there are a number of tests failing. See below.

======================================================================
FAIL: test_clipline_angle (pygame.tests.rect_test.PygameCliplineTest)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.10.13/x64/lib/python3.10/site-packages/pygame/tests/rect_test.py", line 57, in test_clipline_angle
    self.assertTrue(
AssertionError: False is not true : Intersection point (199, 106) is not on the boundary of rectangle <rect(200, 50, 100, 100)>

======================================================================
FAIL: test_clipline (pygame.tests.rect_test.RectTypeTest)
Ensures clipline handles four int parameters.
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.10.13/x64/lib/python3.10/site-packages/pygame/tests/rect_test.py", line 1183, in test_clipline
    self.assertTupleEqual(clipped_line, expected_line)
AssertionError: Tuples differ: ((4, 2), (21, 42)) != ((5, 6), (11, 19))

First differing element 0:
(4, 2)
(5, 6)

- ((4, 2), (21, 42))
  ((5, 6), (11, 19))

======================================================================
FAIL: test_clipline__both_endpoints_inside (pygame.tests.rect_test.RectTypeTest)
Ensures lines that overlap the rect are clipped.
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.10.13/x64/lib/python3.10/site-packages/pygame/tests/rect_test.py", line 1461, in test_clipline__both_endpoints_inside
    self.assertTupleEqual(clipped_line, expected_line)
AssertionError: Tuples differ: ((-10, 5), (10, 5)) != ((-9, 5), (9, 5))

First differing element 0:
(-10, 5)
(-9, 5)

- ((-10, 5), (10, 5))
?    ^^       ^^

  ((-9, 5), (9, 5))
?    ^       ^


======================================================================
FAIL: test_clipline__both_endpoints_outside (pygame.tests.rect_test.RectTypeTest)
Ensures lines that overlap the rect are clipped.
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.10.13/x64/lib/python3.10/site-packages/pygame/tests/rect_test.py", line 1430, in test_clipline__both_endpoints_outside
    self.assertTupleEqual(clipped_line, expected_line)
AssertionError: Tuples differ: ((0, 10), (20, 10)) != ((0, 10), (19, 10))

First differing element 1:
(20, 10)
(19, 10)

- ((0, 10), (20, 10))
?            ^^

  ((0, 10), (19, 10))
?            ^^


======================================================================
FAIL: test_clipline__edges (pygame.tests.rect_test.RectTypeTest)
Ensures clipline properly clips line that are along the rect edges.
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.10.13/x64/lib/python3.10/site-packages/pygame/tests/rect_test.py", line 1547, in test_clipline__edges
    self.assertTupleEqual(clipped_line, expected_line)
AssertionError: Tuples differ: ((10, 45), (10, 25)) != ((10, 44), (10, 25))

First differing element 0:
(10, 45)
(10, 44)

- ((10, 45), (10, 25))
?        ^

  ((10, 44), (10, 25))
?        ^


======================================================================
FAIL: test_clipline__endpoints_inside_and_outside (pygame.tests.rect_test.RectTypeTest)
Ensures lines that overlap the rect are clipped.
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.10.13/x64/lib/python3.10/site-packages/pygame/tests/rect_test.py", line 1513, in test_clipline__endpoints_inside_and_outside
    self.assertTupleEqual(clipped_line, expected_line)
AssertionError: Tuples differ: ((0, 10), (21, 10)) != ((0, 10), (10, 10))

First differing element 1:
(21, 10)
(10, 10)

- ((0, 10), (21, 10))
?            -

  ((0, 10), (10, 10))
?              

- ((4, 2), (21, 42))
  ((5, 6), (11, 19))

======================================================================
FAIL: test_clipline__two_sequences (pygame.tests.rect_test.RectTypeTest)
Ensures clipline handles a sequence of two sequences.
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.10.13/x64/lib/python3.10/site-packages/pygame/tests/rect_test.py", line 1205, in test_clipline__two_sequences
    self.assertTupleEqual(clipped_line, expected_line)
AssertionError: Tuples differ: ((4, 2), (21, 42)) != ((5, 6), (11, 19))

First differing element 0:
(4, 2)
(5, 6)

- ((4, 2), (21, 42))
  ((5, 6), (11, 19))

======================================================================
FAIL: test_clipline__two_sequences_kwarg (pygame.tests.rect_test.RectTypeTest)
Ensures clipline handles a sequence of two sequences using kwargs.
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.10.13/x64/lib/python3.10/site-packages/pygame/tests/rect_test.py", line 1229, in test_clipline__two_sequences_kwarg
    self.assertTupleEqual(clipped_line, expected_line)
AssertionError: Tuples differ: ((4, 2), (21, 42)) != ((5, 6), (11, 19))

First differing element 0:
(4, 2)
(5, 6)

- ((4, 2), (21, 42))
  ((5, 6), (11, 19))

======================================================================
FAIL: test_clipline__zero_size_rect (pygame.tests.rect_test.RectTypeTest)
Ensures clipline handles zero sized rects correctly.
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.10.13/x64/lib/python3.10/site-packages/pygame/tests/rect_test.py", line 1601, in test_clipline__zero_size_rect
    self.assertTupleEqual(clipped_line, expected_line)
AssertionError: Tuples differ: ((10, 25), (10, 25)) != ()

First tuple contains 2 additional elements.
First extra element 0:
(10, 25)

- ((10, 25), (10, 25))
  ()

illume · 2023-11-01T09:15:35Z

Let me know if you want some help continuing this?

<Yilun Fan, u7277320> optimized the logic of calculations of intersct…

1fc4bfa

…ions in rect.c file to fix the problem of the rays colliding with 4 or more rectangles

u7277320 added 2 commits October 22, 2023 01:28

Roll back the function pg_rect_clipline() and create the new function…

f7c29b1

… IntersectRectAndLine'

Fix the syntax error in pg_rect_clipline()

8207ba6

Fix the syntax error in pg_rect_clipline()

6b83173

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Optimized the collision detection logic behind the `clipline` function #4054

Optimized the collision detection logic behind the `clipline` function #4054

Sheepfan0828 commented Oct 20, 2023 •

edited

Loading

illume commented Oct 20, 2023

Sheepfan0828 commented Oct 21, 2023

illume commented Oct 23, 2023

Sheepfan0828 commented Oct 24, 2023

illume commented Oct 27, 2023

illume commented Nov 1, 2023

Optimized the collision detection logic behind the clipline function #4054

Are you sure you want to change the base?

Optimized the collision detection logic behind the clipline function #4054

Conversation

Sheepfan0828 commented Oct 20, 2023 • edited Loading

Contributor

Issue Addressed

PR Summary

illume commented Oct 20, 2023

Sheepfan0828 commented Oct 21, 2023

illume commented Oct 23, 2023

Sheepfan0828 commented Oct 24, 2023

illume commented Oct 27, 2023

illume commented Nov 1, 2023

Optimized the collision detection logic behind the `clipline` function #4054

Optimized the collision detection logic behind the `clipline` function #4054

Sheepfan0828 commented Oct 20, 2023 •

edited

Loading