I am attempting to create a pathfinding algorithm for a game. Basically, after the player rolls a number, I need to determine all possible locations that the player can end up on a grid. The player cannot move directly backwards after a given step, and the player can only move one grid square per step.
The problem is, right now I am attempting to brute force the solution by recursively navigating along the graph and manually checking each valid move.
Pseudocode:
// Recursive function for navigating one step at a time.
function navigate($stamina, $coords, $coords_previous)
{
// If the movement stamina has not been spent.
if ($stamina != 0)
{
// Note: there may be less than four neighboring
// cells in a given location due to obstacles.
foreach ($neighboring_cells as $coords_neighboring)
{
// If the coordinates of the neighbor are not the same as the
// coordinates of the previous move (we can't move backwards)
if ($coords_neighboring != $coords_previous)
{
$stamina--;
// Recurse.
navigate($stamina, $coords_neighboring, $coords);
}
}
}
else
{
// No more stamina.
// Add $coords to our array of endpoints.
}
}
This works for small rolls (low $stamina values). However, as $stamina increases, this methodology starts to become super redundant. This is due to the fact that the player can move in circles over and over again, exponentially increasing the number of potential endpoints.
My question is, what can be done to decrease redundancy in the above function?
Define a state as a combination of a grid position and a facing (i.e., the direction the player moved in to get there). This is useful because we can define successors of a given state: in particular, those at adjacent grid positions (with appropriate facings) other than the one the player just came from.
Then compute the set of states reachable in n steps. For n=0, this is just the player's initial position (with a special "no facing" value if the first move can be in any direction). To compute it for n+1, generate all valid moves from each of the states in the previous set, discarding any duplicates. When you reach the set for $stamina steps, just discard the facings (and any duplicate positions).
This is similar to a breadth-first search on a graph whose vertices are the states and whose edges connect a state to its successor states. However, here we don't disregard new (longer) paths to a state, since some positions might be reachable (in exactly $stamina steps!) only via looping back. One could also include the remaining stamina in the state (and define no edges away from a state with 0 moves left); then you would perform a normal graph search and collect all the leaves.
In either case these would probably be implicit graphs, but the algorithm is clearer implemented directly rather than in terms of a graph.