Jump to content

  • Log In with Google      Sign In   
  • Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


We're also offering banner ads on our site from just $5! 1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.






Small Update

Posted by TheChubu, 22 June 2013 · 651 views

Hi again! Turns out uni is giving me a hard time over the last weeks so I don't have much time at all to code. So this will be a small update, no pics, sorry :P

The third time is the...

So, I decided to implement the algorithm in the paper pretty much literally, without paying much attention to what actually its doing (besides a major issue I did notice).

In short, my implementation doesn't works, height points get generated but the midpoint displacement pass fails to create anything useable.

I did notice that the algorithm as it stands on the paper, uses an awful amount of memory. It has to store the "parent" points (usually 2 to 4) for each of the height values of the map (I'll explain what a parent point is in another journal entry). For a 512x512 is no problem, but for a 4k heightmap you can get 100 million (or more) objects jumping around, which isn't nice at all.

You could use plain arrays and do some index calculations instead but it still is an awful amount of height points to store.

Not everything is lost

Turns out I didn't paid attention at all to the other version of the paper I had (or maybe I just didn't knew what it was doing at the time) but it has the pseudocode of a much nicer way to go about the midpoint displacement inverse process. It is recursive, so it might produce a stack overflow but an iterative approach should be doable if I can wrap my head around the algorithm (which means, wish me luck :P ).

And...?

And that's it for now. See you next time! :D




You can avoid call stack overflows by using a custom stack implementation, for example using a queue:

queue.push(pointFirst);

while(Point *point = queue.shift()){
   
    //process point
    //...

    //process sub-points
    foreach(Point[] *point.subs as *sub) queue.push(sub);
}

That... Makes a lot of sense :D

 

I'll have to check out the algorithm to know if it would work, if I have too many elements in the stack I might return to the issue I had with the previous version (millions of objects, and Java's GC looking angry at me).

 

Thanks for the feedback!

November 2014 »

S M T W T F S
      1
2345678
9101112131415
16171819202122
23 242526272829
30      

Recent Entries

Recent Comments

PARTNERS