clabe45 procedural water-scan

Feeds

14:40

Arcane Engineer has added clabe45 to the list of this room's owners.

Arcane Engineer

Hi!

clabe45

oh hey!

Arcane Engineer

Feel free to let meknow what your prime concerns are, and let's see if we can address 'em.

clabe45

Okay, can you lay out your main idea in different terms? I'm having a hard tiem understanding it

Arcane Engineer

Alright, let me first ask you about your existing simplex noise solution. I assume it's generating large areas of the world without limits? i.e. not chunk-based.

clabe45

14:44

That is correct. Every "terrain stack" is generated individually. And I use simplex noise to determine the temperature, annual rainfall, and height of each terrain stack.

Arcane Engineer

I see, so you've built up some technical debt in using that approach, so that you don't want to let go of that. I understand.

And so that I understand you clearly: you have a catch-22 situation, correct? Can you re-explain that to me?

clabe45

Okay, I did. I hate to say this, but I did change something in my water-generating algorithm: instead of basing it off of a constant height for every biome, I'm using a rainfall-flow algorithm (i invented that name).

I just didn't want ot post that in my question, because that would change the question.

Arcane Engineer

OK, but the question has to be accurate. So what problems are you still facing?

clabe45

Now, different biomes have different amounts of rainfall, which flow into valleys.

I still am facing relying a lot on other terrain stacks for generating a particular one

So, maybe your idea is what i want

Arcane Engineer

Alright. So here's the crux of it, any perhaps I was so wordy in my answer that it was unhelpful :) ...

You need to phase things more finely.

So first, can I make some assumptions? And you correct me if I'm wrong. I'll set the stage (again) for a solution.

Let's assume your columns are indexed by int. Let's assume that when you reach int.MaxValue, your world loops back around to zero.

clabe45

14:52

okay, yes I do index them by in a map with Integer

Arcane Engineer

This just makes it easier since we never have to do real bounds checking on that array, as we now essentially have a Ringworld. :)

clabe45

maybe I should use Long though, because I don't want to loop when I don't need to

Arcane Engineer

OK, now all that matters is that your area-of-interest (what I call AoI) is around the current location of the player, or some other location of interest. And that AoI's radius (distance out in positive and negative) is always far less than the total world range (using uint, that range is about 0-4 billion).

Forget long for now... focus ;) (The numbers as such don't matter.)

clabe45

yeah

Arcane Engineer

Let me know if you are still with me, it's important that you're certain of where we are.

clabe45

14:54

yep I will

Arcane Engineer

All good then? OK, carrying on...

So now you can pick any location in the world, and you can scan the area around it. Cool, awesome.

The problem is this:

You need to scan water before you have generated water.

clabe45

you mean for erosion?

Arcane Engineer

No, as per your question. You wanted to know where you should put lakes.

Please jump in here if I'm headed in the wrong direction?

I know you said you now use a rainfall algo.

clabe45

hold up I'm confused

Arcane Engineer

listening

clabe45

14:56

why would I need to scan the water before I generate it?

Arcane Engineer

Alright, forget that. Let's go back to what you said above:

I still am facing relying a lot on other terrain stacks for generating a particular one
So, maybe your idea is what i want

This problem still stands.

Yes?

clabe45

the problem of circular reasoning? how?

I guess relying on other terrain stacks isn't really a problem

Arcane Engineer

Yes. So once again - the circular reasoning problem is like this, and this is the simplest way I can explain as in code:

You are currently doing this...

for each column
A()
B()
C()

whereas what you need to do is this, to _phase_ it more finely...

foreach column
A()
foreach column
B()
foreach column
C()

...now you are gradually building up your foundation. maybe only in the last phase (C()), will you scan other columns for *whatever*.

BUT, chunks help a lot MORE with this.

clabe45

Okay, how big is a chunk?

Arcane Engineer

so to give concrete info to those phases, I would have like:

foreach column
genLand()

foreach column
scanLandToDoOtherThings()

clabe45

15:00

I see

Arcane Engineer

Whereas you are doing this:

foreach column
genLand()
scanLandToDoOtherThings() //problem! as you don't have all the columns land yet!

This is basically the problem we're looking at.

We could leave this here for now and you could have a long think on that topic alone, and decide whether this knowledge might help you solve things.

Chunks... that's another topic... and for that I think my Answer gives the best info... but if you have specific questions...

clabe45

well, first I have some questions if you don't mind

Arcane Engineer

Go on, I'm listening.

clabe45

oh right, chunks have variable sizes, but how do you define the biome and endpoints of a chunk?

how do I generate chunks?

Arcane Engineer

OK. That depends on how you do things. In my own procgen projects, I generally generate chunks first. Part of the reason for that is I'm not a huge fan of simplex or perlin noise. I prefer controlling within each chunks bounds.

I see that you have a preference for simplex noise. IF THAT DEFINITELY WON'T CHANGE, then the way to answer that question is different.

So what I'd try to do is something like this.

clabe45

15:04

hold on, what's your alternative to simplex noise

Arcane Engineer

...For that, see my answer. Again ;)

