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 |
| 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 |
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 |
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 |
(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 |
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.