Pathing

In designing a game where there is a map to navigate around, and computer-controlled objects that need to find their way somewhere, it is important to be familiar with pathing algorithms. This initial discussion only illustrates some possible challenges you may want to take it upon yourself to face. Since I'm just getting into this myself, I won't be providing any actual algorithms.

To set up a pathing algorithm, you need a few things:

The Maze

Consider a square maze. A single square cell could have up to four walls, one on each primary direction (north, south, east, and west). This maze could be stored in a two-dimensional array, with values in each block describing which walls are present in that cell.

One thing that is nice about practicing with square mazes for pathing is that you get everything you need from the two-dimensional array all by itself (the representation of the map, its obstacles and a clean reference for pathing).

Your challenge:
Write a program that will randomly generate a maze for you. Then start an object in one corner and determine the path to get to the opposite corner. Determine the entire correct path before the object starts moving, then move it one cell at a time following the path you laid out until it reaches its destination.

Advanced challenge:
Same as above, except the object that is moving in the maze can only evaluate its path based on what it can actually see. As more walls are discovered and filled in, the path should be re-evaluated.

The Terrain

Terrain is most commonly structured as a huge array of 3D points, each cell representing a corresponding X,Y position in space, with a height value representing the vertical position of the terrain at that point. The actual surface of the terrain is created by the many triangles that result from joining adjacent points together with line segments.

Terrain pathing is a little different. Imagine some surfaces are too steep to climb, and these slopes determine the obstacles that the object must face as it moves from one corner to the other. Note that a downward slope is not considered an obstacle, and some slopes my be passable depending on the direction you take them. Another challenge is that a pit with steep surfaces all around should be avoided at all costs, because if the object falls in, it can't get out.

You can depend on the terrain itself to represent the obstacles and pathing, but the calculations needed may be a little too intensive for practical use. You may want to consider another structure that is a companion to the terrain data itself, to provide immediate feedback for certain things, like pit areas to avoid.

Challenge:
Same as for the maze, above. Randomly generate a terrain and move an object from one corner to the other, given the maximum slope that can be passed by the object.

The Room

This one can be tricky. A room has variously shaped objects in it. The objects could be anywhere at any time. The goal is to move your object around these other objects without bumping into them.

One way I imagine this being handled is to provide collision volumes for the objects and a network of pathing points for each object that your object can follow to get around them. If the line from your object to its desitination intersects any of the collision volumes of the objects (based on the collision volume of your own object as well), your object should depend on that object's pathing points to guide it around.

By collision volume, I mean an area of any size or shape that, if touched, represents a collision. The easiest representations are spheres, but they can be anything else from cubes or pyramids to complex geometrical figures to structures composed of several polygonal figures. The complexity of determining collisions increases as you progress, so be careful.

The collision volume of your object could be represented as a vertical cylinder to ease up on the collision detection with the existing objects. To really ease it up, ALL collision volumes could be cylinders. This generally works for situations where most movement is horizontal. It gets a little trickier when the challenge moves into the full 3D realm...

Challenge:
Randomly generate the placement of various objects around the room and get your object from one corner to the other.

Advanced challenge:
Make the room full 3D space, with many objects floating all around (sitting still, NOT moving). Move your object from an upper corner to the opposite lower corner. This requires that the volumes be something other than cylinders to be accurate.

Note that pathing is not the same as collision detection, but it may depend on some concepts of collision detection to determine that a given path would actually fail. Without any form of collision detection, all paths would be straight lines!

Also, pathing does not just deal with static, stand-still objects as the challenges on this page suggest. Imagine getting a ship to navigate an asteroid field, with all asteroids moving! Consider how the challenge increases if the asteroids collide with each other and send smaller asteroids off in all directions as the ship tries to maneuver, further complicating the pathing algorithm!

A more common problem encountered is that after a path is established, an object moves to block the path while the object is on its way to its destination. Perhaps you can get your object to move around the obstacle and continue along its path. If the two objects are on the same "team", perhaps they can cooperate with each other to squeeze by. In the worst case, the path will need to be re-evaluated, requiring that your object find another way around.

So many problems to consider... and it's guaranteed to be different for every game.