CODEWITHSUNDEEP
javarecursionstack-overflowmaze
Pierre
Pierre

Reputation: 330

Recursion with maze solver

The project is to code a maze solver in Java using recursion and a tree (I'm using my own linked list, not exactly sure if it's a tree but I don't mind that).

The lecturer never explains anything, so I get all my knowledge online. I'm having trouble with my recursive method, I'm not sure what to do since I can't find an example that can relate to my project

In my linked list, I have links to the node on the right, left, bottom and top. If there is for example a wall on your right, the link would be null. I also have booleans in the linked list wallRight, wallLeft, wallBottom and wallTop to see if there is for example a wall to the right. So if there was a wall to the right, the "Right" link would be null and wallRight would be true.

I also use Labels which are images, so if I landed on a spot, an image shows. I made a method that if I'm on position 1, it makes label 1 display, so in the recursive methods I use the int pos to know which label to display.

Now comes the trouble with my recursive method. I have tried it two ways, but neither work. Here is both of them:

public boolean move(Maze rigting,int pos) // Righting = direction
{
   if(rigting.goal == true)
       return true; //BASE CASE - tests if it is on the goal node

   else if(rigting.wallR != true) //checks if there is a wall on the right
   {
       pos += 1;
       move(rigting.right, pos); //moves right

       showLabel(pos);
       return true;
   }

   else if(rigting.wallD != true) //checks if there is a wall below
   {
       pos += 10;
       move(rigting.down, pos); //moves down

       showLabel(pos);
       return true;
   }

   else if(rigting.wallL != true) //checks if there is a wall on the left
   {
       pos -= 1;
       move(rigting.left, pos); //moves left

       showLabel(pos);
       return true;
   }

   else if(rigting.wallU != true) //checks if there is a wall above
   {
       pos -= 10;
       move(rigting.up, pos); //moves up

       showLabel(pos);
       return true;
   }

   return false; //I know this return is incorrect, but it won't run without one
 }

public boolean move(Maze rigting,int pos) //Righting = direction
{
    if(rigting.goal == true)
        return true;

    return (rigting.wallR != true) ? move(rigting.right, pos += 1) : false ||
    (rigting.wallD != true) ? move(rigting.down, pos += 10) : false ||
    (rigting.wallL != true) ? move(rigting.left, pos -= 1) : false ||
    (rigting.wallU != true) ? move(rigting.up, pos -= 10) : false;
}

Both of these give stackoverflow exceptions...
I think my error is that, if there is a wall on the right, then the link Right is null. If I could somehow make it that none of the links are null, then I wouldn't need the booleans wallRight etc, but I have no idea how to implement that.

I would really appreciate it if you could send me in the right direction! I only need to hand in the project on 10 October, so if I'm doing it completely wrong, I don't mind starting over!

Upvotes: 0

Views: 1215

Answers (1)

Andy
Andy

Reputation: 1994

Since this is your homework, I won't give you a solution here, but some hints.

  1. Your first solution does not consider the result of subsequent calls to move(), therefore the recursion only ends, if you reached the goal (accidentially).
  2. In your second solution you consider the result, but are not prepared for a case, where you are moving in a loop. You need to mark the nodes you already visited and break there (with return value false).

For recursion it's best to start with the break-condition (as you did), and then implement one simple case (e.g. always go right). After managed the simple case you can add others (branches)

Upvotes: 1

Related Questions