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.
Michael Nana wrote:This may help as well. This is how the maze looks like...
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
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.
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
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.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
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
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!
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!
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
luck, db
There are no new questions, but there may be new answers.
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.
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
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
Michael Nana wrote:I also tried this. Doesn't work too.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
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.
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
John 3:16
Welcome to the RanchDavid 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. . . .
You don't know me, but I've been looking all over the world for. Thanks to the help from this tiny ad:
Smokeless wood heat with a rocket mass heater
https://woodheat.net
|