routing.h File Reference

grid pathfinding and routing More...

Go to the source code of this file.

Macros
#define	RT_IS_BIDIRECTIONAL   0
#define	RT_CONN_PX(r, actorSize, x, y, z)   (r.getConn(actorSize, x, y, z, 0))
	Some macros to access routing table values as described above. More...
#define	RT_CONN_NX(r, actorSize, x, y, z)   (r.getConn(actorSize, x, y, z, 1))
#define	RT_CONN_PY(r, actorSize, x, y, z)   (r.getConn(actorSize, x, y, z, 2))
#define	RT_CONN_NY(r, actorSize, x, y, z)   (r.getConn(actorSize, x, y, z, 3))
#define	RT_CONN_PX_PY(r, actorSize, x, y, z)   (r.getConn(actorSize, x, y, z, 4))
#define	RT_CONN_PX_NY(r, actorSize, x, y, z)   (r.getConn(actorSize, x, y, z, 7))
#define	RT_CONN_NX_PY(r, actorSize, x, y, z)   (r.getConn(actorSize, x, y, z, 6))
#define	RT_CONN_NX_NY(r, actorSize, x, y, z)   (r.getConn(actorSize, x, y, z, 5))
#define	RT_STEPUP_PX(r, actorSize, x, y, z)   (r.getStepup(actorSize, x, y, z, 0))
#define	RT_STEPUP_NX(r, actorSize, x, y, z)   (r.getStepup(actorSize, x, y, z, 1))
#define	RT_STEPUP_PY(r, actorSize, x, y, z)   (r.getStepup(actorSize, x, y, z, 2))
#define	RT_STEPUP_NY(r, actorSize, x, y, z)   (r.getStepup(actorSize, x, y, z, 3))
#define	RT_STEPUP_PX_PY(r, actorSize, x, y, z)   (r.getStepup(actorSize, x, y, z, 4))
#define	RT_STEPUP_PX_NY(r, actorSize, x, y, z)   (r.getStepup(actorSize, x, y, z, 7))
#define	RT_STEPUP_NX_PY(r, actorSize, x, y, z)   (r.getStepup(actorSize, x, y, z, 6))
#define	RT_STEPUP_NX_NY(r, actorSize, x, y, z)   (r.getStepup(actorSize, x, y, z, 5))
#define	ModelFloorToQuant(x)   (ceil((x) / QUANT))
	These macros are meant to correctly convert from model units to QUANT units and back. More...
#define	ModelCeilingToQuant(x)   (floor((x) / QUANT))
#define	QuantToModel(x)   ((x) * QUANT)
#define	SizedPosToVec(p, actorSize, v)
	SizedPosToVect locates the center of an actor based on size and position. More...

Functions
int	RT_CheckCell (mapTiles_t *mapTiles, Routing &routing, const int actorSize, const int x, const int y, const int z, const char **list)
	This function looks to see if an actor of a given size can occupy a cell(s) and if so identifies the floor and ceiling for that cell. If the cell has no floor, the floor will be negative with 0 indicating the base for the cell(s). If there is no ceiling in the cell, the first ceiling found above the current cell will be used. If there is no ceiling above the cell, the ceiling will be the top of the model. This function will also adjust all floor and ceiling values for all cells between the found floor and ceiling. More...
void	RT_UpdateConnectionColumn (mapTiles_t *mapTiles, Routing &routing, const int actorSize, const int x, const int y, const int dir, const char **list=nullptr, const int minZ=0, const int maxZ=PATHFINDING_HEIGHT)
	Routing Function to update the connection between two fields. More...
bool	RT_AllCellsBelowAreFilled (const Routing &routing, const int actorSize, const pos3_t pos)
	Check if pos is on solid ground. More...
void	RT_GetMapSize (mapTiles_t *mapTiles, AABB &mapBox)
	Calculate the map size via model data and store grid size in map_min and map_max. This is done with every new map load. More...
