Algorithm to detect enclosed space?

Page: 1 2 3
ID:1333207
 
Jul 24 2013, 2:56 am
(See the best response by Jp.)
I am looking to create an algorithm that can take:

- a passed-in defined block (a set of turfs, within a square)
- a starting location inside that range of turfs
- a list of turf types to look at which is considered dense or blocking, or a variable name to access (ie: "density") and a value to check for (ie: 1)

It should return if the space around the starting location is completely enclosed in by the passed in list of turf types (or if all the tiles enclosing that share the same variable value). Simple example would be checking to see if player is currently in a room he can't escape out of.

Some use examples of how I would like to be able to use it:
IsEnclosed(block(), locate(), list(/turf/wall, /turf/heavy_wall))
//checks for enclosure around locate() within range block()... returns 1 if enclosed by any combination of /turf/wall and /turf/heavy_wall

IsEnclosed(block(), locate(), /turf/wall)
//checks for enclosure around locate() within range block()... returns 1 if enclosed by /turf/wall

IsEnclosed(block(), locate(), "density", 1)
//checks for enclosure around locate() within range block()... returns 1 if enclosed by tiles with variable density equal to 1


Most of the variable checking bloat I could easily take care of... the part I don't know where to begin with is the logic of knowing that the enclosure has a break in it or not... basically the meat of the algorithm! Where would you begin?
Jul 24 2013, 3:00 am
And to be more specific, we're talking about a top-down scenario and diagonal moves are allowed in my case:


##.###
#.#..#
#..X.#
######


That ^ should return 0 where . is a floor, # is a wall, and X is the starting location


######
#....#
#..X.#
######


That ^ should return 1
Jul 24 2013, 4:30 am
Check for a Wall within block(), and make it the starting point. Then use a proc that checks the cardinal directions for another wall. If there isn't one, it's not enclosed. Keep going until you loop around to the inital wall again. If you do, it's enclosed.
Jul 24 2013, 4:35 am
In response to Danny Roe
Decent starting idea! What if block passed in is pretty large and contains a lot of rooms? I'm already thinking you could search for pieces closest to starting location as an optimization, regardless of the block's size. The block size is more of a size cap than it is a hint even though it does provide the "area" to look in...

What about T's and forks?


........#..
..#.....#..
.#####..#..
..#..######
..#X.#..#..
..####..#..
...........


Problem here is, you'd spend a lot of time iterating through those long lines that don't lead anywhere.
Jul 24 2013, 4:51 am
I think working your way out from the Location until you find a Wall will lead you to the enclosing Wall of the Location. If it turns out that it isn't enclosed though, you should check for Walls further out to see if they are enclosed.
..........
.########.
.#......#.
.#.#..#.#.
.#.#X.#.#.
.#.####.#.
.#......#.
.########.

As for T's and Forks, the best thing I can think of would be recursive backtracking. As you backtrack, eliminate said Wall from the Enclosure list. If you backtrack to the initial block, it isn't enclosed.

The point of the Enclosure list would be to later check the lowest and highest x/y values to ensure that it does indeed enclose the Location. Otherwise this would say it is enclosed:
........
.######.
.#....#.
.#..###.
.####X..
........
Jul 24 2013, 12:43 pm (Edited on Jul 25 2013, 5:59 am)
Best response
Alternately, flood-fill and see if you reach the outside.

var/list/next = list(start)
var/list/processed = list()

while (next.len)
    var/turf/t = next[1]
    if (!(t in block)) return FALSE // not enclosed
    for (var/turf/t2 in range(t, 1)) if (!(t2 in next) && !(t2 in processed)) next += t2
    processed += t
    next -= t

return TRUE // enclosed


How important is performance? Obviously that can be done faster, but this is much /easier/ than screwing around with loop detection on walls.

Also, careful of this case:

.....
..###
.x#.#
..#.#
..###


Just because there /is/ an enclosure doesn't mean that the enclosure /contains the start point/.
Jul 25 2013, 1:45 am (Edited on Jul 25 2013, 1:55 am)
Nice! Thanks for the insight!

Here's what I came up with:

proc/trange(dist, atom/center)
    if(!isturf(center) && istype(center, /atom))
        center = center.loc
        
    return block(locate(center.x - dist, center.y - dist, center.z), locate(center.x + dist, center.y + dist, center.z))

proc/IsEnclosed(list/block, turf/start, wall, val)
    if(!block || !start || !wall)
        CRASH("Null argument in IsEnclosed call: IsEnclosed([block], [start], [wall], [val])")
    
    if(!(start in block)) return 0 //invalid request, start point isn't in turfs
    
    var/list/next = list(start) //start search from start point
    
    var/list/processed = list() //holds tiles that have been processed
    
    while(next.len)
    
        var/turf/t = next[1] //select next tile to search
        
        if(!(t in block)) return 0 //if this tile isn't in the given search area, not enclosed
        
        for(var/turf/t2 in trange(1, t)) //for each tile around our next tile
        
            if(!(t2 in next) && !(t2 in processed)) //this tile isn't next and hasn't been processed
            
                if(istext(wall)) //wall is text, like a variable name "density"
                    if(t2.vars[wall] != val) //any turf with a value not equal to val should be checked next
                        next += t2
                        
                else if(istype(wall, /list)) //wall is a list of turf types
                    if(!(t2.type in wall)) //any turf that isn't one of these turf types should be checked next
                        next += t2
                        
                else if(!istype(t2, wall)) //wall is a type path, anything that isn't this type should be checked next
                    next += t2
                    
        processed += t
        next -= t
        
    return 1

mob/verb/Trapped_Type()
    if(IsEnclosed(view(), src.loc, /turf/wall))
        world << "Yes, you are trapped, mate!"
    else
        world << "Nope! You aren't trapped!"

mob/verb/Trapped_List()
    if(IsEnclosed(view(), src.loc, list(/turf/tree, /turf/wall)))
        world << "Yes, you are trapped, mate!"
    else
        world << "Nope! You aren't trapped!"
        
mob/verb/Trapped_Variable()
    if(IsEnclosed(view(), src.loc, "density", 1))
        world << "Yes, you are trapped, mate!"
    else
        world << "Nope! You aren't trapped!"
Jul 25 2013, 3:07 am (Edited on Jul 25 2013, 5:51 am)
Now I've begun optimization phase...

Turns out .Add / .Remove / .Find is much faster than += -= and (x in y)

Edit: They are faster in this situation, not sure why.
Jul 25 2013, 4:44 am
In response to FIREking
FIREking wrote:
Now I've begun optimization phase...

Turns out .Add / .Remove / .Find is much faster than += -= and (x in y)

No it isn't, no it isn't at all. Add() is much slower than list += element.

Not sure about the others but I'm sure about that one.
Jul 25 2013, 4:50 am
+= returns a whole new list

.Add() doesn't

Also, it doesn't matter how sure you are or aren't, I tested both procs in the profiler and the new one is faster. In the grand scheme of my project, I couldn't care less why it is faster though.
Jul 25 2013, 4:53 am
This is what came up using Tobba's disassembler.
var/list/L = list()
var/obj/Object = new

proc/Add1()
    L += Object

proc/Add2()
    L.Add(Object)


/proc/Add1:
    0: get global<113>
    3: addset global<58>
    6: ret
/proc/Add2:
    0: get global<113>
    3: call global<58>[Add] 1
    10: pop
    11: ret
Jul 25 2013, 5:06 am
FIREking wrote:

Profile results (total time)
Proc Name Self CPU Total CPU Real Time Calls
------------------------------ --------- --------- --------- ---------
/mob/verb/test 0.010 0.878 0.878 10
/proc/test2 0.465 0.465 0.465 10
/proc/test1 0.403 0.403 0.403 10
/mob/player/proc/update_screen 0.000 0.000 0.000 1041
/mob/player/proc/movement 0.000 0.000 0.000 1041


test1 is +=
test2 is Add()

I was going off of something I was told so it never hurts to test it yourself.

These results may be different if what you're adding is an actual object, or a list.

That proves exactly what I said? Add() is slower...
Jul 25 2013, 5:10 am (Edited on Jul 25 2013, 5:21 am)
Turns out you get some pretty weird results in these following cases:

