routing.h File Reference

grid pathfinding and routing More...

This graph shows which files directly or indirectly include this file:

Defines
#define	RT_IS_BIDIRECTIONAL 0
#define	RT_CONN(map, actorSize, x, y, z, dir) map[(actorSize) - 1].route[(z)][(y)][(x)][(dir)]
	Some macros to access routing_t values as described above.
#define	RT_CONN_TEST(map, actorSize, x, y, z, dir)
#define	RT_CONN_PX(map, actorSize, x, y, z) (RT_CONN(map, actorSize, x, y, z, 0))
#define	RT_CONN_NX(map, actorSize, x, y, z) (RT_CONN(map, actorSize, x, y, z, 1))
#define	RT_CONN_PY(map, actorSize, x, y, z) (RT_CONN(map, actorSize, x, y, z, 2))
#define	RT_CONN_NY(map, actorSize, x, y, z) (RT_CONN(map, actorSize, x, y, z, 3))
#define	RT_CONN_PX_PY(map, actorSize, x, y, z) (RT_CONN(map, actorSize, x, y, z, 4))
#define	RT_CONN_PX_NY(map, actorSize, x, y, z) (RT_CONN(map, actorSize, x, y, z, 7))
#define	RT_CONN_NX_PY(map, actorSize, x, y, z) (RT_CONN(map, actorSize, x, y, z, 6))
#define	RT_CONN_NX_NY(map, actorSize, x, y, z) (RT_CONN(map, actorSize, x, y, z, 5))
#define	RT_STEPUP(map, actorSize, x, y, z, dir) map[(actorSize) - 1].stepup[(z)][(y)][(x)][(dir)]
#define	RT_STEPUP_PX(map, actorSize, x, y, z) (RT_STEPUP(map, actorSize, x, y, z, 0))
#define	RT_STEPUP_NX(map, actorSize, x, y, z) (RT_STEPUP(map, actorSize, x, y, z, 1))
#define	RT_STEPUP_PY(map, actorSize, x, y, z) (RT_STEPUP(map, actorSize, x, y, z, 2))
#define	RT_STEPUP_NY(map, actorSize, x, y, z) (RT_STEPUP(map, actorSize, x, y, z, 3))
#define	RT_STEPUP_PX_PY(map, actorSize, x, y, z) (RT_STEPUP(map, actorSize, x, y, z, 4))
#define	RT_STEPUP_PX_NY(map, actorSize, x, y, z) (RT_STEPUP(map, actorSize, x, y, z, 7))
#define	RT_STEPUP_NX_PY(map, actorSize, x, y, z) (RT_STEPUP(map, actorSize, x, y, z, 6))
#define	RT_STEPUP_NX_NY(map, actorSize, x, y, z) (RT_STEPUP(map, actorSize, x, y, z, 5))
#define	RT_FLOOR(map, actorSize, x, y, z) map[(actorSize) - 1].floor[(z)][(y)][(x)]
#define	RT_CEILING(map, actorSize, x, y, z) map[(actorSize) - 1].ceil[(z)][(y)][(x)]
#define	RT_FILLED(map, actorSize, x, y, z) (RT_CEILING(map, actorSize, x, y, z) - RT_FLOOR(map, actorSize, x, y, z) < PATHFINDING_MIN_OPENING)
#define	RT_AREA(path, x, y, z, state) ((path)->area[(state)][(z)][(y)][(x)])
#define	RT_AREA_FROM(path, x, y, z, state) ((path)->areaFrom[(state)][(z)][(y)][(x)])
#define	RT_SAREA(path, x, y, z, state) ((path)->areaStored[(state)][(z)][(y)][(x)])
#define	RT_AREA_TEST(path, x, y, z, state)
#define	ModelFloorToQuant(x) (ceil((x) / QUANT))
	These macros are meant to correctly convert from model units to QUANT units and back.
