Of (Quad-) trees and (Texture-) Atlases

Hi guys!

Another update, in which I’ll talk about some technical things.

As always find the game here: https://scavengersfate.myfarynet.eu/

Let’s talk about some new features in the game, which both use some techniques you’d find in a lot of popular games.

First of all, with the creation of an actual world with possible hundreds of ships flying around I had to manage the amount of ships currently rendered and calculated.

So I decided to split up the world into sectors and manage these via Quadtrees (wikipedia link).
What that does is basically sort the ships into a tree with 4 branches, which in return usually have 4 subbranches of their own. The highest node basically represents the whole map and the 4 branches are the 4 quarters. Then these are split into more quarters etc. (if there are enough ships in this area). Read the wiki article if it really interests you :)

So basically for each frame I just check the current location in the quadtree and it runs through the tree to find the ships which are close.

Quadtrees are usually very performant, because finding certain locations is pretty easy. So many games use these for example for physics simulation, because bullets do not have to be checked against all targets, but only the close targets (which are quickly found in the quadtree) and therefore the calculations become much easier.


Right now if you switch to the map (by pressing “m” or clicking on map) – all ships in the world are simulated (!); however, projectiles are not. Therefore these ships may sometimes get into battle and chase enemies around without ever killing them.
In a more final version I will not represent and/or calculate other ships on the map at all (mystery!), so that’s alright.

If all ships are simulated, they all check the distance to all other ships which are calculated right now. I thought I could speed up the process by using quadtrees. Turns out that for some reason that slows things down a lot more than just checking every other ship. I think my implementation of quadtrees is pretty much by the book, so that was a huge disappointment. Maybe javascript is not that great when it comes to reading a lot of different arrays, I don’t know :(

So yeah, I guess it would be faster to just check all ships each frame and only calculate those with a small distance to the player ship instead of the quadtree traversal. (Especially since these make the game a bit more unpredictable (and possibly a bit buggy), for instance you have to change the location of the ships inside the quadtree each time it crosses the borders of the lowest quadtree node…)

I am keeping the quadtree system, I hope it performs better when the world becomes even bigger.
Maybe with some optimization I can get some better results.

A single texture to rule them all

So let’s talk about the next system I implemented with high hopes for performance gains, which in the end were disappointed again and at the same time introduced 100 new possible bugs.02_tex_atlas

So the fun part was to find an algorithm to order these differently sized ships. The result can be seen in the .gif above. For more info: http://en.wikipedia.org/wiki/Texture_atlas (and especially http://clb.demon.fi/files/RectangleBinPack.pdf)

How are ships rendered in the game?

It used to be: Every block on the ship is a vector element and is drawn on the general canvas

Good: Easy to manage.
Bad: super expensive. Drawing every vector graphic every frame is not doable in larger quantities.

Then it was: Every ship has its own canvas, where all elements are drawn onto. This canvas is then drawn onto the screen and rotated/translated. The ship’s canvas is only redrawn if something changes (e.g. zooming in or losing parts, adding new parts)

Good: Super easy to manage. Good performance in general
Bad: I thought it would be inefficient to have as many canvases as ships in the memory.

Now it is: All ships and some other objects (like text) are drawn onto a big texture. When drawing individual ships we look up their position on the texture atlas and draw it from there.

Good: Can trace problems more easily, have only one giant texture. Interesting problem to solve.
Bad: Countless new bugs possibly, performance did not really improve :(


In this picture I have visualized the texture atlas on the top left :)

Why is this likely to cause new bugs?
I read the texture from one giant texture file, but it is non-trivial to find out when to udpate all the ships, what to do when the texture is full etc. We’ll see.

I hope you liked the little tech blog. Does not really inform to much in detail, because I think all of these can be explained better in many many internet articles/ university papers.

Next time it’s gonna be about gameplay and story, I promise!


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s