Tuesday, October 28, 2014

Destructible 2D Terrain Rendering Using QuadTree

When I was in junior high school, I was an addict on playing Gunbound, a Korean turn-based shooting games similar to Worms (but at that time Gunbound was the real thing! haha).

When your shoots hit the ground, it will explode in circular fashion, and the terrain is then destroyed and deformed to the new shaped smoothly. From then on I was quite determined to create the same game, but one thing has always been a hindrance.

 I've always wondered how did they do the rendering on the ground so nicely. When I try to search online for relevant discussion, some suggested using pixel-perfect collision handling, but that is kind of very expensive especially if the map is huge. Then there is a tile-based approach, while it is simple and efficient, it is very limiting in a sense that you cannot have grounds that have arbitrary shapes. Yet the one in Gunbound is arbitrary and natural.

Then I read about rendering terrain using quadtree, and it is awesome! Quadtree is used for keeping track on the "dirt" on the terrain, so each block of pure dirt will get its own node, or otherwise is split into 4 smaller pieces and recursively mapped into the quadtree. The method is really promising and I have just finished a simple implementation of that :D

Here is the link to the demo:
2D Destructible Terrain Rendering using QuadTree