How to find "closest Ocean Plot" performantly? [OBSOLETE]

[raystuttgart]

Hi guys,

I have started to write a "technical concept" (pseudo code) for an algorithm to generate "Large Rivers" by a DLL method called from MapScripts.

My main problem, the algorithm heavily relies that it finds
the closest Ocean Plot (as potential end point of a "Large River")
to a given Land Plot (as potential starting point of a "Large River").

And since I need to do this many many times to find the ideal places to generate "Large Rivers", it needs to be very performant.

@f1rpo @Nightinggale @devolution
So any suggestions?

Basic explanation why that is needed:
(It is a bit more complicated than that but the spoiler should give the general idea.)

Spoiler :

Basically it first checks if the Plot itself is "Flat Land" first, before it does the search for the "closest Ocean Plot" as described above.
(Only then it tries to find that Ocean Plot.)

After it found the "Ocean Plot" it checks it checks the distance to the closest Ocean Plot is too short or too long.
(These are new setting in the "MapSize xml".)

Also the loop to generate "Large Rivers" will end once it has generated the "max number of Large Rivers".
(That is also an new setting in the "MapSize xml".)

Once it looped all Plots it will of of course also end even if it could not generate "enough" Large Rivers as defined in "MapSize xml".)
(There may be Island Map Scripst like "Caribean" that can hardly generate Large Rivers.)

Comments to the rest of the algorithm:
(It is a bit more complicated than that but the spoiler should give the general idea.)

Spoiler :

Everything else in my algorithm is more or less a piece of cake considering implementation.
(I would know how to implement all of that but I would of course give it to other experienced modder to further optimize its performance.)

The rest is basically a (partially randomized) "weighting system" to check in which cardinal direction it should move to create the next "river section".

It considers for "weighting" mostly previous move direction (relative to "end Ocean Plot"), "Mountain Plots", "Hill Plots" and "Water Plots" of adjacent plots to figure out if an adjecent plot could become the next "river section".
(It may find "Lakes" or even other "Large Rivers" but the only "Ocean Plot" it should find in the process is the "end point" we found above though.)

Once I know how to find the "closest Ocean Plot" I can also find the "closest Large River Plot".
(I will try to implement a min-distance between 2 Large Rivers. Also as a setting in "MapSize xml".)

Large Rivers will be generated before any Small Rivers, Terrain Features, Villages, Goodies, ... are placed.
(Thus all of that stuff does not need to be considered in the algorithm.)

@devolution:
Please let me know if you already implemented something like that so I do not waste my time.

@community:
Please leave this discussion to people that understand programming DLL logic for Civ4BTS / Civ4Col.

 

[f1rpo]

So I think you only need to find the nearest non-Lake water plot once for every (potential) source of a large river, i.e., at worst, once for every land plot. In that case, I don't think one can easily gain much by re-using (intermediate) results – and doing so shouldn't be necessary either. I'd just run a breadth-first search (BFS; pseudocode on Wikipedia) at each source. For the queue container, std::queue can be used. If a distance is needed repeatedly, then I'd say just store it in a container that maps (source, destination) pairs (as plot indices) to distance values, e.g. a std::map<std:: pair<int,int>,int>.

This approach will find the nearest salt water plot in terms of stepDistance. plotDistance, as an approximation of Euclidean distance, might be preferable. Could use Dijkstra's algorithm (Wikipedia) for that. Still pretty fast and easy to implement. Or alternatively keep BFS going for a while after encountering the first water plot to see if a water plot with shorter plotDistance will come up.

I assume that you're only interested in the distance, i.e. that the nearest water plot won't automatically become a river mouth. So a bias from always adding adjacent plots to the BFS queue in the same order shouldn't be an issue.

For the starting position algorithm in my AdvCiv mod, I use Dijkstra's algorithm to precompute a distance table for all potential sources and destinations. For reference, this is my DistanceTable class – but I hope you can do something simpler.

 

[Nightinggale]

If we want to keep this simple, we can do something like "distance to Europe". Make an int array of length numPlots. Set all to MAX_INT. Loop through all plots. Set oceans to 0. Once setting a plot to a value, add 1 to the value and call the 8 plots around it. If it's non ocean and the argument (here 1) is lower than the value for the plot, set it to the argument and then call all plots around it.

It might not be performant and maybe it needs a bit of tweaking to avoid a stack overflow of recursive calls, but other than that it should work. Since it's only done once, using the result to call many plots afterwards should not be a performance issue.

Remember to call the function to automatically convert between lakes and oceans if you do not want large rivers to end up in lakes.

 

[raystuttgart]

@Nightinggale, @devolution

My concept kind of looks like this:

