Help with solving D&D maze using Java

Question

I been reading some of the other questions that have been posted on stackoverflow and I am a little overwhelmed by the number of search algorithms there are. I'm not looking for code and more of a page that goes over background of the algorithm and maybe some sudo code. I know there are algorithms like A* but due to lack of time I don't know if I would be able to complete the program with this algorithm. The maze is generated using a server program and the solver connects to the server in order to send commands to more the player piece. I do not have access to the methods within the server program. I have to solve a maze that has been created to be like a D&D maze. Here is a basic overview of the game:

A classical D&D computer game consists of a dungeon (maze), where the purpose of the game is to make one's way through the dungeon, entering at the "entrance" of the maze and exiting at its "exit". To make things more challenging, the layout of the dungeon is not known a priori and there are obstacles (zombies, tar-pits, and doors) that must be overcome by using objects (fares,ladders, and keys) that are found along the way.

I have notice that many of the other post do not have to worry about obstructions to completing the maze, would this be a major problem to adapt the algorithm to compensate for the obstructions? I was wondering if something like the right hand rule would be fine to solve the maze and if not what would be a algorithm that is as simple as possible to solve the maze(Due to the fact that I have to complete the program soon). Any other links would be great as I know that I have to complete this program again in Objective-C and I would like to implement something more powerful then the right hand rule when this happens. Thanks for any help.

Answer 1

well for simple mazes, you basically "walk" along a path until you get to an intersection. At that point you record all of your options. Then you choose one (using whatever heuristic you like, for you right-hand technique, you'd always "go right"). Once you've recorded the options, you stuff that on to a stack. You then continue forward.

When you read a dead end, you either "walk back", or if possible, simply pop the stack, choose another option and continue from there. To walk back, you simply record each move on the stack as well, and start unwinding the stack until you've reached the last intersection.

You can simply continue to do this, noting monsters and such as either something you can get through, or it you're missing an item, as a "dead end". You can then record these passable dead ends at the intersections so that if you ever come back to the intersection still looking for an exit, you can check your inventory for the "key" or "sword" or whatever you need to pass it. When you've come back, check the options for unexplored paths, and for paths blocked by things you can defeat. If you have the item that can defeat the monster, you can retake that route, defeat the monster and continue on.

I don't recall if this technique will work with mazes that have cycles. It should, since you should always be able to tell if you've visited a spot before, leave a trail of "breadcrumbs" behind you or recording locations you've seen.

It certainly won't tell you the optimal path, or the best scoring path, it will just get you to the exit whenever you bumble upon it.

You can also represent the dungeon as a connected graph in memory as you discover the intersections, with each node in the graph being an intersection, and with the path lengths (the number of steps) it takes between each node being the transitions in the graph. You can also represent obstacles in this graph as nodes.

So if you encounter a Vampire, it'll be a node with no exits at the end of a hall. Later, when you get the crucifix and wooden stake, you'll "know" where the Vampire is, and be able to traverse the graph back to the Vampire (assuming it's not moving, of course).

The trick is really building up this graph as you go and using stock graph traversal algorithms (of which there are many, and they're not that difficult) to navigate from one node to another.

But for traversing a simple maze, the stack technique works very well.

Addenda:

For simple mazes, a single stack should be sufficient. I don't know how your map is laid out or how you navigate it, etc.

But what you can do is every time you move, simply place the move on the stack. Then when you want to backtrack, you start popping the stack and go in the opposite direction of the move until you get back to an intersection, then go from there.

This is simply a "depth first" search of a tree that you don't know the layout of yet. But it's also important that you also keep track of where you been in some other way. For example, if you maze is represented as a large array of floor and wall pieces, you can capture the coordinates of each floor piece you entered on a simple list.

The reason for this is so that if there are cycles in the maze, you don't want to "walk forward" on to spaces that you've already walked on. Obviously you need to do that when backtracking. But when exploring, you need to know what you have and have not seen. How you track that is dependent on how the data structure of your map.

Consider this trivial maze:

# ########
# ########
# # #    #
# # #### #
# #a    b#
# # #### #
#   #    #
##### ####
#    c   #
# ########

You can see that you'll need to push on to the stack only at location a, b, and c. If you're able to mark the floor where you've been, your map might look like this at the first intersection:

#.########
#.########
#.# #    #
#.# #### #
#.#a    b#
#.#.#### #
#. .#    #
##### ####
#    c   #
# ########

And you stack would look like:

{d,d,d,d,d,d,d,l,u}

For 7 downs, one left, and one up.

If you can't mark the map, you could track the coordinates instead. It all depends.

Answer 2

I personally would try using recursion to find the path. You could have if statements to handle the traps and what not along with return statements to tell you the path.

  public static int recursion(int x, int y) {
    if (location == end) {
      return 0; //found the end
    }
    if (deadEnd) {
      //backtrack
    }
    if (trapName) {
      //put whatever you need to do to get around it
    }
    if (x+1 <= edge) {
      recursion(x+1,y); //Moves right
    }
  }

This is more or less pseudo code. Hope it helps though!