Node Generation System

Title: Node Generation System
Difficulty: Fairly Easy
By: Maj.Bitch
Email: peblair@frontier.net
Date: 09-27-99
Note: Please give credit where credit is due.
======================================================
This is some source I put together (derived from the previous
work of Warzone, and others). It will generate your node[]
array of valid nodes in a *.bsp file. I'm posting this because
it could use some tweaking (in terms of deleting extra nodes
that it generates) and to give people a head start on the
pathing stuff (so they won't have to reinvent this source again).

Create a new file called grid.c and add it to your standard
Q2 source project.. You'll need to have this in your Q2 source
so you can take advantage of using the gi.pointcontents() function
of the gaming engine. ( Unless you have a better way )...

Use the node that are generated with your new AStar.c stuff and
you'll be off and running pretty quickly..

===========================================================
#include < stdio.h>
#include < stdlib.h>
#include < stdarg.h>
#include < string.h>
#include < errno.h>
#include < math.h>
#include < float.h>
#include < malloc.h>

#include "g_local.h"

#define INVALID -1

FILE *fp;

#define CONTENTS_NODE 0x00

typedef struct {
int nodenum; // node[]
int type; // type of node this is (pointcontents)
vec3_t origin; // location in [x,y,z]
} node_t;

node_t *node;

int numnodes;

// Q2 maps are -4096,+4096 units along each axis
// 8192/256 = 32 units between nodes
// 8192/128 = 64 units between nodes
// 8192/64 =128 units between nodes.

// NOTE: you can vary these number to 128, 64, etc
// to change the granularity of your slices of the world.

// HINT: Keep the zsize 256 else the nodes will be
// too high off the floor... (Your choice)

#define xsize 256 // 32 units
#define ysize 256 // 32 units
#define zsize 256 // 32 units

int grid[xsize][ysize][zsize]; // Temp storage..

#define gridpt grid[x][y][z]

float xevery = 8192/xsize;
float yevery = 8192/ysize;
float zevery = 8192/zsize;

#define MaxOf(x,y) ((x) > (y)?(x):(y))
#define MinOf(x,y) ((x) < (y)?(x):(y))

//==================================================
// Converts a q2 vector into a position in the grid
//==================================================
void vec2grid(vec3_t in, int *x, int *y, int *z) {
*x=(int)MinOf(MaxOf((in[0]+4096)/xevery,0),xsize-1);
*y=(int)MinOf(MaxOf((in[1]+4096)/yevery,0),ysize-1);
*z=(int)MinOf(MaxOf((in[2]+4096)/zevery,0),zsize-1);
}

//==================================================
// Converts a position in the grid into a q2 vector
//==================================================
void grid2vec(int x, int y, int z, vec3_t out) {
out[0]=(float)MinOf(MaxOf(x*xevery-4096+(xevery/2),-4096),4096);
out[1]=(float)MinOf(MaxOf(y*yevery-4096+(yevery/2),-4096),4096);
out[2]=(float)MinOf(MaxOf(z*zevery-4096+(zevery/2),-4096),4096);
}

//===========================================================
void WriteGrid(void) {
int i=0,x,y,z;
char mappath[64];

fprintf(stderr,"Saving Node File...");

sprintf(mappath, "c:/quake2/baseq2/maps/%s.grd",level.mapname);
fp=fopen(mappath,"wb");
if (!fp) {
fprintf(stderr,"ERROR WRITING: %s\n",mappath);
return; }

// How many valid nodes do we have?
numnodes=0;
for (z=0; z < zsize; z++)
for (x=0; x < xsize; x++)
for (y=0; y < ysize; y++)
if (gridpt != INVALID)
numnodes++;

// Write to file the number of nodes
fwrite(&numnodes,sizeof(int),1,fp);

// Allocate a single node for copying purposes
node=(node_t *)xmalloc(sizeof(node_t));

// Assign valid nodes to node_t and write to file
for (z=0; z < zsize; z++)
for (x=0; x < xsize; x++)
for (y=0; y < ysize; y++)
if (gridpt != INVALID) {
node->type = gridpt; // pointcontents
node->nodenum = i++; // nodenum
grid2vec(x,y,z,node->origin); // node origin
fwrite(node,sizeof(node_t),1,fp); }

free(node);

fclose(fp);

fprintf(stderr,"Done\n%d Nodes written to %s\n",numnodes,mappath);
}

//===========================================================
void ReadGrid(void) {
int i;
char mappath[64];

sprintf(mappath, "c:/quake2/baseq2/maps/%s.grd",level.mapname);
fp=fopen(mappath,"rb");
if (!fp) {
fprintf(stderr,"ERROR READING: %s\n",mappath);
return; }

// How many nodes are in this file?
fread(&numnodes,sizeof(int),1,fp);

// Allocate ALL the node_t structs we'll need
node=(node_t *)xmalloc(numnodes*sizeof(node_t));

// Read these nodes from file..
for (i=0;i < numnodes;i++)
fread(&node[i],sizeof(node_t),1,fp);

fclose(fp);

fprintf(stderr,"%d Nodes Loaded\n",numnodes);
}

//========================================================
// Initialize all the cells in grid and delete any extras
//========================================================
void CreateGrid(void) {
int i,k,x,y,z;
int haslava=0;
vec3_t origin;

numnodes=xsize*ysize*zsize;

memset(&grid,0,xsize*ysize*zsize*sizeof(int));

fprintf(stderr, "Wait.. Partitioning map into %d horizontal planes\n",zsize);

// Here, I'm getting the point contents of EVERY node in the grid...

for (x=0; x < xsize; x++)
for (y=0; y < ysize; y++)
for (z=0; z < zsize; z++) {
grid2vec(x,y,z,origin);
gridpt=gi.pointcontents(origin);
if (!haslava && gridpt & (CONTENTS_LAVA|CONTENTS_SLIME))
haslava=1; }

fprintf(stderr,"Deleting nodes in Lava/Slime...");

// If map doesn't have lava nodes then we can skip this part..

if (haslava)
for (z=0; z < zsize; z++)
for (x=0; x < xsize; x++)
for (y=0; y < ysize; y++)
for (i=z; i < zsize; i++)
if (grid[x][y][i] & (CONTENTS_LAVA|CONTENTS_SLIME))
while ((i < zsize) && !(grid[x][y][i] & (CONTENTS_SOLID|CONTENTS_LADDER)))
grid[x][y][i++] = INVALID;

fprintf(stderr,"Done\n");

fprintf(stderr,"Deleting Nodes in mid-air...");

// What I'm trying to do here is to delete any mid-air nodes (CONTENTS_NONE)
// while leaving the very first node directly above the ground. I'm also
// trying to leave ladder nodes intact.

for (z=0; z < zsize; z++)
for (x=0; x < xsize; x++)
for (y=0; y < ysize; y++)
for (i=z; i < zsize; i++)
if (grid[x][y][i] == CONTENTS_NONE || grid[x][y][i] & CONTENTS_WATER) {
while ((++i < zsize) && !(grid[x][y][i] & (CONTENTS_SOLID|CONTENTS_LADDER)))
grid[x][y][i] = INVALID;

fprintf(stderr,"Done\n");

fprintf(stderr,"Deleting Nodes in Solids...");

// Lastly, I want to step thru all the nodes in the grid and remove any of those
// nodes which are in solid but NOT ladder nodes.

//============================
// Now delete ALL solid nodes
//============================
for (z=0; z < zsize; z++)
for (x=0; x < xsize; x++)
for (y=0; y < ysize; y++)
if (gridpt & CONTENTS_SOLID && !(gridpt & CONTENTS_LADDER)))
gridpt = INVALID;

fprintf(stderr,"Done\n\n");

// In the end, I have a layer of nodes covering ALL horizontal surfaces in the
// map with each node being zevery units above the floor or ground (any solid)
// while keeping ladder nodes intact... Understand that?

WriteGrid();
}