Dark Basic/Basic Path Finding

Path finding is the means by which an entity in a game can efficiently navigate from one point in space to another while avoiding all other obstructing entities. There are several different path finding methods including both way-points and A* but i'm only going to talk about the simple and basic way-point method in this tutorial.

WAY-POINTS


This method involves creating preset points at strategic locations within your world space, be it 2D or 3D. These points should be positioned in such a way that it is possible to get from one area of the world space to another area solely by using the waypoints as the only means of navigation. The waypoints would also guide the entity in avoiding obstacles in the world space. Consider the image below:


The image shows the plan layout of a typical bungalow house. You have the Bathroon, Kitchen, Sitting Room, Bedroom and the Corridor. The aim is to be able to get from one of these rooms to another while avoiding obstacles, in this case without passing through the walls partioning the different rooms. Waypoints 1 to 9 are placed at key locations allowing the entity do just this. If you look at the waypoints you can even trace how you would get from one room to another easily.

For example let's trace that path of movement from the Kitchen to the Bathroom. It doesn't matter where in the Kitchen you start from because there will always be a direct path to the Kitchen waypoint '2'. From the Kitchen you need to get to the corridor and the waypoint '1' allows you to do this without passing through a wall. From there you need to get to the point on the corridor that has a unobstructed passage to the Bathroom way point, i.e. from '8' to '9'. So in this case the path would be '2-1-8-9'. If you understood what we just did then you have grabbed the concept behind waypoint path finding, the next step is to setup the computer to do it on its own with no human help.

IMPLEMENTATION


The first step to implementing the waypoint method is to determine the positions of your waypoints. Take care in defining the points to ensure there isn't any redundancy or any more points than that is needed. Once this is done you need to store the positions of these points in a data structure. For this example the world space is in 3D and the way point positions will be stored in an array of type float with 2 dimensions (ignoring the y axis). The code for which would look something like this: 

dim coord(9,2) as float

rem bathroom waypoints
coord(9,1) = 15.1
coord(9,2) = 48.2

rem corridor waypoints
coord(1,1) = 74.7
coord(1,2) = 29.8
coord(3,1) = 64.9
coord(3,2) = 30.3
coord(5,1) = 51.9
coord(5,2) = 30.5
coord(6,1) = 24.9
coord(6,2) = 31.0
coord(8,1) = 15.1
coord(8,2) = 29.3

rem bedroom waypoints
coord(7,1) = 24.9
coord(7,2) = 10.8

rem sittingroom waypoints
coord(4,1) = 64.9
coord(4,2) = 48.2

rem kitchen waypoints
coord(2,1) = 74.7
coord(2,2) = 10.8

Now that we know the 3D coordinates of each of the waypoints we need to define all the possible paths from one waypoint to another. The process is similar to that above, an array stores all the paths from one waypoint to another. This process is necessary so the computer can use the information to find a path, the code for this looks something like: 

dim paths(5,4) as integer

rem bathroom paths
paths(1,1) = 985
paths(1,2) = 9867
paths(1,3) = 9812
paths(1,4) = 9834

rem corridor paths
paths(2,1) = 589
paths(2,2) = 567
paths(2,3) = 512
paths(2,4) = 534

rem bedroom paths
paths(3,1) = 7689
paths(3,2) = 765
paths(3,3) = 7612
paths(3,4) = 7634

rem sittingroom paths
paths(4,1) = 4389
paths(4,2) = 435
paths(4,3) = 4312
paths(4,4) = 4367

rem kitchen paths
paths(5,1) = 2189
paths(5,2) = 215
paths(5,3) = 2167
paths(5,4) = 2134

What this array basically represents is all possible destinations from a particualr waypoint. Take the Bathroom for example, the array stores what waypoints you must traverse to get from the Bathroom to the Corridor, Bedroom, Kitchen and Sitting Room, represented by 985, 9867, 9812 and 9834 respectively. Check for yourself, to get from the Bathroom to the Kitchen you must move through the waypoints 9812. If you have 'X' number of waypoints then you will need to store 'X-1' paths from the current waypoint to all others.

At this point you are ready to start performing your path finding. All you now have to do is determine where you are and where you want to go. To determine where you are you can do a simple 3D corrdinate check against the 'X' and 'Z' axis. You could even use the waypoints and perform distance checks between them and the entity, the shortest distance would represent the waypoint closest to the entity. Your destination would be determine by where the entity wants to go to, in a game the player would click on that part of the map. Once you have the source and destination you check the path array for a path that starts with the source and ends with the destination. Using the same example above, if the source is the Bathroom (9) and the destination is the Kitchen (2) you would search the entire array above for a integer that started with 9 and ends with 2. You would get the integer 9812 if you performed the search successfully. The pseudo code for this would look like this: 

for x = 1 to 5
   for y = 1 to 4

      rem check for bathroom, 9 to kitchen, 2 path
      if first number of paths(x,y) = 9
         if last number of paths(x,y) = 2
            
            return the integer path, 9812

         endif
      endif

   next y
next x
PATH FINDING DEMO

The demo basically demonstrates what we have covered so far. It's a simple example with a 3D representation of the bungalow with plan shown above. A red sphere navigates from one area of the house to another, the destination is set by hitting a key from 1 to 5.

Name: Path Finding Demo (.exe)
Author: Dienye Boham
Version: v1.0
Size: 768KB
Date uploaded: 12/12/05
Download link: Download here

updated 13.10.06