------------------------------------------------------------------- You may distribute this article via any electronic means as long as there is no profit involved. You may not reprint it in whole or in part in any printed publication without my prior permission. ------------------------------------------------------------------- Obstacle Avoidance and Maze Navigation by Shawn C. Swift [Acuity@station.mv.com] So you're making a tank game, and you've finished your amazing 3D texturemapped polygon engine with realtime Phong shading, BSP- tree face culling, and bump-mapping; but you realize that you don't have the foggiest notion how to get the computer controlled tanks to drive around those columns and walls so they can make their way towards the player that is sitting right on the other side of the battlefield. (Don't you hate it when that happens?) Or perhaps you have a game like Wolf-3D or Doom in which the many twisty turning passageways (each one a little diffrent) would confuse even the fabled Minotaur... Not to worry. This document should help you get your computer controlled players behaving semi-intelligent in no time at all! (Getting the human players to behave intelligently, on the other hand, is a little more complicated.) The first step is to imagine your game map is on a grid. You should make sure this grid has small enough squares so that there are clear paths to all destinations, but you should not go down to the pixel level. Any square that contains an obstacle will NOT be passable by your enemies, so if your doorway is too narrow, or your grid is too large, there will be no clear passage to the destination square. You need to create a 2d array which keeps track of which squares are impassable... Obviously if the squares don't go down to the pixel level, they won't line up perfectly with say, walls in Doom. I'll include an idea for getting aound that later. You can get the grid to line up exactly right for a game like Wolf-3D or ROTT without any trouble of course becuase all the walls are multiples of 64 pixels apart, and all walls are 90 degrees. We'll refer to this array as the OBSTACLE array. If you want to save memory, you could binary-encode this array. You could ALSO have diffrent degrees of impassability. For now though, assume 0 is passable, 255 is impassable. Once you have that array, you need to create another 2d array. This will be called the DISTANCE array. It has the same number of positions as the obstacle array, but will need to use unsigned integers instead of bytes. Last thing you need is a couple loop counters, and a DISTANCE COUNTER... I'll explain the distance counter in a sec. Ok, so you have all your arrays allocated, and you've got a start and a destination position on your map, or in your maze. Now what? Step 1: ------- Initialize the DISTANCE array using the OBSTACLE array. If a position is passable in the OBSTACLE array, set the equivalent square in the DISTANCE array to 0. If it is impassable, set the position to 65535. (Reminder: Use UNSIGNED ints) Set the position in the DISTANCE array where the computer controlled player is to 1. Initialize the DISTANCE COUNTER to 1. Step 2: ------- The main loop's psuedocode: --------------------------- THE_GRID = Is_Changing. While THE_GRID = Is_Changing... { THE_GRID = Is_Not_Changing Loop thru the DISTANCE array... { If this position in the DISTANCE array = 0... { If this position is adjacent to a square which contains the value in the DISTANCE_COUNTER... (Up, down, left, or right) { If this position is the destinaton point... { Exit the main WHILE loop, becuase we've finished calculating the path. } otherwise... { Set this square to = DISTANCE+1. THE_GRID = Is_Changing. } } } } } Step 3: ------- The last task in determining the shortest path is starting at the destination square in the 2D array and storing that position in a list... Then you find the square with the LOWEST number that is adjacent to the start position, and store that square in the list... Then from that square you find the adjacent square with the lowest number, and so on until you reach the starting position. BTW, Don't forget the list will be backwards! (You HAVE to build the list in reverse.) Be sure to make sure that the first loop was sucessful in finding a path! If when the loop finally finished executing, THE_GRID = Is_Not_Changing, then there is NO clear path from point A to point B. ------------------------------------------------------ So that you can more easily see what is going on here, look at the following example OBSTACLE array... ------------------------------------------------------ FF FF FF FF FF FF FF FF FF FF FF FF 00 FF 00 FF 00 FF 00 00 00 FF FF 00 FF 00 00 00 FF 00 FF 00 FF FF 00 FF FF FF 00 00 00 FF 00 FF FF 00 00 00 00 00 FF 00 00 00 FF FF FF FF FF FF FF FF FF FF FF FF ----------------------------------------------------- Here's one drawn so you can see the maze structure... SS = Start position XX = Destination ----------------------------------------------------- ** ** ** ** ** ** ** ** ** ** ** ** SS ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** XX ** ** ** ** ** ** ** ** ** ** ** ** ------------------------------------------------------------ Now I've replaced the SS with the 01 that you would init the destination array with... ------------------------------------------------------------ ** ** ** ** ** ** ** ** ** ** ** ** 01 ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** XX ** ** ** ** ** ** ** ** ** ** ** ** --------------------------------------------------- After one iteration through the first while loop... --------------------------------------------------- ** ** ** ** ** ** ** ** ** ** ** ** 01 ** ** ** ** ** 02 ** ** ** ** ** ** ** ** ** ** ** ** XX ** ** ** ** ** ** ** ** ** ** ** ** --------------------------- After several iterations... --------------------------- ** ** ** ** ** ** ** ** ** ** ** ** 01 ** ** ** ** ** 02 ** ** ** ** ** 03 ** ** ** ** ** ** 04 05 06 ** XX ** ** ** ** ** ** ** ** ** ** ** ** ----------------- Completed loop... ----------------- ** ** ** ** ** ** ** ** ** ** ** ** 01 ** 0D ** 0B ** 0D ** ** 02 ** 0C 0B 0A ** 0C ** ** ** 03 ** ** ** 09 0A 0B ** ** ** 04 05 06 07 08 ** 0C 0D XX ** ** ** ** ** ** ** ** ** ** ** ** Note that that the WHOLE array isn't filled in; (Well there ARE zero's in those empty spots) that is what would come out of the loop, becuase it stops after it reaches the the destination, not after it finishes filling the array... Try to follow the path yourself from finish to start... See how the numbers always go down? ------------------------------------------------------------------- You now know most of what you need to know to do obstacle avoidance and maze solving... Now how about ways of improving the algorithm? Idea 1: Do a multi-pass path search using varying grid granularity... Start off with say, an 8x8 grid, and mark off the squares containing obstacles... See if there's a path... If there is, great... (You will want to then interpolate along a line drawn from the center of each grid square to the next square's center along the path so the guy moves smoothly from one square to the next.) If there isn't a path, go to the next level of granularity... Keep making the grid finer and finer until you run out of memory to hold the grid or you find a path that works. Idea 2: Make some squares have finer grids within them... If a square contains an obstacle, you can link it to another grid that just covers that square... Then you'll have to get recursive and tricky with the path-finding routine though. Idea 3: Varying the impassability... If you initialize a square with say, a negative value (you'd have to use signed ints then, and that would force you to have shorter paths... Though I don't see that as a problem really.) when you run the path finding routine, you would increment it it if there were any squares around it with values other than 0 and 65535. (or in this case you'd use 32766 instead) then, when it became 0, you would find the square near it with the highest number (excluding 32766) ad set it equal to that, or greater, or something. I'm not sure... Work it out on paper if you want to try this, It's probabally useful for turn-based RPG's, and in a 3D action game, maybee you actually could have monsters AVOID water if it slowed them down too much. Idea 4: Determining impassability... You could determine impassability in a 3D game where the enemies stay on the ground in two possible ways... You could find the diffrence in angle between the plane that the player is on, and the plane the player is trying to move onto... You might want to weave this check into the main path finding loop, becuase a polygon might be accessable from say, a side with a ramp up, but not from a side with a sheer cliff. If the poly say, has a bottom EDGE, (so both pixels have the same Y) then you coul duse the change in Y to dtermine the polygon's orientation... If you use say polygons that are 64x64, if the Y changes by mre than 16 pixels from the bottom edge to the top edge, then that polygon cannot be moved onto. Idea 5: Saving calculations... Since you know that the only points that will be changed the next time through the main loop are ones that are adjacent to ones you last updated, you could make a list of those newly updated points as you generate them, and then scan only the points that are adjacent to those points on the next loop iteration. Boy, combining all those ideas into one loop could get you some really obfusticated code! Well we should look at the bright side; you probabally don't have to get into recursion with this method. And that's good... Doing it this way is lot faster and neater than trashing the stack with 10,000 calls to a function. Well I hope you've enjoyed this article and find the algorithm useful... If you think I should make any additions, let me know. ------------------------------------------------------------------- I'm currently looking for a job writing games. I program in C and Assembly on the PC. I'm a good computer artist, and I compose .MOD tunes. I'm 20 years old, and live in New Hampshire. I am the sysop of "The Coder's Domain" at (603)437-8053. -------------------------------------------------------------------