ID:1231671
 
I'm currently working on a Survival type game that I've wanted to build for years and years now; ever since Lost upset me by not focussing on the intricacies of forming a new civilization.

Anyway, the entire map is completely randomly generated and so far I'm pretty happy with it. However, I'm not sure how to go about detecting land-locked water. Natural 'ponds' form very often, and I want to be able to detect them and change their attributes from Sea-like to fresh water.



Could anyone help suggest some cheap algorithms for detecting any water not connected to the largest body/sea? I've had some ideas but they all seem very expensive computationally.
The way that I usually do this is probably wrong and it's reasonably expensive but to get the ball rolling..

for(number of repeats) // Higher repeats = higher accuracy. O(r)

for(all water) // Do for all water on the map. O(w)

for(water in w.oview) // Count how much water is in the oview() O(1)

// Decide if it's a pond. (If there's 2 or less water in NORTH SOUTH EAST WEST it's a pond) O(1)
// Make dirt if it's a pond. O(1)


I believe it has a complexity of r * w except when you decide what you want r to be, which is around 3ish then you get 3 * w which is a complexity of O(n) which is reasonably low.

# Notes #

Turf's don't have an oview() function. You have to make one, I use for(get_step(listOfDirections[NORTH,SOUTH,EAST,WEST])).

Accuracy is there because sometimes by deleting one pool you create another. Therefore you can get closer and closer to taking out all the pools by running the main loop more times.
Thank you for helping to get the ball rolling. Firstly, I've found that "range()" works as a great replacement for view()/oview().

That's definitely a viable option, but I have a couple niggles with it. By basing it on oview() I'm going to lose a lot of the interesting coast line. Also, by looping through -all- water it's going to take a while and do a lot of unnecessary processing: I didn't explain before but the player view is huge (50x50) and from each coast there's water as far as the eye can see (by design).

That said, I'm still not sure how I'd do it differently.
Marching squares will help you find the perimeter of your landmass, while allowing you to begin processing the interiors only.

http://devblog.phillipspiess.com/2010/02/23/ better-know-an-algorithm-1-marching-squares/

Albeit, it might be easier to do a four-direction floodfill.
In response to Ease
Sorry man I totally messed that up. I think I pulled 3 or less out of my ass. What I 'meant..' to say was 2 or less and only from tiles which are at NORTH SOUTH EAST WEST.

If you make the water into dirt when you encounter 2 or less water in NORTH SOUTH EAST WEST. Then I believe you effectively solve these cases:

(And these cases will fill in most ponds and general gappyness without inflating your coasts tooo much.)

@Ter13; thank you for that perimeter algorithm, that's very intriguing. I suspect that'll be the way to do it in the end. I've had an attempt this morning before I had a look at this thread, and here was my general thought process:

  • Recursion should shave off a lot of the work.
  • Whilst laying out the dirt I'll maintain a 'topright' and 'bottomleft' turf, updating as required.
  • Then use these two turfs to make a bounding box.
  • Then use a recursive algorithm to grab a Sea turf from the bounding box, add it to a list of "connected" turfs (which at first instance is empty) - then grab all of it's neirbouring Sea turfs; add them to the list, and repeat.
  • If the list gets too big then assume it touches the actual Sea, and blank the list.


Here's the code that I made from this plan. It's done as a verb for testing purposes:

proc
connectedSeas(var/turf/Sea/center, var/list/innerTurfs,var/iter)
if(iter>=4)
return 0
var/list/connected = new/list()
innerTurfs -= center
connected += center
for(var/turf/Sea/adjs in orange(1, center))
if(innerTurfs.Find(adjs))
var/list/temp = connectedSeas(adjs, innerTurfs, ++iter)
if(temp!=0)
connected += temp
else
connected = 0
return 0
return connected

