Jump to content

  • Log In with Google      Sign In   
  • Create Account

Making a Terrain Generator



Design Roadblock

Posted by , 03 December 2013 - - - - - - · 1,482 views
java, terrain generator and 1 more...
So for this entry, text, text, a bit of code, and more text. I'm going to talk about a few issues I'm having with the design part of the generator, in particular when adding new tools, with their own operations.

Design Roadblock


In my previous entry I talked about a bit of eye candy I did for the generator and lightly touched the issue I am having right now, but I'll go ove rit again for the sake of explainin'.

Perspective

Before I started with the whole editor/tool/thing, I had a simple setup for the terrain generator: You would have parameters, fill those in, hit the corresponding generate buttons in order, and that was it.

This makes everything simpler, you do stuff in the wrong order, it breaks, so you shouldn't do so. But the whole "Editor" part means that you dear user shouldn't follow those strict rules right? What if you didn't liked that ridge you put there in the north and you're all the way on the last pass of the generator? You should be able to go back and change it, then go forward and pick up where you left it.

All of this imposes several challenges on a model that is strictly dependent on the order you do things. First the ridges, then the blurring, then the rivers, then the MDI, then finally the Midpoint-Inverse (or better, Diamond-Square).

So you're in step 4, Midpoint Inverse Pass, and want to add a ridge? That's gonna cost considerable time.

First, throw of the window the current map (delete it and reallocate it or re initialize it, both work), then draw the old ridges, then the new ridge... but that's just to get the desired changes written in the map. Then you have to get to where the user was before, that means, blur the map (pretty slow for now), recalculate all river paths (throwing away a lot of stored river positions in the process), do the MDI pass and only then we're back where we started, for just a single ridge in the whole map.

Hell, maybe the user doesn't goes back to the MDI pass but just returns to the river drawing tool (which means that the rest of the stuff would be recalculated anyway).

Other functions

A common function in any editor is the undo function, it poses exactly the same kind of challenges. For example, river undoing.

Say that you actually don't change the tool, but just want to undo a river that you just drew. Its a quite demanding thing actually, the river has to be removed from the generator, then the heightmap has to be reset because the river that you unmade affected the heightmap, then the particle map has to be reset too because the river particle is written there, then you have to draw everything again because you just unmade the last three passes with this process! (ridge drawing, blurring, river generation).

That require some kind of structure to handle those kind of changes. It would be really easy to just add methods to handle each particular case, that's how it is handled right now:
public void undoRiverPaint ( final int mapIndex )
{
    // Retrieve both generators corresponding to the currently selected map.
    final GeneratorRiver genRiver = riverGenList.get( mapIndex );
    final GeneratorRidge genRidge = ridgeGenList.get( mapIndex );
    
    // Check if there is any river to undo.
    if ( genRiver.isAnyRiverLeft() )
    {
        // Retrieve currently selected map.
        final ElevationMap map = mapList.get( mapIndex );
 
        // Remove last added river from generator.
        genRiver.removeLastRiver();
        // Reset heightmap 
        OpsTerrain.resetHeightState( map );
        // Reset particle map.
        OpsTerrain.resetParticleState( map );
        // Write ridges again.
        genRidge.writeRidgeLines( map );
 
        // Retrieve blur associated with the map.
        final BlurringMap blurMap = blurList.get( mapIndex );
        // Force blurring of the map with previous blur settings.
        blurMap.setBlurred( false );
        blurMap.blur( map, blurMap.getLastRadius());
        // Rewrite rivers.
        genRiver.writeRiverLines( map );
    } 
}
Now I dunno about you but to me it looks pretty wasteful.

Not only that but also that's a method in my Controller class, which is very restrictive. It means that for each kind of thing you did (draw a river, draw a ridge, do an MDI pass), you'd need to add a specific method in the Controller class to handle it.

More extensions

I wanted to leave the amount of "tools" you can use open, say for example that I want to add more land features that aren't ridges, like canyons, valleys, and such. Or maybe other water features, like an ocean level.

So for supporting the basic do/undo functions I need a more robust system to handle those, a "Tool Manager" if you will.

I can't seem to figure out a way to do this, ideally, adding a new tool would mean just extending an "AbstractTool", adding it to the manager, make corresponding changes on the UI (buttons, settings panel, etc), and that should be it.

Given that the tools have somewhat different requirements (they need to have different kind of knowledge on the maps, generators, and such) I'll could try to make a tool interface, that these tools would implement.

I'm trying to follow an MVC pattern here for the whole architecture, that's why I already have going a "ToolManager" for the UI part, which is in charge of switching the Listeners that know what method to call (which I hear isn't at all efficient but oh well), and the settings panel that is appropriate for the selected tool.

This one makes working with it pretty simple:
toolAdmin.switchTo( tool );
As long as the tool is set up properly, it shouldn't have many problems. The "bad" part is that the river tool needs knowledge about two settings panels, blurring and river, so that one is done under the same interfaces, but in its own class.

More abstractions

I'd like to have something similar going on for the "Controller" part. An easy way to switch tools, with their draw and undo behaviors, but coming down to a common subset of functionality among the tools that I have (and that I will have), and how they would interact is kinda hard.

Well, that's it for the wall o' text. Bye, until the next entry! :)


Now With Splash Screen...

Posted by , 24 November 2013 - - - - - - · 1,368 views
java, terrain generator
Hi! I'm going to talk of what I've progressed so far, blurring, rivers, some infrastructure for tool switching and a little splash screen Posted Image

Now With Splash Screen


In my last entry I talked about how the new GUI was going, had ridges up and running, plus the binding from the UI parameters to the actual terrain parameters.

