Keeping Things Together

ID:151915
 
Oct 3 2008, 7:42 pm
Suppose you have a clump of objects. You can create new objects anywhere that is next to an existing object in any cardinal direction. You should also be able to remove objects. The question is, how can you restrict which objects the player can remove so that they aren't able to create more than one clump?

Is it even possible?
Oct 3 2008, 7:57 pm
Foomer wrote:
Suppose you have a clump of objects. You can create new objects anywhere that is next to an existing object in any cardinal direction. You should also be able to remove objects. The question is, how can you restrict which objects the player can remove so that they aren't able to create more than one clump?

Is it even possible?

Yes, it's possible. In Goop I worked out how to do this, but when I remade the game (in its early stages only) I discovered the mathematical term for this and an algorithm to help me find which nodes I could not remove safely.

Essentially this boils down to a graph problem, where each object is bound to the object immediately adjacent in any cardinal direction. You need to look for the articulation points, nodes which cannot be removed from the graph without splitting it into two or more graphs. At some point when my brain isn't fuzzy I'll see if I can dig up the algorithm I used.

Lummox JR
Oct 4 2008, 5:12 am
You could probably use a path-finding algorithm. Remove the point. Loop through the objects adjacent to that spot and find a path from each one of them to the rest. If they are still connected (even if by a long route going elsewhere) then the entire grouping should still be a single mass. If it's still one mass, modify the map to reflect the change, if not, add the point back to the list.

To reduce overhead, before you run the path-finding algorithm on every single object adjacent to the point in question, you can group just the adjacent objects together by themselves. If they are all connected to each other, disregarding the rest of the mass, you don't have to run the path finding algorithm on the entire thing. This could reduce the number of times you have to run through the path-finding function a lot: for example, if the spot selected is completely surrounded, then you know that it's safe to remove, instead of running through a path-finder 8 times. If the point is surrounded by 2 groups of 3 objects each (such as objects to the east and north/south east and another grouping of three to the west and north/south west), you run the path-finder twice instead of 6 times.

Here's how I would probably implement something like that. I'm just going to quickly type up the general idea I would use as an example, so it will probably have a bunch of bugs and typos.
// returns 1 if there's 1 group of objects, 0 if 0 groups
//   or 2 if more than 1 group of objects would result
proc/checkConnection(turf/origin)
    var/list
        subGroups[0]
        subGroup[0]
    var
        dir = getFirst(origin)
        cutoffDir

    // if 0 or 8 adjacent tiles are occupied, as decided
    // by getFirst(), no need to continue; we have the answer
    if(dir == 0 || dir == -1)
        return abs(dir)

    cutoffDir = get_dir(origin, subGroup[1])

    addAdjacent(origin, dir, subGroup)
    subGroups += subGroup
    dir = get_dir(origin, subGroup[subGroup.len])
    dir = turn(dir, 90)

    subGroup = new
    while(dir != cutoffDir)
        var/obj/object/O = locate() in get_step(origin, dir)
        while(!O && dir != cutoffDir)
            dir = turn(dir, 45)
            O = locate() in get_step(origin, dir)
        if(dir == cutoffDir)
            return subGroups

        addAdjacent(origin, dir, subGroup)
        subGroups += subGroup

    var
        index1; index2
        group1; group2
        obj/object
            a; b

    for(index1 = 1 to subGroups.len-1)
        group1 = subGroups[index1]
        a = group1[1]
        for(index2 = index1+1 to subGroups.len)
            group2 = subGroups[index2]
            b = groups2[1]

            if(!pathFind(a, b))
                return 2
    return 1

proc/addAdjacent(turf/origin, direction, list/L)
    var/obj/object/O = locate() in get_step(origin, direction)
    if(!O) return
    L.add(O)

    addAdjacent(origin, turn(direction, 45), L)

// returns direction to a "counter-clockwisemost" part of a group, -1 if all 8 adjacent tiles are occupied, 0 if none are
proc/getFirst(turf/origin)
    var/dir = NORTH
    var/obj/object/O = locate() in get_step(origin, dir)

    if(O)
        // go backwards to find the first one.
        dir = turn(dir, -45)
        while(dir != NORTH)
            O = locate() in get_step(origin, dir)
            if(!O) return turn(dir, 45)
            dir = turn(dir, -45)
        return -1

    dir = turn(dir, 45)
    while(dir != NORTH)
        O = locate() in get_step(origin, dir)
        if(O) return dir
        dir = turn(dir, 45)
    return 0

