# Quad grid collisions and spacial partitioning
**URL:** https://discourse.processing.org/t/quad-grid-collisions-and-spacial-partitioning/15426
**Category:** Gallery
**Created:** [November 12, 2019, 6:50pm UTC](https://discourse.processing.org/t/quad-grid-collisions-and-spacial-partitioning/15426 "2019-11-12T18:50:46Z")
**Posts on this page:** 4
**Page:** 1
### Author:  [@paulgoux](https://discourse.processing.org/u/paulgoux)
#### Post date: [November 12, 2019, 6:50pm UTC](https://discourse.processing.org/t/quad-grid-collisions-and-spacial-partitioning/15426/1 "2019-11-12T18:50:46Z")
Hi there, last time I posted about this question, I was attempting to create a program that would help in calculating collisions, in circular bodies, the standard calculation without any grid management involves n to the n calculations and so can be costly when using a large dataset.
My first attempt was very flawed and only barely worked, so after a fresh look at the problem I have addressed all the problems, ideally I would like to turn this into a library later, if anyone has any ideas or would like to contribute please feel free, otherwise here is the code.
check performance by comparing the reg\_collisions, with the quad\_collisions.
Please note further speed improvements can be attained using FX2D, however this may depend on specific use.
> **[spatial partitioning 2 - OpenProcessing](https://www.openprocessing.org/sketch/791166)**
>
> improve collision detection on large datasets by reducing the amount of items needed to be filtered by using grid spacing
If you notice any errors please let me know
---
### Author:  [@jeremydouglass](https://discourse.processing.org/u/jeremydouglass)
#### Post date: [November 17, 2019, 5:51am UTC](https://discourse.processing.org/t/quad-grid-collisions-and-spacial-partitioning/15426/2 "2019-11-17T05:51:20Z")
> [@paulgoux](#):
>
> deally I would like to turn this into a library later
Thanks for sharing this. How do you imagine it becoming a reusable library? Would e.g. quad\_collidable be an interface that users could implement in their objects?
Collision detection can be a bit tricky to generalize as an a la carte small library outside a full framework like JBox2D – or toxiclibs – or gicentre utils (hashgrid) – or Pixelflow. These are all big libraries, and the collision part may be in part because it matters a lot whether you are testing circle-rect or polygon-point or line-line collision, if you do it by axis aligned bounding boxes, and then whether the colliding object classes are important and if the collidee properties like angle/speed/size are needed for what happens next (to bounce, or hitpoints, or inventory etc.)…
---
### Author:  [@paulgoux](https://discourse.processing.org/u/paulgoux)
#### Post date: [November 17, 2019, 6:56pm UTC](https://discourse.processing.org/t/quad-grid-collisions-and-spacial-partitioning/15426/3 "2019-11-17T18:56:38Z")
not sure I’ll have to make use of matrices, and then I suppose I would have to tailor the quad\_collide to account for these cases.
---
### Author:  [@paulgoux](https://discourse.processing.org/u/paulgoux)
#### Post date: [July 24, 2020, 7:20pm UTC](https://discourse.processing.org/t/quad-grid-collisions-and-spacial-partitioning/15426/4 "2020-07-24T19:20:44Z")
an update on this project. Ive updated it and ironed out flaws, and have made a second version which now now makes use of dynamic size grids.
 
note this does not necessarily give the best speed, I was averaging 45-55 fps using the FX2D renderer using 4000 entities however it is useful when you have to compute static neighbouring entities rather than having to go through the entire grid.
original’s (static size) speed.
I understand other established libraries will probably make more robust/ efficient versions of this idea, but this was a fun idea, and allows me to quickly integrate it within any project.
new ( dynamic size);
