[Tutorial] Simple obstacle detection/path-finding

[NikG]

Welcome to my first tutorial... turned out to be a lot longer than I thought. I hope some of you find it useful.

Intro
Let's say you have an object that needs to move from point A to point B.
The shortest distance from A to B, obviously, is a straight line. However, let's say there lies an obstacle in the straight-path between A and B. What then? Well that's where obstacle detection (aka path-finding) comes in.

The tutorial is on simple obstacle detection (not to be confused with collision detection), mostly for use in games. I found I needed this while working on my secret project. I did some research on the matter, and found out about the cool A* (A-star) algorithm used in path-finding, but I wanted something simpler. Well here is my solution.

Files
Only 1. Attached below is the full source code for my program (130 or so lines including spaces; written in Turing 4.0.4c but it should work on previous versions). I will be going over it section by section in this tutorial.
Note: I'm sure the attached code can be made a lot more efficient. The reason you'll notice some not terribly necessary code is that, like I said above, this was written to be used in a game. Therefore there might be functions/procedures that seem like overkill here but are there because I would probably want them in the full code for a game.

Anyways, download the code below and try it.
If you think you can, try changing the obstacle location (remember to update the height/width variables if you do) to test my path-finding.
Let's get into the code.

Tutorial

code:

% Grid for object/destination/obstacle locations var Grid : array 1 .. 10, 1 .. 10 of int for i : 1 .. 10 %y     for j : 1 .. 10 %x         Grid (i, j) := 0 %empty     end for end for Grid (5, 2) := 1 %object start location Grid (5, 9) := 2 %destination location for i : 2 .. 7     for j : 4 .. 7         Grid (i, j) := 9 %obstacle locations     end for end for var ObstacleHeight := 6 % y:2..7 var ObstacleWidth := 4 %x:4..7

That should be fairly self explanatory.

code:

function retPos (which : int, XorY : string (1)) : int     % return x/y positon of which (1/2/9)     for i : 1 .. 10         for j : 1 .. 10             if Grid (i, j) = which then                 if XorY = "x" then                     result j                 elsif XorY = "y" then                     result i                 end if             end if         end for     end for end retPos proc drawGrid  % Draw grid along with object, destination, obstacle     drawbox (10, 10, 110, 110, black)     for i : 1 .. 10         for j : 1 .. 10             if Grid (i, j) > 0 then                 drawfillbox (j * 10, i * 10, j * 10 + 10, i * 10 + 10, Grid (i, j))             end if         end for     end for end drawGrid

retPos is just my little function to return the x or y array coordinate of the object (which=1), destination (which=2) or obstacle (which=9). (This function becomes less feasible as your grid becomes bigger so you may need an alternate method.)
drawGrid draws a visual representation of the grid.

code:

function PathContainsObstacle (x1, y1, x2, y2 : int) : boolean     % Check for obstacle in path from x1,y1 to x2,y2     var x := x1     var y := y1     loop         x += sign (x2 - x)         y += sign (y2 - y)         if Grid (y, x) = 9 then             result true         end if         exit when x = x2 and y = y2     end loop     result false end PathContainsObstacle proc ObstacleRoute     % Obstacle route destination returner     %splits route into 3 stages: 1=start of obs, 2=end of obs, 3=destination     if retPos (1, "x") = DestX and retPos (1, "y") = DestY then         if ObstacleStage < 3 then             ObstacleStage += 1         else             ObstacleStage := 0         end if     end if     if ObstacleStage = 1 then         %check which distance is shorter: up or down         if abs (retPos (9, "y") + ObstacleHeight - 1 - retPos (1, "y")) < abs (retPos (9, "y") - retPos (1, "y") - 1) then             DestY := retPos (9, "y") + ObstacleHeight         else             DestY := retPos (9, "y") - 1         end if         DestX := retPos (9, "x")     elsif ObstacleStage = 2 then         DestX := retPos (9, "x") + ObstacleWidth - 1     elsif ObstacleStage = 3 then         DestX := finalx         DestY := finaly     end if end ObstacleRoute

Here we go, the meat of this tutorial!
PathContainsObstacle, as the name and comment implies, checks for an obstacle from x1,y1 to x2,y2 via simple 8-way movement.
ObstacleRoute is used to define a temporary route around the obstacle once PathContainsObstacle returns true. This is done by splitting the route into 3 stages: Current location to point A (just above or below the start of the obstacle); point A to point B (the end of the obstacle), point B to the final destination.

code:

%Main loop code:     %get next move location     NewX := retPos (1, "x") + sign (DestX - retPos (1, "x"))     NewY := retPos (1, "y") + sign (DestY - retPos (1, "y"))     if PathContainsObstacle (NewX, NewY, DestX, DestY) and ObstacleStage = 0 then         %obstacle found from next move to destination, turn on obstacle route         ObstacleStage += 1     end if     if ObstacleStage > 0 then         ObstacleRoute %changes DestX/DestY to temp destination around obstacle         %change NewX/NewY (watching out for obstacles)         NewX := retPos (1, "x") + sign (DestX - retPos (1, "x"))         NewY := retPos (1, "y") + sign (DestY - retPos (1, "y"))         if Grid (NewY, NewX) = 9 then             NewX := retPos (1, "x")         end if         if Grid (NewY, NewX) = 9 then             NewY := retPos (1, "y")         end if     end if     Grid (retPos (1, "y"), retPos (1, "x")) := 0 %remove old object location     Grid (NewY, NewX) := 1 %update new object location

You guys should know Turing's sign function, and might love it as much as I do. The very first thing we do is get the new location and check if there's an obstacle in its path. If so, we 'activate' ObstacleRoute, which changes the destination temporarily. The rest just updates the position of the object.
(Let me know if I went through all of that too fast)

Time for some testing. Go ahead and try changing the location of the obstacles. You can do this by changing the lower/upper bounds of the for loop.

code:

for i : 2 .. 7     for j : 4 .. 7         Grid (i, j) := 9 %obstacle locations     end for end for var ObstacleHeight := 6 % y:2..7 var ObstacleWidth := 4 %x:4..7

Change the 2/7 to change the height and the 4/7 to change the width. Don't forget to update the ObstacleHeight/ObstacleWidth variables.

Limitations
Several! But that's to be expected... this is a SIMPLE path-finding.
- Obstacles must have simple shapes (for this code, rectangles only).
- This will not work if there is an obstacle in the way of the temporary route created by ObstacleRoute. You will need to change my code and probably implement a little recursion to get around many obstacles located close to each other.
- Obviously, this is limited to 8-way movement using an array for a grid. (For my purposes, what I needed was 360-degree movement without using an array... still trying to figure that out )

Well, that's it. I'd love to hear whether you found this useful or not. I'd also be particulary interested in those who think they have a better solution than mine. (Remember, my goal was simplicity, not efficiency.) If I notice interest in this tutorial, I might add a part 2 to this tutorial which shows how the A* method works and, if I get lucky, I'll figure out how to do this without the use of an array and post that in part 3. Stay tuned.

[MysticVegeta]

Why not use DFS? or even better, BFS for pathfinding its way less code...

[Tony]

aren't DFS and BFS ment for classic maze soluving? There are problems if there are open spaces or worst yet, loops within the maze.

A* is a fairly good algorythm for path-finding in open spaces with obstacles.

NikG - the problem with your code is that it's way to specialized.

code:

var ObstacleHeight := 6 % y:2..7 var ObstacleWidth := 4 %x:4..7

It works only for a single object of a defined shape and location.

I think you should give A* another shot.

(btw, when dealing with this kind of tutorials, it is quite benificiary to include pictures for the sake of visualization.)

[NikG]

Oh I agree, my code is highly specialized.
But keep in mind that this was a small grid (10x10) with only one obstacle.

In a real program, you'd probably want a separate array keeping track of all obstacle properties (startx, starty, endx, endy). Also, since your grid would almost definitely be bigger, it would be beneficial to compartmentalize my code so that it can be called by passing the location of the object and destination along with the array of obstacles.

code:

GetObstacleRoute (Startx, Starty, Destx, Desty, ObstaclesArray)

Edit: as for pics, I agree visuals would help, but at the same time my example is pretty simple and should be a snap to follow along with.

[zylum]

Tony wrote:

aren't DFS and BFS ment for classic maze soluving? There are problems if there are open spaces or worst yet, loops within the maze.

A* is a fairly good algorythm for path-finding in open spaces with obstacles.

Actually only DFS has a problem with open spaces, and neighter has a problem with loops within a maze. BFS is not a bad algorithm to use for pathfinding for a beginner as it is much easier to code than A*.

If you are skeptical about the speed of BFS, i submitted a BFS class in turing source forum. you will notice that the speed is more than fast enough for the purpose of being used in turing games.