wood burning stoves 2.0*
The moose likes Beginning Java and the fly likes How to implement the wall follower algorithm in java? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "How to implement the wall follower algorithm in java?" Watch "How to implement the wall follower algorithm in java?" New topic
Author

How to implement the wall follower algorithm in java?

Michael Nana
Greenhorn

Joined: Feb 10, 2012
Posts: 17
Hey guys,

I'm new here. Well I'm working on my homework in java which is about implementing a rat that will traverse through the maze and exit.
So for my second rat I want to implement a left hand or right hand wall follower rat. i.e the rat will always check to see if there is a wall on the right and move along it.

The problem is I don't see how I can implement it. The reason I say this is because the rat is just a simple dot. I can't really tell it to move forward. I can say move up which is incrementing the rows or move right which is incrementing the cols so I reall can't figure out the wall follow algorithm.

I know I would need direction but every implementation of direction I have made so far just gets my rat stuck.

I'm looking for someone to help me understand the algorithm and how to implement it, like some sort of pseudo code and explanation. That would be greatly appreciated.

This may help as well. This is how the maze looks like.
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
F X X
X XX XXX X XXXXXXXXXXXXXXXXX X
X X XXX X X X
XX X XXX XXXXX XXXXXXXXXXXXX X
XX X XXX X
XX X XXXXXXXXXXXXXXXXXXXXXXX X
XX X XX X XXXX X
XX X XX XXXXXXXXXXXXXXX XXXX X
X X XX X X
X XX XXXXXXXXXXXXXXXX X XXXXXX
X XX X XXXXXX
X XXXXXXXXXXXXXXXXXX XXXXXX
XXXXXXXXXXXXXXXXXXXXXXX XXXXXX
XXXX XXX XXXXXX
XXXXXXXXXXXXX XXXXXX XXXX
X X
X XXXXX XXXXXXXXXXXXXXXXXXXX X
X XXXXX X X X XXXXXXXXX X
X X X X XXXX X XXXXXXXXX X
X XXXXX X X X X X X
X X X X X XXXX XXXXXXXXX X
X X XXXXX X X XXXX XXXXXXXXX X
X X X X
X XXXXX X XXXXXXXXXXXXXXXXXXXX
X X X X
X X XXXXX XXXX XXXX XXXXXXXX X
X X XXXX XXXX X X
XSXXXXXXXXX X X X XX X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Where the x are the walls.

So yeah, thanks in advance.
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Michael Nana wrote:
The problem is I don't see how I can implement it. The reason I say this is because the rat is just a simple dot. I can't really tell it to move forward. I can say move up which is incrementing the rows or move right which is incrementing the cols so I reall can't figure out the wall follow algorithm.


It sounds like the mistake you're making is a very common beginner one. You're tying your internal data representation too tightly to your visual representation. That is, you're treating your Model and your View as if they're the same thing, when they're not.

You can implement the algorithm without any UI whatsoever--no GUI, no console, nothing but a data structure that no human ever sees. You should figure out how to do that first, and then, once that's working, figure out how to display it.

I will tell you this, however: Don't try to display it as a moving dot in a terminal window. While that is possible, it's not reliably portable, and it's probably a bigger hassle than you want to deal with. For the display part of it, you could either redraw the entire maze each time (like a flip book), or use a GUI (which is another whole can of worms altogether.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7064
    
  16

Michael Nana wrote:This may help as well. This is how the maze looks like...

Erm...a mess?

Try UseCodeTags; and for your basic question, there's a lot of stuff in Wikipedia about it.

Winston


Isn't it funny how there's always time and money enough to do it WRONG?
Artlicles by Winston can be found here
Michael Nana
Greenhorn

Joined: Feb 10, 2012
Posts: 17
Jeff Verdegan wrote:
Michael Nana wrote:
The problem is I don't see how I can implement it. The reason I say this is because the rat is just a simple dot. I can't really tell it to move forward. I can say move up which is incrementing the rows or move right which is incrementing the cols so I reall can't figure out the wall follow algorithm.


It sounds like the mistake you're making is a very common beginner one. You're tying your internal data representation too tightly to your visual representation. That is, you're treating your Model and your View as if they're the same thing, when they're not.

You can implement the algorithm without any UI whatsoever--no GUI, no console, nothing but a data structure that no human ever sees. You should figure out how to do that first, and then, once that's working, figure out how to display it.

I will tell you this, however: Don't try to display it as a moving dot in a terminal window. While that is possible, it's not reliably portable, and it's probably a bigger hassle than you want to deal with. For the display part of it, you could either redraw the entire maze each time (like a flip book), or use a GUI (which is another whole can of worms altogether.


Hey Jeff,
thanks for the quick reply. I kind of understand what you're saying. The thing is the maze is already given in the assignment fully implemented as well as the rat. I can alter the maze or the rat. All I can do is write an algorithm that will allow the rat to find the exit of the maze.
Michael Nana
Greenhorn

Joined: Feb 10, 2012
Posts: 17
Winston Gutkowski wrote:
Michael Nana wrote:This may help as well. This is how the maze looks like...

Erm...a mess?

Try UseCodeTags; and for your basic question, there's a lot of stuff in Wikipedia about it.

Winston


Yeah I read that and have tried to implement it but I can't figure out how you keep on hand on the left or right wall and tell the right to move forward.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7064
    
  16

Michael Nana wrote:thanks for the quick reply. I kind of understand what you're saying. The thing is the maze is already given in the assignment fully implemented as well as the rat. I can alter the maze or the rat. All I can do is write an algorithm that will allow the rat to find the exit of the maze.

Then do it; and, as Jeff says, don't worry about how it looks.
Understand how to solve the problem and then apply it to the classes you've been given. And, as with most advice I give to newbies here:
Turn off your computer.

Until you've worked out, on paper, how to solve the problem, any code you write is going to be bad.

Winston
Michael Nana
Greenhorn

Joined: Feb 10, 2012
Posts: 17
Winston Gutkowski wrote:
Michael Nana wrote:thanks for the quick reply. I kind of understand what you're saying. The thing is the maze is already given in the assignment fully implemented as well as the rat. I can alter the maze or the rat. All I can do is write an algorithm that will allow the rat to find the exit of the maze.

Then do it; and, as Jeff says, don't worry about how it looks.
Understand how to solve the problem and then apply it to the classes you've been given. And, as with most advice I give to newbies here:
Turn off your computer.

Until you've worked out, on paper, how to solve the problem, any code you write is going to be bad.

Winston


Thanks that's good advice. But now, before I do how is the wall follow algorithm implemented ?
Viktor Kubinec
Ranch Hand

Joined: Jan 28, 2012
Posts: 34
Hi,

I suggest to track everything in two dimensional array e.g.



use different numbers to mark walls(e.g -1), roads(e.g. 0), rat(e.g. -2)

following wall means that you are touching wall with your left or right hand. If you are touching wall with your right hand it means you prefer to turn righ :
if you can go right go right
else if you can go forward go forward
else if you can go left go left
else if you can go back go back
else - oO there are walls all around you

To know what right, left, forward, back means, you need to remember your direction. you can remember your direction as a two dimensional vector (current_x - previous_x, current_y - previous_y) and use rotation matrix transformation to determine what is left,right,back,forward. If you don't want to use matrix transformations ( easy to find on google) you can also just write code for every option (there are only four options so its not so much to do).

Just follow these rules until current_position != target_position
If I remember right wall follower algorithm doesn't find always the solution - you can end up in infinite loop (but maybe i remember wrong) - so its good to bound maximum moves count with some big enough number to avoid infinite loop.

Good luck!
Michael Nana
Greenhorn

Joined: Feb 10, 2012
Posts: 17
Viktor Kubinec wrote:Hi,

I suggest to track everything in two dimensional array e.g.



use different numbers to mark walls(e.g -1), roads(e.g. 0), rat(e.g. -2)

following wall means that you are touching wall with your left or right hand. If you are touching wall with your right hand it means you prefer to turn righ :
if you can go right go right
else if you can go forward go forward
else if you can go left go left
else if you can go back go back
else - oO there are walls all around you

To know what right, left, forward, back means, you need to remember your direction. you can remember your direction as a two dimensional vector (current_x - previous_x, current_y - previous_y) and use rotation matrix transformation to determine what is left,right,back,forward. If you don't want to use matrix transformations ( easy to find on google) you can also just write code for every option (there are only four options so its not so much to do).

Just follow these rules until current_position != target_position
If I remember right wall follower algorithm doesn't find always the solution - you can end up in infinite loop (but maybe i remember wrong) - so its good to bound maximum moves count with some big enough number to avoid infinite loop.

Good luck!


Thanks a lot Vitor, that helps a lot. I wanted to know is forward the same as up ? like rows-- ?
Michael Nana
Greenhorn