#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.
Functions
int	RT_CheckCell (mapTiles_t mapTiles, routing_t map, 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.
void	RT_UpdateConnectionColumn (mapTiles_t mapTiles, routing_t map, const int actorSize, const int x, const int y, const int dir, const char **list)
	Routing Function to update the connection between two fields.
qboolean	RT_AllCellsBelowAreFilled (const routing_t *map, const int actorSize, const pos3_t pos)
	Check if pos is on solid ground.
void	RT_GetMapSize (mapTiles_t *mapTiles, vec3_t map_min, vec3_t map_max)
	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.
void	RT_WriteCSVFiles (const routing_t map, const char baseFilename, const ipos3_t mins, const ipos3_t maxs)
Variables
qboolean	debugTrace

Detailed Description

grid pathfinding and routing

Definition in file routing.h.

Define Documentation

#define ModelCeilingToQuant ( x ) (floor((x) / QUANT))

Definition at line 104 of file routing.h.

Referenced by Grid_MoveMark(), 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 102 of file routing.h.

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

#define QuantToModel ( x ) ((x) * QUANT)

Definition at line 106 of file routing.h.

Referenced by CL_AddPathingBox(), Grid_Ceiling(), Grid_Floor(), Grid_Height(), Grid_MoveMark(), Grid_StepUp(), RT_CheckCell(), RT_FindOpening(), RT_FindOpeningCeilingFrac(), RT_FindOpeningFloorFrac(), RT_MicroTrace(), and RT_ObstructedTrace().

#define RT_AREA	(	path,
		x,
		y,
		z,
		state	)	((path)->area[(state)][(z)][(y)][(x)])

Definition at line 91 of file routing.h.

Referenced by Grid_MoveCalc(), Grid_MoveLength(), Grid_MoveMark(), Grid_MoveNext(), and Grid_SetMoveData().

#define RT_AREA_FROM	(	path,
		x,
		y,
		z,
		state	)	((path)->areaFrom[(state)][(z)][(y)][(x)])

Definition at line 92 of file routing.h.

Referenced by Grid_MoveNext(), and Grid_SetMoveData().

#define RT_AREA_TEST	(	path,
		x,
		y,
		z,
		state	)

Value:

assert((z) >= 0); assert((z) < PATHFINDING_HEIGHT);\
                                                        assert((y) >= 0); assert((y) < PATHFINDING_WIDTH);\
                                                        assert((x) >= 0); assert((x) < PATHFINDING_WIDTH);\
                                                        assert((state) == 0 || (state) == 1);

Definition at line 94 of file routing.h.

Referenced by Grid_MoveMark(), and Grid_SetMoveData().

#define RT_CEILING	(	map,
		actorSize,
		x,
		y,
		z	)	map[(actorSize) - 1].ceil[(z)][(y)][(x)]

Definition at line 87 of file routing.h.

Referenced by Grid_Ceiling(), Grid_Height(), Grid_MoveMark(), RT_AllCellsBelowAreFilled(), RT_CheckCell(), RT_FindOpening(), RT_PlaceInit(), RT_TracePassage(), RT_UpdateConnection(), and RT_WriteCSVFiles().

#define RT_CONN	(	map,
		actorSize,
		x,
		y,
		z,
		dir	)	map[(actorSize) - 1].route[(z)][(y)][(x)][(dir)]

Some macros to access routing_t values as described above.

Note:: P/N = positive/negative; X/Y =direction; IMPORTANT: actorSize is 1 or greater!!!

Definition at line 57 of file routing.h.

Referenced by Grid_MoveMark(), RT_FillPassageData(), RT_UpdateConnection(), and RT_UpdateConnectionColumn().

#define RT_CONN_NX	(	map,
		actorSize,
		x,
		y,
		z	)	(RT_CONN(map, actorSize, x, y, z, 1))

Definition at line 65 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_CONN_NX_NY	(	map,
		actorSize,
		x,
		y,
		z	)	(RT_CONN(map, actorSize, x, y, z, 5))

