Mesh Navigation

Navigation in games generally utitilizes the A* algorithm. If you are not already familiar with it then there is a massive amount of information on the net to help you out.

For enviroments which are not based on fixed grid cells there are various techniques by which A* can be used to find valid paths. One easy way is to have designers manually place and connect pathing nodes, forming a web on which your agents can navigate and move. Alternatively, a similar approach can be taken whereby the pathing nodes are automatically generated. In both instances the movement of agents will naturally be restricted to the web created.

If you require more flexibility in path finding then you need to decompose your search area (ie the walkable space in your world) into some set of simple, more useful units. An obvious choice would be triangles. If you triangulate your walkable space, and then treat each triangle as a node with up to three neighbours, then you can use A* to find a path from one triangle to another with very little effort. Then, if jagged paths which run through triangle centre points (or the centrepoints of triangle edges) are problematic for you, you can use another algorithm (Funnel algorithm, detailed breifly in the above link) to find the shortest path through the 'corridor' of triangles which lead from the start to the destination. The whole process can be made very fast by only using A* to search between triangles with three neighbours, which is the basic idea behind this paper (note: the paper itself goes a lot further than this).

Another solution is to use 'points of visibility' (and A*). This is the approach taken by PathEngine, and is generally best suited in environments with limited visibility (although PathEngine itself has good means of dealing with open environments).

Hope this helps,
Jackson Allan