Joined: Feb 10, 2012
Posts: 17
Viktor Kubinec wrote:Hi,

I suggest to track everything in two dimensional array e.g.



use different numbers to mark walls(e.g -1), roads(e.g. 0), rat(e.g. -2)

following wall means that you are touching wall with your left or right hand. If you are touching wall with your right hand it means you prefer to turn righ :
if you can go right go right
else if you can go forward go forward
else if you can go left go left
else if you can go back go back
else - oO there are walls all around you

To know what right, left, forward, back means, you need to remember your direction. you can remember your direction as a two dimensional vector (current_x - previous_x, current_y - previous_y) and use rotation matrix transformation to determine what is left,right,back,forward. If you don't want to use matrix transformations ( easy to find on google) you can also just write code for every option (there are only four options so its not so much to do).

Just follow these rules until current_position != target_position
If I remember right wall follower algorithm doesn't find always the solution - you can end up in infinite loop (but maybe i remember wrong) - so its good to bound maximum moves count with some big enough number to avoid infinite loop.

Good luck!


Also the 4 options ...

Are you talking about this ?

if you can go right go right
else if you can go forward go forward
else if you can go left go left
else if you can go back go back
else - oO there are walls all around you

Ryan Sykes
Ranch Hand

Joined: Jan 18, 2012
Posts: 58
Michael...no, he was referring to 4 options being that there are 4 options for the direction in which you moved based on your last and current (x,y) co-ordinates. With the knowledge of those 2 co-ordinates, you should be able to calculate what direction is left/right for the rat. Either you could do it using transformation matrix operations on the co-ordinates in a single shot, or you could have if-then statements (4 sets) to check based on the 2 (x,y) co-ordinates which direction you are traveling.

Once you know which direction is the rat's right at the current location, you then use this algorithm to determine where it goes next and update the current/previous x,y co-ordinates accordingly:

if you can go right go right
else if you can go forward go forward
else if you can go left go left
else if you can go back go back
Michael Nana
Greenhorn

Joined: Feb 10, 2012
Posts: 17
Ryan Sykes wrote:Michael...no, he was referring to 4 options being that there are 4 options for the direction in which you moved based on your last and current (x,y) co-ordinates. With the knowledge of those 2 co-ordinates, you should be able to calculate what direction is left/right for the rat. Either you could do it using transformation matrix operations on the co-ordinates in a single shot, or you could have if-then statements (4 sets) to check based on the 2 (x,y) co-ordinates which direction you are traveling.

Once you know which direction is the rat's right at the current location, you then use this algorithm to determine where it goes next and update the current/previous x,y co-ordinates accordingly:

if you can go right go right
else if you can go forward go forward
else if you can go left go left
else if you can go back go back


Ok ok I see. Now how do I use x y co-ordinates when I'm referring to an 2d array that uses cols and rows ?
Ryan Sykes
Ranch Hand

Joined: Jan 18, 2012
Posts: 58
use the col, row indices as x, y?
Viktor Kubinec
Ranch Hand

Joined: Jan 28, 2012
Posts: 34
No forward is not up...

forward is the direction you have moved last step. It could be any direction (up, down, left, right). Therefore you ned to remember this direction. So it is good to remember your last and current position to know the direction.

It is relative what is right left up and down it depends how you imagine the array. So lets agree that [0,0] is left top corner and [size_x,size_y] is bottom right corner. Than it means that from visualization perspective:

direction [0,1] is right
direction [0, -1] is left
direction [1,0] is down
direction [-1,0] is up

but the left,right (diferent lef and right than on the visualization),forward, backward for the rat is relative on his (lets assume its he ;) ) current direction, which means

if his current direction is [0,1], than his relative right direction is [1,0], his relative forward direction is [0,1], his relative left direction is [-1,0], and relative backward direction is [0,-1]

same you have to think of for all other direction

So for example rats last position was [5,4] , rats current position is [5,5], so rats direction is [5,5] - [5,4] = [0,1] .
as we assume rat preffer to go right so to change direction to [1,0], which means that if [6,5] ( = [5,5] + [1,0]) is road he will move there,
if its not road he will try to go forward ,forward direction is [0,1], so if [5,6] (=[5,5]+[0,1]) is road he will move there, if also this field is no a road (its a wall)
he will try to go left, left direction is [-1,0], so if [4,5] is road he will move there, if its a wall, he will try to go backward
backward direction is [0,-1], so he will try to go to [5,4], and if also this one is no a road he is stucked (but this one is not a wall because its his last position)