Definition at line 72 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_CONN_NX_PY	(	map,
		actorSize,
		x,
		y,
		z	)	(RT_CONN(map, actorSize, x, y, z, 6))

Definition at line 71 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_CONN_NY	(	map,
		actorSize,
		x,
		y,
		z	)	(RT_CONN(map, actorSize, x, y, z, 3))

Definition at line 67 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_CONN_PX	(	map,
		actorSize,
		x,
		y,
		z	)	(RT_CONN(map, actorSize, x, y, z, 0))

Definition at line 64 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_CONN_PX_NY	(	map,
		actorSize,
		x,
		y,
		z	)	(RT_CONN(map, actorSize, x, y, z, 7))

Definition at line 70 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_CONN_PX_PY	(	map,
		actorSize,
		x,
		y,
		z	)	(RT_CONN(map, actorSize, x, y, z, 4))

Definition at line 69 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_CONN_PY	(	map,
		actorSize,
		x,
		y,
		z	)	(RT_CONN(map, actorSize, x, y, z, 2))

Definition at line 66 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_CONN_TEST	(	map,
		actorSize,
		x,
		y,
		z,
		dir	)

Value:

assert((actorSize) > ACTOR_SIZE_INVALID); assert((actorSize) <= ACTOR_MAX_SIZE); \
                                                            assert((z) >= 0); assert((z) < PATHFINDING_HEIGHT);\
                                                            assert((y) >= 0); assert((y) < PATHFINDING_WIDTH);\
                                                            assert((x) >= 0); assert((x) < PATHFINDING_WIDTH);\
                                                            assert((dir) >= 0); assert((dir) < CORE_DIRECTIONS);

Definition at line 58 of file routing.h.

Referenced by Grid_MoveMark(), RT_FillPassageData(), and RT_UpdateConnectionColumn().

#define RT_FILLED	(	map,
		actorSize,
		x,
		y,
		z	)	(RT_CEILING(map, actorSize, x, y, z) - RT_FLOOR(map, actorSize, x, y, z) < PATHFINDING_MIN_OPENING)

Definition at line 88 of file routing.h.

Referenced by Grid_Filled().

#define RT_FLOOR	(	map,
		actorSize,
		x,
		y,
		z	)	map[(actorSize) - 1].floor[(z)][(y)][(x)]

Definition at line 86 of file routing.h.

Referenced by DoRouting(), Grid_Fall(), Grid_Floor(), Grid_Height(), Grid_MoveMark(), RT_CalcNewZ(), RT_CheckCell(), RT_FillPassageData(), RT_FindOpening(), RT_MicroTrace(), RT_PlaceInit(), RT_TraceOnePassage(), RT_UpdateConnection(), and RT_WriteCSVFiles().

#define RT_IS_BIDIRECTIONAL 0

Definition at line 46 of file routing.h.

Referenced by CheckConnectionsThread(), and DoRouting().

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

Definition at line 93 of file routing.h.

Referenced by Grid_MoveLength().

#define RT_STEPUP	(	map,
		actorSize,
		x,
		y,
		z,
		dir	)	map[(actorSize) - 1].stepup[(z)][(y)][(x)][(dir)]

Definition at line 74 of file routing.h.

Referenced by Grid_MoveMark(), Grid_StepUp(), RT_FillPassageData(), RT_UpdateConnection(), and RT_UpdateConnectionColumn().

#define RT_STEPUP_NX	(	map,
		actorSize,
		x,
		y,
		z	)	(RT_STEPUP(map, actorSize, x, y, z, 1))

Definition at line 77 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_STEPUP_NX_NY	(	map,
		actorSize,
		x,
		y,
		z	)	(RT_STEPUP(map, actorSize, x, y, z, 5))

Definition at line 84 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_STEPUP_NX_PY	(	map,
		actorSize,
		x,
		y,
		z	)	(RT_STEPUP(map, actorSize, x, y, z, 6))