Let's talk about simplex first, then we can get back to that, OK?

Simplex noise works on a fundamental principle: you can pick a point (in however many dimensions) and you sample the function at that point. With me?

clabe45

yes

Arcane Engineer

So in your case, you pick a point in x, and you get back a height.

clabe45

right

Arcane Engineer

Cool. Now let's consider this. The boundaries of your biomes/chunks are up to you to choose.

So you can do what I suggested in my answer: Start by creating a long array of start-end, start-end, start-end. Basically an array of segments running in x.

so e.g.

0-10, 10-25, 25-33... etc.

These are the x-bounds of each chunk/biome

Still with me?

clabe45

15:06

yes

Arcane Engineer

OK, what matters here is this. You go through that first phase I discussed in my answer, where you generate your array of these. HOW MANY you generate is entirely up to you, but you MUST generate at least as many as your scanning distance * 2 - so that you can search around the player in both -x and +x.

What you've done now is to create JUST THE SKELETON of each chunk. That is computationally cheap.

And you've only created the skeletons of those chunks that are NEAR you.

Right?

clabe45

rright

I do have a terrain stack oultine data structure that holds the height and temp and rainfall, so I'm sort of familiar with that

Arcane Engineer

Now with those skeletons, you do the next phase, as in our foreach examples.

foreach chunk near player
genChunkSkeletonWithBiomeInfoAndXBounds()

foreach chunk near player
examineAllOtherChunkSkeletonsAndTakeSomeAction()

...and that Action could be, for example, filling in each column within that chunk, now that you know what sort of biome it is, and _rough details_ on each of it's many neighbours.

Awesome, good that you are familiar with the idea already. It's like a ghost-of-a-chunk ;)

clabe45

exactly

Arcane Engineer

Not all the details have been filled in yet - you leave that for a later phase.

Is this starting to make sense, reading the last paragraph above?

Are you starting to see your way to solutions?

clabe45

15:11

sort of, but how do you determine the height of each stack?

and what makes up each stack

Arcane Engineer

When you say stack, do you mean each like, voxel or pixel column? NOT chunk?

Or do you mean chunk/biome

clabe45

correct, NOT chunk, stack/column

Arcane Engineer

OK. So that's just produced by your simplex function, right? You give it x, it gives you some nice height that is smoothly-adjacent to its neighbours.

Storing them,

clabe45

yes

Arcane Engineer

Is done like this:

you remember the biome data items I made early on in my answer? we do similar to that. If you look at that, you'll see I had a mini-array in each biome.

clabe45

15:13

yes

an array of terrain stacks/columns

Arcane Engineer

You can actually do this two ways....

I keep them per chunk.

You probably keep one huge array for the whole world. Right?

clabe45

yes, or you could keep them globally

right

Arcane Engineer

Yes. There is nothing ostensibly wrong with either method, it just depends on your game logic needs and later on, things like optimisation.

