Shortest path related
-
Lets say I'm standing on a matrix and 1. There are obstacles where I cant stand 2. There is a goal in some x,y 3. I only know the content of the 8 adjacent points 4. I need to return one move based on the one i'm standing each time. Any ideas on the algorithm for returning my move each time? I'm more interested in the correctiness rather than the efectiveness
Sorry for the double post, but you did mention that you have all 8 points available. The same method can still be used, but use a WORD matrix and keep 8 bits in the high BYTE and 8 bits in the low BYTE - the same algo, just more possibilities. When saving the paths, label the locations as single letters (A-Z) for both the rows and columns (giving a 26x26 matrix) and thus a two letter location name, or use double letters for (26X26)x(26X26) and thus a four letter location name, or triple letters ... (how nasty do you want to get) Dave.
-
Lets say I'm standing on a matrix and 1. There are obstacles where I cant stand 2. There is a goal in some x,y 3. I only know the content of the 8 adjacent points 4. I need to return one move based on the one i'm standing each time. Any ideas on the algorithm for returning my move each time? I'm more interested in the correctiness rather than the efectiveness
I just thought of a simpler way to log the paths - use a character 0-7 to log the outbound direction from the current location. The path starts at the specified location, thus is unique, and the string length is the length of the path. Note: The maximum string length could be (for an X by Y matrix) (max(((x/2)*y), (x*(y/2)))+1) to allow for snaking around barriers. To avoid special checks at the edges, simply border the matrix with a barrier (on the top, bottom, left, and right) which has to be checked for anyway, even in interior locations (the edge barriers would have to be included in the matrix sizes). If you joined the left to the right you would have a cylinder, and if you also joined top to bottom, you would have a torus and would not have a need for the barriers at those joined edges - there would be no edges at the joints. The calculations for indexing between locations could easily be done with table lookup to get two decrementers/incrementers (-1, 0, or +1), one for east west and another for north south, the table indexed by the direction (0 for north - decrement north south, no change for east west, 1 for north-east - decrement both north south and east west, etc. To handle the cylinder or torus situation, the current location would be incremented/decremented, then the resulting value used to index another array (assume a matrix of 10x10, this new array would be: (9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0). If x and y were different, then two arrays would be needed, one to adjust x another to adjust y. With table lookup, no complicated edge checking is needed. The only checking would be to see what direction to check next, and that could also be done with a 256 element lookup table (i.e. for a direction byte with bit 0 reset, go north, for bit 1 reset go NE, for bit 2 reset go east, etc). Both the matrix and the movement matrix could be combined into one DWORD matrix with the upper WORD for the location specifier (simple location, start location, target location, barrier location), and the lower WORD the two direction BYTES. One speedup would be to check the entire array for barrier locations, and set the corresponding bits in all of the 8 locations adjacent to each barrier location so that it would appear that the path had already tried to go that way. With edge barriers, two solutions are available. First, do edge checking for the edge barriers, then no further edge checking needed. Second, add an extra column outside of all edges, then no edge checking need be done (you would be setting bits in
-
Any ideas for a "contour follow" algorithm? Like "contour follow with left hand on wall" and "countour follow with right hand on wall"
In general, rotate your direction vector right at each step, and when you hit an obstacle rotate left. With your right hand on the wall, you try to rotate right (into the wall) at each step. Since you can't go into the wall, you then rotate left, and your resulting path is a straight line along the wall. If you come to a corner, when you rotate right you turn right, which takes you around the corner. If you come to an obstacle, rotating right doesn't work, so you rotate left (aiming straight ahead). Since there's an obstacle, going straight doesn't work, so you rotate left again. If that path is clear, you proceed in that direction (left from your original direction). If that path is also blocked (a dead end), you rotate left again (facing backwards) and advance back the way you came.
-
Any ideas for a "contour follow" algorithm? Like "contour follow with left hand on wall" and "countour follow with right hand on wall"
P.S. After you've found the goal, you can optimize the path as follows: If a coordinate appears twice in your path, delete all the moves from after the first time the coordinate is reached, up to and including the last time that same coordinate is reached. This eliminates any backtracking that was done.
-
P.S. After you've found the goal, you can optimize the path as follows: If a coordinate appears twice in your path, delete all the moves from after the first time the coordinate is reached, up to and including the last time that same coordinate is reached. This eliminates any backtracking that was done.
Sorry, I havent had the time to read your replies.. but I swear I'll read it tomorrow. Meanwhile, the ones interested in this problem, I found an algorithm called "bug-1" and "bug-2", search for it.. its just what I needed. I've been trying to found other algorithms but in the papers they just talk about the bug algorithm and after that they jump to other problems such as the one knowing the entire map or knowing more than the eight adjacent points.
-
Sorry, I havent had the time to read your replies.. but I swear I'll read it tomorrow. Meanwhile, the ones interested in this problem, I found an algorithm called "bug-1" and "bug-2", search for it.. its just what I needed. I've been trying to found other algorithms but in the papers they just talk about the bug algorithm and after that they jump to other problems such as the one knowing the entire map or knowing more than the eight adjacent points.
Excuse me, but you initially stated that you only knew the 8 cells adjacent to the current cell and that there was "some x,y goal location" and that you are at some starting location. The Bug algorithm assumes that you also know the exact location of the goal so you can construct a line between the start position and the goal and use that as a direction to try to follow. My later posts work from your initially stated "known" parameters. It seems that for that to work, you need some additional parameters, i.e., the bounds of the grid. The bounds are not necessary if you use the bug algorithm, but the assumption is that the obstacles are finite and do not extend forever (or extend to some edge where you cannot proceed to go around them). More pieces of required information are: Wwhat identifies the starting location?, What identifies the goal location?, What identifies the obstacle locations?. Which of the two above problem are you really trying to solve? What are all of the known parameters? Dave.
-
Excuse me, but you initially stated that you only knew the 8 cells adjacent to the current cell and that there was "some x,y goal location" and that you are at some starting location. The Bug algorithm assumes that you also know the exact location of the goal so you can construct a line between the start position and the goal and use that as a direction to try to follow. My later posts work from your initially stated "known" parameters. It seems that for that to work, you need some additional parameters, i.e., the bounds of the grid. The bounds are not necessary if you use the bug algorithm, but the assumption is that the obstacles are finite and do not extend forever (or extend to some edge where you cannot proceed to go around them). More pieces of required information are: Wwhat identifies the starting location?, What identifies the goal location?, What identifies the obstacle locations?. Which of the two above problem are you really trying to solve? What are all of the known parameters? Dave.
"The Bug algorithm assumes that you also know the exact location of the goal" You are wrong. Its way I've always said: What you know is: the eight adjacent points and the DIRECTION of the goal, that is: N, NE, NW, S, etc. That information is refreshed after each move.
-
"The Bug algorithm assumes that you also know the exact location of the goal" You are wrong. Its way I've always said: What you know is: the eight adjacent points and the DIRECTION of the goal, that is: N, NE, NW, S, etc. That information is refreshed after each move.
You never mentioned that you knew the "DIRECTION" of the goal, please re-read your first post. You want the method to "refresh" the direction and the adjacent locations after each move. This is impossible for the method to do if you do not know the current location and the goal location so that you can calculate a new direction. The goal location need not be "exactly" known if its "relative" position is known, but its position relative to the current location is necessary to make any prediction about the "refreshed" direction upon return from the call. You still need the matrix dimensions to determine if you can go around the end of a barrier, or at least that all barriers are finite and contained inside the matrix so that it is safe to go around the end of the barrier. Dave.
-
You never mentioned that you knew the "DIRECTION" of the goal, please re-read your first post. You want the method to "refresh" the direction and the adjacent locations after each move. This is impossible for the method to do if you do not know the current location and the goal location so that you can calculate a new direction. The goal location need not be "exactly" known if its "relative" position is known, but its position relative to the current location is necessary to make any prediction about the "refreshed" direction upon return from the call. You still need the matrix dimensions to determine if you can go around the end of a barrier, or at least that all barriers are finite and contained inside the matrix so that it is safe to go around the end of the barrier. Dave.
My apolagizes.. Its true, I didnt mention I knew the direction... im so lame. Though Im still right that the bug algorithms dont need the exact location of the goal but just the direction of it. Imagine the problem as implementing a method Direction Move ( adjacents[], Direction direction ) Which is called from the outside, so you dont have to worry about refreshing and stuff. Direction could be an enum So... recalling... Do you know more algorithms like BUG? That apply for the exact same situation?
-
My apolagizes.. Its true, I didnt mention I knew the direction... im so lame. Though Im still right that the bug algorithms dont need the exact location of the goal but just the direction of it. Imagine the problem as implementing a method Direction Move ( adjacents[], Direction direction ) Which is called from the outside, so you dont have to worry about refreshing and stuff. Direction could be an enum So... recalling... Do you know more algorithms like BUG? That apply for the exact same situation?
As I mentioned, you wanted to have someone supply you with an algorithm. Which algorithm, the algorithm to do the refresh, or the algorithm to decide the move? The algorithm to do the refresh NEEDS to know at least the location of the goal relative to the current location in order to supply a refreshed direction. It also NEEDS the definition of the identifiers used to specify the start location, the goal location, and barrier locations so it can return the array of adjacents. It also NEEDS the definition of the ordering of the returned array - is it N, NE, E, SE, S, SW, W, NW, or is it a two dimensional array (adjacents[3][3]) where the middle element is never filled in? You wanted algorithm correctness as well, and this implies that it NEEDS to know the matrix bounds. It is not correct to allow the caller to step outside of the array and cause a memory access fault or array bound fault. It NEEDS to know what the current location is so it can check in the matrix to return whatever lies in the adjacent 8 locations. What happens when the caller reaches the edge of the The move algorithm is trivial. It NEEDS to know the current location and the direction desired. It just refreshes the current location x and y indices. Since the caller does not know its current location (your specification says it only knows the the adjacents and the goal direction), it is assumed that the current location is globally known (the current location x and y values). You can combine the refresh and move algorithms into one by supplying the location of the direction value in the call instead of the just the value itself. The value of the direction at entry would indicate which direction you wanted to go from the current location, and on return could contain the refreshed direction of the goal. This does cause a bit of a problem at the beginning because the caller does not know the initial conditions (what the adjacent locations are) so it cannot supply any meaningful direction for the initial move which would return the initial adjacents and direction to the goal. Maybe it would be appropriate to have a special value (-1) supplied for the first move as an indicator that this is an initial move. The caller would also NEED to know the definition of the identifiers used to specify the goal location and barrier locations so that it can determine if a barrier is blocking the way in some direction, or if the goal is in one of the adjacent cells (the returned direction should contain the direction to the goal, but the actual). Note:
-
P.S. After you've found the goal, you can optimize the path as follows: If a coordinate appears twice in your path, delete all the moves from after the first time the coordinate is reached, up to and including the last time that same coordinate is reached. This eliminates any backtracking that was done.
-
:confused: when 1. you know the state of the 8 squares adjacent to your current position; 2. and you can move around; 3. and you have sufficient memory and time to discover and record; then you can scan the whole area, and in the end you know the state of the whole area. And before you have finished that, you also have found the destination cell. Or am I missing something here? :confused:
Luc Pattyn
I only read code that is properly indented, and rendered in a non-proportional font; hint: use PRE tags in forum messages
Luc, My thoughts exactly. You have to know at least the matrix bounds to do a search. See my thoughts in the three posts below (and in the several above). At least it would be a way to find the path knowing only the adjacent 8 cells, BUT, you need to know either the matrix bounds, or the fact that any barrier lies entirely inside the matrix so you do not step outside of the matrix and you are just stepping around the end of the barrier (the barrier inside of the matrix assumes that the direction to the goal from the current location is known - in this case the matrix bounds need not be known and will work without even knowing what the starting, current, or goal location is, but someone, somewhere needs to know the current position and the goal position in at least relative terms to calculate the direction to the goal from the current position). I even covered the case where the direction was not known, but in that case the matrix bounds must be known to do an exhaustive search. In all cases, some thing needs to know in what way the goal is identified to know when you are done, and also what a barrier looks like in the 8 adjacent cells. Something something needs to know how to move around to go from one cell to another. Dave.
-
Luc, My thoughts exactly. You have to know at least the matrix bounds to do a search. See my thoughts in the three posts below (and in the several above). At least it would be a way to find the path knowing only the adjacent 8 cells, BUT, you need to know either the matrix bounds, or the fact that any barrier lies entirely inside the matrix so you do not step outside of the matrix and you are just stepping around the end of the barrier (the barrier inside of the matrix assumes that the direction to the goal from the current location is known - in this case the matrix bounds need not be known and will work without even knowing what the starting, current, or goal location is, but someone, somewhere needs to know the current position and the goal position in at least relative terms to calculate the direction to the goal from the current position). I even covered the case where the direction was not known, but in that case the matrix bounds must be known to do an exhaustive search. In all cases, some thing needs to know in what way the goal is identified to know when you are done, and also what a barrier looks like in the 8 adjacent cells. Something something needs to know how to move around to go from one cell to another. Dave.
yep. the problem setting is far from complete. it is even unclear what is meant by shortest path: - least amount of calculations? or memory? - least amount of travel (discovery+solution)? - shortest path after all required area has been visited? and what is path length? number of steps? what with diagonal steps? number of turns? :)
Luc Pattyn
I only read code that is properly indented, and rendered in a non-proportional font; hint: use PRE tags in forum messages
-
Treat several obstacles as one big obstacle, and make a bigger circle. One way to do this is with a direction vector, the pair of x,y offsets in the direction of your spiral. When you hit an obstacle, you rotate this direction vector 90 degrees (45 degrees if diagonal moves are permitted). When you find a free cell around the obstacle, you rotate back in the other direction. Intuitively, it's like going through a maze, always keeping your right hand on the right wall, as you circle around obstacles.
Yes... In fact this is also the brute-force method to solve micro-mouse maze. It always works.. :)
-
As I mentioned, you wanted to have someone supply you with an algorithm. Which algorithm, the algorithm to do the refresh, or the algorithm to decide the move? The algorithm to do the refresh NEEDS to know at least the location of the goal relative to the current location in order to supply a refreshed direction. It also NEEDS the definition of the identifiers used to specify the start location, the goal location, and barrier locations so it can return the array of adjacents. It also NEEDS the definition of the ordering of the returned array - is it N, NE, E, SE, S, SW, W, NW, or is it a two dimensional array (adjacents[3][3]) where the middle element is never filled in? You wanted algorithm correctness as well, and this implies that it NEEDS to know the matrix bounds. It is not correct to allow the caller to step outside of the array and cause a memory access fault or array bound fault. It NEEDS to know what the current location is so it can check in the matrix to return whatever lies in the adjacent 8 locations. What happens when the caller reaches the edge of the The move algorithm is trivial. It NEEDS to know the current location and the direction desired. It just refreshes the current location x and y indices. Since the caller does not know its current location (your specification says it only knows the the adjacents and the goal direction), it is assumed that the current location is globally known (the current location x and y values). You can combine the refresh and move algorithms into one by supplying the location of the direction value in the call instead of the just the value itself. The value of the direction at entry would indicate which direction you wanted to go from the current location, and on return could contain the refreshed direction of the goal. This does cause a bit of a problem at the beginning because the caller does not know the initial conditions (what the adjacent locations are) so it cannot supply any meaningful direction for the initial move which would return the initial adjacents and direction to the goal. Maybe it would be appropriate to have a special value (-1) supplied for the first move as an indicator that this is an initial move. The caller would also NEED to know the definition of the identifiers used to specify the goal location and barrier locations so that it can determine if a barrier is blocking the way in some direction, or if the goal is in one of the adjacent cells (the returned direction should contain the direction to the goal, but the actual). Note:
So how would it be the algorithm for surrounding an obstacle? Lets say that every node of the matrix have an obstacleId, and that if two obstacles are adjacent.. then they have the same obstacleId (and by induction, a block of obstacles whould have the same obstacleId too) So, I can treat an obstacle block as being the same obstacle. How do I follow it with the right (or left) hand on it all the time? (dont worry about stopping, thats easy) I think its the hardest part on the algorithm. I think I would need to introduce a "robot orientation" helper variable maybe
-
So how would it be the algorithm for surrounding an obstacle? Lets say that every node of the matrix have an obstacleId, and that if two obstacles are adjacent.. then they have the same obstacleId (and by induction, a block of obstacles whould have the same obstacleId too) So, I can treat an obstacle block as being the same obstacle. How do I follow it with the right (or left) hand on it all the time? (dont worry about stopping, thats easy) I think its the hardest part on the algorithm. I think I would need to introduce a "robot orientation" helper variable maybe
It wasnt that hard =P pseudocode: First I orientate myself so that to my left is the obstacle. Then i call M:
M:
if there is wall to the left:
if there is no wall to my diagonal left:
move there
rotate 90º left
M()
else:
if there is wall infront:
rotate 90º to the right
M()
else:
move there.
else:
throw exceptionmodified on Friday, October 30, 2009 1:23 PM
-
So how would it be the algorithm for surrounding an obstacle? Lets say that every node of the matrix have an obstacleId, and that if two obstacles are adjacent.. then they have the same obstacleId (and by induction, a block of obstacles whould have the same obstacleId too) So, I can treat an obstacle block as being the same obstacle. How do I follow it with the right (or left) hand on it all the time? (dont worry about stopping, thats easy) I think its the hardest part on the algorithm. I think I would need to introduce a "robot orientation" helper variable maybe
I think you are responding to one of Alan's prior posts, I never mentioned grouping obstacles. I would never group barrier locations. I would always just try to go in the direction of the goal until I hit a barrier. If, for instance, the goal was reported as north of your current location, try to go north, if that is blocked (or already tried), try to go north east, if that is blocked, try to go north west, if that is blocked, try to go east, if that is blocked, try to go west, etc. When all directions are blocked or tried, backtrack to the prior location and try another direction from that location (one that has not been tried yet). One thing to watch out for: when you enter a new location from, lets say, the south, then mark the south direction as tried. The reason for this can be seen in the entrance to a narrow tunnel with a dead end. After the first step and at each step you can only go north because both sides have barriers. When you hit the dead end, you could try to go south (if you did not block it by marking it as tried) and you would get out, but you have just added twice the length of the tunnel to the path. By blocking the entrance direction, you are forced to backtrack which removes the steps in the tunnel. Once you are back at the entrance of the tunnel, you can chose another direction to try, not optimal since the goal is north, but you tried that already, so try NE, NW, E, W etc. alternating around the primary goal direction until you get around the barrier. Dave.
-
It wasnt that hard =P pseudocode: First I orientate myself so that to my left is the obstacle. Then i call M:
M:
if there is wall to the left:
if there is no wall to my diagonal left:
move there
rotate 90º left
M()
else:
if there is wall infront:
rotate 90º to the right
M()
else:
move there.
else:
throw exceptionmodified on Friday, October 30, 2009 1:23 PM
-
In general, rotate your direction vector right at each step, and when you hit an obstacle rotate left. With your right hand on the wall, you try to rotate right (into the wall) at each step. Since you can't go into the wall, you then rotate left, and your resulting path is a straight line along the wall. If you come to a corner, when you rotate right you turn right, which takes you around the corner. If you come to an obstacle, rotating right doesn't work, so you rotate left (aiming straight ahead). Since there's an obstacle, going straight doesn't work, so you rotate left again. If that path is clear, you proceed in that direction (left from your original direction). If that path is also blocked (a dead end), you rotate left again (facing backwards) and advance back the way you came.