Data Tree Pathfinding Algorithm

Page: 1 2
ID:1395171
 
Oct 9 2013, 4:12 pm
(See the best response by Ter13.)
Code:
var/list/path = pathfind(my_data, desired_data)
for(var/x in path)
    world << x


Problem description:

I have a problem pertaining to pathfinding. I am attempting to traverse through an extensive 'network' of connected datums and locate the closest path to 'desired_data'.

I've tried writing up my own pathfinding algorithm for the situation but I'm really inexperienced in this area. I don't really know what algorithm I should be investigating.

It's worth noting I'm navigating a tree of information, not a spatial grid. X and y values are irrelevant in this scenario.
Oct 9 2013, 4:59 pm
Doohl wrote:
It's worth noting I'm navigating a tree of information, not a spatial grid. X and y values are irrelevant in this scenario.

This seems kind of vague. How is this tree of information defined exactly? Are you talking about an actual "tree" of datum type paths?
Oct 9 2013, 5:25 pm
I should've clarified, yes.

I am attempting to locate a path from one object/datum to another, but not through the x/y grid. Each object has its own list called "links" which is populated by other objects. Each object in that list, in turn, has its own "links" variable, and so on and so forth.

I want to use some pathfinding algorithm to generate a path containing a list of objects from a to b.
Oct 9 2013, 5:42 pm (Edited on Oct 9 2013, 5:48 pm)
I've done something similar to this recently. If you know how to do flood filling it helps.

I'm not sure if this is the best way to do it but I have taken to having two lists, one for temporary usage to avoid redoing things multiple times and another as the actual compiled list. You'll define the temp list with the starting object or point in this network; every pass you'll be adding everything "connected" to this object to the temp list and the final but only if they are not already in the final. You'll also need a while() and a var that resets in the beginning of the while and adds on when new things have been found.

I'm hoping this helps. I use this in a system relating to "connecting" objects together with "joints".


