Grid oriented movement and scanning. More...

#include "common.h"
#include "grid.h"
#include "tracing.h"
#include "routing.h"
#include "pqueue.h"

Data Structures
class	Step
	a struct holding the relevant data to check if we can move between two adjacent cells More...

Macros
#define	RT_AREA_POS(path, p, state) ((path)->area[(state)][(p)[2]][(p)[1]][(p)[0]])

#define	RT_AREA_FROM_POS(path, p, state) ((path)->areaFrom[(state)][(p)[2]][(p)[1]][(p)[0]])

#define	RT_SAREA(path, x, y, z, state) ((path)->areaStored[(state)][(z)][(y)][(x)])

#define	RT_AREA_TEST_POS(path, p, state)

Functions
	CASSERT (lengthof(TUsUsed)==PATHFINDING_DIRECTIONS)

static bool	Grid_CheckForbidden (const pos3_t exclude, const actorSizeEnum_t actorSize, pathing_t *path, pos3_t chkPos)
	Checks one cell on the grid against the 'forbiddenList' (i.e. cells blocked by other entities). More...

static void	Grid_SetMoveData (pathing_t *path, const pos3_t toPos, const int crouch, const byte length, const int dir, const int oldZ)

void	Grid_CalcPathing (const Routing &routing, const actorSizeEnum_t actorSize, pathing_t path, const pos3_t from, int maxTUs, forbiddenList_t fb_list)
	Recalculate the pathing table for the given actor(-position) More...

bool	Grid_FindPath (const Routing &routing, const actorSizeEnum_t actorSize, pathing_t path, const pos3_t from, const pos3_t targetPos, byte crouchingState, int maxTUs, forbiddenList_t forbiddenList)
	Tries to find a path from the given actor(-position) to a given target position. More...

void	Grid_MoveStore (pathing_t *path)
	Caches the calculated move. More...

pos_t	Grid_MoveLength (const pathing_t *path, const pos3_t to, byte crouchingState, bool stored)
	Return the needed TUs to walk to a given position. More...

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) More...

unsigned int	Grid_Ceiling (const Routing &routing, const actorSizeEnum_t actorSize, const pos3_t pos)
	Returns the height of the floor in a cell. More...

int	Grid_Floor (const Routing &routing, const actorSizeEnum_t actorSize, const pos3_t pos)
	Returns the height of the floor in a cell. More...

int	Grid_GetTUsForDirection (const int dir, bool crouched)
	Returns the amounts of TUs that are needed to perform one step into the given direction. More...

pos_t	Grid_Fall (const Routing &routing, const actorSizeEnum_t actorSize, const pos3_t pos)
	Calculated the new height level when something falls down from a certain position. More...

bool	Grid_ShouldUseAutostand (const pathing_t *path, const pos3_t toPos)
	Checks if a crouched actor could save TUs by standing up, walking and crouching again. More...

void	Grid_PosToVec (const Routing &routing, const actorSizeEnum_t actorSize, const pos3_t pos, vec3_t vec)
	Converts a grid position to world coordinates. More...

void	Grid_RecalcBoxRouting (mapTiles_t mapTiles, Routing &routing, const GridBox &box, const char *list)
	This function recalculates the routing in and around the box bounded by min and max. More...

void	Grid_RecalcRouting (mapTiles_t mapTiles, Routing &routing, const char name, const GridBox &box, const char **list)
	This function recalculates the routing surrounding the entity name. More...

Variables
static const int	TUsUsed []

Detailed Description

Grid oriented movement and scanning.

Definition in file grid.cpp.

Macro Definition Documentation

#define RT_AREA_FROM_POS	(	path,
		p,
		state
	)	((path)->areaFrom[(state)][(p)[2]][(p)[1]][(p)[0]])

Definition at line 33 of file grid.cpp.

Referenced by Grid_MoveNext(), and Grid_SetMoveData().

#define RT_AREA_POS	(	path,
		p,
		state
	)	((path)->area[(state)][(p)[2]][(p)[1]][(p)[0]])

Definition at line 32 of file grid.cpp.

Referenced by Step::calcNewTUs(), Step::checkWalkingDirections(), Grid_CalcPathing(), Grid_FindPath(), Grid_MoveLength(), Grid_MoveNext(), Grid_SetMoveData(), and Grid_ShouldUseAutostand().

#define RT_AREA_TEST_POS	(	path,
		p,
		state
	)

Value:

assert((p)[2] < PATHFINDING_HEIGHT);\

assert((state) == 0 || (state) == 1);

PATHFINDING_HEIGHT

#define PATHFINDING_HEIGHT

15 max, adjusting above 8 will require a rewrite to the DV code

Definition: defines.h:294

Definition at line 35 of file grid.cpp.

Referenced by Grid_CalcPathing(), Grid_FindPath(), and Grid_SetMoveData().

#define RT_SAREA	(	path,
		x,
		y,
		z,
		state
	)	((path)->areaStored[(state)][(z)][(y)][(x)])

Definition at line 34 of file grid.cpp.

Referenced by Grid_MoveLength().

Function Documentation

CASSERT ( lengthof(TUsUsed) = =PATHFINDING_DIRECTIONS )

void Grid_CalcPathing	(	const Routing &	routing,
		const actorSizeEnum_t	actorSize,
		pathing_t *	path,
		const pos3_t	from,
		int	maxTUs,
		forbiddenList_t *	fb_list
	)

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

We calculate the table for ALL possible movement states (atm stand and crouch) to be able to propose smart things like autostand.

Parameters

[in]	routing	Reference 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]	maxTUs	The maximum TUs away from 'from' to calculate move-information for
[in]	fb_list	Forbidden list (entities are standing at those points)

See also: G_MoveCalc; CL_ConditionalMoveCalc

< Extended position; includes crouching state

Definition at line 497 of file grid.cpp.

References ACTOR_MAX_STATES, Step::actorSize, pathing_s::area, pathing_s::areaFrom, Step::crouchingState, Step::dir, DIRECTION_CROUCH, DIRECTION_STAND_UP, pathing_s::fbList, Step::fromPos, Grid_CheckForbidden(), Grid_SetMoveData(), Step::init(), Step::isPossible(), MAX_ROUTE_TUS, OBJSET, PATHFINDING_DIRECTIONS, PATHFINDING_HEIGHT, PQueueFree(), PQueueInitialise(), PQueueIsEmpty, PQueuePop(), PQueuePush(), ROUTING_NOT_REACHABLE, RT_AREA_POS, RT_AREA_TEST_POS, Step::toPos, Step::TUsAfter, Vector4Set, and VectorCopy.

Referenced by CL_ActorConditionalMoveCalc(), SV_GridCalcPathing(), and TEST_F().

unsigned int Grid_Ceiling	(	const Routing &	routing,
		const actorSizeEnum_t	actorSize,
		const pos3_t	pos
	)

Returns the height of the floor in a cell.

Parameters

[in]	routing	Reference 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 741 of file grid.cpp.

References Routing::getCeiling(), PATHFINDING_HEIGHT, and QuantToModel.

Referenced by HUD_MapDebugCursor().

static bool Grid_CheckForbidden	(	const pos3_t	exclude,
		const actorSizeEnum_t	actorSize,
		pathing_t *	path,
		pos3_t	chkPos
	)

static

Checks one cell on the grid against the 'forbiddenList' (i.e. cells blocked by other entities).

Parameters

[in]	exclude	Exclude this position from the forbidden list check
[in]	actorSize	width of the actor in cells
[in]	path	Pointer to client or server side pathing table (clPathMap, svPathMap)
[in]	chkPos	Grid position of the cell

See also: G_BuildForbiddenList; CL_BuildForbiddenList

Returns: true 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.

Definition at line 96 of file grid.cpp.

References pathing_s::fbList, forbiddenList_s::getEntSize(), forbiddenList_s::getNext(), and VectorCompare.

Referenced by Grid_CalcPathing(), and Grid_FindPath().

pos_t Grid_Fall	(	const Routing &	routing,
		const actorSizeEnum_t	actorSize,
		const pos3_t	pos
	)

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

Parameters

[in]	routing	Reference 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 783 of file grid.cpp.

References CELL_HEIGHT, Routing::getFloor(), and PATHFINDING_HEIGHT.

Referenced by CL_ActorMouseTrace(), SV_GridFall(), and TEST_F().

bool Grid_FindPath	(	const Routing &	routing,
		const actorSizeEnum_t	actorSize,
		pathing_t *	path,
		const pos3_t	from,
		const pos3_t	targetPos,
		byte	crouchingState,
		int	maxTUs,
		forbiddenList_t *	forbiddenList
	)

Tries to find a path from the given actor(-position) to a given target position.

Unlike Grid_CalcPathing, this function does not neccessarily calculate the TU values for all positions reachable from 'from'. Instead it tries to find the shortest/fastest path to the target position. There is no limit to maxTUs.

Parameters

[in]	routing	Reference 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]	targetPos	The position where we want to end up.
[in]	maxTUs	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]	forbiddenList	Forbidden list (entities are standing at those points)

< Extended position; includes crouching state

Definition at line 590 of file grid.cpp.

References Step::actorSize, pathing_s::area, pathing_s::areaFrom, Step::crouchingState, Step::dir, DIRECTION_CROUCH, DIRECTION_STAND_UP, pathing_s::fbList, forbiddenList, Step::fromPos, Grid_CheckForbidden(), Grid_SetMoveData(), Step::init(), int(), Step::isPossible(), OBJSET, PATHFINDING_DIRECTIONS, PATHFINDING_HEIGHT, PQueueFree(), PQueueInitialise(), PQueueIsEmpty, PQueuePop(), PQueuePush(), ROUTING_NOT_REACHABLE, RT_AREA_POS, RT_AREA_TEST_POS, Step::toPos, Step::TUsAfter, Vector4Set, VectorCompare, VectorCopy, VectorDist, and VectorEqual.

Referenced by SV_GridFindPath().

int Grid_Floor	(	const Routing &	routing,
		const actorSizeEnum_t	actorSize,
		const pos3_t	pos
	)

Returns the height of the floor in a cell.

Parameters

[in]	routing	Reference 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 754 of file grid.cpp.

References Routing::getFloor(), PATHFINDING_HEIGHT, and QuantToModel.

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

int Grid_GetTUsForDirection	(	const int	dir,
		bool	crouched
	)

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
[in]	crouched	The crouching state of the actor

Returns: The TUs needed to move there.

Definition at line 766 of file grid.cpp.

References CORE_DIRECTIONS, PATHFINDING_DIRECTIONS, TU_CROUCH_MOVING_FACTOR, and TUsUsed.

Referenced by Step::calcNewTUs(), Step::checkWalkingDirections(), SV_InitGameProgs(), and TEST_F().

pos_t Grid_MoveLength	(	const pathing_t *	path,
		const pos3_t	to,
		byte	crouchingState,
		bool	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 698 of file grid.cpp.

References PATHFINDING_HEIGHT, RT_AREA_POS, and RT_SAREA.

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

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 vector (see dvecs and DIRECTIONS)

See also: Grid_MoveCheck

< Get TUs for this square

Definition at line 719 of file grid.cpp.

References ROUTING_NOT_REACHABLE, ROUTING_UNREACHABLE, RT_AREA_FROM_POS, and RT_AREA_POS.

Referenced by CL_ActorMaximumMove(), CL_ActorMoveLength(), 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 683 of file grid.cpp.

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

Referenced by SV_InitGameProgs(), and TEST_F().

void Grid_PosToVec	(	const Routing &	routing,
		const actorSizeEnum_t	actorSize,
		const pos3_t	pos,
		vec3_t	vec
	)

Converts a grid position to world coordinates.

Parameters

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

Definition at line 832 of file grid.cpp.

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_GridPosToVec().

void Grid_RecalcBoxRouting	(	mapTiles_t *	mapTiles,
		Routing &	routing,
		const GridBox &	box,
		const char **	list
	)

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

See also: CMod_LoadRouting; Grid_RecalcRouting

Parameters

[in]	mapTiles	List of tiles the current (RMA-)map is composed of
[in]	routing	The routing map (either server or client map)
[in]	box	The box to recalc routing for
[in]	list	The local models list (a local model has a name starting with * followed by the model number)

Note: RT_CheckCell goes from top (7) to bottom (0)

Definition at line 854 of file grid.cpp.

References ACTOR_MAX_SIZE, ACTOR_SIZE_NORMAL, GridBox::addOneZ(), CORE_DIRECTIONS, GridBox::expandXY(), GridBox::getMaxX(), GridBox::getMaxY(), GridBox::getMaxZ(), GridBox::getMinX(), GridBox::getMinY(), GridBox::getMinZ(), RT_CheckCell(), and RT_UpdateConnectionColumn().

Referenced by Grid_RecalcRouting().

void Grid_RecalcRouting	(	mapTiles_t *	mapTiles,
		Routing &	routing,
		const char *	name,
		const GridBox &	box,
		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]	mapTiles	List of tiles the current (RMA-)map is composed of
[in]	routing	The routing map (either server or client map)
[in]	name	Name of the inline model to compute the mins/maxs for
[in]	box	The box around the inline model (alternative to name)
[in]	list	The local models list (a local model has a name starting with * followed by the model number)

Definition at line 922 of file grid.cpp.

References cBspModel_s::angles, CalculateMinsMaxs(), cBspModel_s::cbmBox, GridBox::clipToMaxBoundaries(), CM_InlineModel(), Com_Printf(), AABB::getCenter(), Grid_RecalcBoxRouting(), GridBox::isZero(), m, AABB::maxs, cBspModel_s::origin, AABB::set(), GridBox::set(), AABB::shift(), VectorAdd, VectorCreateRotationMatrix(), VectorNotEmpty, VectorRotate(), and VectorSubtract.

Referenced by CL_GridRecalcRouting(), and SV_RecalcRouting().

static void Grid_SetMoveData	(	pathing_t *	path,
		const pos3_t	toPos,
		const int	crouch,
		const byte	length,
		const int	dir,
		const int	oldZ
	)

static

< Store TUs for this square.

< Store origination information for this square.

Definition at line 124 of file grid.cpp.

References length, makeDV, RT_AREA_FROM_POS, RT_AREA_POS, and RT_AREA_TEST_POS.

Referenced by Grid_CalcPathing(), and Grid_FindPath().

bool Grid_ShouldUseAutostand	(	const pathing_t *	path,
		const pos3_t	toPos
	)

Checks if a crouched actor could save TUs by standing up, walking and crouching again.

Parameters

[in]	path	Pointer to client or server side pathing table
[in]	toPos	Desired position

Definition at line 818 of file grid.cpp.

References RT_AREA_POS, and TU_CROUCH.

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

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 41 of file grid.cpp.

Referenced by Grid_GetTUsForDirection().

Data Structures

Macros

Functions

Variables

Detailed Description

Macro Definition Documentation

Function Documentation

Variable Documentation