Pathfinding Going Haywire

ID:1969319
 
Oct 19 2015, 8:34 am
(See the best response by Lummox JR.)
Code:
proc
    find_path(turf/start, turf/goal)
        var/list/frontier = list(start)

        var/list/came_from = list()
        came_from[start] = null

        while(frontier.len)
            var/turf/current = frontier[frontier.len]
            frontier -= current

            for(var/turf/next in range(1, current))
                if(!(next in came_from))
                    frontier += next
                    came_from[next] = current

        var/turf/current = goal
        var/list/path = list(current)

        while(current != start)
            current = came_from[current]
            path.Insert(1, current)

        return path


Problem description:
I'm going through this great article about pathfinding and recreating each step in DM. The code above implements the Breadth First Search closely following the example code. However, the result it gives has me completely baffled. Take a look at this gif showing what it does with what should be a simple straight line (green being the start, blue the goal, yellow the absurd path):



Can anyone explain why something like this can happen? Thanks!

Oct 19 2015, 10:10 am
This line means you're doing a DFS, not a BFS:

var/turf/current = frontier[frontier.len]

A breadth-first search would be different. I suggest this modification.

proc
    find_path(turf/start, turf/goal)
        var/list/frontier = list(start=1)

        var/list/came_from = list()
        came_from[start] = null

        for(var/i=1, i<=frontier.len, ++i)
            var/turf/current = frontier[i]

            for(var/turf/next in range(1, current))
                if(!frontier[next])
                    frontier[next] = 1
                    came_from[next] = current

        var/turf/current = goal
        var/list/path = list(current)

        while(current != start)
            current = came_from[current]
            path.Insert(1, current)

        return path

I didn't go over the logic in full, but I think those changes ought to fix it. I made use of associative lists to improve speed.

Of course for best results you'd really want to use something like A*, where you're using a heuristic to determine which node is most worth exploring.
Oct 19 2015, 10:31 am (Edited on Oct 19 2015, 10:45 am)
In response to Lummox JR
Thank you for your response!

Lummox JR wrote:
I didn't go over the logic in full, but I think those changes ought to fix it. I made use of associative lists to improve speed.

I would have to adjust the code some more to get it to work with associative lists. I did switch to the for loop and the path is significantly better, but still is not what I expect:



Could this have something to do with using the range() proc? The example here that I based this on gives a completely straight path when the start and goal are parallel.

Edit: I switched from using the range() proc to calculating the neighbor tiles myself with no difference.

Of course for best results you'd really want to use something like A*, where you're using a heuristic to determine which node is most worth exploring.

I intend to use A*, and actually already wrote a rough implementation that suffers from similar problems. That's why I went back to the article I linked to and decided to go through each example to be sure I did not miss something.
Oct 19 2015, 12:45 pm
The path you got from the adjusted algorithm isn't a straight line because you have nothing in your code to ensure that a straight line is preferred. It's just as many steps to use that V as it is to walk a straight line. The A* algorithm includes a heuristic that prefers more direct paths, and would solve this issue.
Oct 19 2015, 1:29 pm (Edited on Oct 19 2015, 1:47 pm)
Best response
Rough A* in soft code (untested):

#define HEURISTIC(T) sqrt((T.x-goal.x)*(T.x-goal.x)+(T.y-goal.y)*(T.y-goal.y))

#define BUBBLE_UP(heap,n) for(i=n, i>1, i=j) {j=i>>1;\
if(heap[heap[i]] >= heap[heap[j]]) break;\
heap.Swap(i,j)}

#define BUBBLE_DOWN(heap,n) for(i=n, (i<<1)<=heap.len, i=j) {j=i<<1;\
if(j>heap.len) break;\
if(j+1<=heap.len && if(heap[heap[j+1]] < heap[heap[j]]) ++j;\
if(heap[heap[i]] <= heap[heap[j]]) break;\
heap.Swap(i,j)}

proc/Astar(turf/start, turf/goal)
    if(!start || !goal || start==goal) return list(start)
    var/list{open=new; cost=new; heu=new; back=new}
    var/turf/cur, next
    var/iter = 0
    var/i, j, c, h
    h = HEURISTIC(start)
    heu[start] = h
    cost[start] = 0
    open[start] = h
    while(open.len && iter++ < 500)
        cur = open[1]
        open.Swap(1,open.len)
        --open.len
        BUBBLE_DOWN(open, 1)
        c = cost[cur] + 1
        for(next in orange(1,cur))
            h = heu[next]
            if(isnull(h))
                // next has never been visited before
                h = HEURISTIC(next)
                heu[next] = h
                cost[next] = c
                open[next] = c + h
                back[next] = cur
                BUBBLE_UP(open, open.len)
                if(next == goal) goto done
                continue
            if(cost[next] > c)
                // found a better route to next
                cost[next] = c
                open[next] = c + h
                back[next] = cur
                BUBBLE_UP(open, open.Find(next))
    // timed out, so find the turf with the lowest heuristic and call that our goal
    goal = cur
    h = heu[goal]
    for(next in heu)
        if(heu[next] < h)
            h = heu[next]
            goal = next
    done:  // jump to here on success
    var/list/result = new
    while(goal)
        result += goal
        goal = back[goal]
    // reverse list
    i=1; j=result.len
    while(i<j) result.Swap(i++, j--)
    return result

There are more efficient implementations, but they get more complicated. (I used a more complex method in SotS II, where I'm looking up an index into another list and then that list contains multiple values like cost, heuristic, etc. It's quicker than using datums.) Here, I'm using the open list as a min-heap. open[turf] is equal to the cost to reach that turf, plus the heuristic (its Euclidean distance to the goal).

On each iteration, the top item is popped off the open heap and assigned to cur. One of the last items in the heap takes its place and it bubbles down to where it belongs. Then, each of cur's neighbors are checked. If the neighbor (next) hasn't been encountered before, its heuristic lookup is null, so a new heuristic is assigned, it's given a cost and a backtrack reference to cur, and then it's added to the open heap where it bubbles up. If the neighbor has been encountered before but has a lower cost than the last time it was seen, the cost and the value on the open heap are adjusted accordingly and again it bubbles up.
Oct 19 2015, 1:36 pm
In response to Lummox JR
Wow, your responses have been excellent. Thank you so much for taking the time to write this example for me. :) I'll experiment with this further tonight. Cheers!