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

1. ## [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

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

Originally Posted by reexre
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. ## Re: [VB6] Spatial Grid for 2D collision detection

Originally Posted by jpbro
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.

#### 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