CWorld::Precache
). There is a global variable called WorldGraph
which is a CGraph
class instance and it's InitGraph()
method is called. In said method, several variables are reset to default values, one of them you need to know right now is bool m_fGraphPresent
which can be translated to "is the node graph present and loaded", the other variables will be covered later.bool WorldGraph.FLoadGraph(char* szMapName)
. This method as you might have already guessed, is responsible for loading and reading the maps/graphs/<mapname>.nod
file, but wait, there's more. After building the path to the mentioned file, the next thing it does is telling the engine/filesystem to load it. If it fails because said file is missing or there is a permission problem or whatever, then false
is returned.int
and check if said version is different from the constant #define GRAPH_VERSION (int)16
.CGraph
class data structure were a source of problems (incomplete data, data mismatch and even worse: crashes).#define GRAPH_VERSION
constant to invalidate those now obsolete node graphs and force them to be rebuilt. If you are a web developer, it's kinda the same habit of increasing an API version when major changes are made and consumers are required to make changes to use the new version.false
is returned.sizeof(CGraph)
is read from the file for some variables we'll see later, then some interesting pointers are reset to NULL
just in case we would run out of memory. Back in 1998/1999, we had systems with 16/32 Mb of RAM, not those fancy 16/32/64 Gb in 2024.calloc
) is performed for the nodes (m_pNodes
) using sizeof(CNode)
as the size and m_cNodes
as the count. After that allocation, sizeof(CNode) * m_cNodes
are read. Then we repeat the process with links (m_pLinkPool
/CLink
/m_cLinks
), sorting info (m_di
/DIST_INFO
/m_cNodes
), routing info (m_pRouteInfo
/char
/m_nRouteInfo
) and hash links (m_pHashLinks
/short
/m_nHashLinks
). Don't worry all of these terms will be explained later when the time comes.false
is returned if a memory allocation operation fails or it is expected to read more data and there is nothing else to read ("corrupted file/loss of data" syndrome). true
is returned when the node graph has been read successfully.CGraph::AllocNodes()
is made which makes a memory allocation for the nodes like explained above. The difference this time is that we're using the constant #define MAX_NODES 1024
as count instead of m_cNodes
that we would read from the saved node graph. This will be used later during the generation process.CNode
class which is how a single node is "modeled" in the code:
class CNode
{
public:
Vector m_vecOrigin; // location of this node in space
Vector m_vecOriginPeek; // location of this node (LAND nodes are NODE_HEIGHT higher).
byte m_Region[3]; // Which of 256 regions do each of the coordinate belong?
int m_afNodeInfo; // bits that tell us more about this location
int m_cNumLinks; // how many links this node has
int m_iFirstLink; // index of this node's first link in the link pool.
// Where to start looking in the compressed routing table (offset into m_pRouteInfo).
// (4 hull sizes -- smallest to largest + fly/swim), and secondly, door capability.
int m_pNextBestNode[MAX_NODE_HULLS][2];
// Used in finding the shortest path. m_fClosestSoFar is -1 if not visited.
// Then it is the distance to the source. If another path uses this node
// and has a closer distance, then m_iPreviousNode is also updated.
float m_flClosestSoFar; // Used in finding the shortest path.
int m_iPreviousNode;
short m_sHintType; // there is something interesting in the world at this node's position
short m_sHintActivity; // there is something interesting in the world at this node's position
float m_flHintYaw; // monster on this node should face this yaw to face the hint.
};
There is a lot of information in that class alone so don't worry if you don't understand everything right now. For this section, focus on the two Vector
that represent the origin, the node info (int m_afNodeInfo
) and the last three variables about hints.CNodeEnt
class, not solid and cannot move. Level designers can configure a "hint type" and "activity hint" but as already mentioned in one the previous pages: Valve didn't had time to finish the "hint" system and thus those are left unused. They did finished and revamped it in Half-Life 2 tho.bool WorldGraph.m_fGraphPresent == true
), if that's the case, the entity is removed right away.WorldGraph::m_cNodes == 0
), then it spawn a test_hull
entity (linked to the CTestHull
class) passing itself as parameter in its Spawn
method. The test hull entity will make sense in a few. Another check is made to see if we are exceeding the maximum amount of nodes (WorldGraph.m_cNodes >= MAX_NODES
), if that's true, the node entity is removed right now.CNode* WorldGraph.m_pNodes
is a "list of nodes" and m_cNodes
in this context act as an "index" because it gets incremented after setting some information about said node. The information being set is the node's origin, the (unused) hints and if the entity is an info_node_air, the bits_NODE_AIR
node type is set.int CNode::m_afNodeInfo
) for a second, it allow to make the distinction between land, air and water nodes because it can have the following bits set:
#define bits_NODE_LAND (1 << 0) // Land node, so nudge if necessary.
#define bits_NODE_AIR (1 << 1) // Air node, don't nudge.
#define bits_NODE_WATER (1 << 2) // Water node, don't nudge.
#define bits_NODE_GROUP_REALM (bits_NODE_LAND | bits_NODE_AIR | bits_NODE_WATER)
Land and water bits are set later, do notice the presence of bits_NODE_GROUP_REALM
to group them all. After incrementing the index, the entity is removed.bool WorldGraph.m_fGraphPresent == false
). If that check fails, the entity is removed immediately.CallBuildNodeGraph()
method. The purpose of said method is simple: disable everything that could call the Touch
method in entities (see the bool gTouchEnabled
global variable and DispatchTouch(edict_t* pentTouched, edict_t* pentOther)
function in dlls/cbase.cpp
), actually call the BuildNodeGraph()
method and re-enable those "touches" after the generation process is over.BuildNodeGraph()
make the test hull remove itself on the next "simulation/thinking" frame, but before that frame happens, the node graph generation process continues. It initialize a temporary list of links, and create the maps/graphs/<mapname>.nrp
file. Yes, you've read it right, the .nrp
file and not the .nod
file, that's not an error..nrp
file is simple: it's a text file that you can open with your favorite text editor and it act as a "report" (or "log" if you prefer to call it this way) of the node graph generation process. At the beginning of the file and node graph generation process, all the information about nodes gathered earlier are logged first.
After that logging part, we "restart" a loop on these nodes and three situations can happen:
UTIL_PointContents( Vector vecSrc ) == CONTENTS_WATER
), then the bits_NODE_WATER
flag is added to the node's m_afNodeInfo
.bits_NODE_LAND
flag is added to the node's m_afNodeInfo
.ignore_monsters
and the other one uses dont_ignore_monsters
when it comes to ignoring entities, they are stored in tr
and trEnt
respectively.trEnt
hit something closer than tr
, hits an entity and said entity is a world brush (entity's v.flags
has the FL_WORLDBRUSH
flag set), then the value of tr.vecEndPos
is changed to be the same as trEnt.vecEndPos
. To rephrase this: the purpose of those traces is to check those nodes would be stuck inside solid brush entities or not (func_door, func_wall and so on)m_vecOrigin
and m_vecOriginPeek
are then moved to the end of the trace (tr.vecEndPos
). In order to compensate for stairs, chairs and any other kind of small "step" (as in "watch your step"), they're lifted 8 units from the ground (defined by the constant #define NODE_HEIGHT
).CLink
class:
class CLink
{
public:
int m_iSrcNode; // the node that 'owns' this link (keeps us from having to make reverse lookups)
int m_iDestNode; // the node on the other end of the link.
entvars_t *m_pLinkEnt; // the entity that blocks this connection (doors, etc)
// m_szLinkEntModelname is not necessarily NULL terminated (so we can store it in a more alignment-friendly 4 bytes)
char m_szLinkEntModelname[4]; // the unique name of the brush model that blocks the connection (this is kept for save/restore)
int m_afLinkInfo; // information about this link
float m_flWeight; // length of the link line segment
};
The comments should be explicit about the variables purposes. With that knowledge, we can resume where we left off in the node graph generation process.bool WorldGraph.LinkVisibleNodes(CLink* pLinkPool, FILE* file, int* piBadNode)
. For each node, it traces a line between that node and all others. If nothing blocks said line, the link is kept by referencing the source and destination in the proper variables, otherwise it's not kept. But wait, there's more.#define MAX_NODE_INITIAL_LINKS
) and more links by itself.#define MAX_MODEL_INITIAL_LINKS
) multiplied by the amount of nodes in the map (m_cNodes
).m_pLinkEnt
, the model name is kept in m_szLinkEntModelname
and the entity receive the FL_GRAPHED
flag which is used in the case where it's deleted (func_breakable blocking passage until it's broken for example).iBadNode
parameter? What is a 'bad' node?" To answer these questions, let's pretend the level designer break the "nodes cannot have 128 (#define MAX_NODE_INITIAL_LINKS
) and more links by itself" and/or "the amount of total links cannot exceed 128 (#define MAX_MODEL_INITIAL_LINKS
) multiplied by the amount of nodes in the map (m_cNodes
)" rules (the "level designer don't trust links to be made" paranoia). Instead of returning true
, false
will be returned but before returning said result, the index of the node that was being treated is stored in that &piBadNode
parameter.false
, the test hull switches to its ShowBadNode
thinking method. This method basically teleport the test hull to the node and spam some particle effects to show you the problematic location. The node graph generation process is canceled in that situation.BuildNodeGraph()
method. We have links but there is an important problem that need to be solved: "size". Remember that those links were checked with trace lines, monsters aren't lines, they are "boxes" (square or rectangular). A gargantua cannot possibly traverse ventilation shafts designed for headcrabs and crouched players. So these links need extra information to determine which monsters can and cannot pass.m_afLinkInfo
comes in which can have one or more of the following bits:
#define bits_LINK_SMALL_HULL (1 << 0) // headcrab box can fit through this connection
#define bits_LINK_HUMAN_HULL (1 << 1) // player box can fit through this connection
#define bits_LINK_LARGE_HULL (1 << 2) // big box can fit through this connection
#define bits_LINK_FLY_HULL (1 << 3) // a flying big box can fit through this connection
#define bits_LINK_DISABLED (1 << 4) // link is not valid when the set
You might have guessed where this is going, the test hull entity will actually test those links to determine which hull sizes can traverse or not. Here's a rundown of what happens for each node's link:
FL_SWIM
flag (this is reset at the end of the iteration).#define HULL_STEP_SIZE 16
) into that direction.bool fWalkFailed
is used to keep track of that.fWalkFailed
is false
, do a sanity check of the distance between the test hull entity and the destination node, if it's higher than 64 units, then it's a failure (bogus walk) and fWalkFailed
becomes true
.fWalkFailed
is true
, the assumption that this hull size can traverse the link is proved incorrect, the bit flag of the hull being tested as well as the larger ones are unset from m_afLinkInfo
and we move on straight to checking the next link.fWalkFailed == false
), repeat the whole algorithm from the second step but with the next hull size which is larger than the previous one (on second iteration, this is the human sized one).int WorldGraph.RejectInlineLinks(CLink* pLinkPool, FSFile& file)
is called. In a nutshell, it check for each link if there is another one for a different node "in-between".m_flWeight
) as the distance between the source node and the destination node being tested.int WorldGraph.RejectInlineLinks(CLink* pLinkPool, FSFile& file)
likely removed some of these links. So we allocate the right amount of memory for the final list (WorldGraph.m_pLinkPool
) and copy from the temporary to the final one.
WorldGraph.SortNodes()
and WorldGraph.BuildLinkLookups()
.for
loop that iterates over the nodes and it's inner for
loop for the links as this is "validation" of an optimization technique to be discussed in said future page.WorldGraph.BuildRegionTables()
method. We're finally back to the original subject. Most importantly:
m_vecOrigin.z -= NODE_HEIGHT
)..nrp
) is closed.m_fGraphPresent = true
).WorldGraph.FSaveGraph(const char* szMapName)
. This is a "standard write file function" which create the maps/graphs
folder hierarchy if needed, create the <mapname>.nod
file in it and write everything that has been generated previously in the same order as reading it (graph version, nodes, links...)bool WorldGraph.m_fRoutingComplete
and the WorldGraph.ComputeStaticRoutingTables()
method, this is another optimization trick to be discussed at a later date.CBasePlayer::Precache()
), a call to WorldGraph.FSetGraphPointers()
is made. This method iterates on the list of links, search if the entity's model name is set (FIND_ENTITY_BY_STRING
on the model
key/value) and assign the m_pLinkEnt
pointer if found. It also set the FL_GRAPHED
flag if needed. If the entity is not found, a warning is printed in the console. This also explains the purpose of bool WorldGraph.m_fGraphPointersSet
.
You must log in to post a comment. You can login or register a new account.