Hi
I''ve been working with pathfinding algorithms for some time now, and to be honest, most of what I found either don''t work in full 3D or rely on waypoints (which I can''t stand). The only one that seems to suit what i need is the quake 3 aas. Not the actual implementation, just some of the ideas - basically, the idea of using volumes instead of waypoints. After many minutes (heh) of thinking, this is what I''ve come up with. It''s not perfect, probably fatally flawed and stupidly ineffeciant, but hey, that''s why I''m posting it here for you lot to poke holes into
. Right then...
The world is split into a set of axis-aligned bounding boxes (aabbs), called volumes. These make up the simplified representation used by the navigation system.
Kept as a structure to make upgrading easier.
typedef struct nav_volume_s
{
bbox_t Box;
}
nav_volume_t;
Now, each volume is tested to see if it intersects with any other volume. If so, a link is created.
typedef struct nav_link_s
{
uint32 Volume1;
uint32 Volume2;
uint32 PlaneID;
int8 PlaneSide1;
}
nav_link_t;
Volume1 and Volume2 are the two volumes that are connected (kept as V1/V2 and not VolumeCurrent and VolumeNext to allow for one link to represent travel in either direction. PlaneID is the index to the plane that splits the two volumes. This is the first part i''m having a little trouble with. Depending on the position and the size of the two boxes, anything from 1 to 4/5 planes can be created. Here''s an example:
Although those two solutions can be solved pretty easily, i''m sure there''s more that cant, especially when using 3D boxes, not 2D as used in the image. Anyway, the Plane is used by the navigation code to direct the agent into the next volume. PlaneSide1 is the side of the plane that Volume1 is on. It can either be +1 or -1. Again, this is used to make going from one volume to another easier. To get the plane side for Volume2, just flip the sign of PlaneSide1.
That''s all well and good, but what about navigating between the volumes? Well, that''s where the paths come in.
typedef struct nav_path_s
{
uint32 VolumeStart;
uint32 VolumeEnd;
uint32 LinkStart;
uint32 LinkNum;
uint32 Cost;
}
nav_path_t;
Unlike the links, paths are a one-way affair. This is because travelling from Start to End could involved a big drop, which would make it impossible to go from End to Start again. So, VolumeStart is the starting volume of the path, while VolumeEnd is... yep, you guessed it, the end of the path.
LinkStart is the index to an array of integers which in turn point to the array of links. The paths quite often share the link index with other paths, i.e.
Volume1-->Volume12-->Volume50
That is the path that needs to be followed.
The link index might read:
LinkIndex0 = 1
LinkIndex1 = 2
Link1 is V1 to V12. Link2 is V12 to V50.
Path:
VolumeStart = Volume1
VolumeEnd = Volume50
LinkStart = 1
LinkNum = 2
Now, what if you wanted to navigate from Volume12 to Volume50? Simple
VolumeStart = Volume1
VolumeEnd = Volume50
LinkStart = 2
LinkNum = 1
Simple data reuse. The first path uses two links, while the second (which is essentially a part of a path) uses only one of the links. Okay, i might not have explained it very well but you get the idea.
The final value is cost. Cost is how expensive it is to get to the destination. This will at present be based on time needed to get to destination (seems like a good one).
When searching for a path, the path with the smallest cost will be selected.
That''s pretty much as far as i got. I will deal with entities and whatnot later on in the development. For now though, this should suffice.
(/me puts on fire-proof clothing) Any suggestions welcome...
typedef struct nav_volume_s
{
bbox_t Box;
}
nav_volume_t;
typedef struct nav_link_s
{
uint32 Volume1;
uint32 Volume2;
uint32 PlaneID;
int8 PlaneSide1;
}
nav_link_t;
typedef struct nav_path_s
{
uint32 VolumeStart;
uint32 VolumeEnd;
uint32 LinkStart;
uint32 LinkNum;
uint32 Cost;
}
nav_path_t;
typedef struct nav_world_s
{
nav_volume_t *Volumes;
nav_link_t *Links;
nav_path_t *Paths;
plane_t *Planes;
uint32 *LinkIndex;
uint32 VolumeNum;
uint32 LinkNum;
uint32 PathNum;
uint32 PlaneNum;
uint32 LinkIndexNum;
}
nav_world_t;
