0

I am currently working on a project that requires us to help a character find an object within a maze, which is run through a GUI.

However, we can only access the nodes neighboring the location that the character is at, so we are unable to pre-process the maze and build the shortest path before moving the character.

We are given a helper method that returns the number of rows + cols (disregarding the walls that block the way) that each of the neighboring nodes are from this object we are looking for, so I have implemented a DFS and included a min-heap to first traverse the path with the neighbor that has the lowest distance.

Our problem is that sometimes, the path with the lowest distance may reach a dead-end, and we have to wait for it to complete an entire DFS of that branch until it can go back and search another path. Is there an algorithm that could circumvent this problem and reach the object in fewer steps?

Alan
  • 389
  • 3
  • 16
  • 3
    You could take advantage of the topology of the problem to prune branches that you can tell lead into a cul-de-sac, but in general, you might need to fully explore a branch to tell that it's a dead end. – user2357112 May 09 '16 at 21:41
  • Related: [Representing and solving a maze given an image](http://stackoverflow.com/questions/12995434/representing-and-solving-a-maze-given-an-image/12995815#12995815). – Matsmath May 09 '16 at 23:29
  • @user2357112: Thought provoking idea: One could consider the path taken thus far, and continuously attempt to (loosely) bisect the "possible" area. When you reach an edge, you can discard the entire section not containing the exit. This would be roughly O(log(n)). – Mooing Duck May 09 '16 at 23:42

0 Answers0