Definition at line 83 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_STEPUP_NY	(	map,
		actorSize,
		x,
		y,
		z	)	(RT_STEPUP(map, actorSize, x, y, z, 3))

Definition at line 79 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_STEPUP_PX	(	map,
		actorSize,
		x,
		y,
		z	)	(RT_STEPUP(map, actorSize, x, y, z, 0))

Definition at line 76 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_STEPUP_PX_NY	(	map,
		actorSize,
		x,
		y,
		z	)	(RT_STEPUP(map, actorSize, x, y, z, 7))

Definition at line 82 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_STEPUP_PX_PY	(	map,
		actorSize,
		x,
		y,
		z	)	(RT_STEPUP(map, actorSize, x, y, z, 4))

Definition at line 81 of file routing.h.

Referenced by RT_WriteCSVFiles().

#define RT_STEPUP_PY	(	map,
		actorSize,
		x,
		y,
		z	)	(RT_STEPUP(map, actorSize, x, y, z, 2))

Definition at line 78 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 111 of file routing.h.

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

Function Documentation

qboolean RT_AllCellsBelowAreFilled	(	const routing_t *	map,
		const int	actorSize,
		const pos3_t	pos
	)

Check if pos is on solid ground.

Parameters:

`[in]`	map	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 323 of file routing.c.

References qfalse, qtrue, and RT_CEILING.

int RT_CheckCell	(	mapTiles_t *	mapTiles,
		routing_t *	map,
		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]`	map	The map's routing data
`[in]`	actorSize	The size of the actor along the X and Y axis in cell units
`[in]`	x	The x position in the routing arrays (0 - PATHFINDING_WIDTH-1)
`[in]`	y	The y position in the routing arrays (0 - PATHFINDING_WIDTH-1)
`[in]`	z	The z position in the routing arrays (0 - PATHFINDING_HEIGHT-1)

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 353 of file routing.c.

References ACTOR_MAX_SIZE, ACTOR_SIZE_INVALID, CELL_HEIGHT, Com_Printf(), debugTrace, DIST_EPSILON, trace_s::endpos, trace_s::fraction, halfMicrostepSize, box_s::maxs, box_s::mins, ModelCeilingToQuant, ModelFloorToQuant, PATHFINDING_HEIGHT, PATHFINDING_LEGROOMHEIGHT, PATHFINDING_MIN_OPENING, PATHFINDING_WIDTH, pos, qtrue, QUANT, QuantToModel, RT_CEILING, RT_FLOOR, SizedPosToVec, UNIT_HEIGHT, UNIT_SIZE, vec3_origin, VectorAdd, VectorCopy, VectorSet, and WALL_SIZE.

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

void RT_GetMapSize	(	mapTiles_t *	mapTiles,
		vec3_t	map_min,
		vec3_t	map_max
	)

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:

`[out]`	map_min	The lower extents of the current map.
`[out]`	map_max	The upper extents of the current map.

See also:: CMod_LoadRouting; DoRouting

Definition at line 244 of file routing.c.

References trace_s::fraction, box_s::maxs, box_s::mins, PATHFINDING_HEIGHT, PATHFINDING_WIDTH, PosToVec, UNIT_HEIGHT, UNIT_SIZE, vec3_origin, VectorAdd, VectorCopy, VectorSet, and VectorSubtract.

Referenced by CM_AddMapTile(), and DoRouting().

void RT_UpdateConnectionColumn	(	mapTiles_t *	mapTiles,
		routing_t *	map,
		const int	actorSize,
		const int	x,
		const int	y,
		const int	dir,
		const char **	list
	)

Routing Function to update the connection between two fields.

Parameters:

`[in]`	map	Routing field of the current loaded map
`[in]`	actorSize	The size of the actor, in units
`[in]`	x	The x position in the routing arrays (0 to PATHFINDING_WIDTH - actorSize)
`[in]`	y	The y position in the routing arrays (0 to PATHFINDING_WIDTH - actorSize)
`[in]`	dir	The direction to test for a connection through