Now I will talk on what I've progressed so far, blurring, rivers, some infrastructure for tool switching and a little splash screen Posted Image

Splashin'
Attached Image

Pretty sweet splash image right? Well no, but you get the idea Posted Image The circle thing actually draws each piece one by one to complete the full circle again and again until the main window is loaded, like every cool loading circle thingy that is so cool these days.

Main thread creates a SplashThread that does the splash frame instancing and drawing, while the Swing Event Queue executes the runnable that instantiates the main window, passing to it the SplashThread. Once the main window is instantiated (not visible yet), the runnable signals the stop to the SplashThread, which closes the splash frame and the main window gets set as visible.

This one is made out of an AWT Frame and an AWT Label, I choose those since they take slightly less to load up, and since the splash screen is the first thing that you should see, it should load fast.

I discovered that Java has an actual API to do these splash screens, loads up a .gif/jpg/etc even before the VM that executes your .jar starts, but I haven't used that, I'll will in the future.

And there was rivers

I got river generation working! Yay! That means that I grabbed the old river generator and made a new one that functioned better with "one at a time" river generation.

River generation is in the same precarious state as before, they can hang the whole program since the condition for them to finis his to reach 0.0f height, and since they don't write their heights modifiers until they're finished, they can get stuck and hang everything.

I added parametric "turbulence" so you can actually say how much your rivers randomly vary in direction in spite of the landscape.

Debug view

Attached Image

Prolly the most useful feature is the "DebugImagePanel". For displaying the heightmap I had a class that inherited from JPanel but draw itself from a BufferedImage.

Bad thing is that height values are only one part of the whole thing, there is also the state map, direction map, and I could make use of an non colored heightmap view.