So what you need to do is to define relative direction for every direction. As I wrote before this can be also easily done with matrix transformations, but I don't know your level of algebra and if you dont know about these transformation stay rather with hardcoded directions and relative directions.

Darryl Burke
Bartender

Joined: May 03, 2008
Posts: 4523
    
    5

Micheal, please BeForthrightWhenCrossPostingToOtherSites
http://au.answers.yahoo.com/question/index?qid=20120210075339AAwDYV6
http://www.java-forums.org/new-java/55382-how-implement-wall-follower-algorithm-java.html
http://www.javaprogrammingforums.com/java-theory-questions/13915-how-implement-wall-follower-algorithm-java.html


luck, db
There are no new questions, but there may be new answers.
Michael Nana
Greenhorn

Joined: Feb 10, 2012
Posts: 17
Viktor Kubinec wrote:No forward is not up...

forward is the direction you have moved last step. It could be any direction (up, down, left, right). Therefore you ned to remember this direction. So it is good to remember your last and current position to know the direction.

It is relative what is right left up and down it depends how you imagine the array. So lets agree that [0,0] is left top corner and [size_x,size_y] is bottom right corner. Than it means that from visualization perspective:

direction [0,1] is right
direction [0, -1] is left
direction [1,0] is down
direction [-1,0] is up

but the left,right (diferent lef and right than on the visualization),forward, backward for the rat is relative on his (lets assume its he ;) ) current direction, which means

if his current direction is [0,1], than his relative right direction is [1,0], his relative forward direction is [0,1], his relative left direction is [-1,0], and relative backward direction is [0,-1]

same you have to think of for all other direction

So for example rats last position was [5,4] , rats current position is [5,5], so rats direction is [5,5] - [5,4] = [0,1] .
as we assume rat preffer to go right so to change direction to [1,0], which means that if [6,5] ( = [5,5] + [1,0]) is road he will move there,
if its not road he will try to go forward ,forward direction is [0,1], so if [5,6] (=[5,5]+[0,1]) is road he will move there, if also this field is no a road (its a wall)
he will try to go left, left direction is [-1,0], so if [4,5] is road he will move there, if its a wall, he will try to go backward
backward direction is [0,-1], so he will try to go to [5,4], and if also this one is no a road he is stucked (but this one is not a wall because its his last position)

So what you need to do is to define relative direction for every direction. As I wrote before this can be also easily done with matrix transformations, but I don't know your level of algebra and if you dont know about these transformation stay rather with hardcoded directions and relative directions.


I have been trying to implement what you are saying.
So I was wondering do I make 4 different methods for the 4 different options left, right forward and back
Ryan Sykes
Ranch Hand

Joined: Jan 18, 2012
Posts: 58
I don't think you can get any clearer pseudocode than what Viktor has been nice enough to post. There are several different ways to implement things. It doesn't matter if you write 4 different methods or implement a single Move method, what matters is how you implement it. It is up to you to try and implement the logic. You can always post specific code if you are stuck with something specific.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7064
    
  16

Michael Nana wrote:I have been trying to implement what you are saying.
So I was wondering do I make 4 different methods for the 4 different options left, right forward and back

There are two separate things going on here:
1. Your current direction (personally, I like North, South, East and West; but Left, Right, Up and Down are perfectly reasonable).
2. A choice of turn (ie, a change of direction): Left, Right, Back or None.

And I think, if I was doing it, I'd probably use enums: A Direction enum, pretty much as Viktor described, but with an after() method that returns the new Direction after applying a turn; and a Turn enum which is used by after() to change Directions.

That way your code would end up looking something like:which seems pretty clear to me.

Winston
Michael Nana
Greenhorn

Joined: Feb 10, 2012
Posts: 17
Ahhhhhh ok. Disregard that code. I now understand what you guys where meaning by a vector. Back on it will update later.
Michael Nana
Greenhorn

Joined: Feb 10, 2012
Posts: 17
So i tried starting off with this code but it doesn't seem to work. I don't understand why my facing is never updated.
Michael Nana
Greenhorn

Joined: Feb 10, 2012
Posts: 17
I also tried this. Doesn't work too.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7064
    
  16

Michael Nana wrote:I also tried this. Doesn't work too.

Have a look at your code. What you've done is ensure that both currentRow-previousRow and currentCol-previousCol are 1, yet your code never checks for that combination.

