Part 1 ( not finished)

Waypoints drawbacks

1.My understanding is many bot-users or designers dislike waypoints because they must usually be defined manually, ie it is not using waypoints for navigation computations which is the problem.
2. Travelling around the map
Waypoints are rather good at that, providing there are enough waypoints and a smart use of them to avoid a feeling of repetitive trajectories and too much zig-zagging.
3. Localization
Waypoints are very lousy: usual configuration of maps ( crates you can jump on,...) makes it painful if not impossible to have a generic process to find the closest reachable waypoint to a bot/item- or even only a reachable one- from any playable position with a 100% chance of success in a reasonable time.
4. representation of space
Waypoints are very lousy: even when they have a "free-move" radius attached to them, there is no way they can capture the whole playable area. This restricts move opportunities for bots.
Moreover, radii around waypoints does not tell anything on their connection with other waypoints, as it is implicitely reduced to a segment ( or rather a vertical plane). When a bot enters a "out-of-the-nav-system" move ( a "local move" ) like combat strafing or grenade avoidance, especially in between waypoints, no info is available on where it can go without problems ( bump into a wall, fall off an edge): I have never seen a 100% safe solution to cope with that problem in a waypoint-based system.
5. path finding
An extensive coverage of the playable area with a lot of waypoints partially solve problems mentioned hereabove( as do automatic waypoint net generators I have seen), but then path finding ( A* ie A-star) takes a lot more time. If the Floyd algorithm and the resulting matrix can be used instead of the more general A-star, this is probably quite acceptable ( memory size should not be a problem).

Waypoint-less Navigation

My first aim when starting thinking on that topic was to be able to play any map( and there are a lot in Half-life and Counter-Strike) without having to build a waypoint net manually or having to use some ill-defined ones available for the "PodBot".
Taking into account waypoints drawbacks, I wound up to build a navigation system based on the following data :
"the minimum set of maximum sized convex volumes with maximum overlapping covering the full playable area". Needless to say that building the data is the biggest issue.
Rationale:
a- maximum sized convex volumes: by definition of convex, once localized in a given convex volume, the bot can freely move between any 2 points within the volume, providing it stays away from volume bounds.I will refer to those volumes as "MoveVolumes" in the following.
b- covering the full playable area: this means that MoveVolumes bounds must lie on the world faces. Actually usual maps have gravity, which introduces a complication and requires adding vertical so-called "gravity" faces/planes which may have no map face on them. The purpose of these "gravity" faces is to prevent the bot from falling off dangerous edges.
c- maximum overlapping: this obviously makes it easier for moving from one convex volume to another as this overlapping is their intersection.
Note: this is the core difference with a nice implementation of such a system for quake3 I have read about, based like all others I have seen on portals. Portals are somehow arbitrary and depend on the bsptree structure; overlapping and intersections, by providing more information, are meant to overcome major limits of portal-based navigation systems.

How to build the data

Using a Binary Space Partitioning tree ( bsptree) looks fine for "a-" and "b-", but unfortunately not at all for "c-". Still, bsptree building is the work-horse of the process.
. The data-structure I have introduced are
- my own MMap data structure ( double "m" just to prevent confusion with the usual meaning of map for games );
- the usual bsptree in my own format.
- the MoveVolume and intersection between MoveVolumes.

The tools I have coded allow to
- build a MMap from a text file or from a Half-lifev1/CSv1.5 ".bsp" file( referred to as HLBsp tree or file thereafter)
- retrieve a HLBsp tree in my own format
- build a bsptree, extend a bsptree by adding new faces
- perform comprehensive merging of convex faces
- carve convex faces out of other convex faces
- make an extended MMap by adding Gravity faces/planes on relevant edges ( March 2007).
- group adjacent walkable faces, including faces identified as belonging to stairs( March 2007).
- decompose a MMap into solid convex volumes( brushes)
- build a Bsptree and a MMap from a set of brushes
- perform set operations on bsp trees ( union, intersection)
- compute the Minkowski sum/difference of a convex hull and a bsp tree
- build the MoveVolumes and their intersections
- compute gravity planes and faces
- visualize all that with a very simplistic orthographic 3D viewer using OpenGl

