Warning: Parameter 1 to NP_Poll::event_PreSkinParse() expected to be a reference, value given in /home/pokelege/public_html/nucleus/libs/MANAGER.php on line 370
The Project Gamma Development Progress Blog » Archive
The Project Gamma Development Progress Blog

PokčCave

Dec 06, 2011 by DX-MON |
There has been yet more progress, libAudio's module mixing engine now plays a truckload more songs right thanks to our new member, marinu666.

Further to that, he has been busy generating a small side-site so you have something to play and talk over while the main project continues. The site is called PokčCave. Playing helps to fund this project and the servers we have to run for PokčLegends as we have 4 servers to run to even have the game

~DX-MON

QuadTrees

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,
~DX-MON