bool	RT_CanActorStandHere (const Routing &routing, const int actorSize, const pos3_t pos)
	Check if an actor can stand(up) in the cell given by pos. More...
void	RT_WriteCSVFiles (const Routing &routing, const char *baseFilename, const GridBox &box)

Variables
bool	debugTrace

Detailed Description

grid pathfinding and routing

Definition in file routing.h.

Macro Definition Documentation

#define ModelCeilingToQuant

(

x

)

(floor((x) / QUANT))

Definition at line 77 of file routing.h.

Referenced by Step::init(), RT_CheckCell(), and RT_FindOpeningCeilingFrac().

#define ModelFloorToQuant

(

x

)

(ceil((x) / QUANT))

These macros are meant to correctly convert from model units to QUANT units and back.

Definition at line 75 of file routing.h.

Referenced by CL_ActorMouseTrace(), RT_CheckCell(), RT_FindOpening(), RT_FindOpeningFloorFrac(), and RT_MicroTrace().

#define QuantToModel

(

x

)

((x) * QUANT)

Definition at line 79 of file routing.h.

Referenced by Step::checkVerticalDirections(), CL_AddPathingBox(), Grid_Ceiling(), Grid_Floor(), RT_CheckCell(), RT_FindOpening(), RT_FindOpeningCeilingFrac(), RT_FindOpeningFloorFrac(), RT_MicroTrace(), and RT_ObstructedTrace().

#define RT_CONN_NX	(		r,
			actorSize,
			x,
			y,
			z
	)		(r.getConn(actorSize, x, y, z, 1))

Definition at line 53 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_CONN_NX_NY	(		r,
			actorSize,
			x,
			y,
			z
	)		(r.getConn(actorSize, x, y, z, 5))

Definition at line 60 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_CONN_NX_PY	(		r,
			actorSize,
			x,
			y,
			z
	)		(r.getConn(actorSize, x, y, z, 6))

Definition at line 59 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_CONN_NY	(		r,
			actorSize,
			x,
			y,
			z
	)		(r.getConn(actorSize, x, y, z, 3))

Definition at line 55 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_CONN_PX	(		r,
			actorSize,
			x,
			y,
			z
	)		(r.getConn(actorSize, x, y, z, 0))

Some macros to access routing table values as described above.

Note

P/N = positive/negative; X/Y =direction

IMPORTANT: actorSize is 1 or greater!!!

Definition at line 52 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_CONN_PX_NY	(		r,
			actorSize,
			x,
			y,
			z
	)		(r.getConn(actorSize, x, y, z, 7))

Definition at line 58 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_CONN_PX_PY	(		r,
			actorSize,
			x,
			y,
			z
	)		(r.getConn(actorSize, x, y, z, 4))

Definition at line 57 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_CONN_PY	(		r,
			actorSize,
			x,
			y,
			z
	)		(r.getConn(actorSize, x, y, z, 2))

Definition at line 54 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_IS_BIDIRECTIONAL   0

Definition at line 40 of file routing.h.

Referenced by CheckConnectionsThread(), and DoRouting().

#define RT_STEPUP_NX	(		r,
			actorSize,
			x,
			y,
			z
	)		(r.getStepup(actorSize, x, y, z, 1))

Definition at line 63 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_STEPUP_NX_NY	(		r,
			actorSize,
			x,
			y,
			z
	)		(r.getStepup(actorSize, x, y, z, 5))

Definition at line 70 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_STEPUP_NX_PY	(		r,
			actorSize,
			x,
			y,
			z
	)		(r.getStepup(actorSize, x, y, z, 6))

Definition at line 69 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_STEPUP_NY	(		r,
			actorSize,
			x,
			y,
			z
	)		(r.getStepup(actorSize, x, y, z, 3))

Definition at line 65 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_STEPUP_PX	(		r,
			actorSize,
			x,
			y,
			z
	)		(r.getStepup(actorSize, x, y, z, 0))