mob
verb
SeaToWater(a as num,b as num,c as num,d as num)
var/list/innerTurfs = new/list()
for(var/turf/Sea/s in block(locate(a, b, 1), locate(c+a, d+b, 1)))
innerTurfs+=s
var/obj/overlay/O = new(s)
var/turf/p = innerTurfs[1]

var/list/connected
for(var/turf/Sea/checker in innerTurfs)
connected = new/list()
connected = connectedSeas(checker, innerTurfs,1)
if(connected!=0)
if(connected.len<=6&&connected.len>=1)
for(var/turf/Sea/cSea in connected)
var/turf/Water/w = new(cSea)


But the results are most unexpected...





I should add that I've also coated all turfs that were processed with an overlay for testing purposes.
Just a minor pet peeve, but could you not stretch the art? It makes it hard to determine what I'm looking at.
Heh, those pictures are stretched. Each tile is 9x9 pixels. I've done some tinkering, and the peculiar rows of Water (solid light blue turfs) in the sea have vanished. It's still not doing what I expect though.

proc
connectedSeas(var/turf/Sea/center, var/list/innerTurfs,var/iter)
if(iter>=3)
return 0
var/list/connected = new/list()
innerTurfs -= center
connected += center
for(var/turf/Sea/adjs in orange(1, center))
if(innerTurfs.Find(adjs))
var/list/temp = connectedSeas(adjs, innerTurfs, ++iter)
if(temp!=0)
connected += temp
else
connected = 0
return 0
return connected

mob
verb
SeaToWater(a as num,b as num,c as num,d as num)
var/list/innerTurfs = new/list()
for(var/turf/Sea/s in block(locate(a, b, 1), locate(c+a, d+b, 1)))
innerTurfs+=s
var/obj/overlay/O = new(s)

var/list/connected
for(var/turf/Sea/checker in innerTurfs)
connected = new/list()
connected = connectedSeas(checker, innerTurfs,1)
if(connected!=0)
if(connected.len<=6&&connected.len>=1)
for(var/turf/Sea/cSea in connected)
var/turf/Water/w = new(cSea)




Okay, trying it Ter13's way now. This has actually been relatively difficult, and is still not entirely complete, but it's coming along great. If I can perfect this I might even make a library from it as I'm sure it could help with a lot of other applications.

Here's a picture of the boundary finder in action, as it slowly (for demonstration purposes) circumnavigates the island anti-clockwise:



Good work. it's not an easy algorithm, but it's entirely useful.
Got it working like a champ. The finding the boundary bit, at least. Now I've got a list of every turf the top right square of the 2x2 grid touches, and if needed I can add each turf every square in the grid touches, but I'm not exactly sure how to use this list to get a list of all the turfs within the boundary, if you know what I mean? I'm finding it hard to explain. I've got some rudimentary (i.e., stupid and clumsy) ideas for how to do it, but suggestions from greater minds would be appreciated ^_^
I'm not exactly an expert at this, but as far as finding the internal tiles of the boundaries, wouldn't a breadth-first search be ideal?

Store all of the boundary tiles in a list, then choose a tile inside the boundaries - start from that tile and expand outwards until you can't expand anymore (Stop when you hit a boundary tile).
In response to Albro1
Albro1 wrote:
I'm not exactly an expert at this, but as far as finding the internal tiles of the boundaries, wouldn't a breadth-first search be ideal?

Store all of the boundary tiles in a list, then choose a tile inside the boundaries - start from that tile and expand outwards until you can't expand anymore (Stop when you hit a boundary tile).

Indeed, once you have found the boundary, you then have to do something of a reverse floodfill FROM the boundary to locate the ocean tiles.

To make it more efficient, you could store the maxx,maxy, coordinates of the border, that way you are only performing the floodfill out to the maximum boundary of the land. Then you can get your square within a block(minx,miny,z,maxx,maxy,z), subtract all ocean tiles that you floodfilled, and you just found yourself a list of all interior tiles.

