0
\$\begingroup\$

I cant seem to get breadth first search right. Ive gone through redblobs implementation guides of hex grids and have that all figured out but pathfinding is proving to be difficult.

So I have a search function that implements the algorithm.

function searchPath(graph, start, goal) {
    let cameFrom = [start]
    let frontier = new Queue()
    frontier.enqueue(start)

    while (!frontier.isEmpty) {
        const current = frontier.dequeue()

        if (current === goal) break

        graph[current].forEach(next => {
            if (!cameFrom.includes(next)) {
                frontier.enqueue(next)
                cameFrom.push(next)
            }
        })
    }
    return cameFrom
}

my graph is a two dimensional array where each index corresponds to a tile on the map and the value of each is an array of indexes of neighbors of that tile.

Example:

const graph = [
    [3,1,4],
    [0,4,2,5],
    [1,5,6],
    [7,0,4,8],
    [0,3,8,1,5,9],
    [1,4,9,2,6,10],
    [2,5,10,11],
    [3,8,12],
    [3,7,12,4,9,13],
    [4,8,13,5,10,14],
    [5,9,14,6,11,15],
    [6,10,15],
    [7,8,13,16],
    [8,12,16,9,14,17],
    [9,13,17,10,15,18],
    [10,14,18,11],
    [12,13,17],1
    [13,16,14,18],
    [14,17,15]
]

The function returns the indexes of searched tiles.

Example 1: searchPath(graph, 12, 13) will return [12, 7, 8, 13, 16, 3, 4, 9] Example 2: searchPath(graph, 8, 1) will return [8, 3, 7, 12, 4, 9, 13, 0, 16, 1, 5, 10, 14, 17]. Its returning a lot of nodes for what would seem to be a

Now I attempt to reconstruct a path with this function but I cant get it to work. It ends up with an infinite loop.

function findPath(cameFrom, start, goal) {
    let current = goal
    let path = []
    while (current !== start) {
        path.push(current)
        current = cameFrom[cameFrom.indexOf(current)]
    }
    return path
}

I have a feeling my graph data structure is off but I just don't know. Heres a link to the current version of the "game". If you open the console you should see the output of the search and the start + goal arguments that are supplied.

https://cwahlfeldt.github.io/hex-game/

Any help would be much appreciated. Thanks!

\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

It looks like you are confusing Predecessor Node List and Closed Set.

What's the meaning of cameFrom? In searchPath you use it to store all visited node, but in findPath you use it to reconstruct a path. That's the crux of the matter.

Fix:

function searchPath(graph, start, goal) {
    let frontier = new Queue();
    frontier.enqueue(start);

    var predecessorMap = {}; //a map of the node found by which node

    while (!frontier.isEmpty) {
        const current = frontier.dequeue();
        if (current === goal) break;

        graph[current].forEach(next => {
            if (!(next in predecessorMap)) {
                frontier.enqueue(next);
                predecessorMap[next] = current;
            }
        });
    }
    return predecessorMap;
}

function findPath(predecessorMap, start, goal) {
    let current = goal;
    let path = [];
    while (current !== start) {
        path.push(current);
        current = predecessorMap[current];
    }
    return path;
}
\$\endgroup\$
3
  • \$\begingroup\$ It worked like a charm, thank you so much! I honestly don't know what cameFrom was for, it was in a guide I was using for a* and it still didnt make sense to me. This makes so much more sense. I had a feeling I needed to use an object map instead of an array, but it felt weird using index numbers as keys in an object. Thank you again so much!!!! \$\endgroup\$
    – cwahlfeldt
    Apr 23, 2022 at 15:59
  • \$\begingroup\$ cameFrom in the guide is what Mangata calls predecessorMap: it's a map from one node to another. In your code you were using it as an array instead of an object map. \$\endgroup\$
    – amitp
    Apr 23, 2022 at 16:34
  • \$\begingroup\$ Ahh ok makes sense. Also @amitp just wanna say I am forever grateful for all your amazing work on red blob! \$\endgroup\$
    – cwahlfeldt
    Apr 23, 2022 at 17:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .