Quad Tree gives 3 x fps for collision detection of 180 sprites

spikey

Maybe you stumbled upon collision detection limits too.

A Quad Tree is a kind of a linked list, where every node has 4 children. Every children stores sprites in one quadrant of the screen. And every quadrant splits up again in four quadrants and so on, until there are not more than k sprites in one node (visually in one field). Here I defined k as 3.
If the tree has been built, it is possible to only check each field that contains more than one sprite if it collides with one of the other sprites, in the same field.

This is my first draft of a Quad Tree and it's still "work in progress". Your help is also much appreciated in improving this code.

Share code: 9M2P3MNDN8 (live)

Thats how far I was able to push this:
Collision checks of 180 sprites at > 30 fps (which is the minmal frame rate I try to keep). Checking the collisions one by one (180 x 180 checks), I got 10 fps.

Maybe I can get around with that, if I handle moving and not moving objects differently in my game Last Worm Creeping I try to improve.

PickleCatStars

Wow, that’s a massive improvement!

vinicity

I downloaded your demo, @spikey, and it’s very interesting and quite impressive.

I came to think about my old light based sneak game. Do you think your technique could be used in that one as well?
I just shared it (so still pending), but maybe you could take a look if you have the time?

Download ID: NN8AVRND5C

spikey

@vinicity Sure I can have a look. I have something that needs to be done first, but I will work hard to get that done this week. Only after this, it will show, if its practical.

spikey

I need an insert() function for the Quad Tree, but run into a huge problem: one element of a custom array attribute of a sprite cannot be changed, as far I can tell. e.g.:

node = createSprite()
node.customAttribute = [1, 2, 3]
node.customAttribute[0] = 8

returns the error Attempted to index non-array type.
Same for adding an element node.customAttribute[3] = 4

I check now if I can change the code to always set the whole array at once.

spikey

The second problem is I cannot use recursion to pass references to arrays: this is an example how I was hoping to be able to change an id of a linked element (in my project I would have used this to remove and insert elements in the middle of the tree)

node = [.children = [], .id = 0]
node.children[0] = [.children = [], .id = 1]

function changeId(ref node)
   if len(node.children) == 0 then
      node.id = 888
   else      
      changeId(node.children[0])
   endif
return void

print(node.children[0].id)
update()
sleep(10)

This always shows 1 and never 888.

spikey

Ok, if I want to build an insert and remove function, I will have to pass indexes to a major array instead of references, I guess.

spikey

I also tried this without success:

struct NODE_TYPE
   NODE_TYPE children = []
   int id
endstruct

NODE_TYPE node
node.id = 0
node.children[0] = create()

function create()
   NODE_TYPE node
return node

// same changeId() function and test as above

shows also 1. I am wondering if I miss something.

Z-Mann

Yeah, that's one way 'ref' does not work. Currently, the thing passed to a ref argument needs to be a simple variable for changes to it to become visible, no array element, no struct element, no array slice. Go with a big array to store your nodes, pass around and store indices into it. That seems to be the only way to manage complex mutable data structures right now.

Devieus

I gave this a look and I found an easy improvement as it is now is to increase the node capacity to around 9 or 10. It seems to perform much better than 3. After that it starts to bottleneck somewhere else.