I think you're still looking at this far too procedurally: "first I do this; then I do this...", and I suspect you're in for a long slog if you continue down this path.
What you need to do is to get objects working with each other. Did you look at setting up a Direction enum as I suggested?

Another thing that might be worth thinking about is to have your Maze class keep a currentPosition. There is a very useful class called java.awt.Point, which you can use to store a 2D-Point in (x, y) form. That way you can pass positions around without endless references to rows and columns.

Also, I would think that a method like move() would be in your Maze class, rather than acting on it; but it's only my opinion.

Just a few thoughts.

Winston
Meshulam Silk
Greenhorn

Joined: Feb 12, 2012
Posts: 22
Hey man I made a (pretty bad) grid based game and the first thing I did was create a coordinates class which contains (obviously) simple x and y members (you can make getters/setters for them if you like).
Then to "easify" movement (both the player's and the ai, which is what I think you need) I made another class called "dir" (direction) which also contains x and y members. The only difference is that in dir the x/y can only be 1, 0 or -1.
You can see that for a dir to signify "up" the x value is 0 and the y is -1 (2d arrays work like that) and so on.
Now to "add" a dir to a coordinate I made a very simple method in the coordinates class called addDir which receives a dir, gets the x and y of the dir and adds them to the x and y of the coordinate. Very simple.

If you don't get it tell me and I'll try to provide some more examples, maybe even a couple of videos with explanations.

Good luck!

Edit: like a couple of people said, remember there's a difference between having a blue dot at (5, 5) and showing a blue dot at (5, 5). First make the logic (the brains of the rat in your case) and then do the graphics. You'll find it's a lot easier. Also I don't consider myself an experienced programmer so if anyone has any input regarding my system I'd be happy to hear.
dennis deems
Ranch Hand

Joined: Mar 12, 2011
Posts: 808
Winston Gutkowski wrote:I think you're still looking at this far too procedurally: "first I do this; then I do this...", and I suspect you're in for a long slog if you continue down this path.
What you need to do is to get objects working with each other.

This.

I disagree, however, with suggestion that the maze should store a current position. That is not maze-appropriate behavior. Some other object that traverses the maze should store the current position.
Michael Nana
Greenhorn

Joined: Feb 10, 2012
Posts: 17
Hey guys, well thanks for all your help. After a lot of think I just came out with this and it worked

David Stephansen
Greenhorn

Joined: May 14, 2012
Posts: 1
Hey, members!

I have the same problem. I have to admit that I am a Newbie. Since I have most experience in C#, i try to implement it there. I have used your code and translated it into c# language. My "maze" class is called "_GridNode". When I tried to play, after a few steps my rat isnt going further and remains in a loop. ( e.g. up and down). My question is: the variables currentCol respectively currentRow... are these dynamically changin (=view point of the rat) or are they the right north-oriented directions, which means they only represent the coordinates without any orientations? And the Output of the code are only the new x and y -values for the rat in the maze- Am i correct?

According to my code:

North:= Nodewalls[1]
East:= Nodewalls[2]
South:= Nodewalls[3]
West:= Nodewalls[0]

I have the following coding used: _GridNode[x,y].Nodewall[1]=0 ... would mean that northern field is possible to visit.

m.xcoordinate and m.ycoordinate are the start coordinates of the rat... they are previously generated randomly.

"m" is an instance of the class rat.

My code is the following, if it helps:



Thanks in advance,
br David
Jordan D. Williams
Ranch Hand

Joined: Jan 03, 2012
Posts: 51

Michael Nana wrote:Hey guys, well thanks for all your help. After a lot of think I just came out with this and it worked



Hey there!

I am much newer to Java than you are and this maze solving is really interesting. I understand the code algorithm though at least at a basic level. Do you mind posting the rest of the code for the complete application? I would like to be play with it and experiment and see how the maze and the rat were set up etc. Thanks! I appreciate your consideration.

Great job on figuring that you and awesome job from all the posters too!


John 3:16
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 36508
    
  16
David Stephansen wrote: . . . Since I have most experience in C#, i try to implement it there. I have used your code and translated it into c# language. . . .
Welcome to the Ranch

C# and Java™ are so similar that translation should be easy. You need to find the original algorithm, which will probably be written in a sort of pseudo-code, which can easily be translated into real code.
 
jQuery in Action, 2nd edition
 
subject: How to implement the wall follower algorithm in java?
 
Similar Threads
Who is this guy?
FBN:Taking follow up exam
Need An Idea to solve This
(NX)Do not have right to upload:
NX: Finishing touches before upload on Monday.