CODEWITHSUNDEEP
algorithmpath-finding
Moomba
Moomba

Reputation: 3

Finding all paths of length n between two points in a tile grid

I have a 2D tile-based map with two points which sit adjacent to each other. I would like to find all paths of length n between these two points (the points are always adjacent and the value of n would always be at least 3 so these would never be the shortest paths), with the possibility of excluding any path which passes through one or more arbitrarily defined points.

I've looked into many pathfinding algorithms, but am having trouble coming up with a way to modify them to return all paths with a precise length. Could someone point me in the right direction?

Upvotes: 0

Views: 1493

Answers (2)

Juan Lopes
Juan Lopes

Reputation: 10595

Simply run an exhaustive search. You can prune some branches that would never reach your destination anyway:

search(from, to, n):
    if from is outside boundaries: return
    if distance(from, to) > n: return
    if n == 0:
        if from == to:
            do something with your path
        return
    search(left of from,  to, n-1)
    search(right of from, to, n-1)
    search(up of from,    to, n-1)
    search(down  of from, to, n-1)

If your paths need to have no repeated points, just keep track as you would normally do with a DFS, but remember to unmark as visited when you exit a node (so you can visit it again in another path).

Upvotes: 0

Cort Ammon
Cort Ammon

Reputation: 10903

Finding all paths is unusual, so pathfinding algorithms probably will not help you here. You're really looking for a slow exhaustive search.

I'd start by using Dijkstra's algorithm to find the shortest path between your end node and every node within n steps. This will be useful later because it finds the shortest path from every node. Later, we can use that to prune useless paths.

Then I would begin an iterative search of the grid. At each step, keep track of the path it took to get there, call the length m. Remember that you will have many paths (potentially looping paths) to arrive at the same node. You'll want to keep all of them. At each iteration, look at the neighbors to the current node, and push new paths into the search which go to each neighbor which can reach the endpoint in n-m steps.

Eventually you'll run out of nodes which can possibly reach the endpoint, and you can simply look at all paths which reached the endpoint.

Upvotes: 1

Related Questions