Shortest path related
-
Follow an expanding spiral from your starting position. When you encounter am obstacle, circle around it in the same direction (clockwise/counter~) as your spiral.
-
Nice idea, hadnt thought about spirals.., thanks. Though "circle around an obstacle" its not that simple because there might be several obstacles one each to the other, making a kind of wall.. for example
######## #goal # me
#####
#
#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.
-
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.
-
You may be making it more complex than it needs to be. If you were feeling your way through a maze in the dark with your right hand on the right wall, you'd just keep going straight until you hit an obstacle. Then since you couldn't continue in the same direction, you'd rotate your direction vector 45 degrees to the left. If that direction was free you'd advance, else you'd rotate again.
-
For this particular problem, you may also want to store the coordinates of the spiral you've already traversed, so that you take up where you left off once you've circled around obstacles.
-
For this particular problem, you may also want to store the coordinates of the spiral you've already traversed, so that you take up where you left off once you've circled around obstacles.
-
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
well you should just use A* (A-Star)use 1, 2 or 3 ;) unless there is a reason NOT to use A* in your program? :^) why do you only know adjacent squares...? if this is all the information you are allowed to know you are going to have serious issues with finding the path.... SERIOUS issues. You would need at least one rule that all paths adhere to, so that you can follow/implement a heuristic.. say something like if you take a right then you will take a left next(but where is the fun in that?) otherwise it is ..very easy .. to get the character stuck, or use up way too much memory
-
Any ideas for a "contour follow" algorithm? Like "contour follow with left hand on wall" and "countour follow with right hand on wall"
-
well you should just use A* (A-Star)use 1, 2 or 3 ;) unless there is a reason NOT to use A* in your program? :^) why do you only know adjacent squares...? if this is all the information you are allowed to know you are going to have serious issues with finding the path.... SERIOUS issues. You would need at least one rule that all paths adhere to, so that you can follow/implement a heuristic.. say something like if you take a right then you will take a left next(but where is the fun in that?) otherwise it is ..very easy .. to get the character stuck, or use up way too much memory
-
"why do you only know adjacent squares...?" Why do you wan't to change my problem? Thats the problem.. don't try to help me solving another problem :P
: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
-
: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
-
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 played around with this many years ago on my NEC APC. I had a matrix of moves for each intersection (think of the path to the next location as a road, and the location having 4 directions to go), each element of the move matrix was a byte, the high nibble had 4 bits indicating the entry direction (for backtracking), the low nibble had 4 bits indicating which directions had been tried. When a direction was tried (when you started to go that direction) you set a bit in the low nibble for the selected direction, and set the bit in the high nibble for the entry direction, and if the move was valid you continued. If this was a barrier or if you had already visited this intersection (some bit set in either high or low nibble, then you backtrack to the first intersection which had some available path and tried a different direction. If you backtrack FROM an intersection, then reset the bit in the high nibble of the intersection you are returning FROM but not the bit in the low nibble you are returning TO. You need to check the original matrix to see if the location is a barrier or if you have found the target. Note: You do not want to visit an intersection more than once, not to cross (from east to west, crossing a north to south path), not to touch (east to north where there was a path from west to south), and not to follow a prior path (huge loop). To find the shortest path (maybe more than one the same length), try all paths from the starting point and save the path intersections you visit (deleting the last intersection point for each backtrack) until you find the target. The length of that one path is then known. Continue the searches until all directions from the starting point have been tried. To find the longest path, modify the test for visiting an intersection to allow either a touch, and/or a cross, and try all paths and select the longest. I played around with depth first searches (described above), then breadth first searches (harder to implement). Fun exercise! 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
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.