Definition at line 62 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_STEPUP_PX_NY	(		r,
			actorSize,
			x,
			y,
			z
	)		(r.getStepup(actorSize, x, y, z, 7))

Definition at line 68 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_STEPUP_PX_PY	(		r,
			actorSize,
			x,
			y,
			z
	)		(r.getStepup(actorSize, x, y, z, 4))

Definition at line 67 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_STEPUP_PY	(		r,
			actorSize,
			x,
			y,
			z
	)		(r.getStepup(actorSize, x, y, z, 2))

Definition at line 64 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define SizedPosToVec	(		p,
			actorSize,
			v
	)

Value:

{ \
    assert(actorSize > ACTOR_SIZE_INVALID); \
    assert(actorSize <= ACTOR_MAX_SIZE); \
	v[0] = ((int)p[0] - 128) * UNIT_SIZE   + (UNIT_SIZE * actorSize)  / 2; \
	v[1] = ((int)p[1] - 128) * UNIT_SIZE   + (UNIT_SIZE * actorSize)  / 2; \
	v[2] =  (int)p[2]        * UNIT_HEIGHT + UNIT_HEIGHT / 2;  \
}

SizedPosToVect locates the center of an actor based on size and position.

Definition at line 84 of file routing.h.

Referenced by Grid_PosToVec(), RT_CheckCell(), RT_FindOpening(), and RT_MicroTrace().

Function Documentation

bool RT_AllCellsBelowAreFilled	(	const Routing &	routing,
		const int	actorSize,
		const pos3_t	pos
	)

Check if pos is on solid ground.

Parameters

[in]	routing	The map's routing data
[in]	actorSize	The size of the actor along the X and Y axis in cell units
[in]	pos	The position to check below

Returns

true if solid

See also

CL_AddTargetingBox

Todo:

see CL_ActorMoveMouse

Definition at line 331 of file routing.cpp.

References Routing::getCeiling(), and i.

bool RT_CanActorStandHere	(	const Routing &	routing,
		const int	actorSize,
		const pos3_t	pos
	)

Check if an actor can stand(up) in the cell given by pos.

Definition at line 237 of file routing.cpp.

References Routing::getCeiling(), Routing::getFloor(), PLAYER_STANDING_HEIGHT, and QUANT.

Referenced by CL_ActorMoveMode(), CL_ActorStandCrouch_f(), and SV_CanActorStandHere().

int RT_CheckCell	(	mapTiles_t *	mapTiles,
		Routing &	routing,
		const int	actorSize,
		const int	x,
		const int	y,
		const int	z,
		const char **	list
	)

This function looks to see if an actor of a given size can occupy a cell(s) and if so identifies the floor and ceiling for that cell. If the cell has no floor, the floor will be negative with 0 indicating the base for the cell(s). If there is no ceiling in the cell, the first ceiling found above the current cell will be used. If there is no ceiling above the cell, the ceiling will be the top of the model. This function will also adjust all floor and ceiling values for all cells between the found floor and ceiling.

Parameters

[in]	mapTiles	List of tiles the current (RMA-)map is composed of
[in]	routing	The map's routing data
[in]	actorSize	The size of the actor along the X and Y axis in cell units
[in]	x,y	The x/y position in the routing arrays (0 - PATHFINDING_WIDTH-1)
[in]	z	The z position in the routing arrays (0 - PATHFINDING_HEIGHT-1)
[in]	list	The local models list (a local model has a name starting with * followed by the model number)

Returns

The z value of the next cell to scan, usually the cell with the ceiling.

See also

Grid_RecalcRouting

Note

Remember that ceiling values of 1-16 belong to a cell. We need to adjust topQ by 1 to round to the correct z value.

Definition at line 360 of file routing.cpp.