But if you want to keep a global array,

then you DONT have to keep it per chunk.

Because...

You already have the start and end index stored in the biome/chunk... don't you? :)

clabe45

yes that would be redundant

Arcane Engineer

Those indexes are used to look into the global array.

Yip. So to give you the outline I'm seeing at this stage...
-we get the player's pos
-we generate biome-ghosts for the area around the player, in -x/+x, to however many units you decide (say 100) . so we are running from playerPos-scandist/2 to playerpos+scandist/2.
-(OPTIONAL) we sample at the extents (start and end) of the chunk. store in biome.
-(OPTIONAL) we sample at centre of the chunk. store in biome.
[these above two steps can help you deduce things about the chunks terrain, without having to calculate ALL the columns per chunk]

and when I say "sample" in the (OPTIONAL) parts, I mean getting the simplex height.

(be sure to click "read more" above, lol)

(just so you can see everything)

Give that some thought over the next few mins if you need to. I'll be here.

clabe45

15:20

okay thank you very much, I will certainly think about that

but you mean you only have endpoints and a midpoint for each biome (and you interpolate for the rest)?

Arcane Engineer

Remember also: In some cases chunks near the player will have already been generated. But because you can not always rely on that, you should probably never rely on that as it will make your code more complex. Easier to just rely on ghost info.

At that stage, yes, you only have that info. But by the end - see last step - you generate all the missing columns... using your scanned info from all the ghost chunks.

DON'T interpolate :)

It will look crap

;)

Use simplex throughout - but in early phases, only use simplex for the start, end, and (maybe) middle (if you want)

clabe45

I don't understand, so you're still using simplex noise for all of your heightmap?

I'd prefer throughout, for simplicity

Arcane Engineer

Yes, but AT THE END of your process.

clabe45

why?

Arcane Engineer

Because catch-22, that's why.

You can't generate full chunks without generating full chunks.

clabe45

15:23

I mean the ghost chunks contain full heightmap right?

Arcane Engineer

You want every chunk to know its neighbours final state, when you know not all the others have been generated yet.

OK so what happens is this...

In the early / intermediate phases, you sample only for the start, end, and maybe midpoint. You do this while you are creating all the chunk objects in the player's locale.

At the final phase you sample for all the non-end, non-start, non-midpoint columns/stacks. Because your chunks (which used to be ghost chunks - it's the same array of objects) now reference columns that have been correctly simplex-generated, they're no longer ghost-chunks, are they?

clabe45

Hang on, I thought you needed all of your heightmap to generate the "extra" stuff - like water

Arcane Engineer

Focus. In other words,

-gen all ghost chunks in range of player, populate them with a little info (start, end, mid). you can also sample simplex for start, end, mid at this point.
-for each chunk near player, look at its ghost neighbours, make some decisions based on that ghost info
-for each chunk near player, populate every last as-yet unpopulated stack - they are now no longer ghost chunks

You're thinking yourself round and round in circles.

;)

Edited the last bullet point above.

to explain to you,

water, vegetation, monsters, whatever - that all happens in the second phase above

where you look at the ghost chunks

clabe45

I am focusing, it's just I don't understand why you wouldn't need the heightmap for water generation

Arcane Engineer

You may or may not do MORE with them in the final phase.

Look. You've told me you use a rainfall algorithm. Do you want to keep doing that, or not?

Because to my mind, rainfall algorithms are a better plan.

but as you've said, you will still have the catch-22 for OTHER things.

clabe45

15:31

Yes, I will keep using the rainfall algo, but you need the slopes of the land to know where it flows

Arcane Engineer

Ahhh. OK.

So with rainfall algo, you do it after the final step.

Or in the final step above.

clabe45

ohh

Arcane Engineer

After you've populated ALL stacks.

clabe45

so ...

1) generate endpoints and midpoint of chunk

2) generate all other points (stacks) of chunk

3) generate water/monsters/ other extra stuff

Arcane Engineer

Not quite.