Where am I now? ( May 2007)

More tests are needed to check gravity faces use in bsptree building.
Half-life maps create a lot of painful accuracy problems, due the way their data is "simplified" to floats before saving to .bsp files. I have coded edge and face splitting differently to gain robustness by relying on topological relationships instead of numerical checks whenever possible: the new functions are not yet extended to all computations.
I am testing a Floyd shortest-paths implementation using waypoints automatically build from MVolumes intersections data.
I am looking on a concept of "generalized" walkable face, to avoid bsptree splitting based on each walkable face of a bumpy but overall walkable ground, and to get bigger and fewer MoveVolumes; this would also apply to most stairs.
Then I will make my decision on how to deal both with hulls and gravity faces/planes( the basic tools are there).
I will then test the complete solution pack with my own CS1.5 bot on a CS 1.5 map without ladders, swimming,...( de_aztec ).
I will next add ladders, which should not cause too much problems.
Then Jumps, another big one...

the MMap data structure

A MMap is a consistent set of convex Faces, with their Vertices, the Planes they are lying on, and Half-edges.
Faces are linked to the Plane they lie on, without indication of (but no restriction on) the "sign" of their respective normals.
A Face is represented as an ordered circular list ( or ring-list) of Half-edges.
A Half-edge is unique to a face; it always points to a vertex. Moreover, whenever adjacency info has been computed, it also points to its "companion" Half-edge belonging to the adjacent Face when such a Face is found. This is what a MMap being a "consistent" set of Faces refers to.
A Half-edge is also flagged as being NoAdjFace or { Acute, Obtuse or Flat} depending on the angle between the 2 faces.
A "well-behaved" MMap is a map that is a realistic world ( no adjacent faces with opposite normals only, no dangling face), with no Half-edge without "companion".
Half-life/CS maps as available from their bsp file unfortunately do not meet 100% ot the criteria.
Faces do not carry texture information as I am only interested in a map face blocking movement or not.Their are only identified as being blocking/not, and walkable/not.
The Half-edge data structure is very powerful and my advice is, opposite to what I have done, to use it from the start.

Bsptree

For free general information, I suggest looking at the Net, especially on works from Bruce Naylor and William Thibault( in particular his thesis), as well as the source code of quake# and Half-life1 SDK.

From a MMap, my bsptree code builds a 3D leafy or non-leafy bsptree with parametrized heuristics for plane selection, maintaining face-adjacency info of split faces.

The program allows insertion of faces in more than one run. This implies that Leafs and internal nodes are the same objects ( instanciations of the same class).
A Leaf does not have a split plane and both its children are NULL.
An internal node always has a split plane and at least one non NULL child; if only one of its children is not NULL , it is called "non-discriminating"; if both are non NULL, it is a "discriminating node". A good bsptree has no "non-discriminating" node between the top node and any "discriminating node". If not build-in, this property can be enforced after the build phase.

The program also allows "assignment" of faces: faces do not trigger new node creation but end up in the existing leafs. This makes sense only for a leafy tree. It allows to have all world faces in the tree while not using some( faces of small objects like buttons, or very flat objects like paintings , or objects a bot will never touch like neon lamps on the ceiling...) for space partitioning. These face are sometimes referred to as "non-structural" faces; Half-life1/CS and Quake maps/bsptrees do not identify those faces.

The program allows the use of predefined planes. Hence the bsptree buiding process may be autopartitioning as usual( splitting planes are exclusively selected among those the input faces lie on) or not. This is useful when vertical "gravity" planes need to be introduced, and also because the same code will be used for outdoors scenes ( autopartitioning is not the good solution in that case).

A leafy Bsptree can be changed to non-leafy and vice-versa. This is used in the set-operations ( union,...) code.

The program builds leaf bounds, including portals, separately from the tree building process.

From a bsptree, it creates a representation of a map as set of brushes ( closed and convex polyhedra). This is used in the Minkowski sum: the Minkowski sum of a convex hull and a bsp tree is the union of the Minkowski sums of the convex hull with each brush of the bsptree.

