Problem in a Maze.

[Martin Maarten]

Hello folks, I got a question for you all.

I have made a maze in the program BlueJ see Screenshot



The goal is that the Robot (triangle) will find it's own way to the ball, while finding the way
he has to remember where dead end's/obstacles were, so he will find the way back in one smooth path
and won't walk into dead end's nemore.

My question now is that i got no idea how to put it into write it in Java language how my robot will remember
were the obstacles were.

Would be so great if somebody could help me on this.

Greetings,

Sala.

[Henry Wong]

I remember one solution to this problem, was to, when ecountering a fork on the road, to always take the right most fork (by right, I mean right most relative to the moving object).

Henry

[Martin Maarten]

That's not really my question henry.

If he just goes right on a fork all the time he might end up @ the end but he will also go back into the same dead end's
he was in before.

I want him to find his way to the ball and remember all obstacles so he will not go back in there.
This will also lead to know the way excatly when he goes back to it's starting position after he went to the ball.

Maybe also gimme some Written code if possible, so i can check stuff out i'm not that great with java yet only just started so
by saying stuff i don't really think i ll be able to make code out of it yet.

Greetings,

Sala.

[Miklos Szeles]

Henry: the right hand rule not always gives a solution. Imagine a labyrinth where the exit is in the middle and you can walk around in that case you will go round and round without finding the exit.
Martin: For example you can represent the labirynth as a graph, and then you can use some graph algorithm to find a route from the start to the end.

[Jesper de Jong]

Martin Maarten, welcome to JavaRanch.

When you create a new topic, please use a meaningful subject line instead of something like "A question".

[Maneesh Godbole]

For a human, that's a grid with allowed track(green) and walls(?) in red. For the robot those are just grid cells.
A grid indicates co-ordinates.

You can always maintain a collection of cul de sac co-ordinates when you encounter them. At each robot move you can figure out if this is a blocked path or else.

Maybe also gimme some Written code if possible...

I am sorry. This is not the way we do it here at the Ranch. We do not believe in handing out ready made code.
However, if you post your code, and tell us what your problem is, we will be more than eager to point you in the right direction.

[Martin Maarten]

Ok no ready made code i understand, but still my real question is how do i get my robot to
remember where the obstacles he encountered were. So he will not go back there.

It's basically that he tries to find the way to the ball by randomly trying out pahts on it's way to the ball. When he encounters dead end's he will remember the
coords of them and will not go back in there.

So on it's way back it should have a way smoother path back to it's startin position.

Also i haven't started with the code yet cuz i really got no idea =P.

Greetings,

Sala

[Michael Dunn]

in the Programming Diversions forum, the July 2003 Newsletter was a Maze Solver problem,
with a lot of interesting solutions.

you should find it with a search, then see if you can understand how they work.

[Martin Maarten]

Too be honestly the stuff in That newsletter it's all WAY too complicated for me. I got some packages that are already programmed for me etc.
And i need to let this robot do something smart. So i wanted it to find a way in the maze but with simple code.

import world.Robot;


public class RobotDertien extends Robot
{
//make Global Variables
int gox; //the x position where the Robot has to go
int goy; //de y position
int backy = 1; // de y position where the next Ball has to be placed down
    public RobotDertien(String s)
    {
        super(s);
    }
    
    public void hoofdProgramma()
    {            
    //start de loop
    while(true)
    {
        //controleer of karel op de plaats is waar hij de piepbal terug moet leggen
        if(pos_x == 1 && pos_y == backy)
        {
            if(hasBall())
            {
            putDownBall();
            backy++;
            }
            if(!scanBall())
            {
                turnSouth();
                step();
                say("All balls are returned");
                turnNorth();
                break; //Stops the program
            }
        }
        
        //Go east if the destination of the Robot is to his right
        if(pos_x < gox)
        {
            turnEast();
            step();
        }
        //Go west if the destination of the Robot is to his left
        if(pos_x > gox)
        {
            turnWest();
            step();
        }
        //Go north if the destination of the Robot is above him.
        if(pos_y > goy)
        {
            draaiNaarNoord();
            stap();
        }
        // ga naat het zuiden als de bestemming onder karel is
        if(pos_y < goy)
        {
            turnSouth();
            step();
        }
        //If Robot stands on a Ball he will grab the ball unless he already has a Ball
        //and then change the coordinates of where the ball has to be put down.
        if(onBall() && !notHaveBall())
        {
            grabBall();
            goy = backy;
            gox = 1;
        }
        
        
    }
    }
    //This method scans for Balls, sets the destination the Ball position, and says if there are more Balls that can be found.
    public boolean scanBall()
    {
        boolean succes = false;
         for(int x = 2 ; x <= 18 ; x++)
        {
            for(int y = 1 ; y <=18 ; y ++)
            {
      if(myWorld.Ball(x,y))
      {
          gox = x;
          goy = y;
          succes = true;
        } 
        
    }
    }
    return(succes);
}
//Below here the code that make the Robot turn to different sides.
     public void turnNorth()
    {
        while ( compas()!=0 )
        {
         turnRight();
        }
    }
    public void turnSouth()
    {
        while ( compas()!=2 )
        {
         turnRight();
        }
    }
    public void turnEast()
    {
        while ( compas()!=1 )
        {
         turnRight();
        }
    }
    public void turnWest()
    {
        while ( compas()!=3 )
        {
         turnRight();
        }
    }
}

[edit]Add code tags. CR. Please always use the "code" button[/edit[




This is my Lvl of coding this is some other programming but it shows you @ what lvl i am working at.
Now is it possible to let this robot find the way remember obstacles and go back in 1 smooth path to it's starting point.

[Ulf Dittmer]

It's a bit hard to figure out what the code is supposed to be doing due to the non-English methods, field names and comments; it might be helpful to folks here if that was changed.

What does method "stap" do?

[Martin Maarten]

I translated it into english, i hope it's more understandable.
stap(); just means it does a step forward.

But to be honestly it doesn't really matter to figure out what that program does cuz it's just an example of what lvl of programming i am at
on this lvl i want tips on how to get a robot remember where obstacles where and that he will not go back in there.

[Martin Maarten]

WTB help on how to make a Robot remember where obstacle were and how to not go back there.

BUmp.

[Sean Clark]

Hey,
I would suggest rather than trying to remember where all the dead ends are, it makes more sense to remember where the forks are.

So when you hit a fork, remember it and choose one of the directions, and keep doing this at every fork. if you hit a dead end then backtrack to the last fork and try the other way (or others) if you have tried all possibilities on that fork then backtrack to the fork before etc.

You will systematically eventually reach your goal.

That's my initial thoughts anyway.

Sean

[Miklos Szeles]

Hi Martin,

If you can't figure out a solution I think first you should search the internet(or some books) to find algorithm which can traverse the labyrinth. These algorithm will show you what to store and how to do things. Then you should try to implement the algorithm in Java and then if you have any problem with the implemenation you can post the code here and we can help to you.

[fred rosenberger]

I think Sean is right. the ONLY thing that matters is a fork. if there is no decision, you don't care, you just keep moving forwards. Only when you get to a fork do you need to pay attention to anything.

What i'd probably try (and I don't know if this works or how efficient it is) would be to create a fork object that records the position (on an x,y coordinate), what the options are, and what one's i've taken.

so when you arrive at the first fork (on your graph, about 2/3 down the right wall), you need to store that you could go straight or right, then pick one, and mark that you've taken it. I'd push that object onto a stack.

If i reach a dead end, pop the top object off the stack, reset the robot to there, and choose a new direction.

Each time you come to a fork, you would probably need to check to see if you've been there already, since your maze allows loops.

If you need to find the most EFFICIENT way, you'll need to do something more. again, the loops in your maze make it more complicated. you'd need basically a tree. at each intersection, you'd have a new node on the tree. Each path in the maze would take you down a level in the tree, and you'd have to build the entire thing. Then, you'd have to search the tree for the shortest path.

[Martin Maarten]

I can make the maze how i want it to look that's no problem =P.
So you suggest i make it easier the maze?

[fred rosenberger]

I am not suggesting you make the maze easier... you just need to take into account the fact that with loops, you can return to a point you've already visited, or else you could get stuck in an infinite loop and never get the solution.

Whether the maze should have loops or not isn't up to me.

If you're just learning how to program, it might be easier to not have them first and solve it. Once you've figured that out, maybe put them back in and leverage your working code to deal with them.