What is (1) on it's own like that going to do for you? Why do you currently need endpoints and midpoint? Where are you using that info?

You may as well just do 2 & 3, no?

clabe45

15:33

yeah i have no clue, yes

so why did you mention (1) in the first place; it had to have a reason

Arcane Engineer

OK. There are a few reasons.

-Your chunks ARE your biomes. So you need to know where they start and end, e.g. for colouration. This ALONE is enough to justify knowing the start and end of each chunk, and it's biome type (so e.g. a grassland biome is coloured green).

-But also, it is an optimisational tool, as discussed in the entire conversation above. You already HAVE TO know the start and end point. But if you also sample HEIGHT at start and end, you start to have a clue about what the terrain looks like - even if you only have its average altitude. This CAN allow you to make other deci…

So think about the second point like this:

It's like you're just taking a quick peek at nearby chunks.

It's like a soldier in a firefight peeking around a corner for just a second. He gets some idea of what is going on. He could stick his head out and STARE, and he'd get a lot more info, but that would have other problems like in your cast cost and catch 22, and in his case, getting his head blown off.

So look, let's step back.

Your rainfall algo will be awesome. But you should do things like this:

1. Gen all ghost chunks in range of player, stick them in an array, populate them with a little info (start, end, mid), maybe get simplex height for start, end, mid point.
2. for each chunk near player, look at its ghost neighbours, make ANY DECISIONS YOU NEED TO MAKE based on that ghost info (have this step in here, because you may need it later! even if it does nothing right now)
3. for each chunk near player, populate every last as-yet unpopulated stack - they are now no longer ghost chunks but full-fat chunks.

Hmm. I'm just thinking about step 2. Give me a couple mins.

clabe45

ok

I guess I'll ask again: why would you get caught in a catch-22 if you had more than the endpoints/midpoint?

after you figure at step 2

Arcane Engineer

OK, that goes back perhaps to a preconception you created in your original question. The water issue. If that is the only problem like that which will ever exist for you, then you don't need to worry about catch 22 again.

I am giving you this fuller solution in case there is anything in your code which requires you to know about other, neighbouring biomes terrain stacks BEFORE they can have been generated.

clabe45

ok I see

Okay, so I'll reiterate what I'm understanding

Arcane Engineer

By the way.. will you be generating more biomes than the player can see? Or only the very nearby ones?

clabe45

15:45

very nearby ones

Arcane Engineer

OK cool.

Go on..

clabe45

okay to continue

```void genChunk() {
genBaseHeightMap(); // midpoint and endpoints
calcBaseDecisions();
genFullHeightMap();
genWater();
genVegetation();
}```

of course, that doesn't make sense because there is no argument x

Arcane Engineer

that's fine, we're just talking pseudocode, we know what each other means.

clabe45

i can't get it to look like code lol, but yeha

yeah*

i still don't understand how i would generate the chunk boundaries

Arcane Engineer

Hehehe... So I would say...

1. gen all biomes: range + type. I know you need this to be deterministic. A simple hash function (even one built into C# system libs) will do this for you - same input, same output every time.
2. pick a range in stacks around your player. find out which biomes that overlaps. Now you know which chunks you need to generate here and now.
3. generate full stacks for all those chunks.
4. gen water, veg etc.

You can use the same hash function to get the chunk/biome start and end, for each boime. Do like this:

Hmm, just requires a little thought...

Need a few minutes, boiling hot here and I've been thinking fast all day.

Anyway, you can easily ask that question on the site.

clabe45

15:54

oh lol no worries

Arcane Engineer

And others will give you a rapid answer.

clabe45

okay

thank you so much for your time

I will bookmark this conversation and refer to it probably lol

Arcane Engineer

Hope I helped, even if long-winded. At least now you can reason things through more easily.

You're welcome :) Best of luck, probably see you around again on the site!

clabe45

yeah you too!

Arcane Engineer

Have a good weekend. Take care :)

clabe45

15:55

thank you again

Transcript for

♦ clabe45 procedural water-scan