Sea or Pond?

ID:1231671
 
Apr 9 2013, 12:40 am
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.
Apr 9 2013, 3:45 pm (Edited on Apr 10 2013, 12:27 am)
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.
Apr 9 2013, 11:11 pm
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.
Apr 9 2013, 11:55 pm
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.
Apr 10 2013, 12:26 am (Edited on Apr 10 2013, 1:48 am)
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.)

Apr 10 2013, 2:33 am
@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.
Apr 10 2013, 3:58 am
Just a minor pet peeve, but could you not stretch the art? It makes it hard to determine what I'm looking at.
Apr 10 2013, 5:46 am
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)




Apr 10 2013, 11:56 pm
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:



Apr 11 2013, 12:18 am
Good work. it's not an easy algorithm, but it's entirely useful.
Apr 11 2013, 7:57 am
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 ^_^
Apr 11 2013, 8:23 am
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).
Apr 11 2013, 8:35 am
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.
Apr 11 2013, 1:17 pm
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.
Apr 11 2013, 1:29 pm
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.
Apr 11 2013, 1:48 pm
Got it a little better now. I also applied the cleanup to this because the single pools were causing issues.
Apr 12 2013, 2:36 am
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.
Apr 12 2013, 5:35 am
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.
Apr 12 2013, 6:34 am
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 ^_^