To make this more efficient, you may wish to store the land you have generated in a list already, and use binary list operators to speed up the list manipulation.

Just subtract all land and external ocean after the floodfill, and you have a list of all interior water. Run through the list and replace with fresh water.
I decided to take a whack at that marching squares algorithm. It's not as easy as I thought it was going to be. This is what I have so far: (Note I haven't applied my cleanup procedure to the small pools in the island)



Here's my rather messy code for this:
proc
get_perimeter(z=1)
var
turf/bottom_right = find_start_point(z)
turf/bottom_left = locate(bottom_right.x-1, bottom_right.y, bottom_right.z)
turf/top_right = locate(bottom_right.x, bottom_right.y+1, bottom_right.z)
turf/top_left = locate(bottom_right.x-1, bottom_right.y+1, bottom_right.z)
turf/last_step
turf/next_step = bottom_right
list/movement = list("1" = NORTH, \
"2" = EAST, \
"4" = WEST, \
"8" = SOUTH, \
"3" = EAST, \
"10" = SOUTH, \
"12" = WEST, \
"5" = NORTH, \
"7" = EAST, \
"11" = SOUTH, \
"14" = WEST, \
"13" = NORTH, \
"9" = NORTH, \
"6" = WEST)
list/perim_turfs = list()
state = 0
bottom_right.icon_state = "perim"
while(!(next_step in perim_turfs))
perim_turfs.Add(next_step)
bottom_right = next_step
bottom_left = get_step(bottom_right, WEST)
top_right = get_step(bottom_right, NORTH)
top_left = get_step(bottom_right, NORTHWEST)
state = 0
last_step = next_step
if(is_tile_solid(top_left))
state |= 1
if(is_tile_solid(top_right))
state |= 2
if(is_tile_solid(bottom_left))
state |= 4
if(is_tile_solid(bottom_right))
state |= 8
var/d = 0
if("[state]" in movement)
d = movement["[state]"]
if(d)
if(isnull(get_step(bottom_right, d)) || get_step(bottom_right, d) in perim_turfs)
if(d == SOUTH)
d = WEST
else if(d == NORTH)
d = EAST
else if(d == WEST)
d = NORTH
else if(d == EAST)
d = SOUTH
next_step = get_step(bottom_right, d)
if(state == 6)
if(get_dir(next_step, last_step) == NORTH)
next_step = get_step(bottom_right, WEST)

if(state == 9)
if(get_dir(next_step, last_step) == EAST)
next_step = get_step(bottom_right, NORTH)

next_step.icon_state = "perim"
sleep(1)


find_start_point(z=1)
var
x = 1
y = 1
turf/t

for(y=1 to world.maxy)
for(x=1 to world.maxx)
t = locate(x,y,z)
if(is_tile_solid(t))
break
if(is_tile_solid(t))
break
return t

is_tile_solid(turf/t)
if(istype(t, /turf/Land)) return 1
return 0


I just call get_perimeter(z) once everything is generated.

One of my main problems is when the generation makes the land go to the edge of the map, the marching squares bug up.
Either you need to account for the edge of your map, or set your cellular automata to weight probability of spreading to zero as it approaches the map edge.
Got it a little better now. I also applied the cleanup to this because the single pools were causing issues.
Haha, your code is lot prettier than mine, Albro! My method is finally complete, and working in full with only one small bug. That said, my floodfill method seems really inelegant to me, and I suspect it's 10-100 fold more computationally intensive than it needs to be.

My bug is in finding the start point of the boundary. With tiny little islands surrounding my main island I can't do the "from x=1 y=1 inwards" approach, as I could easily hit one of these islands, so at the moment I start from the centre of the island (which is always 100,100,1 in my program) and go North until I hit a turf of Sea that has more than 4 other Sea turfs within its oview(2). This isn't perfect, but it's working 19 times out of 20 for me.

I'm thinking of making it continue North until it hits a turf of Sea which has every turf in its oview(2) as Sea as well, and once that is found march back South until the coast is found.