So I implemented the debug panel that can draw four images on itself, thus allowing me to view when exactly everything changes (because I can't remember all the stuff I did, when or where).

Upper left is raw heightmap, upper right is a colored heightmap, lower right is the state map (white is NULL, blue RIVER, brown RIDGE) and lower left is the direction map, which is used so the river particles know where to go at each position.

There is no "strength" for the river direction, that means that all height differences are equal. I could probably work out some "direction strength" coefficient so the directions aren't as plain.

Tool madness

Now, the issue I'm having right now is that I need to come up with some abstraction for the tools. See, when you switch from ridge to river, there is a bunch of state changes that go around.

You have to grab the blur bean, blur the selected map with its parameters, generate the direction map, and let the user draw what they want. But what happens if the user goes back to ridge tool? Then you have to discard blurred heights, re initializing all heights to 0 and re write the existing ridges to the map.

Worse, what happens if you undo a river? You have to zero everything, write ridges, blur them, create the direction map then draw the rivers again. Madness!

I have to come up with some abstraction for what it is a tool, besides the Listeners and parameter JPanels they use.

Moar dependencies
The only good thing of all of that is that by chance the way I designed the generators lends itself to the undoing of particles. I just have to grab the particle collection, remove the last one, and that's it. Particles contain every position they touch so by deleting particles I delete all their effects. That doesn't means that they're removed from the heightmap, generators receive a map as a parameter so they cant grab a map and undo their changes.

Moreover, if only the generators know what changes are going to be made (river carving, position state, etc), how are they going to back up what they did? They can't know every single map they have touched.

My idea is to create some sort of undo system that grabs a generator, a map and saves up every single thing that could be touched. I don't want to couple generators or maps with undo actions since they're pretty much an GUI tool.

El Fin

So that's it for now, I'll see what can I do about the tools and undo operations, bye! Posted Image


GUI Advanced

Posted by , 21 October 2013 - - - - - - · 1,430 views
not GBA Advanced, java and 1 more...
Hi! I haven't made a journal entry in a while, but stuff hasn't stopped! I got a few new things to show.

GUI Advanced


At first glance, things haven't changed a lot since my last entry.

Attached Image

Thing is, there is a lot more stuff happening in the background now.

Ridges, it is always the ridges...

Random ridge generation is thrown outside the house and now you can draw the ridges by hand with various parameters you can tweak. Just click where the ridge begins, then click where it ends, and that's it.

Since the previous ridge generation is out, the new one has different tweakable parameters:

Amplitude: Now ridges behave more like a wave, and the "amplitude" controls how much a ridge can divert from the center line traced from the begining point to the end point. Remember, this is a "maximum" so the ridge could be displaced anywhere from +amplitude to -amplitude.

Deviation: This part hasn't changed. The deviation controls how rapidly ridges lower their height at their extreme points.

Divisions: This parameter controls how many points along the ridge will be affected by random amplitude variations. Many divisions = noisy ridge.

Max Height: I decided it might be good for this parameter to be tweakable, before it was hard coded. This controls the maximum height of the ridge you're about to draw. Ridges height will go from this value to 0, so now you can have various ridges at different heights.

There will be probably more settings for the subridges that need to be spawned.

Undo function works perfectly for ridges. Though I'm not sure if implementing a redo function is worth it. Ridge objects are pretty much self contained so it shouldn't be too much work.

One thing that I haven't redone is checking ridge collision, it might or might not be added in the future.

The beans and the peas

I had a little scuffle with the GUI and passing data to the generators. For now I was just adding methods as I go, "drawRidge(ridgeData)" and so on, but it seemed kinda convoluted so I did a little google search for GUI design.

Ended up with the term "data binding". Data binding is the process of binding the data in your view with the data on your model, and given that Java is such an "enterprise" platform (and "enterprise" drools all over MVC pattern), there was a library ready for binding stuff from Swing to JavaBeans, specifically, "beansbinding-1.2.1.jar".

beansbinding-1.2.1.jar

You can download it from here

Attached Image

(btw, I got Eclipse's dark theme here)

This is an "abandoned" library. Its the reference implementation of JSR-295 (Java Specification Request), the last version is from 2008 or 2009 I believe. JSR-295 specifies a way to bind properties among components, usually, a Swing widget with a JavaBean.

In any case, works pretty well. If you import the library, you get a new tab in WindowBuilder for your Swing widget to make the bindings among your components. You can do stuff like, read property from A and update B, vice versa, or keep both A and B in sync each time one of them is modified.

Have in mind that you need this library if you're using Swing. SWT comes with its own data binding library, its already included in WindowBuilder and Eclipse should auto import them when you create a SWT project. Just create a new SWT project, and the bindings tab should appear in your WindowBuilder editor window. Also, I think JavaFX has data binding built in though I'm not sure.

Beans?

Yep, beans, Java ones. A JavaBean isn't more than an object with a default constructor with no parameters, getters/setters for each of its attributes and implements the Serializable interface. Makes for a predictable public interface and for easy initialization.

Mirrors and reflections

beansbinding uses the reflection API to know what new data it has to instance so it can pass it around. It was problematic since I didn't knew the JFormattedText components would hold Doubles or Longs depending on what formatting rules they had, by the time those values reached my bean, I would get a ClassCastException because beansbindings would try to cast the Double/Long object into the float/int attributes I had in my bean.

In the end I set up the bean to hold Number references (superclass of every boxed primitive pretty much), so whatever the JFormattedText outputted, the bean would capture it and then I could use Number's handy methods like num.floatValue() or num.intValue(), no matter what type they actually represented.

Now ridges, tomorrow the world!

Anyway, now I need to implement river "drawing". For that I need to remake the river generator and organize things a little bit, for example, I need to implement a way to switch what tool you have currently selected, as it is right now, you always draw ridges no matter what you selected.

The idea is that when I select "Blur", I can configure how much ridge lines get blurred for the river generation process, that is sort of done, there is the blur settings panel and the bounded bean.

Then, when you select "River", the heightmap should be blurred according to whatever is set in the blur settings, the image should be updated and it should let you place river starting particles wherever you want. That means, place river, calculate path, update heightmap, redraw it, place another river, calculate path, and so on.

That is pretty straightforward but it's because my river implementation sucks Posted Image Proper river tracing should acknowledge river collisions which affect the volume of the rivers and their paths. That means that for each subsequent river particle added, I should check for collisions and change other river paths accordingly.

Optimization thoughts

If changing to "River" placement changes the image to the blurred heightmap, then changing back to "Ridge" should show the empty ridges. This is no problem since all the ridge particles and all the positions they cover are stored (and now I'm thinking I could "cull" unneeded ridge positions), but I think it could be a performance concern.

I'd need to reset the heightmap (that means, heightmap, particle map and state map) and redraw all the ridges. For 512x512 maps this is pretty fast but it starts to bog down at 1k x 1k or 2k x 2k (nevermind 4k x 4k).

As I probably mentioned in previous entries, once I get the major features set up, I'll probably have to consider multithreading the passes I can. From what I've profiled, the generator spends most of it's time writing the heightmap to a BufferedImage.

I have a switch to deal with the different colors that each pixel can have depending on its state (river, ridge, land, etc). I could probably get rid of it with some thought.

In any case, its something I'll have to look up in the near future.

And they lived...

That's it for now, bye people! Have a nice week! Posted Image


Moar Functionality

Posted by , 14 September 2013 - - - - - - · 1,375 views
functionality, more of it, java and 2 more...
Hi! On this entry I talk about features I'm going to add to the terrain generator, to make it both more usable and prettier.

Moar Functionality!


In the previous entry I made a GUI for using the generator, you can go there and download the generator if you want.

The GUI I made for the terrain generator isn't all I wanted it to be. Ideally, it should be more "interactive". I had theorized that it should be possible to add ridge lines and/or river on already generated terrain, as it is, you set up all at the begging, let the random.nextFloat() do its magic, and you got a randomly generated terrain.

Attached Image
This is the GUI I made a week or two ago, I'm still pretty happy about the fact that resizing the window works perfectly as long as you use LayoutManagers in Java Posted Image

Purrformance
The way the terrain gets generated allows some quite nice ways to "sculpt" it. Well, its not like you can seamlessly add new ridges to it once all other passes have been made, but remaking the necessary steps shouldn't be too taxing unless you're doing 2k maps or something... weirdo Posted Image

Of course, using several threads for processing could speed up things considerably, but I should structure the whole program better before doing that. While I know the threading structures in Java and I have the theory worked out, I have yet to properly do a multi thread implementation of something.

For example, the Diamond-Square pass (I honestly don't remember if I ended up using diamond-square or midpoint displacement) probably lends itself well to multi threading once corner cases have been taken care of. Gaussian blur... I have no idea, probably yes, I have to look it up.

Ridge lines and river lines... now that's different. It would be basically a primitive multi threaded physics system, and I'm not sure of the benefits. Ridge lines are simple enough that 1 thread alone can do the work in 50ms or less on a 2k x 2k map (on a Core i5 2500 mind you), which is good enough.

Thing is, both rivers and ridges should check for collisions among themselves. Good thing is that height isn't directly writes on the heightmap while ridges/rivers are being generated, height values are written after the generation stopped. So the heightmap should be constant while the ridge/river generation is working, the particle map on the other hand needs to get written so particles know what other particles are around when they move. And that's when multiple threads don't look nice Posted Image

It is doable, sure, now, it is worthwhile? In the case of the rivers probably yes, river generation is expensive. In any case, muti-threading the generator is on hold for now.

Prototype! (Disclaimer: Not the game)
I prototyped a GUI that should expose tools kinda like a paint application. You'd have a panel of tools with buttons for selecting them (ridges, rivers, or something else) to the side, and you could create new heightmaps pretty much like you create a new image in paint.

I also changed the LookAndFeel to "Nimbus" because its nice and rounded:
Attached Image

Say that you want to place a new ridge, you'd select the ridge button, then click where you want the beginning of the ridge in the heightmap, then click on the end, the program should generate a random ridge line (with subridges) that starts and ends on those points.
Rivers would work differently, they would follow the "rules" of the maps, that means, rivers start at the top of ridge lines, and they fall accordingly to the heights surrounding them. So the river tool would allow you to place the beginning of a river only.

On a semi related note, I'm half sure I could implement coast lines not in a very different way than the ridge lines, but I have to investigate it further.

Broken Stuff be Broken

Now, say that we place two ridge lines, the program should be able to do the MDI and MD passes to show a terrain that somewhat conforms to those ridges. The problem right now is that I actually don't draw the ridges on the map, they're there just to act as a support for the rivers. The rivers are the ones who define the general shape of the map. Without rivers, placing a ridge or not will net you the same result, it doesn't affects the landscape at all.

If I do write the main ridge lines to the map, they end up as a soft line that looks much like a dry river or something like that, which isn't what I want.

Extra Benefits

One of the benefits of bringing such features is that testing the algorithms should be far easier now. Before I randomly generated everything, now I'd be arbitrarily set ridges and rivers where I want and see how they behave. Besides, it'll be more fun to use that way.

Well, I rambled enough I think! Cya on the next entry Posted Image


Apps n' Rivers

Posted by , 02 September 2013 - - - - - - · 2,165 views
java, terrain generation, gui
Hi! Well, after I got the generator (sort-of) working, I decided it could be nicer to use with a little GUI. So now you can download it and try it by yourself Posted Image Besides that, small discussion on the next milestone, proper rivers. Also updated it to fix the GUI.

Small Update: Updated the GUI so it doesn't "forgets" to repaint the heightmap and it uses a single instance of the map unless you change its size. Download section has been updated. Also, link to the last entry if you want to check it out. Talked about various things that popped out while coding the height filling algorithm (diamond-square based).

Apps n' Rivers

Attached Image

Decided it would be a nice thing to have a GUI to use the generator rather than commenting/uncommenting stuff all around to test it. Having a GUI attached to it is nice not only for usage but for the general shape of the code.

When I was using just code, many steps in the generation consisted on arbitrary array copying or calling various methods on each generator., everything depends on the assumptions that I made some specific call earlier.

When you use a GUI you have to think "How would I use that from a single button?". You can't just pop method calls from nowhere since that would be cumbersome to an user. "Now press the copy blurredHeights float array to riverMap float array button to continue!" is too ugly. Implementing that in more concise steps, that encapsulate better what is being done on the terrain should prove a good influence on the generator code.

The UI is implemented with two classes only: The Swing frame and a "Mastermind" that pulls the strings to make the generators do what the UI wants.

Settings

For now, besides the map size, you can have a few settings:
  • How many ridge lines you want.
  • How big is their deviation
  • How often the ridge lines change in direction, in steps.
  • How broad is the rotation arc they can have.
  • How big is the blur factor of the ridge lines.
  • How many river particles are going to be spawned.
  • How rough is going to be the midpoint pass.
Attached Image

Ridge amount is self explanatory, deviation not so much. Remember that ridge particles start at an arbitrary highest point, and from there they descend describing a gaussian/normal distribution. The deviation indicates how far the particles are going to get from the mean (middle/highest) value. Its a pretty heavy statistics subject to just use it on a ridge line but oh well Posted Image

Ridge lines are supposed to follow a "fractional brownian motion", since at the time didn't knew how to implement it (and to be fair, I still don't know Posted Image) I just made it so after a certain amount of steps, the ridge particles would rotate their directions by a randomly selected degree amount, in an arbitrary arc (say, if the arc is 90º, you'd rotate between -45º and 45º).

Blur factor of ridge lines determines the terrain in which the rivers will be generated. Since we don't have a complete terrain at this point, the river generator uses a heightmap with just the ridge lines traced on it, blurred by a determined factor. More blurring means that the river lines will take longer to reach the bottom of the heightmap.

River particle amount is self explanatory.

And last, midpoint displacement roughness. Midpoint displacement works by averaging the heights of the corners of a given subsquare in the map, and then applying a random offset to it, this offset is given by the maximum height variation at the time of the iteration multiplied by the roughness factor. If the roughness factor is 1, and the maximum height is 1024, then you'd have big variations in height, if the roughness factor is 0.25 instead, your heights would vary by just 256 values.

So in the end the generator is pretty configurable, and there are a few constants that probably I missed out Posted Image

Attached Image
(3D viewer not included Posted Image)

Download and how to use it

First and foremost, it needs Java 7 to work. 32 or 64 bit. Second, it uses a LOT of ram, so choose a reasonable map size (513x513, or 1025x1025).

Once the heightmap is generated, ideally you'd have several options for saving it. As a 8bit greyscale png, as a plain array of floats, as a color map, etc. For now, the app just plain saves whatever step you're on, save buttons don't work. So you'll end up with a .png of each stage, plus an extra colored one for the last one, in the same directory as the .jar is located.

And finally, since it is in a very early state, you need to press the buttons in order, from top to bottom for it to work at all, also, don't put letters on the numerial field please http://public.gamedev5.net//public/style_emoticons/default/smile.png

Update: Now you have a "New Map" button. You have to click it to create a new map and select its size. As a side effect of the changes now you can recalculate the ridge lines without having to create a new map. Besides, now the UI actually tries to repaint the image accordingly so now you can resize the window freely without loosing the view on the heightmap (plus other repaint glitches got solved too).

First you create the map selecting it size, then you generate the ridges, third, you blur the heights, fourth, you generate the rivers, fifth you do the MDI pass, and last, you do the regular diamond square pass.

Here it is Attached File  TerrainGeneratorUpdt.rar (56.6KB)
downloads: 110 Enjoy.

Rivers

The rivers look "fine". There is this major thing I'd like them to do, and that thing is join streams. River particles have no notion of collision nor other river particles, so they just wander in the map until I arbitrarily say "NO MOAR RIVER CALCULATION" (literally, there is this while loop that stops after a second or so).

I'd like them to be able to join other river particles. The paper more or less describes a way to do it, you check for collisions with other river particles, stop the particle that is colliding, and grab the other river particle. With that particle you erase its path until the point of collision, and then set it free again but with increased river width.

I'm on my way to implement this behavior but I'm having a few problems that I simply don't know how they even work. For some reason the entire map gets sunk into the black void of nothingness if any particle dares to touch other particle.

In any case, if I manage it to work, next step is implementing some kind of friction that makes the particles stop naturally. The original velocity field erosion paper has some complex (to me) "energy impact" calculation when the particle's velocity vector collides with the surface of the heightmap. Long story short, I don't understand how it works, nor why a simple direction vector wouldn't work well enough, so I'll follow my simpler road and just try with a friction factor.

And that's it for now. Bye! Until the next entry http://public.gamedev5.net//public/style_emoticons/default/smile.png


Finishing touch

Posted by , 15 July 2013 - - - - - - · 1,317 views
fractal terrain and 2 more...
Hi people! Free time == moar entries : D The generator is kinda fixed (as far as I can notice). Now I have to fix up all the parameters around and the river generation process too. Also, pictures... in 3D.

Memory is for the weak!

Well, honestly I half remember all the things I touched from the last entry, but I'll try to get to them. This is the base ridge (with sub ridges) map:

Attached Image

The indices of my squares were off. After analyzing how the Square class gets initialized and what the loops use for strides and sizes, I reorganized them so each square would be the right size.

After that I realized that a part of my implementation was wrong. The paper differentiates between DEM and C_DEM (Digital Elevation Model and Copy of Digital Elevation Model respectively) and there were a few spots where in my implementation, both got mixed and parts of the algorithm affected the DEM where it should have affected the C_DEM and vice versa.

Once I had that solved, the additional data got into the heightmap just fine.

Lost in translation?

The weird thing is that while I get similar results, the recursive MDI method in my case only generates the additional height data, I still have to do a "context-aware" midpoint displacement pass over the heightmap to fill in the missing heights. As far as I understand, the recursive MDI method should do all of that already.

This is the same map, blurred, with the (broken) river network generated, and with the (hopefully) correct MDI values:

Attached Image

You can see the dots that the MDI pass generates all around, the rest of the blurred heights are there just for reference, they shouldn't matter for the final passes. The river network turned out to be quite important since it defines the slopes of the ridges on many places though you can vary a lot by just messing with the max heights, base heights, amount of blurring, ridge/river quantity, etc.

In any case, an additional call to midpointDisplacementPass() was enough to fill in what was missing. The midpoint displacement pass showed a lot of squared artifacts, so I tried with a diamond square pass, which should in theory excibit less artifacts.

I used the diamond square algorithm to fill the remaining heights, working without big artifacts as expected but something was wrong...

Artifacts in my soup! Wait, already did that one...

See, when I tried to color the heightmap, I use the elevation state map as a reference to know if I have to color the vertex blue (river), or green/brown (land/ridge). When I did the coloring pass, turns out that most of the values were in NULL state (ie, greyscale color), yet the heightmap was created fine.

The final regular diamond square pass checked for already computed height states but, for the missing ones, it calculated the height without setting the new state as "LAND" (or DONE like in the paper). So it was "aware" of the previously computed states but it wasn't "self aware" in the sense that it didn't kept track of the missing heights it was filling.

I set up the thing to put the correct states and bam! Artifacts again everywhere. So the root of the squared (and now, "diamoned" ) artifacts wasn't the algorithm itself but its "self awareness".

I left it "broken", ie, without the state changes, and it works fine that way heh.

Finally(ish)

Attached Image

Here you can see how the ridge lines help to define high places whereas the river lines help to define the lower ones. Have in mind that the river network generation is pretty broken so the river lines don't make much sense.

And here is a colored version for your viewing pleasure ( "I can make a lerp with a gradient woot!" ).

Attached Image

From what I've experimented, it seems that for the algorithm to look kinda good, it needs to have nice ridge lines, and a good river network that makes sense. Terrain gets weird if the ridge lines are at odd positions or if the rivers get traced badly.

I can also show you the terrain in 3D with all of its per-vertex coloring glory (nevermind the Great Green Cube Overlord of the "Positive Y Axis" house watching over his realm):

Attached Image

Attached Image

The borders are messed up but it seems like its a common trait of the diamond square algorithms. You could make it have some checks and wrap it around but I think I'd just crop the borders (ie, instead of 513^2 map, cropping it to a 512^2 map).

What is left...

Now I'll have to fix up the river network generation, which means possibly trying later with a water erosion algorithm (since the river generation is just that, a water erosion algorithm applied to a few particles). Besides that, the generator is currently a big mess o' code for the most part, so I'm going to tidy it up and see if I can come up with something more useable.

For example, at first I had an "ElevationMap" class with a bunch of arrays with ElevationState, floats, Particles, etc, but now I think I'm going to repurpose my CmpMat matrix class to have all of them under a more homogeneous interface. ElevationMap has like 4 kinds of "getValueAt(x,y)" methods, one for each type of data it stored. Half the code is using the older ElevationMap, the other half is using the "newer" CmpMat matrix storing ElevationState and height values.

I'll have to come up with a bigger structure for all the generator if I want it to be useable. The good thing is that it was very useful for completing my math library, coming up with some generic components and so on.

Right now I have a lot of static stuff (I remind you I'm doing all of this in Java). For example, all of the midpoint displacement, diamond square and mid passes are static methods on an "UtilsTerrain" class, I have a image utils class that has a bunch of static methods to convert from ElevationMaps to ImageBuffers so I can store them in a .png.

There is also some cruft from my previous project, the renderer above, in the math utils and some array/matrix classes that I need to get rid of. For example, in Java you need to write your float arrays to FloatBuffers before passing them around to native libraries. For the OGL project it seemed perfectly fine for each matrix class to have its own FloatBuffer inside... Which suddenly stopped making any sense once I started using the matrices for non GL stuff. So for using the math library, i had to import the matrix/vector classes, which needed the buffer utils to work for no good reason. See what I did there?

I'm 80% done on fixing the whole math utils and classes, and once I fix them, I'll have to replace all the old code and banish those buffer utils / data array classes out of existence. And then retroimplement them on the OpenGL project where they came from.

What is left isn't right

I'll try to do all of that once I'm on my desktop again. Coding with an Atom N450 (1,6Ghz and single core mind you) isn't the most efficient thing in the world. Its better than no coding at all though Posted Image See ya in the next entry!


Results! Yay!

Posted by , 11 July 2013 - - - - - - · 964 views
terrain generation and 2 more...
Hi again! I'm getting back on track with this terrain generator project since I have more time now Posted Image Tried the recursive MDI and had some success with it, which means pictures obviously Posted Image

Back in Time

I'll try to reconstruct this paragraph since I deleted it by mistake (closed the browser without saving the changes Posted Image)

In the last entry I commented about the massive data ammounts that the Midpoint Displacement's Inverse process needed as it was on the paper, so I decided to try the recursive approach I found on another version of the paper. I was going to discuss why the previous method needed so much data but I forgot exactly what I was going to say (had a draft of only one paragraph) and I'm not looking forward to delve into that code again so I'll just jump over the issue completely.

Forever a Point
So, Midpoint Displacement's Inverse. This process comes from the idea that a Midpoint Displacement algorithm (which isn't the same as a Diamond-Square algorithm) result depends on the height data generated by the previous iterations of the same algorithm. Thus, each set of new points depend (more or less) on the points that preceded them.

With that in mind there could exist a MD algorithm that is aware of already existing data. The paper achieves this by having two arrays: One with the height data and the other with the state of each height value. There are various states that each point can have (river, ridge, done, null) but the most important part is differentiating between those already computed (river, ridge, done) and those that need to be computed (null).

I don't know exactly how the paper achieves this "awareness" but its probably with a check before calculating each point. If the state at (x,y) is NULL, then calculate the point normally, if it isn't null, then leave it as it is.

For simplicity I used a map with only ridge lines traced on it to begin the process:
Attached Image

The state checks alone won't give you good results:
Attached Image

You can see that the MD algorithm sort-of adapts to the ridge lines in some places but rapidly loses track and it gets ugly.

Inverse or Reverse?
To solve these issues, the paper introduces the Midpoint Displacement's Inverse process. It is an algorithm that steps through the data and places height values where the MD algorithm expects them and that make sense in the context of the present pre-computed data. That way the MD algorithm has more data to work with and can adapt better to the main features of the terrain. You can check it out on the alternate version of the paper that I found.

There are a few parts of the paper algorithm that I don't understand, for example:
if nns>0 then;
• a ←for each corner of square in DEM:
  the altitude average of all non-NUL
  cordinates;
• for each corner (l, m)of square with
  a NULL coordinate:
  –altitude(CDEM[l][m])←a + s * ur()
  –state(CDEM[l][m])←DONE;
nns is the counter of non null states. That means, if we have at least one corner pre calculated in our square, make a rough assumption about the heights of the other corners. DEM is digital elevation model, your run off the mill heightmap. And ur() is an uniform random value between -1.0f and 1.0f. s is the current stepping of the MDI iteration and the square represents the subarea where we're working on.

Now, that "for each corner of square in DEM: the altitude average of all non-NULL cordinates" is kinda weird. I *think* it means that I have to average all the height values of the known corners. (ie, (corner1+corner2)/2 ) but I'm not sure.

Then, the next part I just don't have any idea what it means. "For each corner (1,m) of square" ? Where the "m" comes from? Why the constant 1? I guessed that it means that for each corner that has a null state, calculate it with the average of the non-null corners like it says in "a + s * ur()". Then set the state of that coordinate as DONE. But its just a guess based on what I'd expect it to do, I honestly have no idea what that "corner (1,m)" means.

Artifacts in my soup!

I half expected it to burst into flames, but alas it kinda worked. Not only it wasn't awfully slow like my last attempt (70ms against like whole seconds for a 513^2 map), but it worked better, still ugly, but better:

Attached Image

You can see that the algorithm adapts way more to the ridge lines than before, misses a lot of terrain and has weird points around. I'm thinking I have issues with the sub-square sizes. This result is actually after arbitrarily creating each subsquare with square.width = stepping + 1. This is what happens if I leave it as square.width = stepping (like the paper suggests), albeit with a different base ridge network:

Attached Image

And this is what happens when I leave it as square.width = stepping - 1

Attached Image

I know the artifacts on the first image since I had them while implementing a regular MD algorithm, I was sizing my subsquares with a width off by 1. That's why the white points are spaced by long black lines. Now for the second image I have no idea what is going on. Probably missing all the corners or most of them, so barely any new point gets generated.

And the moral of the story is...

I'll try to find out what's happening with the squares. I'm pretty sure its some width/height/range issue. Maybe I'll attach some code next time Posted Image (though I hope to have it complete and "readable" someday). Until then, have a good night! Posted Image


Small Update

Posted by , 22 June 2013 - - - - - - · 933 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


Skipping Ahead

Posted by , 09 June 2013 - - - - - - · 1,155 views

Hi again! For this entry I'm going to talk about the Midpoint Displacement stage and post more pictures, everybody loves pictures! (Yes, I'm a sellout, shush!) Skipping whatever is left of the ridge generation phase and the river generation phase since I'm having difficulties with the last stage right now and the river phase is incomplete.

In the beggining...

I remind you the paper where all of this comes from: Ridges and Rivers, Bottom Up Approach There is another version somewhere that was meant for other presentation I think, same authors, same date, just described differently.

Stages of the terrain generation algorithm:
  • Ridge particle generation. Traces ridge lines on the map, blurs the height values.
  • River particle generation. Creates velocity field and traces river lines on the map. Discard everything except river lines and the original ridge lines after that.
  • Inverse midpoint displacement pass. Fill up the ridges and rivers network with some relevant data.
  • Midpoint displacement pass. Fill up the rest of the missing data.
Last two are pretty much a single stage.

We covered up ridge generation stage in the previous entries. River generation stage is more or less an erosion algorithm applied to few particles. You spawn a particle at the top of a random ridge, and simulate its trajectory around the terrain, "carving" a river on the landscape.

Craving for rivers

All of this is made with a single purpose, feeding specific data to a midpoint displacement algorithm. That specific data represents the features of a believable terrain, ie, ridges and rivers that follow a logical path (at least for the rivers).

Once that stage is done you'd end up with something like this:
Attached Image
Image is lightened up a little because it was too dark for viewing.

Rivers are light blue and ridges are the yellow lines. The blurred gray heights are there just for reference, they're actually dropped once the river generation stage is complete (ie, you're only left with the ridge lines and the river lines).

There are a few problems with the river generation, such as, they live in a magical land without friction, thus they carve their way around like balls in a pinball, and they have no notion of water mass, so their size is constant.

This particular stage could go on forever as it is (perpetual motioners dream)... But I placed a timer on it, it stops after a second or so. Hack, totally, I know. I'll get it fixed eventually. It deserves its own entry though.

Midpoint Displacement's Inverse

Now here is where it gets more interesting. Remember that I said that the point of the algorithm is to feed a midpoint displacement pass some useful data? Well, its not that simple.

The midpoint displacement algorithm is nice in the sense that for a given square, its internal values depend on the external values (this link might have more information about it). The center and the sides of the square depend on the heights of the corners. For any subsquare inside, it follows the same rule.

It is an algorithm that can be feed some data, say, reference points like, oh surprise, ridges and rivers. In theory the algorithm could follow the points already precomputed as reference to compute the points that are missing. Thus obtaining a terrain that makes sense in the context of the rivers and ridges already present in it.

In reality, it isn't that simple. If you grab the heightmap as it is. The information available would be just too low to get a decent "contextualized noise" out of it. That's why the paper presents another stage to fill up the heightmap with some "guide points" for the midpoint displacement algorithm.

The authors use something they call... (dramatic drum roll in the background) Midpoint Displacement's Inverse. (MDI from now on) And the point of all of this is that I can't understand what it is.

MDI and my problems with it

It sort of describes it as a way of guess the corner values of every square and subsquare of the heightmap by interpolating its "child values", which I guess it means the midpoints that you obtain from a regular midpoint displacement pass.

So far I can't understand their (lack of) explanation about the process.

See, say that I have the 5 midpoints of a square, and I want to figure out the corner values. You can get a rough estimate (as in "almost wrong estimate" ) of what the corner values were by interpolating the values that it contributed to.

Attached Image
Example from the Wikipedia.

As you can see there, the top left corner contributes to the values of the left midpoint, upper midpoint and the middle midpoint. If you do (1+2+3.5)/3 you get 2.16'. Which isnt 0 at all but I guess is better that having no point at all.

These (very) rough estimates should help the regular midpoint displacement pass so the values it produces follows the general landscape that the ridges and rivers defined. That's all I could get from the paper.

Doing the MDI pass as I imagined doesn't yields good results:
Attached Image
There you have the bright higher ridge lines and the wider darker river lines going down from the top of the ridges.

As you might or might not see, the map isn't filled with corner points like the example of the paper shows. I'm producing barely any new point, but I can't see how could I be more lax with the algorithm so I can interpolate more points.

The interpolation as I see it needs at least one thing. The point I'm trying to find contributes to three other points, and I need those 3 points to exist to get an average out of them and get the corner value's estimate.

This happens very little on the map given the information it has. There just isn't that many points to get corners from. Moreover, the image you saw its not even checking for the middle value of the square, it tries to find the midpoints of the sides of the square and averages them, and it stills doesn't happens a lot.

So I end up without enough data to feed the regular Midpoint Displacement pass. Here is an example:
Attached Image
The result shows almost the same discontinuities the paper talks about before trying with the MDI pass. That means that my MDI pass isn't working as it should.

Though I understand now why the paper insist on storing everything on a few lists for processing later. If you want to do all of this on some for loops, you're going to need a lot of if checks, since you have to check if there is a need of calculating the height value, and if it isn't, to use the height value that already exists for the later computations. Which usually means to check for all of the 9 values of every sub-square (corners and midpoints) to see if you have to calculate them or not. It was a bit of an index madness for me there Posted Image

Here is a colored version just for giggles:
Attached Image

So...

That's it until I figure out the MDI proccess. If someone want's to help, it would be appreciated. Bye!


Problems...

Posted by , 31 May 2013 - - - - - - · 1,207 views

Hi! So I wrote a little bit more. And this time I have pictures! Shiny pictures! Have in mind that I might jump around a lot since its kinda hard to summarize everything and have in mind I haven't finished this project so every decision I made it might be subject to change in the future.

Also, sometimes the links look black on my end so it might be hard to distinguish them from normal text.

Problems...

One of the various things that either the paper doesn't describes properly or I just don't understand them (4 page long paper? It's a trap!) is the secondary ridge line generation.

After some steps (say, 20 advance() method calls), the ridge particles are supposed to spawn two more ridge lines with opposite directions, with half the deviation from the main one in perpendicular direction to the main ridge that spawns them.

Spawning them isn't difficult. If the main ridge direction is (X,Y), their two child ridge particles would have (-Y,X) direction and (Y,-X) direction. They would proceed just like the main ridge particles but with half (one quarter in my case) the deviation of its parent.

This is the heightmap with the main and secondary ridge lines:

Attached Image

The paper mentions "blending" the ridge lines to compute the river network. It doesn't says with what criteria, nor if it means just blending the ridge lines or blurring all the height values, to end up with an image like the paper shows. I choose to do a gaussian blur pass over the heights to blend them all together.

Blurry vision

Plain ridge lines don't look right and it isn't enough height information for the next steps, we need to spread them around:

Attached Image

I found a very nice library for image filters Jhlabs.com. It has all sort of filters, though we're interested in the blurring ones.

The Java library operates on top of BufferedImage objects. Which means first and foremost that they're very easy to use. The first blurring passes I did were made with that library by "transforming" the height array into a BufferedImage, blurring it, then bringing out the new height values again to a float array.

It worked pretty well at first but after I while I had some problems. Pixel range is quite... limited. I could go only from 0 to 255 on fixed integer steps. So no matter how detailed were my height calculations, after some integer conversions they looked quite bad.

Say that you want to have 1m resolution, so one pixel is one meter. Thats quite great, you could compute a heightmap with a 2km x 2km surface and have some fun with it in no time. But on the height side, you're limited to 0-255 values (255m tall mountain isn't the definition of scary precisely) if you decide to go for a grayscale heightmap using the previous library.

So in the end I had to knock off my own gaussian blur pass which would work with the float array directly. Turns out not only works quite well, but it also takes half the time to compute than doing a filter pass over the BufferedImage. While integer operations on pixel colors should be quite cheap, there is a lot of bitshifting around plus many integer to float conversions (and viceversa), thus the blurring pass over the float array was a better option.

Family, Ridges, and their limits

Something that isn't very clear (to me at least) is that if the ridge lines really should stop only when they reach "null" height (I guess the author meant 0.0f ?). See, if the ridges are supposed to reach 0.0f, which would be the lowest point of your heightmap, then the river lines wouldn't be able to carve their way around when you spawn them later. They'd carve their way around the mountain side, then reach 0.0f immediately after and stop since you can't carve a river line anymore.

If you start your heightmap with a middle value, say, your heights go from 0.0f to 1000.0f, and you set all the initial height values to 500.0f. As it is, the ridge lines would carve their way all down to 0.0f before stopping, that is, the mountains would go under your landscape. Which not only looks bad, but it produces plain pools of river particles later on, which isn't helpful. Though I don't discard the possibility of doing canyons this way sometime in the future, it should work with some tweaking I guess.

For now, and as you might see on the previous pictures, I decided to set up an initial height value for all the map, the ridge lines go from their highest points all down until they reach the initial height of the height map instead of the lowest point. This leaves a lot of terrain for the river particles to produce more interesting lines. I made a few helper classes to map back the height values to BufferedImages so I can visualize the results at each stage, only generating the terrain without doing this in the middle should be quite fast.

So for now the ridge particles stop on any of these 3 conditions:
  • They reached the "bottom" of the heightmap, which is an arbitrary value, one quarter of the maximum height in my case.
  • They collided with another ridge particle (first one to discover it has collided stops, the other keeps going). Collisions within the same particle aren't considered.
  • They reached the limits of the heightmap.
The child ridge line generation follows the same rules. In some rare cases child ridge particles they might collide with their parent's right after their first advance() method invocation since the child particles actually aren't "child" particles. They're normal ridge particles, thus they don't know their parent. Tragic story isn't it?

Umm...

So that does it for now Posted Image There may be some ridge particle stuff that I forgot, I'll add it up to the next journal entry if I remember something valuable. Bye! Posted Image






August 2016 »

S M T W T F S
 123456
78910111213
14151617181920
21222324252627
2829 30 31   

Recent Entries

Recent Comments



PARTNERS