Finding all possible paths of n length in hexagonal grid

Question

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.

Do you wish to actually enumerate all the paths, or aggregate them in some way (say find the cheapest one)? If it's the former, there's not much to do in terms of efficiency. — Ami Tavory, Feb 02 '16 at 10:23
I wish to enumerate them. I know the problem cannot be solved in an extraordinarily efficient way by definition but still I am looking for the best solution. — Dorukhan Arslan, Feb 02 '16 at 10:29

score 1 · Accepted Answer · answered Feb 02 '16 at 10:31

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.

answered Feb 02 '16 at 10:31

Ami Tavory

74,578
11
141
185

One can do slightly better than that by pruning partial paths that cannot lead to the destination. For example to go from (2,3) to (5,2) we know it takes at least 3 steps. If there are less then 3 steps available this path can be abandoned. – Henry Feb 02 '16 at 10:42
Thanks. Is it possible to enhance this algorithm by adding some constraints on the grid. For instance. if we want to go from (3, 2) to (5, 1) in 2 steps, there is no need to continue algorithm for some neighbours such as (2, 2), (2, 3) and (3, 3), since it is not possible to reach (5, 1) by using the remaining 1 step. In other words, can we specify some limits for the grid cells which might be visited for each recursive call? @Henry I added this comment for Ami. You are faster than me. Also, you explained what I want to say in a better way. Thank you as well. – Dorukhan Arslan Feb 02 '16 at 10:48
@Henry Yeah, excellent point, thanks! I'll add it when I'm at a computer. – Ami Tavory Feb 02 '16 at 11:07
@DorukhanArslan Yes, that is absolutely correct! Will edit when I can. – Ami Tavory Feb 02 '16 at 11:08
I modified your answer a little below. I mentioned about this implementation in the previous comment but still I may miss some other pruning possibilities. – Dorukhan Arslan Feb 02 '16 at 20:53
Good for you! – Ami Tavory Feb 02 '16 at 20:53

score 1 · Answer 2 · edited May 23 '17 at 10:28

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:

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.

Finding all possible paths of n length in hexagonal grid

2 Answers2

Linked