Working on a ambitious world generating tool...

[Redrobes]

ViewingDale does render on the fly. Its basically a scene graph editor / renderer. It works on a hierarchy of images and it manages the scale so that it displays only whats needed on the screen and doesn't try to draw whats not on the screen. So it draws only the bit of continent that it needs to draw. As you zoom in there is usually more detail but the extents are smaller too. At a certain point which we have reached now, computers were able to draw the detail vs extents at a speed where its useful. Actually in the last few years we have more power than is necessary. There is a setting in the program which tells it how much detail to draw so if you have lots of power then it can draw down to very small stuff otherwise you can say cut it off when its at a certain level.

So there is no limit to the overall complexity of the world, only a limit to the complexity at the bit your looking at. And with modern PCs and graphics thats now pretty complex. It can draw about 100,000 objects a second. So the worst case is a forest full of single tree objects and you zoom out to a point where each tree just about needs to be drawn. Of course, you don't normally draw forests by the individual tree.

If your set on doing it in this direction then consider OpenSceneGraph or Ogre game engines. But even then I wouldn't think they would be able to do the job that ViewingDale does as fast as it can. There's a new API out called OpenCL which looks like it might replace some of the scene graph engines by using GPU assist for them. Don't know much about that at this stage. It was only publicized late this year.

You might also consider using WorldWind as a means of displaying maps too. When I tried it last time it was slow though I hear its got better in the last few years.

SeerBlue on these boards codes up maps into the format required by the Google API. Theres some newer tools to do that in a limited way now too. Though I don't like the fact that its hard to then edit the maps afterwords. Also, the map needs to be streamed from a web server which I guess you could install one locally. But that's all faff I wanted to bypass.

My GeoTerSys (GTS) is unreleased and ongoing - forever ongoing. Thats a really hard thing to write and its hard mainly due to the water bit. I track lots of water parameters doing sediment, erosion, velocity and momentum etc and it still wont do meandering or oxbow lakes. I have been on that about 2 years and ViewingDale about 4 plus there was an application prior to the final version of ViewingDale which I called Mapper and I started that in about 1990 on the Commodore Amiga. Both of these two make up only about half of what you have in mind. I don't wish to put you off, but your looking at about 10 years work in front of you.

[covatex]

... I don't wish to put you off, but your looking at about 10 years work in front of you.

I hope not!!!

[RobA]

Here is a another river reference that may be useful.

http://www.cartographersguild.com/showthread.php?t=1754

-Rob A>

[Nickadimos]

Ok I actually have a lot to say about this project. In particular when it comes to these rivers.

Ok, Anyone ever hear of the Chaos Theory?

All that it implies, is that ALL things no matter how big or small ALWAYS ALWAYS ALWAYS take the easiest route possible through ALL things, period point and blank.

