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

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

Nice example! Could almost not stop touching the screen

Fantastic example! Thanks!