Finding all possible paths of n length in hexagona

问题:

Assume that a function takes s (origin hexagon), f (target hexagon) and n (length of the path) values as parameters and outputs list of all possible paths that has n length. To visualize the problem please check the figure below:

Let's say our origin (s) is the red dotted hex (2, 3) and the target (f) is the blue dotted one (5, 2). We want to reach blue dotted hex in 5 steps (n = 5). Also consider that if a walk reaches a specific hex, it may stay in that hex as well in the next step. In other words, one of the possible paths can be (3, 2) - (4, 2) - (5, 2) - (5, 2) - (5, 2). It is also counted as 5-length path.

These are some example paths from (2, 3) to (5, 2):

(1, 3) - (2, 3) - (3, 2) - (4, 3) - (5, 2)
(3, 3) - (4, 4) - (5, 4) - (5, 3) - (5, 2)
(2, 3) - (2, 3) - (3, 3) - (4, 3) - (5, 2)

I want to find all of these paths in a way. However, I could not determine which algorithm gives the most efficient solution to handle this problem. The first thing comes to mind is to use depth-first-search but I wonder is there any better alternative to use in this case.

回答1:

Say you define the following recursive function, returning a list of lists of pairs, where each list of pairs is a path from from to to with length i:

find_paths_from_to_with_length(from, to, i):
    if i == 1:
        if to in neighbors(from) or from == to:
            return [[(from, to)]]
        return []

    all_paths = []
    for node in neighbors(from) + [from]:
        neighbor_all_paths = find_paths_from_to_with_length(node, to, i - 1)
        for path in neigbor_all_paths:
            all_paths.append([(from, node)] + neighbor_path

    return all_paths

Then you just need to call it with your source, target, and required length.

回答2:

For a hex grid like this,

the Manhattan distance between two nodes can be computed by using:

function dist = manhattan_dist( p, q )

    y1 = p(1);
    y2 = q(1);
    x1 = p(2);
    x2 = q(2);

    du = x2 - x1;
    dv = (y2 - floor(x2 / 2)) - (y1 - floor(x1 / 2));

    if ((du >= 0 && dv >= 0) || (du < 0 && dv < 0))
        dist = abs(du) + abs(dv);

    else
        dist = max(abs(du), abs(dv));
    end

end

This problem had been discussed in these questions before:

• Distance between 2 hexagons on hexagon grid
• Manhattan Distance between tiles in a hexagonal grid

I believe that we can enhance Ami's answer by combining it with manhattan_dist:

function all_paths = find_paths( from, to, i )

    if i == 1
        all_paths = to;
        return;
    end

    all_paths = [];
    neighbors = neighbor_nodes(from, 8);
    for j = 1:length(neighbors)
        if manhattan_dist(neighbors(j,:), to) <= i - 1
            paths = find_paths(neighbors(j,:), to, i - 1);
            for k = 1:size(paths, 1)
                all_paths = [all_paths; {neighbors(j,:)} paths(k,:)];
            end
        end
    end

end

Lastly, as you can see, there is a helper function to get indices of neighbor nodes:

function neighbors = neighbor_nodes( node, n )

    y = node(1);
    x = node(2);

    neighbors = [];
    neighbors = [neighbors; [y, x]];

    if mod(x,2) == 1
        neighbors = [neighbors; [y, x-1]];

        if y > 0
            neighbors = [neighbors; [y-1, x]];
        end

        if x < n - 1
            neighbors = [neighbors; [y, x+1]];
            neighbors = [neighbors; [y+1, x+1]];
        end

        neighbors = [neighbors; [y+1, x-1]];

        if y < n - 1
            neighbors = [neighbors; [y+1, x]];
        end

    else
        if y > 0
            neighbors = [neighbors; [y-1, x]];
            neighbors = [neighbors; [y-1, x+1]];
            if x > 0
                neighbors = [neighbors; [y-1, x-1]];
            end
        end

        if y < n
            neighbors = [neighbors; [y+1, x]];
            neighbors = [neighbors; [y, x+1]];    

            if x > 0
                neighbors = [neighbors; [y, x-1]];
            end
        end
    end

end

The main idea is simply pruning a node if its Manhattan distance to the target node is larger than the length n of the current recursive call. To exemplify, if we can go from (1, 1) to (0, 3) in two steps (n = 2), all neighbor nodes except (1, 2) should be pruned.