Tile Finder

ID:157352
 
Mar 27 2010, 6:29 pm
How would I go about making a procedure which would find tiles around a mob which the mob is capable of traveling to, and no diagonal movement with a limited number of steps the mob can take?

mob
    var/steps = 3
    proc
        tile_find()


Mar 27 2010, 6:33 pm
Describe better. This might need a pathfinding algorithm, like Dijkstra's.
Mar 27 2010, 7:49 pm
In response to Popisfizzy
Would it help if I mentioned games like Final Fantasy Tactics and Advanced Wars?
Mar 28 2010, 3:17 am
I think what Speedro means is a system where the player clicks on a tile (or highlights the tile) and the mob moves to it, like a chessboard.

As far as my contribution, I'll tell you its possible, you'll probably use Move(), and from my understanding its been done several times so a look into some demos wouldn't hurt.
Mar 28 2010, 4:09 am
As Popisfizzy said, generally you would use a good pathfinding algorithm for problems like this. If, however, all you want to know is "Is it possible for object A to get to location B using only N steps?" for all locations B within N steps and N is guaranteed to be small, and you don't care about the best path, then you can make a very simple algorithm to check this.

If you want to check for object A, but the turf at object A's coordinates into a list L. Now start the following loop:

for index = 1 to numberOfSteps
for all locations B in list L
for all locations C in list(get_step(B, NORTH), get_step(B, SOUTH), etc.)
if it is possible to move from B to C and C is not in L or in L2
add C to list L2 (yes, a different, temporary list, so it doesn't modify L until we're done looping through C in L)
add all elements from L2 to L, then empty L2

You're starting at the initial location, then adding in any tiles you could step to from there, then you're also adding in any tiles you could step to from those tiles, then any tiles you could step to from those tiles, and you're doing this a number of times equal to numberOfSteps.

With minor modifications, this could also take into account warp portals, stairs, and other relocation effects and the continued motion on the other side of them as well.

Please NOTE: For the specific pseudocode I gave, that is a terribly, horrendously UNoptomized way to do it, so it will take more time to compute than necessary. It should not be too difficult, though, to optimize it in several ways. I leave that as an exercise to you; however, if your numberOfSteps is small enough, it should be good enough even if left unoptimized. If the number of steps is 3, for example, it's still going to take only a fraction of a millisecond to figure out even if not optimized.
Mar 28 2010, 5:42 am (Edited on Mar 28 2010, 6:10 am)
In response to Loduwijk
How would I make it flexible with more list entries than just 3 though, because some things might be able to move as far as 6 or 8? Or do I have to continually rewrite it?


mob
    var/steps = 3
    proc
        tile_find()
            for(var/s = 0, s < steps, s++)
                var/list/a = new //first level of steps from character
                var/list/b = new //second level etc...
                a.Add(get_step(src,NORTH), get_step(src,SOUTH), get_step(src,EAST), get_step(src,WEST))
                //and then i have no idea what I'm doing...




mob
    var/steps = 3
    proc
        tile_find()
            for(var/s = 0, s < steps, s++)
                var/list/a = new //first level of steps from character
                var/list/b = new //second level etc...
                a.Add(get_step(src,NORTH), get_step(src,SOUTH), get_step(src,EAST), get_step(src,WEST))
                //and doing this just flat out shouldn't work because the list doesn't relate like that.:
                b.Add(get_step(a,NORTH), get_step(a,SOUTH), get_step(a,EAST), get_step(a,WEST))


Yeah, I clearly have no idea what I'm doing:

mob
    var/steps = 3 //what if steps is 5?
    proc
        tile_find()
            for(var/s = 0, s < steps, s++)
                var/list/a = new //first level of steps from character
                var/list/b = new //second level etc...
                var/list/c = new //do i have to keep rewriting for every extra step capable of taking?
                var/list/all = new //a final list
                a.Add(get_step(src,NORTH), get_step(src,SOUTH), get_step(src,EAST), get_step(src,WEST))
                for(var/turf/t in a) //find all turf's that are one step away from player
                    b.Add(get_step(t,NORTH), get_step(t,SOUTH), get_step(t,EAST), get_step(t,WEST)) //now\
                    list b contains steps of those steps
                for(var/turf/t in b) //must i rewrite it? Can't it be flexible?
                    c.Add(get_step(t,NORTH), get_step(t,SOUTH), get_step(t,EAST), get_step(t,WEST))
                //list c now contains all possible steps from the third area
                //how does this know when to stop? How can i get that list? Sure I can do it if I always\
                know the mob is only taking 3 steps but what if it changes?
                
                
                //now weeding out overlaps
                for(var/turf/m in a)
                    for(var/turf/n in b)
                        if(m == n)
                            del n
                for(var/turf/m in a)
                    for(var/turf/n in c)
                        if(m == n)
                            del n
                for(var/turf/m in b)
                    for(var/turf/n in c)
                        if(m == n)
                            del n
                all.Add(a,b,c) //what if there were more paths? ex a,b,c,d,e,f then what?


None of that even makes sense.
Mar 28 2010, 10:14 am
In response to Loduwijk
You could, alternatively, use a recursive algorithm.

turf
    proc/GetAdjacent()
        // This will get the tiles adjacent to this one.
        // By default, it will get the ones to the north,
        // south, east, and west. If this were, say, a portal
        // turf, you'd make the adjacent tile the one that
        // it transports to.
        return list(get_step(src, NORTH), 
                    get_step(src, SOUTH),
                    get_step(src, EAST),
                    get_step(src, WEST))

mob
    proc/GetSteppable(steps, turf/source, list/current)
        if(!steps)
            return

        if(!source)
            source = loc

        if(!current)
            current = new

        for(var/atom/a in source.GetAdjacent())
            if(a in current)
                continue

            if(a.Enter(src))
                current += a
                GetSteppable(steps - 1, a, current)

        return current


This assumes that /turf.Enter() doesn't do any checking as to whether the mob is adjecent to the turf or any directional checking, mind. If you need that, you may have to fiddle with the proc a bit. This also only finds the turfs the mob can step to. It doesn't actually find the path for them to get somewhere. The good thing about this, though, is that it will make pathfinding quicker. Since you know that they are allowed to step anywhere in the list that this proc returns, their path should only include turfs in this list, so you can ignore anything outside it.
Mar 28 2010, 10:44 am
In response to Popisfizzy
You could easily get a path from that with one simple modification. Change the line:

current += a


to:

current[a] = source


Then, you can find the path to a destination by following the association backwards, like so:

var/list/L = src.GetSteppable(4)
var/turf/T = destination
var/list/path = list(T)
while(L[T] != null)
  path.Insert(1,L[T])
  T = L[T]


Actually, that'll break because your algorithm doesn't include the source turf. So you'd need to change one other line:

current = new
// to
current = list(source)
Mar 28 2010, 11:29 am
In response to Garthor
You could, but I think there's the possibility that may provide a peculiar path rather than the shortest or most visually correct one.
Mar 30 2010, 10:35 am
In response to Popisfizzy
Seems to make sense...

mob
    proc/GetSteppable(steps, turf/source, list/current)
        if(!steps)
            return

        if(!source)
            source = loc

        if(!current)
            current = new
            
        //Above is assigning/ending proc if not all arguments are present

        for(var/atom/a in source.GetAdjacent()) //for atoms in adjacent turfs of the current turf
            if(a in current) //if the atom is already in the list of turfs found, don't re-add it.
                continue

            if(a.Enter(src)) //if calling src can enter the turf (returns true)
                current += a //add it to the list of possible locations
                GetSteppable(steps - 1, a, current) //recall the procedure, so now all turfs\
                that are checked for adjacent squares include the new ones, and repeat process until\
                out of steps
                

        return current //return an easy use list of these turfs