1. Step: generate array of Land Plots with Ocean Plot distance (lenght iNumPlots --> really huge for Gigantic Maps)
2. Step: filter that array of Land Plots by throwing out all of them where Ocean Plot distance is too short or too long (min length / max length defined in MapSettings)
3. Step: randomly pick a set of Land Plots (specific number defined in MapSettings), repeat until ensured that they are not too close to each other (min distance defined in MapSettings) --> Land Plots Set
4. Step: For each Plot in Land Plots Set find its actual closest Ocean Plot --> Plot Pairs (Land + Ocean)
5. Step: for each Pair generate a path from the Land Plot to the Ocean Plot (e.g. using "Dijkstra's algorithm" + weighting of Plot Types)
6. Step: Make the method available to Python and call it from Python during Map generation (before any Terrain Features or other stuff is generated)

Does that sound reasonable?
Maybe we can even do a pair programming session and implement it together?

It actually sound pretty challenging and interesting to implement something like that.

---

All of that is only called / computed during MapGeneration.
So none of the data needed (e.g. Plot pairs) will somehow be stored or later used ingame again.

Acually it is a petty that the information "Spring of River" and "Ocean Delta of River" is otherwise not useful data ingame.
After we invest so much frontloaded performance to match it is there anything else this information could be used for?

 

[Nightinggale]

A few comments for possible improvements

Step 1 and 2

Make a distance map like I proposed, though it's easier if it can stop working after max length. Then do step 1 and 2 in one go by looping all plots and store all plots with a value within the range. I think that will be more performant as the plot distance calculation is done once and for all.

Step 5
Do we want the shortest path possible? Rivers can snake through the landscape. Ideally it should make a few possible paths, which are the shortest and almost shortest and pick one of them. This could be done by having more than one code for shortest path and pick a random one for each river. Or we could just add randomness to an existing one, like randomly pick something like "one down, one left, one down" when the pathfinder wants to go down. After such a diversion, it makes the shortest path from the plot it ended up on.

Through first generation of this should likely be simple, like using Manhattan pathfinding. Once that and everything else works, we can look into making rivers look more interesting.

 

[raystuttgart]

Do we want the shortest path possible?.

No, because it is actually an "Dijkstra's algorithm" that will e.g. add "length" to a plot / node if the node is e.g. a Mountain (+6) or a Hill (+3), so it is more likely that it will move Flatland and snake around Mountains and Hills.
Also it has to avoid to touch / connect to Lakes (Land Plot adjacent to a Lake +10) on its path because otherwise it would not end in the Ocean but in a Lake. So it also has to snake around Lakes.

Also there needs to be a bit of randomness in there because it can not go diagonal. e.g. if the best next plot towards Ocean would be "SouthEast" it can randomly decide if it goes South or East.
The direction it has moved in the previous move will influence that choice (by weighting) as well.

For the path it calculates "recursively" by "lowest path weight", it will generate a path that avoids to transform Mountain Plots / Hill Plots and also paths that will bring it to close to a Lake.
It is basically all about smart adaptation of "Dijkstra's algorithm" for "node weights" that sum up to a "total path length" that will determine a "shortest path", which is however not the "shortest distance".

 

[raystuttgart]

So ok, after a constructive internal "concept" discussion, we figured out that there is probably a better technical solution.
@FlaviusBelisarius is going to try to implement this directly in the FaireWeatherTweakEx.py Mapscript.

The reason for that decision is, that this MapScript already creates pretty natural looking landscapes and also good looking "small rivers", so it should theoretically also be able to create good looking "large rivers".
Thus the new solution approach is probably superior to the solution concept I originally thought about in this thread. Since I am really bad in implementing MapScripts I could simply not have realized the new better concept myself.

@FlaviusBelisarius
Thanks for your willingness to take responsibility for this topic.
We had been searching for support for this topic for a long time already and almost given hope to find any.
So we are really greatful that we finally found sombody motivated and skilled enough to give this challenging task a try.

 

[f1rpo]

Great. Hopefully this way the large rivers can correlate better with small rivers, jungles, deserts etc.

Just to set some details in my earlier post right:

[...] I don't think one can easily gain much by re-using (intermediate) results [...]

If we want to keep this simple, we can do something like "distance to Europe". [...]

I stand corrected. For step distances, it should be possible to use dynamic programming as Nightinggale's post describes. Should also be possible to store, for each land plot, the plot index of the closest coastal water plot while computing the distances.

[...] maybe it needs a bit of tweaking to avoid a stack overflow of recursive calls, but other than that it should work.

I think this here is a non-recursive (Python) implementation of the algorithm you describe, originally by cephalo (PerfectWorld2).

[...] store it in a container that maps (source, destination) pairs (as plot indices) to distance values, e.g. a std::map<std:: pair<int,int>,int>.

Needlessly complicated – don't need to index by the destinations. So just a vector storing the distance to the sea for every (land) plot index.