James Tauber

journeyman of some

blog > 2006 > 03 > 24 >

Quadtrees in Javascript and CSS

Quadtrees are a data structure that involves recursively dividing squares into quarters. I like to think of them as binary trees for spatial data. Indeed, they get used a lot for spatial indexing. They also get used a lot in games (especially MMORPGs) as a way of varying the level of detail required in different areas of a map.

For a browser-based game idea I have, I want a way of selecting arbitrary regions and I wondered if a quadtree approach might work for the UI. So I then wondered if quadtrees could be displayed and manipulating using CSS and Javascript.

It took me a little while to settle on the best way to arrange four consecutive div elements into a 2x2 arrangement and it was quite frustrating that adding borders to the divs threw off the layout regardless of what approach I took. But I'm very happy with the end result.

It took even longer to sort out the manipulation of CSS via Javascript as I'm a novice in that area. But again, it all turned out nicely, even better than I expected.

You can see a demo of the result. Select "divide" mode and clicking on a square will divide it into four. Select "select" mode and clicking on a square will toggle whether it's part of the selection or not.

It works in Safari and Firefox. I can't be bothered testing it in IE :-)

Categories:
prev « games » next
prev « javascript » next
prev « css

Comments (6)

Nelson Clemente on March 25, 2006:

Should I be concerned that your demo kept me entertained for a few minutes this morning? *click* *click* ok one more... *click* :P

James Tauber on March 25, 2006:

No more concerned than the rest of us have been about you for a while, Nelson :-)

John Cowan on March 27, 2006:

For the record, it does not work in IE6. You can click on the mode buttons and the latest one lights up, but clicking on the big gray square does nothing.

Nelson Clemente on March 27, 2006:

It doesn't work on IE7 Beta 2 Build 5335 either...

Scott W on March 30, 2006:

For the record, use Firefox!

John Cowan on May 16, 2006:

Of course I *use* Firefox. But I *test* with IE6 as well.
Created: March 24, 2006
Last Modified: March 24, 2006
Author: jtauber