Pathfinding algorithm with specified distance/number of nodes

Question

I'm in need of an algorithm that would give me a path from start node to end node, but the path has to have an exact number of nodes, otherwise the pathfinding should fail.

To expand, I have a grid of tiles. The movement can only be to the immediately adjacent up, down, left or right tile (meaning, no diagonal movement). There are numerous rules to what tile can and can not be used in the path, but mostly it can be boiled down to a simple bool to tell if the tile can or can not be used (and this can be calculated before even starting the algorithm. The thing that is giving me trouble, though, is the fact that I have a specfied distance the path has to have, meaning, every move from one tile to the adjacent one is a distance of one, and the whole path should have a specified distance, no more, no less. Also, once a tile has been stepped on (but all tiles are available at the start of the algorithm), it can not be stepped on again, kind of like playing the old Snake game where you have to watch out not to eat yourself.

I've looked at Dijkstra/A* and I've googled algorithms for pathfinding, but all are, as far as I can tell, focused towards the shortest path, which doesn't do me much good. I don't care which path it is, just as long as it follows the aforementioned rules.

Have I missed something, does such and algorithm already exist, or is there an easy way to modify Dijkstra/A* to give this result? As I'm not a native english speaker, I may be using the wrong terminology, so I welcome keyword suggestions for this type of algorithm.

Here's an illustration of what I mean when I say it has to be and exact distance and can't use the same tile twice.

Let's say the distance has to be 7. Now let's mark the tiles that can be used in the path with O, the tiles that can't be used with and X, the starting point with S and the goal with E.

X X X X X X X
X O O E S O O
X O O O O O O

If there weren't a distance limitation, one could just go left and problem solved. If there were the distance limitation, but not the "can't step on the same tile" limitation, one could go down once, then left, then right, then left, then right, then left, then up and arrive at the goal. Since there are both the limitations, one would need to go right, down, left, left, left, up and then right to get to the goal. If the situation was like this, however, there would be no valid path.

X X X X X X X
X O O E S O O
X X O O O X O

In case it will be relevant, I'm developing this board game in C#.

As for the maximum distance, here's the range the distance will be in. The player will throw a dice and get a number 1-6. If the player gets a 6, he throws the dice again and if he gets another 6, again and again until he doesn't get a 6. The distance is the resulting number plus the number of items the player has picked up which could theoretically go up to 8, but will usually be 0-3, maaaybe 4.

On another note, I've just received new orders, the rules of the game changed to allow stepping on the same position twice in the same path which I believe simplifies the process a great deal, but I'll leave this question as is as I think it has nice answers that could help someone in that situation.

Answer 1

Now that the question has been updated with usual values of the distance...

So, at each time step, you have at most 4 choices, and there are at most 5+4 = 9 steps. That makes less than 4⁹ = 262 144 potential paths. Try brute-force first, and see how far it can go.

Also, note that repeatedly throwing a dice until you get something else than 6 is equivalent to drawing a random number between 1 and 5. Trivial on a comupter game, and there are physical such dice (google for "5 sided dice" images). Using a ten sided dice is also common.

Answer 2

Since you have a problem where each step has cost 1, a simple variant of depth-first search called depth-limited search should be able to find the kind of path you want. Naive version in Python:

def dls(path, goal, depth):
    last = path[-1]
    if len(path) == depth:
        if last == goal:
            return path
    else:
        for n in neighbors(last):
            if allowed(n) and n not in path:
                path.append(n)
                solution = dls(path, depth)
                if solution:
                    return solution
                path.pop()

# call as:
dls([start], goal, depth)

As others have noted, the problem is NP-complete, so don't expect miracles for longer path lengths.

Russell & Norvig is the definitive textbook for this kind of algorithms.

Answer 3

Since it is NP-complete, as pointed out by Haile, here is a heuristic in case your problem is small enough:

• Find peninsulas (i.e. parts of the graph connected to the rest by just one node) that do not contain S nor E and remove them.
• Find a shortest path P from S to E. If n is smaller than len(P), there is no solution.
• Now, do a depth-first search from S to E, using the following heuristic to choose which node to dig first. Let A be the current tile in the depth first search. In euclidian geometry, project the position of A on the line (SE) and call this point A'. Try to keep the ratio len(current path) / n close to len([SA']) / len([SE]). Or better, somehow "project" A on the path P to get A'' and keep keep the ratio len(current path) / n close to len([SA''] along P) / len(P).

We don't know much about the exact cases you will be handling, there are certainly more heuristics to add to discard parts of the depth-first search tree.

Answer 4

If there were a fast algorithm for this, you could plug in number of nodes = n and the algorithm would quickly tell you if there's a Hamiltonian Path. Since that problem is NP-complete, so is your problem.