dcsimg
Results 1 to 4 of 4

Thread: [VB6] Spatial Grid for 2D collision detection

  1. #1

    Thread Starter
    Hyperactive Member
    Join Date
    Sep 2010
    Location
    Italy
    Posts
    452

    [VB6] Spatial Grid for 2D collision detection

    SPATIAL GRID for 2D COLLISION DETECTION

    Author: reexre, MiorSoft
    (04/2019)

    When having a lot of objects (2D) collision detection may be computionally very expensive.
    In this case when I talk about "collision detection", I mean the detection of the proximity between 2 points below a certain distance. (without involving any "shape")
    Checking each pairs of N objects without any optimization would bring to a N*(N-1)/2 proximity tests. (Number of unique pairs)
    eg:

    Code:
    N of Objects | N of Unique pairs
         4       |         6
        10       |        45
        50	     |     1.225
       100       |     4.950 
      1000	     |   499.500 
      2000       | 1.999.000
    Not really the case to do so.



    -cSpatialGrid-
    This is a Class to speed up the 2D "Collision detection".

    It Works so:
    It divides the 2D space in squared cells forming a Grid.
    The Cell dimension is equal to the Proximity distance to detect.
    Each point is "inserted" in its corresopnding grid's Cell.


    To check for Pairs of points closer than proximity distance we iterate through each cell this way:

    1) Check Each pairs in current cell
    2) Check Pairs between current cell and cell at right (X+1)(Y)
    |X>X|
    -----
    |.|.|


    3) Check Pairs between current cell and cell at down (X)(Y+1)
    |X|.|
    -v---
    |X|.|


    4) Check Pairs between current cell and cell at Right-Down (X+1)(Y+1) (Top-Down Diagonal)
    |X|.|
    --\--
    |.|X|


    5) Check Pairs between one cell Down (X,Y+1) and one cell Right (X+1)(Y) (Bottom-Up Diagonal)
    |.|X|
    --/--
    |X|.|


    The class returns the points indexes that forms detected pairs and the relative distances in X and Y directions.
    We may add to returned values even the Squared Distances between Pairs of points. (Still don't know if it worths it... easily feasible)

    In this Code example is performend even a minimal Force engine.

    I would not add much more. I think the code is enough self-explanatory.




    This code uses vbRichClient (Sorry for those who may be reluctant about using it)
    Anyway It's needed exclusively for "rendering" purpose.

    (I still have to test if it's faster than the QuadTree (For collision detection) implementation present on VBForums codebank)

    If you have any idea to optimize/speed up the code, it is welcome. (else if you mean to use a complete different approach I'd like you to do it in another thread. Thanks)

    One last thing:
    (When Compiled) On exiting MainLoop / App the program crashes... I need help to solve this. Thanks

    [ Resolved from V3]



    EDIT:
    Update to V2 since I found bug about Cell pairs (hope they are resolved)
    Update to V3 . Resolved crash on exit and further cell pairs optimization


    You can find here example of use and 3D version
    http://www.vbforums.com/showthread.p...hydrodynamics)
    Attached Files Attached Files

  2. #2
    Frenzied Member
    Join Date
    Aug 2010
    Location
    Canada
    Posts
    1,360

    Re: [VB6] Spatial Grid for 2D collision detection

    Quote Originally Posted by reexre View Post
    One last thing:
    (When Compiled) On exiting MainLoop / App the program crashes... I need help to solve this. Thanks

    Try putting New_C.CleanupRichClientDll in your Form_Unload event to see if this helps with the crash on exit.

  3. #3

    Thread Starter
    Hyperactive Member
    Join Date
    Sep 2010
    Location
    Italy
    Posts
    452

    Re: [VB6] Spatial Grid for 2D collision detection

    Quote Originally Posted by jpbro View Post
    Try putting New_C.CleanupRichClientDll in your Form_Unload event to see if this helps with the crash on exit.
    thanks I resolved the problem doing as you said.

  4. #4
    Lively Member
    Join Date
    Feb 2014
    Location
    Ohio
    Posts
    122

    Re: [VB6] Spatial Grid for 2D collision detection

    This is really cool! I played with it and looked through the code. I wouldn't be able to do that if you put a gun to my head, so everyone will have to excuse me that I'm in awe over stuff like this.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Featured


Click Here to Expand Forum to Full Width