River Connection Algorithm
- Thread starter whoward69
- Start date
I guess you only want to know if the three tiles are connected "in a row" by a river (for instance, on your screenshot, perhaps it is only one long river looping back further east).
I believe it boils down to proving that the middle tile (B) has two consecutive river edges that link the other two tiles (A and C).
I don't know what data structure you are dealing with but assuming A is linked to B through edge E (an integer in [0:5], so that B is linked to A through (E+3)%6), then :
-edge (E+1)%6 and (E+2)%6 must be rivers in B
OR
-edge (E+4)%6 and (E+5)%6 must be rivers in B
That leaves the rare case where the river ends abruptly (like exactly on the cow icon between B and C). If R(T, E) means there is a river on the edge E of tile T, then the full expression becomes (in C style notation):
(assuming that all values for E are modulo 6)
I believe it boils down to proving that the middle tile (B) has two consecutive river edges that link the other two tiles (A and C).
I don't know what data structure you are dealing with but assuming A is linked to B through edge E (an integer in [0:5], so that B is linked to A through (E+3)%6), then :
-edge (E+1)%6 and (E+2)%6 must be rivers in B
OR
-edge (E+4)%6 and (E+5)%6 must be rivers in B
That leaves the rare case where the river ends abruptly (like exactly on the cow icon between B and C). If R(T, E) means there is a river on the edge E of tile T, then the full expression becomes (in C style notation):
Code:
R(B, E+1) && R(B, E+2) && (R(A, E) || R(A, E+1)) && (R(C, E+3) || R(C, E+2))
||
R(B, E+4) && R(B, E+5) && (R(A, E) || R(A, E+5)) && (R(C, E+3) || R(C, E+4))(assuming that all values for E are modulo 6)
whoward69
DLL Minion
It's not just in a straight row, but any three tiles.
If you call the tile immediately to the right of B tile F, then B-C-F form a river connection - and that involves four river segments.
Call the tile immediately to the left of A tile G and G-A-B form a river connection only involving one segment
If you call the tile immediately to the right of B tile F, then B-C-F form a river connection - and that involves four river segments.
Call the tile immediately to the left of A tile G and G-A-B form a river connection only involving one segment
How about A-B-F in your example? Do you need to detect if the river takes a "detour" as well?
If not, you will only need a method for telling if two river edges on a tile are part of the same river:
... and a method for knowing onto which edge a river (e1) flows from one tile (t1) to the next (t2):
... and the main call:
If not, you will only need a method for telling if two river edges on a tile are part of the same river:
Code:
bool sameRiver(Tile t, int e1, int e2)
{
//are e1 and e2 the same, or consecutive (necessarily connected)?
int dist = abs(e1-e2);
if (min(dist, 6-dist) < 2) return true;
//is there nothing but rivers between e1 and e2 clockwise?
bool allRiver = true;
for (int mid = (e1+1)%6;mid != e2;mid=(mid+1)%6)
if (!t.isRiver(mid))
{allRiver = false; break;}
if (allRiver) return true;
//if not, try the other way around
for (int mid = (e2+1)%6;mid != e1;mid=(mid+1)%6)
if (!t.isRiver(mid))
return false;
return true;
}... and a method for knowing onto which edge a river (e1) flows from one tile (t1) to the next (t2):
Code:
int riverEntryEdge(Tile t1, int e1, Tile t2)
{
int edgeToT2 = t1.edgeTo(t2);//<--hope you have something similar at hand
//is e1 the edge directly between t1 and t2?
if (e1 == edgeToT2)
return (e1+3)%6;
//if not, there are two possibilities left (on either side of the edge directly between t1 and t2)
if ((e1+1)%6 == edgeToT2 && t2.isRiver((e1+5)%6))
return (e1+5)%6;
if ((e1+5)%6 == edgeToT2 && t2.isRiver((e1+1)%6))
return (e1+1)%6;
return -1;
}... and the main call:
Code:
bool areConnectedByRiver(Tile a, Tile b, Tile c)
{
//for all river edges in a, for all river edges in c
for (int e1=0;e1<6;e1++)
if (a.isRiver(e1))
for (int e2=0;e2<6;e2++)
if (c.isRiver(e2))
{
//do e1 and e2 lead to tile b?
int eab = riverEntryEdge(a, e1, b);
if (eab < 0) continue;
int ecb = riverEntryEdge(c, e2, b);
if (ecb < 0) continue;
if (sameRiver(b, eab, ecb))
return true;
}
return false;
}whoward69
DLL Minion
A-B-F are not connect (at this level), but a more general river connection algorithm (which is where I'm heading) would detect them as connected as A-B-C and B-C-F are both connected
The general case is P1 is connected to Pn if the set of tuples (Pi, Pi+1, Pi+2) are all connected for i=1 to n-2
The really hard part is finding that set of tuples!
The general case is P1 is connected to Pn if the set of tuples (Pi, Pi+1, Pi+2) are all connected for i=1 to n-2
The really hard part is finding that set of tuples!
So much for my algos 
It seems like your better off just storing all the tiles in a set for each river, and then checking each set to see if it contains your three tiles simultaneously. Something with a fast lookup, like a hash set. That should cover just about any definition of river-connected.
It seems like your better off just storing all the tiles in a set for each river, and then checking each set to see if it contains your three tiles simultaneously. Something with a fast lookup, like a hash set. That should cover just about any definition of river-connected.
whoward69
DLL Minion
I'm rapidly coming to that same conclusion (cache it all) as (IGE excepted), unlike roads/rails, rivers don't change over the course of the game
whoward69
DLL Minion
ww2commander
Emperor
As always, can you elaborate more on this moment of insanity?
Whats it used for?
Whats it used for?
whoward69
DLL Minion
I can finally answer the question "Is there a river connection from plot A to plot B, and if so, what is it"
Although I've been working on and off on this code for so long now I've forgotten why I originally wanted to do this!
It's all in Lua. (With a couple of mods to the DLL to call events) you could use it to create a trait like "forms trade routes between cities via rivers", or to add the +1 gold from being next to a river back to a plot if there is trade along that section of river.
The code to highlight the plots is a variation of
Although I've been working on and off on this code for so long now I've forgotten why I originally wanted to do this!
It's all in Lua. (With a couple of mods to the DLL to call events) you could use it to create a trait like "forms trade routes between cities via rivers", or to add the +1 gold from being next to a river back to a plot if there is trade along that section of river.
The code to highlight the plots is a variation of
Code:
include("RiverConnections")
local gRiverManager = RiverManager:new()
local pPlots = gRiverManager:getRiverBankRoute(5, 4, 5, 1)
for _, pPlot in ipairs(pPlots) do
print(string.format("Plot: (%i, %i)", pPlot:GetX(), pPlot:GetY()))
end
whoward69
DLL Minion
Which misses the point of "if there is trade along that section of river"
Editing the XML adds the gold back to every tile next to a river, not just those along river edges between "trade hubs" (however you want to define those)
kaspergm
Deity
- Joined
- Aug 19, 2012
- Messages
- 5,829
That is something that should be able to create some interesting effects, like establishing city connections and trade routes via river, faster religion spread via rivers, gold on river tiles connecting cities, etc. A question with regards to the latter, in the screenshot it only highlights south bank of the river between Assur and Hit, and only west bank on the river between Assur and Carchemish. Is that significant, and is it random which side is highlighted? (For instance, if one wanted to add +1 Gold to only these tiles, would only one side of the river get the gold.)
Ekmek
on steam: ekmek_e
could this be used for an appian way wonder that connects cities with roads?
whoward69
DLL Minion
Short answer no and no. The banked followed depends on which side of the river the starting plot is on.
S3rgeus
Emperor
This is really interesting! How did you work out the connections in the end?
whoward69
DLL Minion
By ditching everything I'd done and starting from scratch! The question is not "are A, B and C connected by a river" (which is actually quite easy to answer), but "on what river segment(s) are plot A and plot D, and are those segments connected"
A river segment can have at most two upstream and two downstream segments, and traversing a river by segment is just a variation on a sparsely populated binary-tree walking algorithm.
The code caches all rivers at startup (and can be forced to re-cache if mods like IGE change the river system) which means the initial question of "are A and D connected by a river" can be answered as "are any river segments flowing around A and D part of the same river" and also gives the start and end segment for the river traversal algorithm
whoward69
DLL Minion
Similar threads