Here's my current code:
mob
verb
Boundary()
var/list/Boundary = fillBoundaryList()
world<<"[bottomLeft.x] [bottomLeft.y] & [topRight.x] [topRight.y] && [Boundary.len]"

var/list/incTurfs = block(bottomLeft,topRight)
world<<"inc=[incTurfs.len]"
var/list/excTurfs = new/list()

sleep(25)

for(var/turf/origin in Boundary)
fillSea(origin, excTurfs, incTurfs)

incTurfs -= excTurfs
for(var/turf/Sea/T in incTurfs)
new /turf/Water/ (T)
world<<"done inc=[incTurfs.len] exc=[excTurfs.len]"

proc

fillBoundaryList(var/turf/origin)
var/list/Boundary = new/list()
if(!origin)
origin = locate(100,100,1)
origin=findBoundary(origin)
var/turf/current = origin
current=walkBoundary(current)
Boundary+=current
while(current!=origin)
current=walkBoundary(current)

if(current.x<bottomLeft.x)
bottomLeft=locate(current.x,bottomLeft.y,1)
if(current.y<=bottomLeft.y)
bottomLeft=locate(bottomLeft.x,current.y,1)
if(current.x>=topRight.x)
topRight=locate(current.x,topRight.y,1)
if(current.y>=topRight.y)
topRight=locate(topRight.x,current.y,1)

Boundary+=current
if(!current)
break

// for(var/i=1; i<=Boundary.len; i++)
// world<<Boundary[i]

return Boundary



findBoundary(var/turf/origin)
while(origin.type != /turf/Sea)
origin=get_step(origin,NORTH)
var/list/temp = new()
for(var/turf/Sea/s in oview(2,origin))
temp+=s
if(temp.len<=4)
origin=get_step(origin,NORTH)
origin=findBoundary(origin)
return origin


walkBoundary(var/turf/origin, bType) //origin is starting point, bType is the Boundary Type
if(!bType)
bType = /turf/Sea

if(!origin.step)
origin.step=EAST


var/turf/TOPRITE=origin
var/turf/TOPLEFT=get_step(TOPRITE,WEST)
var/turf/BOTLEFT=get_step(TOPLEFT,SOUTH)
var/turf/BOTRITE=get_step(BOTLEFT,EAST)

/* var/obj/overlay/O = new (TOPLEFT) // For demonstration only
O.pixel_x=rand(-1,1)
var/obj/overlay1/O1 = new (TOPRITE)
O1.pixel_x=rand(-1,1)
var/obj/overlay2/O2 = new (BOTLEFT)
O2.pixel_x=rand(-1,1)
var/obj/overlay3/O3 = new (BOTRITE)
O3.pixel_x=rand(-1,1) */


if(TOPLEFT.type==bType&&\
TOPRITE.type==bType&&\
BOTLEFT.type==bType&&\
BOTRITE.type==bType) //1111
origin=get_step(origin,EAST)
origin.step=EAST
else if(TOPLEFT.type==bType&&\
TOPRITE.type!=bType&&\
BOTLEFT.type==bType&&\
BOTRITE.type==bType) //1011
origin=get_step(origin,EAST)
origin.step=EAST
else if(TOPLEFT.type!=bType&&\
TOPRITE.type!=bType&&\
BOTLEFT.type==bType&&\
BOTRITE.type==bType) //0011
origin=get_step(origin,EAST)
origin.step=EAST
else if(TOPLEFT.type!=bType&&\
TOPRITE.type!=bType&&\
BOTLEFT.type!=bType&&\
BOTRITE.type==bType) //0001
origin=get_step(origin,EAST)
origin.step=EAST

