在六边形网格中找到所有长度为 n 的可能路径

Question

假设一个函数以s（原六边形）、f（目标六边形）和n（路径长度）值作为参数并输出所有可能的列表长度为 n 的路径。为了使问题可视化，请检查下图：

假设我们的起点 (s) 是红色虚线十六进制 (2, 3)，目标 (f) 是蓝色虚线十六进制 (5, 2)。我们希望通过 5 个步骤 (n = 5) 达到蓝色虚线十六进制。还要考虑，如果步行到达特定的六角形，它可能会在下一步中也停留在该六角形中。换句话说，可能的路径之一可以是(3, 2) - (4, 2) - (5, 2) - (5, 2) - (5, 2)。也算作5长路径。

这些是从 (2, 3) 到 (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)

我想以某种方式找到所有这些路径。但是，我无法确定哪种算法可以提供最有效的解决方案来处理这个问题。首先想到的是使用深度优先搜索，但我想知道在这种情况下是否有更好的替代方法。

Answer 1

假设您定义了以下递归函数，返回一个对列表，其中每个对列表都是从 from 到 to 的路径，长度为 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

然后你只需要用你的来源、目标和所需的长度来调用它。

Answer 2

对于这样的六角网格，

可以使用以下方法计算两个节点之间的曼哈顿距离：

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

这个问题之前在这些问题中讨论过：

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

我相信我们可以通过将 Ami 的答案与 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

最后，如您所见，有一个辅助函数可以获取邻居节点的索引：

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

主要思想是简单地修剪一个节点，如果它到目标节点的曼哈顿距离大于当前递归调用的长度n。举个例子，如果我们可以分两步（n = 2）从(1, 1)到(0, 3)，则应该修剪除(1, 2)之外的所有邻居节点。

在六边形网格中找到所有长度为 n 的可能路径

Finding all possible paths of n length in hexagonal grid

algorithm

recursion

depth-first-search

graph-algorithm