And, obviously, if you have abstract objects instead of physical objects tiled on a map, you can utilize whatever method you have connecting the objects. And even if you're using the map but have larger masses of areas instead of a single tile you want to test for, you can split the areas up into units.
Oct 4 2008, 10:20 am
In response to Lummox JR
Lummox JR wrote:
Essentially this boils down to a graph problem, where each object is bound to the object immediately adjacent in any cardinal direction. You need to look for the articulation points, nodes which cannot be removed from the graph without splitting it into two or more graphs. At some point when my brain isn't fuzzy I'll see if I can dig up the algorithm I used.

Something like this? http://www.ibluemojo.com/school/articul_algorithm.html
Oct 4 2008, 12:28 pm
In response to Loduwijk
And if you mass happens to be a big fat donut with only two tiles on each side connecting either sides of the donut? You'd pretty much have to check each tile to determine if its still connected, and that seems like an awfully intensive approach.
Oct 5 2008, 4:08 am
In response to Foomer
Foomer wrote:
And if you mass happens to be a big fat donut with only two tiles on each side connecting either sides of the donut?

If I understand what you're saying properly, that would not require any calls to the path-finding algorithm at all, as the initial check to see what's directly around the point in question would tell you that it's still one mass.

At the very most, this algorithm would only ever require 4 calls to a path-finding algorithm per removed point; that is worst-case scenario and shouldn't happen often. Best-case scenario is that you won't have to call it at all, which should probably happen most of the time.
Oct 5 2008, 12:49 pm
In response to Foomer
Yeah, you're right Foomer; that's one of the bounding examples of the algorithm. Thankfully, BFS (http://en.wikipedia.org/wiki/Breadth-first_search) is a pretty quick algorithm (compared to depth-first.) And, it will always return the shortest path to the goal. (Forgive me if I've played Cpt. Obvious.)

I couldn't tell if the code above was already implementing it. (I don't read other people's code very well.) But if you are/will be using BFS, try to look for a way to cut down the number of times you have to run it per removal.

E.g. If BFS connected north and south by the east tile, then east has a path with north and south, so you only need to check E-W, W-S, W-N paths... saves 2 runs.

So, I think you should be okay, unless you're working on "Donut Eater" or some other special case. (Speaking of, what are the details of the application? If I may know.)

Hope I've helped.
Oct 5 2008, 2:05 pm
Code like this seems to work reasonably well and reasonably quickly (reasonably meaning I've tested it a bit and haven't found a situation where it keels over or takes a lot of time, for chains and loops of up to 100 objects:
mob/var
    list
        myClump = list()

obj
    clumpable
        Click()
            var/list/clump = usr.myClump.Copy()
            clump -= src
            var/obj/clumpable/c = pick(clump)
            var/list/cclump = c.checkClump(null,list(src))
            
            cclump -= src

            if(compareLists(cclump,clump)) 
                usr.myClump -= src
                del(src)
            else usr << "You cannot delete that one!"

        proc/checkClump(list/closedClumps,list/ignore)
            
            if(!closedClumps)closedClumps = list()
            if(src in closedClumps)return

            . = closedClumps
            . += src

            for(var/obj/clumpable/c in cardinals(src))
                if(ignore && (c in ignore))
                    continue
                if(!(c in .)) 
                    var/list/added = c.checkClump(.,ignore)
                    for(var/a in added)
                        if(!(a in .)). += a

proc
    cardinals(atom/t)
        var/list/retval = list()
        for(var/dir in list(1,2,4,8))
            var/turf/addTurf = get_step(t,dir)
            retval += addTurf
            retval += addTurf.contents
        return retval
    compareLists(list/a,list/b)
        for(var/object in a)
            if(!(object in b))
                return 0
            
        for(var/object in b)
            if(!(object in a))
                return 0
        return 1

turf/Click()
    usr.myClump += new/obj/clumpable(src)
    world << "[usr.myClump.len] clumpables"


This snippet only checks removals, not additions, but you'd just have to check to see if a member of the user's clump is within one tile of an addition candidate.

It takes a noticable amount of time to tell whether or not an object in a long (>100 object) chain is deletable but it's only just noticable on my machine.
Clumping works by adding each object in cardinal directions to the clump, and then recurring, ignoring objects already in the clump. Checking works by creating a new clump with the removal candidate ignored, 'centered' around a randomly selected object. If the object is removable, then a full clump minus the candidate will be returned. If the object is not removable, only a section of the clump will be returned.

I'm sure there are either more efficient ways of doing it or more efficient ways of implementing this particular method, but this seems to work and it beats doing a ton of pathfinding.