Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 25 Jun 2013
Offline Last Active Yesterday, 11:52 AM

Posts I've Made

In Topic: Distinct quadtrees for static and moving objects

19 August 2016 - 06:46 PM

I am currently finishing to implement a small prototype, and fix some bugs.

After that, I plan to run a first benchmark between a simple quadtree with all game objects and a quadtree with two layers, one for static objects and another for moving objects.

I will publish my results here of course.

Then, I will try to implement some other structures to compare their performance with quadtrees.

In Topic: Distinct quadtrees for static and moving objects

18 August 2016 - 12:35 PM

I have done some search about AABB tree and it looks promising for both static and moving objects. Are they faster than Quad Tree?

In Topic: Distinct quadtrees for static and moving objects

18 August 2016 - 10:09 AM

There are data structures that are optimized for "build-once read-many". So there is definitely some value in separating out static objects from movable ones. You wouldn't use the same data structure for both, though. There are a lot of data structures out there that are optimized for different situations, so choose the right one for each case if you need optimization.


That said... if you keep your code well designed, it should be easy to swap out implementations later after you have everything built so you can test real world situations and find the data structure that works best for you.

Would you have some suggestions about data structures that could be more suitable than quadtrees for static objects?

In Topic: Land/Sea ratio from a Heightmap

01 August 2015 - 07:14 AM

Thank you for your reply. While you were writing your answer, I came up with another solution involving the histogram.
I define my ranges according to the average altitude of the map and its standard deviation.
First, I compute the cumulative histogram cumHisto:
    var cumHisto = 0;

    for (var i = 0; i < World.width; i++) {
        for (var j = 0; j < World.height; j++) {
            cumHisto += World.mapData[i][j];
        } // for j
    } // for i
Then, I compute the average altitude avgHeight:
    var nbPoints = World.width * World.height;
    var avgAltitude = cumHisto / nbPoints;
I need a loop to compute the standard deviation stdevAltitude, based on the variance varAltitude:
    var varAltitude = 0;
    for (var i = 0; i < World.width; i++) {
        for (var j = 0; j < World.height; j++) {
            var diff = World.mapData[i][j] - avgAltitude;
            varAltitude += diff * diff;
        } // for j
    } // for i

    var varAltitude = varAltitude / nbPoints;
    var stdevAltitude = Math.sqrt(varAltitude);
Given the average altitude and its standard deviation, I can define four ranges which seem to give quite reliable results:
    for (var i = 0; i < World.width; i++) {
        for (var j = 0; j < World.height; j++) {
            if (World.mapData[i][j] < avgAltitude) {
                World.mapData[i][j] = Terrain.DEEP_OCEAN;
            else if (World.mapData[i][j] < avgAltitude + 0.5 * stdevAltitude) {
                World.mapData[i][j] = Terrain.COASTAL_OCEAN;
            else if (World.mapData[i][j] < avgAltitude + 2 * stdevAltitude) {
                World.mapData[i][j] = Terrain.FLAT;
            else {
                World.mapData[i][j] = Terrain.MOUNTAIN;
        } // for j
    } // for i
mini_837212Capturedcran20150801142639.pn mini_317439Capturedcran20150801142726.pn mini_441266Capturedcran20150801142737.pn mini_372853Capturedcran20150801142749.pn

In Topic: Some programmers actually hate OOP languages? WHAT?!

29 January 2015 - 10:02 AM

Just to feed this tr.. topic, I recently had to do some reverse engineering on a game's codebase in C#, strongly OO. It was a real nightmare...


However, understanding a large C (well-written) codebase, even without documentation is a piece of cake.