Et-Setera

They say that slow and steady wins the race. In the case of this project, the only thing I have going for me is the slow part. Nicolas Gramlich, author of the AndEngine library on which this is based, referred to this part of the project as “destroyable terrain”. I really like that phrase, so I think I will continue to use it here.

In Early Digger Support I covered the initial digger support. At that point I had managed to update the in-memory collision map , but updating the actual textures driving AndEngine was proving to be a bit more difficult. I’m still not there, but I think I’m moving in a positive direction. The following video shows the current state of things. The textures are being updated with a full red fill to make it clear that they have been hit.

So, why is everything turning red? Well, that turns out to be the next item that will need to be dealt with… shared textures. To save memory, many of the sprites share common textures and texture regions. Thus, in the current implementation, changing the underlying texture information affects all sprites that share that information. This is something I knew would have to be dealt with eventually, so it appears that eventually is now .

Quad Trees

When I initially started playing with altering the texture data, I was worried about performance. My first attempt to locate the sprites to be altered used the standard AndEngine functionality to query collisions using the “collidesWith” method for shapes. This proved to be really expensive for gross-level collision detection. My performance tests using the built in Android tools for capturing trace data showed that much of the cost of the terrain destruction was accountable to simply finding the sprite to be altered.

I had heard previously about the use of Octrees in 3D to help do quick searches on the boundaries of objects. In the 2D world, Quadtrees are used instead. I was surprised not to find an actual Quadtree implementation on the web, but was able to piece together a nice generic implementation based on lots of research. With the Quadtree, I was able to get closer to reasonable performance, as you can see in the video capture. My hope is that using a Quadtree and doing the necessary cloning to split sprite textures will lead to a reasonably performant destroyable terrain implementation, but that is still yet to be seen.

Java Generics Aside

My Quadtree implementation initially was built to accept a single object type. It seemed more useful to use Java Generics to make the Quadtree more generally useful. I was hung up by one thing though. I wanted to be able to allow the Quadtree to accept objects with a certain interface declaration. Basically, I wanted this:

public class Quadtree<T implements IBoundedObject> {

Where IBoundedObject is simply defined as:

public interface IBoundedObject {
	Rect getBounds();
}

However, the implements extension is not supported by the generics syntax. This had me confused for a while until I realized that it is possible to do what I wanted to do, but needed to specify extends :

public class Quadtree<T extends IBoundedObject> {

I’m sure there is some perfectly good technical reason for doing things this way, but personally I find the lack of consistency confusing and unnecessary.

Next Time

With any luck, I will be able to show a reasonably performant implementation of destroyable terrain by pulling the various pieces together.