(I'm not talking about the thing that a butterfly flaps its wings in India and there is a tornado in Oklahoma..)

It also implies, that no matter how complicated or random something looks or seems to be, it is always so simple, that most never find the answer to the question they are asking until they look away and do something else, or they see a clock on a wall as they are riding a bus (Einstein) and figure out the theory of relativity.

I know your English isn't that great, so I will do my best to explain this theory I have on generating streams rivers and the like, and have complete control over it...

OK...

On a grey-scale height-map of a terrain there are only so many colors you can have.

For simplicity sake and continuity of argument, we are going to say that our terrain has only 255 colors in it ranging from Pure Black "0" to Pure White "255".

I have provided an image to help you follow along with what im saying.

The first step in the Algorithm, is to establish your high points.

You have your program search out the Highest points on the terrain.

You can have it set so you put for example, 10 colors variation.

So it finds the highest point, for example 255 (most likely you will never have a 255 unless you want it). If you set your number to 10 earlier it would mark every area from 255 to 245.

On the image below those are the red dots. (normally there are way more)

Then you have your program find the Lowest points in the same manner.

We will set our number to 10 again. so it will find all the colors ranging from 0 to 10 only.

On the image below I have these areas marked as the bright Yellow spots.

The last part of the finding phase is the midpoints.

Once again we set the program to work finding the all the points that are directly int he middle of the highest point and the lowest point.

On this example it is all the colors that are 127-128.

Once again we set our range to a 10. so it will find everything from 117 to 138.

These areas are marked as a bright green spot on the image below.

Now is the time that you need to set it so that the person doing the map can erase or eliminate points he does or doesn't want.

Say, he has a desert area with no water at all.. he can go through and delete any of the points found in the area that is desert.

Now the fun part and the heart of our river algorithm comes through, and my point about Chaos Theory comes to light.

All your system does from this point, is generate a river "seed" from the highest point to the lowest point. with a twist!

Your first thought is, "well all that does is make strait lines"!

No not with my super complicated math algorithim!

Actually im kidding its probably the simplest math problem known to man.

It does find a strait line, AT FIRST! this is just so it knows which direction to head in.

THE MEAT

Since all things follow the simplest path NO MATTER WHAT as my theory states. were going to give it the simplest path to follow with some simple rules.

1, in order to continue, the path must find the VERY next closest color in the height map to continue that is at least 1 below the current color.

EXAMPLE;

If the path it will follow starts at color 246 (Our highest point). And the absolute next closest color is 240. the program simply draws a line from 246 to 240. Then the next color is 238. the program draws a line from 240 to 238, and so on and so forth till it gets to the midpoints that were left behind by the mapper that are around 138 or so.

Once it gets to this step. It repeats the process to get from the midpoints to the closest low points or it hits zero. whichever comes first.

Example;
The program runs out of numbers in its path trying to get to the lowest point from the midpoint (probably wont) and the stream/river stops.

SUBTRACTION! Thats the hardest algorithm EVER! LOL.

For the base of the river it is slightly different. Its the same theory except in a positive direction.

First the program tries to find a way using colors from one lowest point to another. once it has exhausted its options at a color of 0 (which will most likely be really quick). It tries to get to the other point with a range from 0 to 1. Once it cant make it from there, it tries to get there with a range from 0 to 2. and so on until it gets from one point to the next, then it starts over to get to the next point and so on until it gets to the point the mapper left in the ocean area.

You will actually end up with a pretty neat winding river with thick points and thin points being fed along the way with winding smaller rivers.

They may not meander perfectly, they will be winded and believable.


Now I know I can be wordy, and im sure your going to scratch your head a few times. But it will work im sure of it, I wish i could code it myself for you.

In the end all im saying is the world or the universe doesn't care about velocities and force and sediment distribution, im sure it looks like it does, and you can take 10 years to try and make sense of it.

OR you can just say what it is, rivers flow downhill and they take the easiest and most direct path to get where they are going.

A few techie things.

1, you should give the ability to set the number of smaller streams coming off of any given point.

each point can only go to each point once. So if I set MIDPOINT 1 to have 2 streams branching, 1 stream will go to LOWPOINT 1 and the other will try to get to LOWPOINT 2 (if it is the next closest one to MIDPOINT 1), It will ALWAYS try to go to the next closest one even if that means it is LOWPOINT 8..

MIDPOINT 2 can have a stream going to LOWPOINT 1 or 2 if it wants.

Thanks

Terry

Any question ill try to explain more for the sake of me and everyone else.

my picture isnt perfect.. the lowest river going yellow dot to yellow dot would be much bigger and thicker due to adding to get from one to the other!

[Sigurd]

One thing to talk about how it should work in theory, another to see it through to the trials and compromises of completion.

How bout a working demo Nick ?

Sigurd

[Nickadimos]

Sigurd,

In all theorys of course you need proof. And of course you have skeptics. .

But you see my proof in my image that I provided.

I did all the steps from my explanation manually and slowly.. took 4 hours..

Its not as perfect as it would be if it was coded with a nice interface to work from with a more direct approach instead of the color select tool and 800% zoom.

And would take minutes if it was in a prog.

And of course, the whole purpose behind explaining the Chaos theory in the first part, was to explain my method. We arent trying to implement the Chaos theory in the program, were taking a feather out of its hat.

Im not a coder so I cant make it.

They also use a similar system in L3DT with thier rivers and such. Mine is just simpler still.

Thanks!
Terry

[Redrobes]

Aaron of L3DT does not do it your way. Here is a quote from him.

The 'dropwise' algorithm I use (I've coined another one!) simulates the path of each drop individually, which has certain limitations, but works well with large tiled data that's too large to hold in memory all at once (crucial in the context of L3DT.)

He has two models one of which he has released in his app and the other (at least as far as I know) he did not because its too slow. The dropwise algorithm he talks about takes a drop of water at each pixel and looks to see where it flows to get to the sea by moving to the lowest point adjacent to it. Eventually it must either pool or hit sea. He then aggregates the amount of water in each pixel and draws rivers where there is a lot of water. Makes sense and is the simple 'water flows downhill' theory.

It has limitations and he knows all about them. If you are on a flat-ish plane near the sea and this plane is like a mud flat then in this algo the water takes the most direct course to the sea. Usually in a few straight line sections. In real life it does not because sediment is dropped and the river changes direction. If you don't drop sediment then it wont meander.

Your straight down to the sea idea is fine in only a limited instance and the reason why you haven't found why it doesn't work so well is that you haven't programmed it and haven't tested it. If you look at your height field in 3D you will see that its actually a mass of spikes in which the water droplet will fill a depression and clog. With no accumulation it will stay there and fail. If you accumulate then you have a series of pools which will spread out and because you cant model the very low viscosity of water then it will spread out in a fan like direction instead of a nice thin line to the sea.

If your looking for the highest and lowest points and then interpolate then that's fine for the top & bottom but you have a million middle points in your spiky terrain to choose from and even then how do you know that you wouldn't have to go up hill before going down again to make that line.

So we need to see a working program that we can enter some height fields in and watch it plot water courses. Nothing else will cut it. Theres a lot of experienced and bright people looking at this problem and its not all that simple.

[Nickadimos]

RedRobes;

The dropwise algorithm he talks about takes a drop of water at each pixel and looks to see where it flows to get to the sea by moving to the lowest point adjacent to it. Eventually it must either pool or hit sea. He then aggregates the amount of water in each pixel and draws rivers where there is a lot of water. Makes sense and is the simple "water flows downhill" theory.

You do realize that is almost exactly what I said right? (where do you think i even got the idea from??) Did anyone even read what I wrote?

Except mine is WAY simpler and doesnt allow water to pool as much. Mine goes from pixel to pixel just the same high to low, except instead of finding the next lowest point, it finds the very next lower color on the height-map.

Which, in so many ways is the same cause you use color to determine height anyway, but it is not as absolute as the very next total lowest point.

The other major difference is the fact that the whole drop of water at every pixel then tracing between the ones that form a pool of water, is an over complicated way of just saying here are the lowpoints.

In my method it finds the high middle and low points, then you can choose which ones you want to keep, then it traces in between them following my basic subtraction method.

This is better cause you dont end up with any suprize pools of water or rivers.

What this method fixes is the tendancy for things to pool and the algo to fail.

The reason that the dropwise algorithm method fails so often is because of the method itself. It finds the absolute next lowest point, which could very easily be a height considerably lower at the next pixel.

Aarons,
Say it is at 240 White, the program checks all 8 of the adjacent pixels, starting at the top left they are, (S = start) (U = used once)

238 - 246 - 220
190 - S - 224
168 - U - 222

Now the path that the dropwise method will take is easy to figure out. it will go to 168 because that is the lowest next pixel.

In my method,
Say it is at 240 White, the program checks all 8 of the adjacent pixels, starting at the top left they are, (S = start) (U = used once)

238 - 246 - 220
190 - S - 224
168 - U - 222

Now the path that mine will take will be 238. because it is the very next lower pixel. Not the lowest.

It has limitations and he knows all about them. If you are on a flat-ish plane near the sea and this plane is like a mud flat then in this algo the water takes the most direct course to the sea. Usually in a few straight line sections. In real life it does not because sediment is dropped and the river changes direction. If you don't drop sediment then it wont meander.

I agree that this is could be a fundamental problem with both mine and aarons methods But also remember that mine finds its way from lowest point to lowest point (main rivers) by counting up as outlined in my first post and the only river/rivers of water that go to the sea are the ones you choose to go there...

Your straight down to the sea idea is fine in only a limited instance and the reason why you haven't found why it doesn't work so well is that you haven't programmed it and haven't tested it(1). If you look at your height field in 3D you will see that its actually a mass of spikes in which the water droplet will fill a depression and clog(2). With no accumulation it will stay there and fail. If you accumulate then you have a series of pools which will spread out and because you cant model the very low viscosity of water then it will spread out in a fan like direction instead of a nice thin line to the sea.

As previously explained, its not strait down to sea, its strait down to the next midpoint, then the next lowest points, that you chose to leave behind once the high, middle, and low points were all determined in the first part.

(1) I have tested it,

But you see my proof in my image that I provided.

I did all the steps from my explanation manually and slowly.. took 4 hours..

Its not as perfect as it would be if it was coded with a nice interface to work from with a more direct approach instead of the color select tool and 800% zoom.


(2) I made that heightfeild in L3DT by the way. I own the professional version. I beleive it got pixelated when saves as a jpeg from L3DT to gimp to here and thats why you would think its a ton of spikes...

I could make another picture at the pixel level if that helps more.

And please read the rest of what I wrote.

What we do need, is something that is in between the two methods I would presume.

Thanks
Terry

[Redrobes]

Terry, I will look at it some more. Maybe I didn't read it well enough. I have read it again and I still don't see how by looking at the next lower value it will work any better than using the lowest point. It still seems as though you can almost immediately run into a dead end pooling situation in the same way. Its a bit late here so ill try again shortly and I might even code up the app for you because I am interested to see it too. It should not be difficult for me to write something to take a 64x64 image which has large blocks to see the action.

[Nickadimos]

I will however digress and admit that I am terrible at getting my thoughts on paper in a clear and concise way as I am dyslexic.

90% of the time it seems like im being mean or sarcastic or whatnot. If we were talking face to face and i could use my hands to talk to you we would be in like flint.

Just please try to remember that about me guys..

Im a great public speaker.. LOL

Terry

The little faces help!