else if(TOPLEFT.type==bType&&\
TOPRITE.type!=bType&&\
BOTLEFT.type==bType&&\
BOTRITE.type!=bType) //1010
origin=get_step(origin,SOUTH)
origin.step=SOUTH
else if(TOPLEFT.type==bType&&\
TOPRITE.type==bType&&\
BOTLEFT.type==bType&&\
BOTRITE.type!=bType) //1110
origin=get_step(origin,SOUTH)
origin.step=SOUTH
else if(TOPLEFT.type!=bType&&\
TOPRITE.type!=bType&&\
BOTLEFT.type==bType&&\
BOTRITE.type!=bType) //0010
origin=get_step(origin,SOUTH)
origin.step=SOUTH

else if(TOPLEFT.type==bType&&\
TOPRITE.type==bType&&\
BOTLEFT.type!=bType&&\
BOTRITE.type==bType) //1101
origin=get_step(origin,WEST)
origin.step=WEST
else if(TOPLEFT.type==bType&&\
TOPRITE.type==bType&&\
BOTLEFT.type!=bType&&\
BOTRITE.type!=bType) //1100
origin=get_step(origin,WEST)
origin.step=WEST
else if(TOPLEFT.type==bType&&\
TOPRITE.type!=bType&&\
BOTLEFT.type!=bType&&\
BOTRITE.type!=bType) //1000
origin=get_step(origin,WEST)
origin.step=WEST
else if(TOPLEFT.type==bType&&\
TOPRITE.type!=bType&&\
BOTLEFT.type!=bType&&\
BOTRITE.type==bType) //1001
if(origin.step==SOUTH)
origin=get_step(origin,EAST)
origin.step=EAST
else
origin=get_step(origin,WEST)
origin.step=WEST

else if(TOPLEFT.type!=bType&&\
TOPRITE.type==bType&&\
BOTLEFT.type==bType&&\
BOTRITE.type==bType) //0111
origin=get_step(origin,NORTH)
origin.step=NORTH
else if(TOPLEFT.type!=bType&&\
TOPRITE.type==bType&&\
BOTLEFT.type==bType&&\
BOTRITE.type!=bType) //0110
if(origin.step==EAST)
origin=get_step(origin,NORTH)
origin.step=NORTH
else
origin=get_step(origin,SOUTH)
origin.step=SOUTH

else if(TOPLEFT.type!=bType&&\
TOPRITE.type==bType&&\
BOTLEFT.type!=bType&&\
BOTRITE.type!=bType) //0100
origin=get_step(origin,NORTH)
origin.step=NORTH
else if(TOPLEFT.type!=bType&&\
TOPRITE.type==bType&&\
BOTLEFT.type!=bType&&\
BOTRITE.type==bType) //0101
origin=get_step(origin,NORTH)
origin.step=NORTH


else if(TOPLEFT.type!=bType&&\
TOPRITE.type!=bType&&\
BOTLEFT.type!=bType&&\
BOTRITE.type!=bType) //0000
origin=null

return origin

fillSea(var/turf/origin, var/list/excTurfs, var/list/incTurfs)
var/turf/current = origin
if(incTurfs.Find(current)&&!excTurfs.Find(current))
excTurfs+=current
for(var/turf/Sea/s in oview(1,current))
if(incTurfs.Find(current)&&!excTurfs.Find(s))
fillSea(s, excTurfs, incTurfs)
return excTurfs
else
return


As you can see there's a lot of room for improvement.
If you use my method of finding the start point(going from x=1 to world.maxx, then y+1), you should be able to not only find the main island but also all of the smaller ones. Just change the starting y to the y value of the topmost turfs (you can do this by storing all of your perimeter turfs in a list and looping to find the one with the highest y value) and setting the x value to the rightmost turf (same concept, highest x value) and starting the search again. This way you won't hit the same island again.
Sorry for not providing any sort of code examples but I'm on my phone.
I'm on my phone too ^_^ That sounds like a great idea Albro, I'll implement it when I get home on Monday. If I ever release this game you and Ter will receive significant credit ^_^