References ACTOR_MAX_SIZE, ACTOR_SIZE_INVALID, CELL_HEIGHT, DIST_EPSILON, trace_s::endpos, footBox(), trace_s::fraction, Routing::getFloor(), halfMicrostepSize, i, AABB::maxs, ModelCeilingToQuant, ModelFloorToQuant, PATHFINDING_HEIGHT, PATHFINDING_LEGROOMHEIGHT, PATHFINDING_MIN_OPENING, PATHFINDING_WIDTH, QUANT, QuantToModel, AABB::set(), Routing::setCeiling(), Routing::setFilled(), Routing::setFloor(), AABB::shift(), SizedPosToVec, tr, UFO_assert(), UNIT_HEIGHT, UNIT_SIZE, VectorCopy, VectorSet, and WALL_SIZE.

Referenced by CheckUnit(), CMod_RerouteMap(), and Grid_RecalcBoxRouting().

void RT_GetMapSize	(	mapTiles_t *	mapTiles,
		AABB &	mapBox
	)

Calculate the map size via model data and store grid size in map_min and map_max. This is done with every new map load.

Parameters

[in]	mapTiles	List of tiles the current (RMA-)map is composed of
[out]	mapBox	The lower and upper extents of the current map.

See also

CMod_LoadRouting

DoRouting

Definition at line 253 of file routing.cpp.

References DIST_EPSILON, trace_s::fraction, i, AABB::maxs, AABB::mins, PATHFINDING_HEIGHT, PATHFINDING_WIDTH, PosToVec, TRACE_VISIBLE_LEVELS, UNIT_HEIGHT, UNIT_SIZE, VectorAdd, VectorClear, VectorCopy, VectorSet, and VectorSubtract.

Referenced by CM_AddMapTile(), and DoRouting().

void RT_UpdateConnectionColumn	(	mapTiles_t *	mapTiles,
		Routing &	routing,
		const int	actorSize,
		const int	x,
		const int	y,
		const int	dir,
		const char **	list,
		const int	minZ,
		const int	maxZ
	)

Routing Function to update the connection between two fields.

Parameters

[in]	mapTiles	List of tiles the current (RMA-)map is composed of
[in]	routing	Routing table of the current loaded map
[in]	actorSize	The size of the actor, in units
[in]	x,y	The position in the routing arrays (0 to PATHFINDING_WIDTH - actorSize)
[in]	dir	The direction to test for a connection through
[in]	list	The local models list (a local model has a name starting with * followed by the model number)
[in]	minZ,maxZ	Limit the update to a part of the column

< The current z value that we are testing.

Definition at line 1292 of file routing.cpp.

References ACTOR_MAX_SIZE, ACTOR_SIZE_INVALID, dvecs, PATHFINDING_WIDTH, RT_ConnSetNoGo(), and RT_UpdateConnection().

Referenced by CheckConnectionsThread(), CMod_RerouteMap(), and Grid_RecalcBoxRouting().

void RT_WriteCSVFiles	(	const Routing &	routing,
		const char *	baseFilename,
		const GridBox &	box
	)

Definition at line 1330 of file routing.cpp.

References ACTOR_MAX_SIZE, Com_DefaultExtension(), f, FILE_WRITE, FS_OpenFile(), FS_Printf(), Routing::getCeiling(), Routing::getFloor(), GridBox::getMaxX(), GridBox::getMaxY(), GridBox::getMaxZ(), GridBox::getMinX(), GridBox::getMinY(), GridBox::getMinZ(), i, MAX_OSPATH, RT_CONN_NX, RT_CONN_NX_NY, RT_CONN_NX_PY, RT_CONN_NY, RT_CONN_PX, RT_CONN_PX_NY, RT_CONN_PX_PY, RT_CONN_PY, RT_STEPUP_NX, RT_STEPUP_NX_NY, RT_STEPUP_NX_PY, RT_STEPUP_NY, RT_STEPUP_PX, RT_STEPUP_PX_NY, RT_STEPUP_PX_PY, RT_STEPUP_PY, and Sys_Error().

Referenced by DoRouting().

Variable Documentation

bool debugTrace

Definition at line 38 of file routing.cpp.

Referenced by DoRouting(), and RT_MicroTrace().