This week's book giveaway is in the OCPJP forum. We're giving away four copies of OCA/OCP Java SE 7 Programmer I & II Study Guide and have Kathy Sierra & Bert Bates on-line! See this thread for details.
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.
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.
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.
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.
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.
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.
Joined: Sep 15, 2009
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.
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.
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.
Joined: Sep 15, 2009
WTB help on how to make a Robot remember where obstacle were and how to not go back there.
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.
I love this place!
Joined: Oct 21, 2008
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.
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
Joined: Sep 15, 2009
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?
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.