adjacent nodes

ID:1347909
 
Aug 8 2013, 11:01 am
My GIAW entry uses the Depth-first search algorithm for maze generation and the algorithm requires a way to get a list of adjacent nodes for constructing the maze. Here's the method I used to do that:
atom
    proc
        neighbours(type)
            if(locate(type) in get_step(src, 1)) . += list(type)
            if(locate(type) in get_step(src, 2)) . += list(type)
            if(locate(type) in get_step(src, 4)) . += list(type)
            if(locate(type) in get_step(src, 8)) . += list(type)

It has many additional uses, as well. It can be used in A*, which also requires you to get a list of adjacent nodes. It only returns a list of nodes that are north, south, east, or west of the current node, but it's not hard to modify so that it returns a list of diagonal nodes too. Enjoy.
Aug 8 2013, 11:34 am
I don't see how this returns anything useful.
Aug 8 2013, 11:39 am
You might not have no use for it but I did, and others might.
Aug 8 2013, 11:53 am
I mean, you're returning a list of 0 to 4 of 'type'. Wouldn't you want to return a list of turfs or something?
Aug 8 2013, 6:36 pm
Perhaps you should show an example of this in application. All I gather from this is that, you can detect which of the surrounding objects are of a definite type.
Aug 8 2013, 6:52 pm (Edited on Aug 9 2013, 1:59 am)
As set up, its not quite even that. Just how many of the surrounding objects are of a definite type. The return value wont tell you which.

EDIT: Actually, if you pass in a turf, it gives you nothing. Any other atom or type path and it gives you a list containing as many copys of 'type' as there are in the surrounding turfs.
Aug 10 2013, 2:21 pm
Make it into a loop using a list containing all the directions you want to use.
Aug 10 2013, 3:00 pm
That's pretty much what I did before.
proc
    neighbours(atom/source)
        for(var/turf/t in range(1, src))
            switch(get_dir(t, source))
                if(1, 2, 4, 8) . += list(t)

In the actual depth-first algorithm, I used it like this:
for(var/turf/node in neighbours(src))
            if(node.density)
                //  remove walls


I ran into a few bugs with this one though, which is why I switched to the initial(the first code snippet I posted) method.
Aug 10 2013, 7:04 pm
All I meant was to take your original proc and make it a loop, not to iterate through range and cut out turfs that aren't in the right direction. I can see why that would be buggy.

var/cardinals = list(NORTH, SOUTH, EAST, WEST)
var/directions = list(NORTH, SOUTH, EAST, WEST, NORTHEAST, SOUTHEAST, NORTHWEST, SOUTHWEST)

proc/neighbors()
     . = list()

     for(dir in cardinals)
          var/turf/T = get_step(src, dir)
          if(T.density) //Or whatever else
               continue
          . += T


And then include the type checking in a separate proc.

. = list()
for(var/turf/T in neighbors())
     var/found = locate(type) in T
          if(found)
               found += .


Your original proc was technically fine especially for such a small proc. For a larger one though, getting in the habit of looping through a list rather than hardcoding everything will save you time and effort later on when you want to change things. Plus being two procs means you can use both of them later on and save yourself some time and energy.