aspose file tools*
The moose likes Beginning Java and the fly likes Problem in a Maze. Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Problem in a Maze." Watch "Problem in a Maze." New topic
Author

Problem in a Maze.

Martin Maarten
Greenhorn

Joined: Sep 15, 2009
Posts: 7
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
author
Sheriff

Joined: Sep 28, 2004
Posts: 18896
    
  40


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


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Martin Maarten
Greenhorn

Joined: Sep 15, 2009
Posts: 7
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
Ranch Hand

Joined: Oct 21, 2008
Posts: 142
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
Java Cowboy
Saloon Keeper

Joined: Aug 16, 2005
Posts: 14273
    
  21

Martin Maarten, welcome to JavaRanch.

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


Java Beginners FAQ - JavaRanch SCJP FAQ - The Java Tutorial - Java SE 8 API documentation
Maneesh Godbole
Saloon Keeper

Joined: Jul 26, 2007
Posts: 10451
    
    8

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.


[How to ask questions] [Donate a pint, save a life!] [Onff-turn it on!]
Martin Maarten
Greenhorn

Joined: Sep 15, 2009
Posts: 7
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
Ranch Hand

Joined: Jun 09, 2003
Posts: 4632
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
Greenhorn

Joined: Sep 15, 2009
Posts: 7
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.


[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
Marshal

Joined: Mar 22, 2005
Posts: 42291
    
  64
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?


Ping & DNS - my free Android networking tools app
Martin Maarten
Greenhorn

Joined: Sep 15, 2009
Posts: 7
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
Greenhorn

Joined: Sep 15, 2009
Posts: 7
WTB help on how to make a Robot remember where obstacle were and how to not go back there.

BUmp.

Sean Clark
Rancher

Joined: Jul 15, 2009
Posts: 377

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


I love this place!
Miklos Szeles
Ranch Hand

Joined: Oct 21, 2008
Posts: 142
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
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11422
    
  16

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.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Martin Maarten
Greenhorn

Joined: Sep 15, 2009
Posts: 7
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
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11422
    
  16

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.
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Problem in a Maze.