Quadtree example

Code Sharing
1

Hey all,

Looking through the web for terrain optimizations, I noticed that quite a few people don’t seem to understand tree data structures.

For those interested, here is a simple version of the quadtree class I use on my current terrain project.

Quadtrees are great for 2D collision detection, culling terrain, and a lot more stuff I don’t know about…

Example program: http://pastebin.com/XUP11aWi

The quadtree class:

Quadtree = class()

function Quadtree:init(xmin, ymin, xmax, ymax, depth)
    self.xmin = xmin
    self.xmax = xmax
    self.ymin = ymin
    self.ymax = ymax
    self.children = {}

-- Subdivide until desired depth is reached
    if depth > 0 then
        depth = depth - 1
        
        local xmoy = (xmin + xmax)/2
        local ymoy = (ymin + ymax)/2
        
        self.children[1] = Quadtree(xmin, ymin, xmoy, ymoy, d)
        self.children[2] = Quadtree(xmin, ymoy, xmoy, ymax, d)
        self.children[3] = Quadtree(xmoy, ymoy, xmax, ymax, d)
        self.children[4] = Quadtree(xmoy, ymin, xmax, ymoy, d)
    end

end

------------------------------

qt = Quadtree(0, 0, 512, 512, 4)

Cheers,

Xavier

2

Nice example! Could almost not stop touching the screen :slight_smile:

3

Fantastic example! Thanks! :slight_smile: