grid.c File Reference

Grid oriented movement and scanning. More...

#include "common.h"
#include "grid.h"
#include "tracing.h"
#include "routing.h"
#include "../shared/parse.h"

Include dependency graph for grid.c:

Functions
	CASSERT (lengthof(TUsUsed)==PATHFINDING_DIRECTIONS)
static qboolean	Grid_CheckForbidden (const pos3_t exclude, const actorSizeEnum_t actorSize, pathing_t *path, int x, int y, int z)
	Checks one field (square) on the grid of the given routing data (i.e. the map).
static void	Grid_SetMoveData (pathing_t path, const int x, const int y, const int z, const int c, const byte length, const int dir, const int ox, const int oy, const int oz, const int oc, priorityQueue_t pqueue)
static void	Grid_MoveMark (const routing_t map, const pos3_t exclude, const actorSizeEnum_t actorSize, pathing_t path, const pos3_t pos, byte crouchingState, const int dir, priorityQueue_t *pqueue)
void	Grid_MoveCalc (const routing_t map, const actorSizeEnum_t actorSize, pathing_t path, const pos3_t from, byte crouchingState, int distance, byte **fb_list, int fb_length)
	Recalculate the pathing table for the given actor(-position).
void	Grid_MoveStore (pathing_t *path)
	Caches the calculated move.
pos_t	Grid_MoveLength (const pathing_t *path, const pos3_t to, byte crouchingState, qboolean stored)
	Return the needed TUs to walk to a given position.
int	Grid_MoveNext (const pathing_t *path, const pos3_t toPos, byte crouchingState)
	Get the direction to use to move to a position (used to reconstruct the path).
unsigned int	Grid_Ceiling (const routing_t *map, const actorSizeEnum_t actorSize, const pos3_t pos)
	Returns the height of the floor in a cell.
int	Grid_Height (const routing_t *map, const actorSizeEnum_t actorSize, const pos3_t pos)
	Returns the height of the floor in a cell.
int	Grid_Floor (const routing_t *map, const actorSizeEnum_t actorSize, const pos3_t pos)
	Returns the height of the floor in a cell.
pos_t	Grid_StepUp (const routing_t *map, const actorSizeEnum_t actorSize, const pos3_t pos, const int dir)
	Returns the maximum height of an obstruction that an actor can travel over.
int	Grid_GetTUsForDirection (int dir)
	Returns the amounts of TUs that are needed to perform one step into the given direction.
int	Grid_Filled (const routing_t *map, const actorSizeEnum_t actorSize, const pos3_t pos)
	Returns non-zero if the cell is filled (solid) and cannot be entered.
pos_t	Grid_Fall (const routing_t *map, const actorSizeEnum_t actorSize, const pos3_t pos)
	Calculated the new height level when something falls down from a certain position.
void	Grid_PosToVec (const routing_t *map, const actorSizeEnum_t actorSize, const pos3_t pos, vec3_t vec)
	Converts a grid position to world coordinates.
void	Grid_RecalcBoxRouting (mapTiles_t mapTiles, routing_t map, const pos3_t min, const pos3_t max, const char **list)
	This function recalculates the routing in the box bounded by min and max.
void	Grid_RecalcRouting (mapTiles_t mapTiles, routing_t map, const char name, const char *list)
	This function recalculates the routing surrounding the entity name.
Variables
static const int	TUsUsed []

Detailed Description

Grid oriented movement and scanning.

Definition in file grid.c.

Function Documentation

CASSERT ( lengthof(TUsUsed) = =PATHFINDING_DIRECTIONS )

unsigned int Grid_Ceiling	(	const routing_t *	map,
		const actorSizeEnum_t	actorSize,
		const pos3_t	pos
	)

Returns the height of the floor in a cell.

Parameters:

`[in]`	map	Pointer to client or server side routing table (clMap, svMap)
`[in]`	actorSize	width of the actor in cells
`[in]`	pos	Position in the map to check the height

Returns:: The actual model height of the cell's ceiling.

Definition at line 641 of file grid.c.

References Com_Printf(), PATHFINDING_HEIGHT, QuantToModel, and RT_CEILING.

Referenced by HUD_MapDebugCursor().

static qboolean Grid_CheckForbidden	(	const pos3_t	exclude,
		const actorSizeEnum_t	actorSize,
		pathing_t *	path,
		int	x,
		int	y,
		int	z
	)			`[static]`

Checks one field (square) on the grid of the given routing data (i.e. the map).

Parameters:

`[in]`	map	Routing data/map.
`[in]`	actorSize	width of the actor in cells
`[in]`	path	Pointer to client or server side pathing table (clPathMap, svPathMap)
`[in]`	x	Field in x direction
`[in]`	y	Field in y direction
`[in]`	z	Field in z direction
`[in]`	exclude	Exclude this position from the forbidden list check

See also:: Grid_MoveMark; G_BuildForbiddenList; CL_BuildForbiddenList

Returns:: qtrue if one can't walk there (i.e. the field [and attached fields for e.g. 2x2 units] is/are blocked by entries in the forbidden list) otherwise false.

< Holding variables for the forbidden x and y

Definition at line 92 of file grid.c.

References byte, Com_DPrintf(), DEBUG_PATHING, pathing_s::fblist, i, qfalse, qtrue, and VectorCompare.

Referenced by Grid_MoveMark().

pos_t Grid_Fall	(	const routing_t *	map,
		const actorSizeEnum_t	actorSize,
		const pos3_t	pos
	)

Calculated the new height level when something falls down from a certain position.

Parameters:

`[in]`	map	Pointer to client or server side routing table (clMap, svMap)
`[in]`	pos	Position in the map to start the fall (starting height is the z-value in this position)
`[in]`	actorSize	Give the field size of the actor (e.g. for 2x2 units) to check linked fields as well.

Returns:: New z (height) value.; 0xFF if an error occurred.

Todo:: if an actor can fly, then set this to true.

Definition at line 742 of file grid.c.

References CELL_HEIGHT, Com_DPrintf(), DEBUG_PATHING, PATHFINDING_HEIGHT, qfalse, and RT_FLOOR.

Referenced by CL_ActorMouseTrace(), and SV_InitGameProgs().

int Grid_Filled	(	const routing_t *	map,
		const actorSizeEnum_t	actorSize,
		const pos3_t	pos
	)

Returns non-zero if the cell is filled (solid) and cannot be entered.

Parameters:

`[in]`	map	Pointer to client or server side routing table (clMap, svMap)
`[in]`	actorSize	width of the actor in cells
`[in]`	pos	Position in the map to check for filling

Returns:: 0 if the cell is vacant (of the world model), non-zero otherwise.

Definition at line 726 of file grid.c.

References PATHFINDING_HEIGHT, and RT_FILLED.

int Grid_Floor	(	const routing_t *	map,
		const actorSizeEnum_t	actorSize,
		const pos3_t	pos
	)

Returns the height of the floor in a cell.

Parameters:

`[in]`	map	Pointer to client or server side routing table (clMap, svMap)
`[in]`	actorSize	width of the actor in cells
`[in]`	pos	Position in the map to check the height

Returns:: The actual model height of the cell's floor.

Definition at line 678 of file grid.c.

References Com_Printf(), PATHFINDING_HEIGHT, QuantToModel, and RT_FLOOR.

Referenced by CL_AddPathingBox(), Grid_PosToVec(), HUD_MapDebugCursor(), and SV_InitGameProgs().

int Grid_GetTUsForDirection ( int dir )

Returns the amounts of TUs that are needed to perform one step into the given direction.

Parameters:

[in] dir the direction in which we are moving

Returns:: The TUs needed to move there.

Definition at line 712 of file grid.c.

References PATHFINDING_DIRECTIONS, and TUsUsed.

Referenced by Grid_MoveMark(), and SV_InitGameProgs().

int Grid_Height	(	const routing_t *	map,
		const actorSizeEnum_t	actorSize,
		const pos3_t	pos
	)

Returns the height of the floor in a cell.

Parameters:

`[in]`	map	Pointer to client or server side routing table (clMap, svMap)
`[in]`	actorSize	width of the actor in cells
`[in]`	pos	Position in the map to check the height

Returns:: The actual model height of the cell's ceiling.

Definition at line 659 of file grid.c.

References Com_Printf(), PATHFINDING_HEIGHT, QuantToModel, RT_CEILING, and RT_FLOOR.

Referenced by Grid_MoveMark().

void Grid_MoveCalc	(	const routing_t *	map,
		const actorSizeEnum_t	actorSize,
		pathing_t *	path,
		const pos3_t	from,
		byte	crouchingState,
		int	distance,
		byte **	fb_list,
		int	fb_length
	)

Recalculate the pathing table for the given actor(-position).

Parameters:

`[in]`	map	Pointer to client or server side routing table (clMap, svMap)
`[in]`	actorSize	The size of thing to calc the move for (e.g. size=2 means 2x2). The plan is to have the 'origin' in 2x2 units in the bottom-left (towards the lower coordinates) corner of the 2x2 square.
`[in,out]`	path	Pointer to client or server side pathing table (clMap, svMap)
`[in]`	from	The position to start the calculation from.
`[in]`	distance	The maximum TUs away from 'from' to calculate move-information for
`[in]`	crouchingState	Whether the actor is currently crouching, 1 is yes, 0 is no.
`[in]`	fb_list	Forbidden list (entities are standing at those points)
`[in]`	fb_length	Length of forbidden list

See also:: Grid_MoveMark; G_MoveCalc; CL_ConditionalMoveCalc

< Extended position; includes crouching state

< if reaching that square already took too many TUs, don't bother to reach new squares *from* there.

Definition at line 513 of file grid.c.

References ACTOR_MAX_STATES, pathing_s::area, pathing_s::areaFrom, Com_DPrintf(), count, DEBUG_PATHING, pathing_s::fblength, pathing_s::fblist, Grid_MoveMark(), MAX_ROUTE, PATHFINDING_DIRECTIONS, PATHFINDING_HEIGHT, PATHFINDING_WIDTH, pos, PQueueFree(), PQueueInitialise(), PQueueIsEmpty, PQueuePop(), PQueuePush(), ROUTING_NOT_REACHABLE, RT_AREA, Vector4Set, and VectorCopy.

Referenced by CL_ActorConditionalMoveCalc(), and SV_InitGameProgs().

pos_t Grid_MoveLength	(	const pathing_t *	path,
		const pos3_t	to,
		byte	crouchingState,
		qboolean	stored
	)

Return the needed TUs to walk to a given position.

Parameters:

`[in]`	path	Pointer to client or server side pathing table (clPathMap, svPathMap)
`[in]`	to	Position to walk to
`[in]`	crouchingState	Whether the actor is currently crouching, 1 is yes, 0 is no.
`[in]`	stored	Use the stored mask (the cached move) of the routing data

Returns:: ROUTING_NOT_REACHABLE if the move isn't possible; length of move otherwise (TUs)

Definition at line 592 of file grid.c.

References Com_DPrintf(), DEBUG_PATHING, PATHFINDING_HEIGHT, ROUTING_NOT_REACHABLE, RT_AREA, and RT_SAREA.

Referenced by CL_ActorMoveLength(), CL_AddPathingBox(), and SV_InitGameProgs().

static void Grid_MoveMark	(	const routing_t *	map,
		const pos3_t	exclude,
		const actorSizeEnum_t	actorSize,
		pathing_t *	path,
		const pos3_t	pos,
		byte	crouchingState,
		const int	dir,
		priorityQueue_t *	pqueue
	)			`[static]`

Parameters:

`[in]`	map	Pointer to client or server side routing table (clMap, svMap)
`[in]`	exclude	Exclude this position from the forbidden list check
`[in]`	actorSize	Give the field size of the actor (e.g. for 2x2 units) to check linked fields as well.
`[in,out]`	path	Pointer to client or server side pathing table (clMap, svMap)
`[in]`	pos	Current location in the map.
`[in]`	crouchingState	Whether the actor is currently crouching, 1 is yes, 0 is no.
`[in]`	dir	Direction vector index (see DIRECTIONS and dvecs)
`[in,out]`	pqueue	Priority queue (heap) to insert the now reached tiles for reconsidering

See also:: Grid_CheckForbidden

Todo:: flier should return true if the actor can fly.

< This can be keyed into whether an actor can fly or not to allow flying

Todo:: has_ladder_support should return true if 1) There is a ladder in the new cell in the specified direction or 2) There is a ladder in any direction in the cell below the new cell and no ladder in the new cell itself.

< Indicates if there is a ladder present providing support.

Todo:: has_ladder_climb should return true if 1) There is a ladder in the new cell in the specified direction.

< Indicates if there is a ladder present providing ability to climb.

Todo:: falling_height should be replaced with an arbitrary max falling height based on the actor.

<This is the maximum height that an actor can fall.

Note:: This value is worthless if it is between CORE_DIRECTIONS and FLYING_DIRECTIONS: These are defined actions or climbing.

< The compass direction of this move if less than CORE_DIRECTIONS or at least FLYING_DIRECTIONS

Note:: This is the actor's height in QUANT units.

< The actor's height

< Get the difference value for x for this direction. (can be pos or neg)

< Get the difference value for y for this direction. (can be pos or neg)

< Get the difference value for z for this direction. (can be pos or neg)

< "new" x value = starting x value + difference from chosen direction

< "new" y value = starting y value + difference from chosen direction

< "new" z value = starting z value + difference from chosen direction

Todo:: actor_height is currently the fixed height of a 1x1 actor. This needs to be adjusted to the actor's actual height, including crouching.

Note:: Fliers use this code only when they are walking. First test for opening height availablilty. Then test for stepup compatibility. Last test for fall.

< The stepup needed to get to/through the passage

< The actual stepup height without the level flags

Todo:: actor_stepup_height should be replaced with an arbitrary max stepup height based on the actor.

Note:: If you need to know about how pathfinding works, you need to understand the following brief. It may cause nausea, but is an important concept.

OK, now some crazy tests: Because of the grid based nature of this game, each cell can have at most only ONE floor that can be stood upon. If an actor can walk down a slope that is in the same level, and actor should be able to walk on (and not fall into) the slope that decends a game level. BUT it is possible for an actor to be able to crawl under a floor that can be stood on, with this opening being in the same cell as the floor. SO to prevent any conflicts, we will move down a floor under the following conditions:

The STEPDOWN flag is set
The floor in the immediately adjacent cell is lower than the current floor, but not more than CELL_HEIGHT units (in QUANT units) below the current floor.
The actor's stepup value is at least the inverse stepup value. This is the stepup FROM the cell we are moving towards back into the cell we are starting in. This ensures that the actor can actually WALK BACK. If the actor does not have a high enough stepup but meets all the other requirements to descend the level, the actor will move into a fall state, provided that there is no floor in the adjacent cell.

This will prevent actors from walking under a floor in the same cell in order to fall to the floor beneath. They will need to be able to step down into the cell or will not be able to use the opening.

Definition at line 163 of file grid.c.

References byte, CELL_HEIGHT, Com_DPrintf(), CORE_DIRECTIONS, DEBUG_PATHING, DIRECTION_CLIMB_DOWN, DIRECTION_CLIMB_UP, DIRECTION_CROUCH, DIRECTION_FALL, DIRECTION_STAND_UP, dvecs, FLYING_DIRECTIONS, Grid_CheckForbidden(), Grid_GetTUsForDirection(), Grid_Height(), Grid_SetMoveData(), MAX_MOVELENGTH, ModelCeilingToQuant, PATHFINDING_BIG_STEPDOWN, PATHFINDING_BIG_STEPUP, PATHFINDING_DIRECTIONS, PATHFINDING_HEIGHT, PATHFINDING_MAX_FALL, PATHFINDING_MAX_STEPUP, PATHFINDING_WIDTH, PLAYER_CROUCHING_HEIGHT, PLAYER_HEIGHT, PLAYER_STANDING_HEIGHT, qfalse, QuantToModel, ROUTING_NOT_REACHABLE, RT_AREA, RT_AREA_TEST, RT_CEILING, RT_CONN, RT_CONN_TEST, RT_FLOOR, RT_STEPUP, TU_CROUCH_MOVING_FACTOR, and UNIT_HEIGHT.

Referenced by Grid_MoveCalc().

int Grid_MoveNext	(	const pathing_t *	path,
		const pos3_t	toPos,
		byte	crouchingState
	)

Get the direction to use to move to a position (used to reconstruct the path).

Parameters:

`[in]`	path	Pointer to client or server side pathing table (le->PathMap, svPathMap)
`[in]`	toPos	The desired location
`[in]`	crouchingState	Whether the actor is currently crouching, 1 is yes, 0 is no.

Returns:: a direction index (see dvecs and DIRECTIONS)

See also:: Grid_MoveCheck

< Get TUs for this square

Definition at line 619 of file grid.c.

References ROUTING_NOT_REACHABLE, ROUTING_UNREACHABLE, RT_AREA, and RT_AREA_FROM.

Referenced by CL_ActorMaximumMove(), CL_ActorTraceMove(), HUD_MapDebugCursor(), and SV_InitGameProgs().

void Grid_MoveStore ( pathing_t * path )

Caches the calculated move.

Parameters:

[in] path Pointer to client or server side pathing table (clPathMap, svPathMap)

See also:: AI_ActorThink

Definition at line 577 of file grid.c.

References pathing_s::area, and pathing_s::areaStored.

Referenced by SV_InitGameProgs().

void Grid_PosToVec	(	const routing_t *	map,
		const actorSizeEnum_t	actorSize,
		const pos3_t	pos,
		vec3_t	vec
	)

Converts a grid position to world coordinates.

See also:: Grid_Height

Parameters:

`[in]`	map	The routing map
`[in]`	actorSize	width of the actor in cells
`[in]`	pos	The grid position
`[out]`	vec	The world vector

Definition at line 781 of file grid.c.

References Com_Printf(), Grid_Floor(), PATHFINDING_HEIGHT, SizedPosToVec, and UNIT_HEIGHT.

Referenced by CL_ActorAdd(), CL_ActorAppear(), CL_ActorTraceMove(), CL_AddPathingBox(), CL_AddTargetingBox(), CL_DisplayFloorArrows(), CL_DisplayObstructionArrows(), CL_EntAppear(), CL_TargetingGrenade(), CL_TargetingStraight(), LE_ActorGetStepTime(), LE_PlaceItem(), LET_PathMove(), and SV_InitGameProgs().

void Grid_RecalcBoxRouting	(	mapTiles_t *	mapTiles,
		routing_t *	map,
		const pos3_t	min,
		const pos3_t	max,
		const char **	list
	)

This function recalculates the routing in the box bounded by min and max.

See also:: CMod_LoadRouting; Grid_RecalcRouting

Parameters:

`[in]`	map	The routing map (either server or client map)
`[in]`	min	The lower extents of the box to recalc routing for
`[in]`	max	The upper extents of the box to recalc routing for

Note:: RT_CheckCell goes from top (7) to bottom (0); The new version of RT_UpdateConnectionColumn can work bidirectional, so we can trace every other dir, unless we are on the edge.

Definition at line 801 of file grid.c.

References ACTOR_MAX_SIZE, Com_DPrintf(), CORE_DIRECTIONS, DEBUG_PATHING, PATHFINDING_WIDTH, RT_CheckCell(), and RT_UpdateConnectionColumn().

Referenced by Grid_RecalcRouting().

void Grid_RecalcRouting	(	mapTiles_t *	mapTiles,
		routing_t *	map,
		const char *	name,
		const char **	list
	)

This function recalculates the routing surrounding the entity name.

See also:: CM_InlineModel; CM_CheckUnit; CM_UpdateConnection; CMod_LoadSubmodels; Grid_RecalcBoxRouting

Parameters:

`[in]`	map	The routing map (either server or client map)
`[in]`	name	Name of the inline model to compute the mins/maxs for

Definition at line 861 of file grid.c.

References cBspModel_s::angles, CM_InlineModel(), Com_DPrintf(), Com_Printf(), DEBUG_PATHING, DEBUG_ROUTING, Grid_RecalcBoxRouting(), i, m, cBspModel_s::maxs, cBspModel_s::mins, cBspModel_s::origin, PATHFINDING_HEIGHT, PATHFINDING_WIDTH, VecToPos, VectorAdd, VectorCenterFromMinsMaxs(), VectorCreateRotationMatrix(), VectorNotEmpty, VectorRotate(), and VectorSubtract.

Referenced by CL_CompleteRecalcRouting(), CL_RecalcRouting(), and SV_RecalcRouting().

static void Grid_SetMoveData	(	pathing_t *	path,
		const int	x,
		const int	y,
		const int	z,
		const int	c,
		const byte	length,
		const int	dir,
		const int	ox,
		const int	oy,
		const int	oz,
		const int	oc,
		priorityQueue_t *	pqueue
	)			`[static]`

< Store TUs for this square.

< Store origination information for this square.

Todo:: add heuristic for A* algorithm

Definition at line 127 of file grid.c.

References Com_Error(), Com_Printf(), ERR_DROP, makeDV, pos, PosSubDV, PQueuePush(), RT_AREA, RT_AREA_FROM, RT_AREA_TEST, Vector4Set, VectorCompare, and VectorSet.

Referenced by Grid_MoveMark().

pos_t Grid_StepUp	(	const routing_t *	map,
		const actorSizeEnum_t	actorSize,
		const pos3_t	pos,
		const int	dir
	)

Returns the maximum height of an obstruction that an actor can travel over.

Parameters:

`[in]`	map	Pointer to client or server side routing table (clMap, svMap)
`[in]`	actorSize	width of the actor in cells
`[in]`	pos	Position in the map to check the height
`[in]`	dir	the direction in which we are moving

Returns:: The actual model height increase needed to move into an adjacent cell.

Definition at line 697 of file grid.c.

References Com_Printf(), PATHFINDING_HEIGHT, QuantToModel, and RT_STEPUP.

Variable Documentation

const int TUsUsed[] [static]

Note:: these are the TUs used to intentionally move in a given direction. Falling not included.

Definition at line 33 of file grid.c.

Referenced by Grid_GetTUsForDirection().

grid.c File Reference

Functions

Variables

Detailed Description

Function Documentation

Variable Documentation