edit: just realized this probably does in fact not help finding an exact "path". :(
Oct 9 2013, 5:45 pm
That seems like a good way to 'find' something, but not a good way to return a path to it. Could you elaborate a bit on your method?
Oct 9 2013, 5:54 pm
Essentially, what you are suggesting is that one start object "contains" the other end object, after a certain number of recursive iterations. It seems like it might be quite CPU intensive to work out the path.

I guess you would have to search downward from the start object and look for the end object at each iteration. All the while, the algorithm will need to keep a list updated of the current path that is being searched. Once it finally does find the end object, it can then return the resulting path list.
Oct 9 2013, 6:04 pm
Is it actually a tree, where each node has a single parent node and optionally multiple child nodes? Or is it a graph, where there could be multiple paths between your two nodes?

Do you have a heuristic to estimate how far one node is from your target node?
Oct 9 2013, 6:05 pm
In response to Doohl
Doohl wrote:
That seems like a good way to 'find' something, but not a good way to return a path to it. Could you elaborate a bit on your method?

Well my method would be more useful in the case of A,B, and C where A is connected to B, and B to C but A and C are not at all connected. This "flood fill" would identify ABC as a final result regardless of which one I start the search. I only realized afterwards that it doesn't really help in your case most likely.
Oct 9 2013, 6:40 pm
I suppose I ought to give some insight into what I'm actually doing rather than just examples.

Take this image, and imagine I am trying to find the 'path' from one star to another.

I suppose I could somehow tie a normal pathfinding algorithm to what I currently I have, and I have tried, but they all seem to be hit-and-miss (making every turf dense except the ones the lines are on).
Oct 9 2013, 7:02 pm (Edited on Oct 9 2013, 7:10 pm)
I just got an idea, what if you assign directions to these connections and just kind of nudge the code into abstractly going in that direction?



To clarify, lets say you have some how assigned coords to each point and then can find that A to B would be a southwestern path, then you could just look for the connections closest to A that are either Southwest, South or West (in order of priority) and go through those connections until it finds one that is connecting to B.

note: the N/S establishes that that connection has south and north as potential "directions".
Oct 9 2013, 7:16 pm
I don't think that would really work in a situation like this:



The problem is sometimes you need to go in odd directions in order to find the star you want to get to.
Oct 9 2013, 7:23 pm
I don't think any kind of coordinate method is going to work for something like this. I suspect all the connection lines are a purely visual representation, which means they have no real meaningful physical location.

This is definitely a representation of the kind of data structure that I had imagined. I think a recursive breadth-first search algorithm is the only proper way to handle this kind of monster. It could be hard to do with DM's limited data structures.

Basically, just think of the stars as if they were folders in a directory tree, then search through the levels of "folders" until you get to the target.

Who would have thought simply connecting the dots could be so complicated? It's one of those things that's very easy for humans, but not so much for computers.
Oct 9 2013, 7:25 pm
Well... in that case you want to go Northwest, and there's no Northwest, north or west, but there's a southwest - perhaps instead of assinging from the 8 cardinal directions you could compare which direction is more/most north or west? If that makes sense.

I'm thinking of it now like...



Then at E you literally burn through north and west and default to south being less west than east... Then you get another west and finally arriving at the point. :I

So like you'd look for the most "north" and most "west" I guess, hard to explain, but since there is no point more north than A in it's direct choices you'd go for most westward.
Oct 9 2013, 7:29 pm
In response to Multiverse7
Multiverse7 wrote:
I don't think any kind of coordinate method is going to work for something like this. I suspect all the connection lines are a purely visual representation, which means they have no real meaningful physical location.

This is definitely a representation of the kind of data structure that I had imagined. I think a recursive breadth-first search algorithm is the only proper way to handle this kind of monster. It could be hard to do with DM's limited data structures.

Basically, just think of the stars as if they were folders in a directory tree, then search through the levels of "folders" until you get to the target.

Who would have thought simply connecting the dots could be so complicated? It's one of those things that's very easy for humans, but not so much for computers.

I'm more or less ignoring the lines and focusing more on the dots, which although purely visual they still have coords for where they are visually placed. Idk, just trying to help. It's how I'd do it with my scope of knowledge.
Oct 9 2013, 7:31 pm
Oh, so it is a graph, and it is spatial, just not tile-based. Yea, that's easy enough, something like the A* algorithm should work fine. The demo's you'll find on BYOND will probably all be tile-based, a node-based implementation shouldn't be too hard.

Just based on the pseudocode from wikipedia, something like this should work:
Node
    var
        x
        y
        list/links = list()

    New(x,y)
        src.x = x
        src.y = y

    proc/distTo(Node/b)
        return sqrt((x-b.x)*(x-b.x) + (y-b.y)*(y-b.y))

proc/FindPathHeuristic(Node/node, Node/goal)
    return node.distTo(goal)

proc/FindPath(Node/start, Node/goal)
    var/list
        closedNodes = list()    // Nodes that have been evaluated
        openNodes = list(start) // Nodes that need to be evaluated

        cameFromMap = list()  // Associative list tracking which node led to each node
        g_scores = list()     // Associative list tracking the length so far of each path to an intermediary node
        f_scores = list()     // Associative list tracking estimated length of a path passing through an intermediary node

    g_scores[start] = 0
    f_scores[start] = FindPathHeuristic(start, goal)

    while(openNodes.len)
        var/Node/node = openNodes[1]

        if(node == goal)
            // Build a list containing the path
            var/list/result = list()
            while(node)
                result += node
                node = cameFromMap[node]
            return result

        openNodes.Cut(1,2)
        closedNodes[node] = 1

        for(var/Node/neighbor in node.links)
            var/g_score = g_scores[node] + node.distTo(neighbor)
            var/f_score = g_score + FindPathHeuristic(neighbor, goal)

            if(closedNodes[neighbor] && f_score >= f_scores[neighbor])
                continue // Node is already a part of another path that is shorter

            var/inOpen = (neighbor in openNodes)
            if(!inOpen || f_score < f_scores[neighbor])
                cameFromMap[neighbor] = node
                g_scores[neighbor] = g_score
                f_scores[neighbor] = f_score

                // Remove the neighbor so it can be resorted
                if(inOpen) openNodes -= neighbor

                // Add the neighbor into the openNodes list, sorted so the lowest f_scores come first
                for(var/i = 1 to openNodes.len)
                    var/Node/other = openNodes[i]
                    if(f_scores[other] >= f_score)
                        openNodes.Insert(i, node)

    return null


Didn't have a chance to test it, but it should give you the right idea. Basically, it's a guided breadth-first search, using a heuristic to prioritize which nodes it tests next. The heuristic is just the euclidean distance from the current node to the target (which is basically a best-case guess hoping that the current node connects directly to our target). It tracks the actual distances covered by each path so far in the g_scores list, and the estimates of how long the paths will ultimately be in f_scores. It keeps openNodes sorted such that the nodes that are part of the paths with the lowest estimated distance (f_scores) are tested first.

It loops through the openNodes list, popping off the front node to work on, gets all of its neighbors, calculates their distances so far (g_score) and estimated total distance to target (f_score), and adds the relevant neighbors into openNodes to be checked. While it does this, it keeps track of which nodes led to the each node in the cameFromMap variable. Once we reach the target, we can just work our way backward through the cameFromMap to get the full path (cameFromMap[path[n]] = path[n-1])
Oct 9 2013, 7:35 pm
"Basically, it's a guided breadth-first search, using a heuristic to prioritize which nodes it tests next."

Kind of what I was thinking just with the lack of specialized knowledge. :(
Oct 9 2013, 7:41 pm
That is some scary code right there!

I guess in a way it kind of is like "pathfinding", if you are in fact looking for the shortest paths to take between nodes.
Oct 9 2013, 7:42 pm
@Multiverse7: Yes, the lines connecting the stars are purely visual and does not have any sort of spatial properties.

@Jittai: That makes a lot of implications that I'm not quite comfortable making, because the connections can't be accurately described by direction alone.

@DarkCampaigner: I was looking into breadth-first searching, but this seems to make more sense. The only problem is that the distance should be entirely irrelevant, the only thing that matters is the number of lines. I'm trying to look for a path that contains the less lines between, not the less distance; but this helps.
Oct 9 2013, 7:45 pm
I think Dark's looks for the one making the least jumps.
Oct 9 2013, 7:48 pm
Nah, mine was distance based. If you just want the least jumps, a breadth-first search is all you need:

proc/FindPath(Node/start, Node/goal)
    var/list
        closedNodes = list()    // Nodes that have been evaluated
        openNodes = list(start) // Nodes that need to be evaluated
        cameFromMap = list()    // Associative list tracking which node led to each node

    while(openNodes.len)
        var/Node/node = openNodes[1]

        if(node == goal)
            // Build a list containing the path
            var/list/result = list()
            while(node)
                result += node
                node = cameFromMap[node]
            return result

        openNodes.Cut(1,2)
        closedNodes[node] = 1

        for(var/Node/neighbor in node.links)

            if(closedNodes[neighbor])
                continue // Node is already a part of another path

            if(!(neighbor in openNodes))
                // Remember which node led to this one
                cameFromMap[neighbor] = node

                // Add the neighbor to the end of the openNodes list
                openNodes += neighbor

    return null
Page: 1 2