if(!list.Find(something)) //test1

if(list.Find(something)) //test2

if(!(x in list)) //test 3

if(x in list) //test 4



                           Profile results (total time)
Proc Name                          Self CPU    Total CPU    Real Time        Calls
------------------------------    ---------    ---------    ---------    ---------
/mob/verb/test                        0.001        0.984        0.984            1
/proc/test1                           0.308        0.308        0.308           10
/proc/test3                           0.249        0.249        0.249           10
/proc/test2                           0.241        0.241        0.241           10
/proc/test4                           0.185        0.185        0.185           10
/mob/player/proc/update_screen        0.000        0.000        0.000           57
/mob/player/proc/movement             0.000        0.000        0.000           57
Jul 25 2013, 5:10 am
In response to Rushnut
I don't think you even read my post...

So I'll post it again with explanations:

test1 is +=
test2 is Add()

I was going off of something I was told so it never hurts to test it yourself.

This is basically me admitting that in the test results what you said remains true, but that still does not explain why my optimized version of the procedure is faster.

These results may be different if what you're adding is an actual object, or a list.

This means if you try other inputs you may get different results.
Jul 25 2013, 5:20 am
In response to Rushnut
Ok well here's the proof guys, no explanation as to why:

proc/trange(dist, atom/center)
    if(!isturf(center) && istype(center, /atom))
        center = center.loc

    return block(locate(center.x - dist, center.y - dist, center.z), locate(center.x + dist, center.y + dist, center.z))

proc/trange_(dist, turf/center)
    return block(locate(center.x - dist, center.y - dist, center.z), locate(center.x + dist, center.y + dist, center.z))

proc/IsEnclosed_1(list/search, turf/start, wall, val)
    if(!search || !start || !wall)
        CRASH("Null argument in IsEnclosed call: IsEnclosed([search], [start], [wall], [val])")

    if(!(start in search)) return 0 //invalid request, start point isn't in turfs

    var/list/next = list(start) //start search from start point
    var/list/processed = list() //holds tiles that have been processed

    var/turf/t
    var/turf/t2
    while(next.len)
        t = next[1]

        if(!(t in search)) return 0

        for(t2 in trange_(1, t))

            if(!(t2 in next) && !(t2 in processed))

                if(istext(wall))
                    if(t2.vars[wall] != val)
                        next += t2

                else if(istype(wall, /list))
                    if(!(t2.type in wall))
                        next += t2

                else if(!istype(t2, wall))
                    next += t2

        processed += t
        next -= t

    return 1

proc/IsEnclosed_2(list/search, turf/start, wall, val)
    if(!search || !start || !wall)
        CRASH("Null argument in IsEnclosed call: IsEnclosed([search], [start], [wall], [val])")

    if(!search.Find(start)) return 0 //invalid request, start point isn't in turfs

    var/list/next = list(start) //start search from start point
    var/list/processed = list() //holds tiles that have been processed

    var/turf/t
    var/turf/t2
    while(next.len)
        t = next[1]

        if(!search.Find(t)) return 0

        for(t2 in trange_(1, t))

            if(!next.Find(t2) && !processed.Find(t2))

                if(istext(wall))
                    if(t2.vars[wall] != val)
                        next.Add(t2)

                else if(istype(wall, /list))
                    if(!wall:Find(t2.type))
                        next.Add(t2)

                else if(!istype(t2, wall))
                    next.Add(t2)

        processed.Add(t)
        next.Remove(t)

    return 1

mob/verb/test()
    for(var/i = 1 to 100)
        IsEnclosed_1(view(), src.loc, "density", 1)

    for(var/i = 1 to 100)
        IsEnclosed_2(view(), src.loc, "density", 1)


results
                           Profile results (total time)
