|
I wasn't
going to post this source but I thought that others would be interested on
how I can parse a huge map (like city64.bsp) in a few seconds and get
individual nodes where a player could stand. The standard Q2dm maps take even
less time.. I use this as part of my pathing stuff..
BTW, the concept of a
grid was originally put forth by WarZone (yes, the admin for the QDevels
Message Board) a few years ago so much credit goes to him for his inspiration
and coding acumen!
However, the way
CreateGrid specifically performs was the product of well over 1 year of
trial/error and testing/debugging! I used to think that the previous ways I
parsed a map into a grid were really clever and that I was doing really well
when I could successfully parse a standard q2dm map in less than 2 to 5
minutes!! And, I'm sure there are even further enhancements that can be made
to the following functions to achieve the same thing even quicker!! But, as
of today, this is the best way to do it..
Here it is:
Create a new file call grid.c and paste in all the following:
#include "g_local.h"
int numnodes=0;
// NOTE: This size of the pathnode array may have to change if a larger array is needed for your individual maps..
vec3_t pathnode[10000];
#define maxx 256 // 32 units/node x=[0..255]
#define maxy 256
#define maxz 512 // 16 units/node z=[0..511]
#define xevery 32 // 32=8192/maxx
#define yevery 32
#define zevery 16
#define gridz(z) (int)MinOf(MaxOf(((z)+4096)*0.06250,0),511)
#define g2v0(x) (float)MinOf(MaxOf((x)*xevery-4096+(xevery*0.5),-4096),4096)
#define g2v1(y) (float)MinOf(MaxOf((y)*yevery-4096+(yevery*0.5),-4096),4096)
#define g2v2(z) (float)MinOf(MaxOf((z)*zevery-4096+(zevery*0.5),-4096),4096)
//=====================================================
// NOTE: you may already have this function someplace
//=====================================================
void G_Spawn_Trails(int type,vec3_t start,vec3_t endpos) {
gi.WriteByte(svc_temp_entity);
gi.WriteByte(type);
gi.WritePosition(start);
gi.WritePosition(endpos);
gi.multicast(start,MULTICAST_PVS);
}
//========================================================
// Put this at very top of ClientThink() so you can see
// the nodes created by CreateGrid as you walk around!
// Also, prototype this function above ClientThink()...
//========================================================
void DrawNearbyGrid(edict_t *ent) {
vec3_t v,forward;
AngleVectors(ent->s.angles,forward,NULL,NULL);
for (int i=0;i<numnodes;i++) {
VectorSubtract(pathnode[i],ent->s.origin,v);
if (VectorLength(v)>128) continue; // limit view distance to eliminate overflows
if (DotProduct(v,forward)>0.3) { // infront?
VectorCopy(pathnode[i],v);
v[2]-=4; // node height
G_Spawn_Trails(TE_BFG_LASER,pathnode[i],v); } }
}
//========================================================
int AdjustDownward(edict_t *ignore,vec3_t start) {
vec3_t endpt;
VectorSet(endpt,start[0],start[1],-8192);
trace_t tr=gi.trace(start,tv(-1,-1,0),tv(1,1,0),endpt,ignore,CONTENTS_SOLID);
tr.endpos[2]+=32;
return (int)(tr.endpos[2]-start[2]); // return delta, if needed later..
}
//========================================================
void CreateGrid(void) {
int x,y,z,cnt=0;
vec3_t v,endpt;
trace_t tr1,tr2;
float v0,v1,v2;
numnodes=0;
vec3_t min1={-3,-3,0}; // width 6x6
vec3_t max1={+3,+3,0};
vec3_t min2={-12,-12,0};// width 24x24
vec3_t max2={+12,+12,0};
for (x=0;x<maxx;x++) {
v0=g2v0(x); // convert grid(x) to v[0]
for (y=0;y<maxy;y++) {
v1=g2v1(y); // convert grid(y) to v[1]
for (z=maxz-1;z>=0;z--) {
v2=g2v2(z); // convert grid(z) to v[2]
//--------------------------------------
VectorSet(v,v0,v1,v2);
// Skip world locations in solid/lava/slime/window/ladder
if (gi.pointcontents(v) & MASK_OPAQUE) { z--; continue; }
//-----------------------------------------------
// At this point,v(x,y,z) is a point in mid-air
//-----------------------------------------------
// Trace small bbox down to see what is below
VectorSet(endpt,v[0],v[1],-8192);
// Stop at world locations in solid/lava/slime/window/ladder
tr1=gi.trace(v,min1,max1,endpt,NULL,MASK_OPAQUE);
// Set for-loop index to our endpt's grid(z)
z=gridz(tr1.endpos[2]);
// Skip if trace endpt hit func entity.
if (tr1.ent && (tr1.ent->use || tr1.ent->think || tr1.ent->blocked)) continue;
// Skip if trace endpt hit lava/slime/window/ladder.
if (tr1.contents & (CONTENTS_LAVA|CONTENTS_SLIME|CONTENTS_WINDOW)) continue;
// Skip if trace endpt hit non-walkable slope
if (tr1.plane.normal[2]<0.7) continue;
//----------------------------------------
// Test vertical clearance above v(x,y,z)
//----------------------------------------
VectorCopy(tr1.endpos,endpt);
tr1.endpos[2]+=2; // set start just above surface
endpt[2]+=32; // endpt at approx crouch height
tr2=gi.trace(tr1.endpos,min2,max2,endpt,NULL,MASK_OPAQUE);
// Skip if not reachable by crouched bbox - trace incomplete?
if (tr2.fraction != 1.0) continue;
// Skip if linewidth inside solid - too close to adjoining surface?
if (tr2.startsolid || tr2.allsolid) continue;
//-------------------------------------
// Now, adjust downward for uniformity
//-------------------------------------
AdjustDownward(NULL,endpt);
// Houston,we have a valid node!
VectorCopy(endpt,pathnode[cnt]); // copy to pathnode[] array
cnt++; } } }
numnodes=cnt;
gi.dprintf("%d Nodes Created\n",numnodes);
}
Be sure to prototype the
functions in one of your header files and add grid.c to your project!
Be advised that the
CreateGrid() function does ALOT of work and takes about 10-15 seconds to
complete, on a 600 P-III with 640Megs of RAM (yes, that's 640!).., so be
patient!. If you've got a real slow machine or are starved for memory
resources, it may take longer..
Now, put a call to
CreateGrid() at the very bottom of SpawnEntities() so all the pathnodes will
be automatically created at the start of each level. Compile and start the
game (and wait for it to complete).. Then, run around and look at all the
nodes created. If you are really clever, the nodes generated can be used with
any of the standard bots like Acebot, for example, (although you will have to
integrate the pathnode array into the bot's routing scheme to make it work,
not a simple integration!)...
NOTE: I use this same
function but I do some other stuff as well. For instance, I hash all valid
nodes as they are generated in CreateGrid() and I use a rather clever
technique in a function called NearbyNodeExists() (also using hashing) which
I call in CreateGrid() just before I copy the endpt to the pathnode[] array.
I using hashing so it finds existing neighbor pathnodes almost instantly. So,
if a nearby node exists (neighbor node) then I DO NOT copy it to the pathnode
array. In this way, I can effectively reduce the total nodes generated in the
CreateGrid() function by a factor of 4 (by keeping a center node while
removing 4 adjacent nodes surrounding it, if they exist).. So, I get about
3000 nodes total for city64.bsp (which is a huge map!) and I get well less
than 1000 for most of the standard q2dm maps..
Perhaps, the hashing and
other stuff I wrote will be the subject of another tutorial.. But.. not
today..
Let me know if I've let
something out..
Maj.Bitch
|