As I am lazy, I also use my 3D bsptree for comprehensive face merging, where a 2D one should be used.( Maybe I will templatized the bsptree code,as beyond navigation, a 4D or 5D bsptree will be needed for visibility/occlusion as a part of a Map Tactical Analysis programm still in my head)

Minkowski sum/difference

One can find interesting articles on the net, but the code I found leaves you at the end of the process with a soup of vertices, which is far from the MMap and bsptree data I need. So I build my own Minksum code based on faces rather than on vertices, which needs improvement: it works but I think it should and could be less time-consuming.
The Minkowski sum ( or actually difference) gives for a convex hull - the mobile- ( only translation moves ,no rotation) the bounds another convex polyhedron -the obstacle- imposes to the moves of the mobile center. Actually, any reference point other than the center works the same, the resulting polyhedron describing the "bumping into" limit being just translated.
The MinkSum has more faces than the obstacle, and these are referred to as "bevel" faces lying on "bevel" planes.
By performing the union of MinkSums of a bot hull and all the brushes of the world bsptree, depending on the geometry and size of the hull, some faces/area of the map will disappear, indicating that this hull "cannot go there".
To keep the minksum union bsptree structure close to the original world bsptree, faces parallel to the obstacle are inserted first, then faces parallel to edges, then faces attached to a vertex. This allows to limit additions from the Minksum to small leafs around edges and around vertices.
For a given hull, the MinkSum bsptree can be used as the base bsptree to build the hull own MoveVolumes. Each hull will have then its own set of faces, vertices,...
In a different process which I prefer, I build a unique set of MoveVolumes and intersections with no hull, ie where the mobile is a point; the MinkSum is then used to flag in some way some intersections as being too small to allow this hull to move from one volume to the other. This should allow to perform Minksums locally, instead of doing the full span bsptree one.

Move volume

To build Movevolumes, I start from a leafy bsptree set of empty leafs, as this is the best set of "free-move" convex volumes I have to start from. Each leaf and its faces are the base of a new bsptree, the purpose being to get a convex volume with at least one map face fragment on each of its bounds, which does not happen with a bsptree leaf in general. Whenever the leaf does not meet this requirement, some more map faces must be added :the map faces are culled to the leaf volume, which is un-bounded in some direction; faces that cannot possibly close the leaf volume in a convex way (wrong facing) are rejected. The bsp tree is build, rejecting on the fly coplanar faces lists that do not include at least one fragment of the leaf faces. It is actually build in two steps , with two different heuristics to be as sure as possible to select quickly the best "closing" face(s).
Actually some map configuration requires this process to be recursive, as one leaf may in the end generate more than one "closed" MoveVolume.
The end result is a set of MoveVolumes ( duplicates may show up and are eliminated) structured like small bsptrees, with one node per plane and at least one map face one each plane. The MoveVolumes are then fully bounded by adding portals on each plane to complement map faces if needed.

A usual map have around 1000 empty leafs, which at first sight means re-building 1000 bsptrees. But a leaf original faces cull away a great deal of MMap faces right from the start. Tests I have made on CSv1.5 maps (de_aztec and de_inferno) showed that computing MoveVolumes is much shorter than I expected: to get all the MoveVolumes, it takes around "only" 3 times the time to build a leafy bsptree.

Move volumes intersection

Having a set of MoveVolumes, I compute pair-wise intersections, which are structured a bit like portals. Shared faces are identified as well as, separately for each MoveVolume, intersection faces which are actually portals to the other MoveVolume. Each intersection object points to the two MoveVolumes and the corresponding two separate lists of nodes with planes and intersection faces.

How to use the data for Navigation

The data building code is not finished, but basically
- I will use a map bsp tree for localization of objects in the word (including bots and MoveVolumes) and to localize bots within MoveVolumes.
- MoveVolumes will be the base for "local move" computations.
- MoveVolumes and their intersections form a graph on which AStar or the Floyd algorithm can be applied. I already have a flexible templatized AStar code which is is used in my present bot waypoint nav.
- if need be, waypoints for travelling can easily be derived from MoveVolumes intersections( will probably be needed, at least as temporary data to get distances as cost function for pathfinding).