1

Given a multi dimensional array where X is a wall and * is the goal position. How would you find a path without getting suck in loops?

$map=
array( array("X","X"," ","*"),
       array(" ","X"," ","X"),
       array(" "," "," "," "),
       array(" ","X","X"," "));
Improve this question
2
  • 1
    Where do you start at? This is something a graph-traversal algorithm would be helpful at, I'm sure.
    – CBredlow
    Commented Sep 10, 2012 at 12:13
  • I'm wrong, a graph traversal wouldn't be optimal, a tree traversal (BFS or DFS) would be better here.
    – CBredlow
    Commented Sep 10, 2012 at 12:31

1 Answer 1

Reset to default
2

First, you will need a function that gives you the valid neighbors for each cell, or node.

Then, for finding the shortest way to the goal, Breadth First Search should do. If you start from the start location and expand nodes until you hit the goal, you will always find the shortest path (if any). Alternatively, you can start from the goal and expand until you cover the entire map and you will have the shortest path to the goal for every starting location (this of course only makes sense if the goal is not moving).

For not getting stuck in loops, the most important aspect is to keep a list (or set, or map, or whatever) of the nodes that have already been expanded.

For more complex maps, or when different "costs" for certain paths come into play, you might rather use A* or Dijkstra's Algorithm.

Improve this answer
0

Not the answer you're looking for? Browse other questions tagged or ask your own question.