How to find an inverse of an Astar created divide tree?

Hmm not really sure how to answer your question as it stands, but if the goal was to generate river paths on a known distance field/heightmap, I would probably do it the ugly way and brute force it with an agent simulation.

What I am imagining is spawn a few thousand 'rain drops' and simulate/map where they path during their lifetime. Then check for overlaps in the path and if the overlap exceeds a certain threshold, consider that the path of the river, something like this or this

This is something best done using compute shaders, so godot 4.x+. Something I'm curious to try out at some point myself, too.

Yeh Mr. Lague makes the same point in his videos, but I kinda wonder how hard it would be to dump it in/out of a texture using viewports and write a shader that generates it that way (albeit slower)? I don't know shaders well enough yet to know what limitations may be hit there.

Hmm, couldn't you iterate the noise array and apply max(value)-value to effectively invert each value?

This assumes your storing/working with a texture heightmap and not a graph data structure (wasn't aware Godot really exposed one of these but I guess AStar outputs technically would be?)

Sorry I'll try to be a bit clearer, if you consider this texture as storing your height information:

To invert it, you would iterate each pixel in the texture (what I called a noise array as I wasn't sure how you were storing it. Texture... Array... same same in this context), and invert it by taking it's value away from the max available values.

For example, as heightmaps tend to be greyscale each pixel can be be considered a float between 0 and 1. if the float value for a given pixel was say 0.8, then it's new value becomes 1 - 0.8, or 0.2. Applying this to every point should invert the whole array and provide an inverse heightmap.

Which in this instance would look like:

I didn't think this was what you were after at first, hence suggestion about simulating rain, but it may be helpful?

No, I'm not sure how the inverse of the heightmap would be used to identify rivers, was just responding to the need to invert the values but wasn't sure how you needed to implement.

I don't know what the best or mathematical solution is to identify rivers (delauney triangulation may be involved though?), there may be some papers on it somewhere?

I had this in mind for how I would do it jankily:

And to be clear 'agents' makes it sound fancier than it is. In janky pseudo-code I'm imagining:

cutoff = texture_width/2 # seems sane but less/more may be necessary
drop_paths = []
accuracy_mod = 0.2 #speed/accuracy trade off. Below a certain point your not gonna get any rivers
simulation_range = texture_width * texture_height * accuracymod 

For i in range(simulation_range ):
	iterations = 0
	pixel = random pixel #with a heightmap value above say 0.8 (start at tops of mountains)
	while iterations < cutoff:
		pixel = min(nearest pixel (eg.  indices like
				-1, 0, +1 
				-1, SKIP, +1
				-1, 0, +1)
		drop_paths [i].append[pixels index]
		iterations+=1

This should give you an array of rain drop paths, which you then would need to iterate and check for where paths overlap.

This is I think obviously computationally expensive and I doubt it's the 'best' way, but if it's for say procedural level generation and only needs to be run once or in background threads at a chunked scale, I think it would be practical even on a modest CPU. SebLague mentions he does 70k CPU iterations on a 255*255 heightmap in 0.75s (which would be accuracy_mod = ~1.1, way higher than what we would likely need to identify rivers)

Though as mentioned a Compute shader could simulate something similar in a fraction of the time.

This totally sounds like fun so I might try and hash something up myself just to see how well this method does/doesn't work, but won't be any time soon (work -.-)

if you performed erosion on the chunk you're loading up, the edges won't end up matching up with the next loaded chunk as it'll have to perform the simulation seperately

Good point, but for placement of rivers rather than eroding the entire terrain I imagine it would be a matter of snapping positions on the edge of each tile with some nearby interpolation only for the river's endpoints. Similarly, just for identifying river paths, I suspect the number of simulation iterations can be considerably lower than an erosion simulation.

Tiling definitely makes the problem more interesting :3

Anywayhopefully others can provide a better answer, as mine is purely how I would do it and is very unlikely to be the 'best' way to do it ^.

Maybe give it five for YouTube to generate the non-potato version

Another thing I forgot to mention is I think the tooling for A.N.T will disappear if you click away from the mesh and may not come back afterward. If so you just have to 'finalise' all your actions in one go (the Sapling TreeGen plugin is like this too).

ANOTHER thing I forgot (why I shouldn't make tutorials lol) is to turn off 'Falloff' under 'Landscape Displace':

Otherwise, this flattens the outer edge of the terrain by default, which may look pleasing, but will not match the heightmap. The terrain shown should have looked like this:

and not

FYI My pseudocode above isn't 'that' far off:

The above took about a minute to process on a single thread/GDScript, but suspect will need more passes to identify river paths with a good degree of accuracy, so will multithread it once bugs are ironed out. Might rewrite in C# too if I really want to give myself a headache.

Does seems to be an issue with paths ending once they reach a valley floor, but if anything that's an issue with this heightmap having a flat plane along the bottom, which kinda shouldn't happen.

Haven't yet implemented the bit that checks for overlaps in the paths to fully identify rivers, feel like this is going to have the worst performance so still mulling over how I'll do it.

I think what I'll do is write each path out to a texture, where each points adds 0.1 to the colour. That way as paths overlap it should increase, maybe applying a basic blur to the image and threshold out values below a certain number easily. Essentially creating a river heightmap.

Edit: Which also seems to in principle work:

The lack of rivers identified at the top is because I thresholded out everything below a certain height to speed it up, but once threaded can lower the height/increase the sample count. Then thresholding out rivers that don't overlap below a certain threshold:

Ramping up sample count/blurring is definitely needed to tidy up a lot of it, but otherwise should be good. Should be able to use this to generate another mesh with points slightly higher than the terrain layer...

Edit #2: Which looks iffy as. I need to rethink this last bit lol