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 :-)

The original post was in the categories: games javascript css but I'm still in the process of migrating categories over.

The original post had 6 comments I'm in the process of migrating over.