Proc Name                          Self CPU    Total CPU    Real Time        Calls
------------------------------    ---------    ---------    ---------    ---------
/mob/verb/test                        0.021        0.714        0.714            1
/proc/IsEnclosed_1                    0.420        0.448        0.448          100
/proc/IsEnclosed_2                    0.219        0.245        0.245          100
/proc/trange_                         0.054        0.056        0.060        37600
/mob/player/proc/update_screen        0.000        0.000        0.000           99
/mob/player/proc/movement             0.000        0.000        0.000           99
Jul 25 2013, 5:41 am
Here's an even faster third one which cuts down on how many checks are being made against the wall argument by splitting up the algorithm into three forks

proc/IsEnclosed_3(list/search, turf/start, wall, val)
    #ifdef CRASHING
    if(!search || !start || !wall)
        CRASH("Null argument in IsEnclosed call: IsEnclosed([search], [start], [wall], [val])")
    #endif
    
    if(!search.Find(start)) return 0 //invalid request, start point isn't in turfs
    
    var/list/next = list(start) //start search from start point
    var/list/processed = list() //holds tiles that have been processed

    var/turf/t
    var/turf/t2
    
    if(istext(wall))

        while(next.len)
            t = next[1]
    
            if(!search.Find(t)) return 0
    
            for(t2 in trange_(1, t))
    
                if(!next.Find(t2) && !processed.Find(t2))
    
                    if(t2.vars[wall] != val)
                        next.Add(t2)
                        
            processed.Add(t)
            next.Remove(t)
            
        return 1
            
    else if(istype(wall, /list))
        while(next.len)
            t = next[1]
    
            if(!search.Find(t)) return 0
    
            for(t2 in trange_(1, t))
    
                if(!next.Find(t2) && !processed.Find(t2))
    
                    if(!wall:Find(t2.type))
                        next.Add(t2)
                        
            processed.Add(t)
            next.Remove(t)
            
        return 1
            
    else
        while(next.len)
            t = next[1]
    
            if(!search.Find(t)) return 0
    
            for(t2 in trange_(1, t))
    
                if(!next.Find(t2) && !processed.Find(t2))
    
                    if(!istype(t2, wall))
                        next += t2
                        
            processed.Add(t)
            next.Remove(t)

        return 1


Results
                           Profile results (total time)
Proc Name                          Self CPU    Total CPU    Real Time        Calls
------------------------------    ---------    ---------    ---------    ---------
/mob/verb/test                        0.074        3.271        3.271            3
/proc/IsEnclosed_1                    1.464        1.543        1.543          300
/proc/IsEnclosed_2                    0.745        0.837        0.837          300
/proc/IsEnclosed_3                    0.727        0.817        0.817          300
/proc/trange_                         0.261        0.267        0.288       199800
/mob/player/proc/update_screen        0.000        0.000        0.000          100
/mob/player/proc/movement             0.000        0.000        0.000          100
Jul 25 2013, 5:46 am
Gained more speed by changing trange_ from a proc to a define macro

#define trange_(dist, center) block(locate(center.x - dist, center.y - dist, center.z), locate(center.x + dist, center.y + dist, center.z))
Jul 25 2013, 5:53 am
I guess ignorantly disregarding what I say, telling me you don't care for what I say, and then still acting high and mighty when you're wrong is common practice now adays.

Whatever.
Jul 25 2013, 5:59 am
I think you're reading a bit too far into what I'm saying and making assumptions. I don't think either of us is high and mighty because there's a discrepancy at all and because we're all simply trying to reach a most efficient goal line. Its easy for passion to come into play, but at the end of the day its a all 1's and 0's mate, black or white!

That said, I'm just trying to find the fastest thing. I only care about the performance of the proc itself which is why I made the post on this forum. Outside of this post, and this forum, the proc doesn't do anything for you or me or our lives so lets not get too heated here. We're simply discussing a really fast way of detecting enclosure.

Why IsEnclosed_3 is faster than the others, I have no idea (it uses .Add, .Remove, .Find) but in all reality it doesn't matter unless the answer helps us arrive at an even faster version.

If you have any information about how to get anything faster please let me know. No hard feelings, friend.
Jul 25 2013, 6:02 am
It's a microoptimisation, anyway, it' barely relevant.

Although I'm not sure you had enough data to conclude either way, Fireking. Good to see that you've got a functioning bit of code.
Page: 1 2 3