sektor2111 wrote:<latest reply>

ReachSpecs are, indeed, internal features. However, if I recall correctly, they cap out at 32.

And I didn't really realize you were talking about an XC-boosted, yet

backwards compatible, instance of the Unreal Editor, wow. Nice.

Anyway, I was thinking about a slightly different approach to navigation. Illustrations in progress.

We could use a navigation mesh, or set of convex planes. This is my approach to building one via UnrealScript:

1. Define the contour nodes of our navmesh. Every corner of a wall will have one. There probably is a way to place those automatically, from NavigationPoints; maybe one can use Trace from those outward (i.e. toward corners), and find a Trace distance for 8 or so directions, and only plop contour nodes where the two (or so) smallest of the Trace distances are both smaller than a set value. In this case, every new contour point should have a reference to its source NavigationPoint, the originator trace's direction, and the surface normal of the plane below (i.e. of the floor).

2. Once we have the contour nodes, we can begin splitting those into mesh polygons. First, we just assume the navmesh is basically a set of polygons, where each polygon is, in turn, formed by contour nodes that share a source NavigationPoint in common. Every polygon must store, as a variable, an average floor normal vector, i.e. the summation of all the contour nodes' floor surface normal vectors, divided by the number of contour nodes (and thus the number of summed vectors). We can call this vector the polygon's FNV.

3. Merge all polygon vertexes (i.e. contour nodes) that are close to each other. In case we decide that hypothetical contour nodes A and B are close enough to be merged: if A and B are part of the same polygon we just replace them by a single node, at the average of both nodes' locations (or, if there is no open space in that location, at A's location); otherwise, we just either move A and B to their median position, or move B to A, so either way they share the exact same location.

4. We begin to group up the polygons, into Coplanar Groups (CPGs). A CPG basically contains all polygons that:

- are contiguous to each other, i.e., are either directly(a) or indirectly(b) connected, and
- are coplanar to each other, i.e. have a similar enough Floor Normal Vector (FNV) to be grouped.

(a) Directly connected polygons are those who share at least two contour points, i.e., where there are at least two instances where a contour point from an hypothetical polygon A is close enough from an hypothetical polygon B.

(b) If the set of all considered polygons formed a graph, where every graph node A is connected to every graph node B if both the represented polygons are directly connected, indirectly connected polygons would be those between the which there is a traversal path in the graph, i.e., there is a way from and to both, even if through middle polygons.

5. Finally, we divide each CPG into a list of convex polygons, by triangulating the polygons that participate of a CPG. Ensure there are no obstacles between two contour nodes, and that bots can avoid obstacles in the

middle of the CPG by detecting those and plopping FearSpot-like actors that trigger slight path deviation and thus dodging. All the resulting convex polygons, from all CPGs, are indexed into a single navigation mesh.

It is, of course, much easier to use an external program to do all of this, rather than rely on UnrealScript, which has a few limitations accessing map geometry.