Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 [Tutorial] Simple obstacle detection/path-finding
Index -> Programming, Turing -> Turing Tutorials
View previous topic Printable versionDownload TopicRate TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
NikG




PostPosted: Thu Apr 20, 2006 1:49 pm   Post subject: [Tutorial] Simple obstacle detection/path-finding

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); A to point B (the end of the obstacle), 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 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 Sad)

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.
Sponsor
Sponsor
Sponsor
sponsor
Display posts from previous:   
   Index -> Programming, Turing -> Turing Tutorials
View previous topic Tell A FriendPrintable versionDownload TopicRate TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 1 Posts ]
Jump to:   


Style:  
Search: