The Project Gamma Development Progress Blog


Dec 03, 2011 by DX-MON
Ok, been a while since I last said anything here..
I swear there is a good reason and it's down to a project that has taken 5 months of hell to get to Beta (3 of which were months I was going to spend working on PokÚLegends but that got shot rather, now didn't it.. >_>)

Anyway, onto the meat of things:

It's been known by the team and myself for some time that rendering 24k tile maps (the not-yet-complete Hoenn map in this case) was taking quite some time for our poor computers to accomplish. My original and quite n´ave thought on the matter was that the rendering functions were being called all too often and that the requests were stacking up as a result. Well, this was true to a point but fixing that as best I could didn't fix the terrible render lag.

To explain our previous approach: For speed, when reading the map in, each new tile is a new element appended to a doubly-linked list of all the tiles in the current layer and current region (where a region will eventually become a town, or a route, etc). When we came to rendering this, run through every element in the lists checking if the element was in the current viewport or not and if so, render it.

This works great for small (up to about 5000) tile sets and pumps out reasonable performance at those levels, but give it 24k tiles and you have probably worked it out by now.. laggy is putting it mildly..

Our new approach is to directly load all the tiles into a QuadTree (same splitting patterns as the linked lists in terms of regions, etc, so multiple QuadTrees). This actually affords us an unexpected optimisation: you cannot have two tiles occupying the same space in the tree, it's just impossible, so duplicates of the first have to be dropped! Anyway, the reason for using a QuadTree is that they are just like Binary Trees, only.. rather than allowing you to index only linear (1D) data which has a singular unique key, it allows you to *efficiently* index data that has 2 keys - 2D data. Using this and a neat bit of recursion, we end up with a highly efficient storage and recall structure which allows us, with any given viewport, to render the entire map in the same amount of time as it takes to do a binary search for just the tiles that are inside the viewport.

The results are just brilliant, render times have dropped from ~250ms/frame to ~1ms/frame - a nice, dramatic, improvement.

The other thing about this structure is there are a lot of operations you can do on it that are far speedier than our previous approaches, so they will see very heavy use very shortly.

Till next time,


No comments yet

Add Comment

This item is closed, it's not possible to add new comments to it or to vote on it