routing.c File Reference

grid pathfinding and routing More...

#include "common.h"
#include "routing.h"

Include dependency graph for routing.c:

Data Structures
struct	place_s
struct	opening_s
	An 'opening' describes the connection between two adjacent spaces where an actor can exist in a cell. More...
Defines
#define	RT_NO_OPENING -1
#define	halfMicrostepSize (PATHFINDING_MICROSTEP_SIZE / 2 - DIST_EPSILON)
#define	half1x1Width (UNIT_SIZE * 1 / 2 - WALL_SIZE - DIST_EPSILON)
#define	half2x2Width (UNIT_SIZE * 2 / 2 - WALL_SIZE - DIST_EPSILON)
Typedefs
typedef struct place_s	place_t
typedef struct opening_s	opening_t
	An 'opening' describes the connection between two adjacent spaces where an actor can exist in a cell.
Functions
static void	RT_PlaceInit (const routing_t map, const actorSizeEnum_t actorSize, place_t p, const int x, const int y, const int z)
static qboolean	RT_PlaceIsUsable (const place_t *p)
static qboolean	RT_PlaceDoesIntersectEnough (const place_t p, const place_t other)
static int	RT_PlaceIsShifted (const place_t p, const place_t other)
	This function detects a special stairway situation, where one place is right in front of a stairway and has a floor at eg. 1 and a ceiling at eg. 16. The other place has the beginning of the stairway, so the floor is at eg. 6 and the ceiling is that of the higher level, eg. 32.
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.
qboolean	RT_AllCellsBelowAreFilled (const routing_t *map, const int actorSize, const pos3_t pos)
	Check if pos is on solid ground.
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.
static int	RT_FillPassageData (routing_t *map, const actorSizeEnum_t actorSize, const int dir, const int x, const int y, const int z, const int openingSize, const int openingBase, const int stepup)
	Performs traces to find a passage between two points given an upper and lower bound.
static trace_t	RT_ObstructedTrace (mapTiles_t mapTiles, const vec3_t start, const vec3_t end, actorSizeEnum_t actorSize, int hi, int lo, const char *list)
	Helper function to trace for walls.
static int	RT_FindOpeningFloorFrac (mapTiles_t mapTiles, const vec3_t start, const vec3_t end, const actorSizeEnum_t actorSize, const float frac, const int startingHeight, const char *list)
	Performs a trace to find the floor of a passage a fraction of the way from start to end.
static int	RT_FindOpeningCeilingFrac (mapTiles_t mapTiles, const vec3_t start, const vec3_t end, const actorSizeEnum_t actorSize, const float frac, const int startingHeight, const char *list)
	Performs a trace to find the ceiling of a passage a fraction of the way from start to end.
static int	RT_FindOpeningFloor (mapTiles_t mapTiles, const vec3_t start, const vec3_t end, const actorSizeEnum_t actorSize, const int startingHeight, const int floorLimit, const char *list)
	Performs traces to find the approximate floor of a passage.
static int	RT_FindOpeningCeiling (mapTiles_t mapTiles, const vec3_t start, const vec3_t end, const actorSizeEnum_t actorSize, const int startingHeight, const int ceilLimit, const char *list)
	Performs traces to find the approximate ceiling of a passage.
static int	RT_CalcNewZ (const routing_t *map, const actorSizeEnum_t actorSize, const int ax, const int ay, const int top, const int hi)
static int	RT_TraceOpening (mapTiles_t mapTiles, const routing_t map, const actorSizeEnum_t actorSize, const vec3_t start, const vec3_t end, const int ax, const int ay, const int bottom, const int top, int lo, int hi, int lo_val, int hi_val, const char **list)
	Performs actual trace to find a passage between two points given an upper and lower bound.
static int	RT_FindOpening (mapTiles_t mapTiles, const routing_t map, const actorSizeEnum_t actorSize, place_t from, const int ax, const int ay, const int bottom, const int top, int lo_val, int hi_val, const char *list)
	Performs traces to find a passage between two points given an upper and lower bound.
static int	RT_MicroTrace (mapTiles_t mapTiles, const routing_t map, const actorSizeEnum_t actorSize, place_t from, const int ax, const int ay, const int az, const int stairwaySituation, opening_t opening, const char **list)
	Performs small traces to find places when an actor can step up.
static int	RT_TraceOnePassage (mapTiles_t mapTiles, const routing_t map, const actorSizeEnum_t actorSize, place_t from, place_t to, opening_t opening, const char *list)
	Performs traces to find a passage between two points given an upper and lower bound.
static void	RT_TracePassage (mapTiles_t mapTiles, const routing_t map, const actorSizeEnum_t actorSize, const int x, const int y, const int z, const int ax, const int ay, opening_t opening, const char *list)
	Performs traces to find a passage between two points given an upper and lower bound.
static int	RT_UpdateConnection (mapTiles_t mapTiles, routing_t map, const actorSizeEnum_t actorSize, const int x, const int y, const int ax, const int ay, const int z, const int dir, const char **list)
	Routing Function to update the connection between two fields.
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.
void	RT_WriteCSVFiles (const routing_t map, const char baseFilename, const ipos3_t mins, const ipos3_t maxs)
Variables
qboolean	debugTrace = qfalse
static const box_t	footBox
static const box_t	actor1x1Box
static const box_t	actor2x2Box

Detailed Description

grid pathfinding and routing

Definition in file routing.c.

Define Documentation

#define half1x1Width (UNIT_SIZE * 1 / 2 - WALL_SIZE - DIST_EPSILON)

Definition at line 54 of file routing.c.

#define half2x2Width (UNIT_SIZE * 2 / 2 - WALL_SIZE - DIST_EPSILON)

Definition at line 55 of file routing.c.

#define halfMicrostepSize (PATHFINDING_MICROSTEP_SIZE / 2 - DIST_EPSILON)

Definition at line 48 of file routing.c.

Referenced by RT_CheckCell().

#define RT_NO_OPENING -1

Definition at line 45 of file routing.c.

Referenced by RT_CalcNewZ(), RT_FindOpening(), RT_TraceOnePassage(), and RT_TraceOpening().

Typedef Documentation

typedef struct opening_s opening_t

An 'opening' describes the connection between two adjacent spaces where an actor can exist in a cell.

Note:: Note that if size is 0, the other members are undefined. They may contain reasonable values, though

typedef struct place_s place_t

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.

static int RT_CalcNewZ	(	const routing_t *	map,
		const actorSizeEnum_t	actorSize,
		const int	ax,
		const int	ay,
		const int	top,
		const int	hi
	)			`[static]`

Note:: Return a value only if there is a floor for the adjacent cell. Also the found adjacent lo must be at lease MIN_OPENING-MIN_STEPUP below the top.

Definition at line 832 of file routing.c.

References CELL_HEIGHT, Com_Printf(), debugTrace, PATHFINDING_HEIGHT, PATHFINDING_MIN_OPENING, PATHFINDING_MIN_STEPUP, RT_FLOOR, and RT_NO_OPENING.

Referenced by RT_FindOpening(), and RT_TraceOpening().

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

static int RT_FillPassageData	(	routing_t *	map,
		const actorSizeEnum_t	actorSize,
		const int	dir,
		const int	x,
		const int	y,
		const int	z,
		const int	openingSize,
		const int	openingBase,
		const int	stepup
	)			`[static]`

Performs traces to find a passage between two points given an upper and lower bound.

Parameters:

`[in]`	map	The map's routing data
`[in]`	actorSize	The actor's size
`[in]`	dir	Direction of movement
`[in]`	x	Starting x coordinate
`[in]`	y	Starting y coordinate
`[in]`	z	Starting z coordinate
`[in]`	openingSize	Absolute height in QUANT units of the opening.
`[in]`	openingBase	Absolute height in QUANT units of the bottom of the opening.
`[in]`	stepup	Required stepup to travel in this direction.

< Floor and ceiling Z cell coordinates

Definition at line 601 of file routing.c.

References CELL_HEIGHT, Com_Printf(), debugTrace, PATHFINDING_HEIGHT, PATHFINDING_NO_STEPUP, RT_CONN, RT_CONN_TEST, RT_FLOOR, and RT_STEPUP.

Referenced by RT_UpdateConnection().

static int RT_FindOpening	(	mapTiles_t *	mapTiles,
		const routing_t *	map,
		const actorSizeEnum_t	actorSize,
		place_t *	from,
		const int	ax,
		const int	ay,
		const int	bottom,
		const int	top,
		int *	lo_val,
		int *	hi_val,
		const char **	list
	)			`[static]`

Performs traces to find a passage between two points given an upper and lower bound.

Parameters:

`[in]`	map	The map's routing data
`[in]`	actorSize	The actor's size
`[in]`	from	Starting place
`[in]`	ax	Ending x coordinate
`[in]`	ay	Ending y coordinate
`[in]`	bottom	Actual height of the starting floor.
`[in]`	top	Actual height of the starting ceiling.
`[out]`	lo_val	Actual height of the bottom of the found passage.
`[out]`	hi_val	Actual height of the top of the found passage.

Returns:: The new z value of the actor after traveling in this direction from the starting location.

Definition at line 916 of file routing.c.

References ACTOR_SIZE_NORMAL, place_s::ceiling, place_s::cell, CELL_HEIGHT, Com_Printf(), debugTrace, trace_s::endpos, ModelFloorToQuant, PATHFINDING_HEIGHT, PATHFINDING_MIN_OPENING, PATHFINDING_MIN_STEPUP, pos, QuantToModel, RT_CalcNewZ(), RT_CEILING, RT_FLOOR, RT_NO_OPENING, RT_TraceOpening(), SizedPosToVec, UNIT_HEIGHT, VectorCopy, VectorInterpolation, and VectorSet.

Referenced by RT_TraceOnePassage().

static int RT_FindOpeningCeiling	(	mapTiles_t *	mapTiles,
		const vec3_t	start,
		const vec3_t	end,
		const actorSizeEnum_t	actorSize,
		const int	startingHeight,
		const int	ceilLimit,
		const char **	list
	)			`[static]`

Performs traces to find the approximate ceiling of a passage.

Parameters:

`[in]`	start	The starting coordinate to search for a ceiling from.
`[in]`	end	The starting coordinate to search for a ceiling from.
`[in]`	actorSize	The actor's size.
`[in]`	startingHeight	The starting height for this upward trace.
`[in]`	ceilLimit	The highest the ceiling may be.

Returns:: The absolute height of the found ceiling in QUANT units.

Definition at line 802 of file routing.c.

References Com_Printf(), debugTrace, and RT_FindOpeningCeilingFrac().

Referenced by RT_TraceOpening().

static int RT_FindOpeningCeilingFrac	(	mapTiles_t *	mapTiles,
		const vec3_t	start,
		const vec3_t	end,
		const actorSizeEnum_t	actorSize,
		const float	frac,
		const int	startingHeight,
		const char **	list
	)			`[static]`

Performs a trace to find the ceiling of a passage a fraction of the way from start to end.

Parameters:

`[in]`	start	The starting coordinate to search for a ceiling from.
`[in]`	end	The starting coordinate to search for a ceiling from.
`[in]`	actorSize	The actor's size.
`[in]`	frac	The fraction of the distance traveled from start to end, using (0.0 to 1.0).
`[in]`	startingHeight	The starting height for this upward trace.

Returns:: The absolute height of the found ceiling in QUANT units.

< Midpoint line to trace across

< Tracing box extents

Definition at line 730 of file routing.c.

References ACTOR_SIZE_NORMAL, Com_Printf(), debugTrace, DIST_EPSILON, trace_s::endpos, ModelCeilingToQuant, PATHFINDING_HEIGHT, QUANT, QuantToModel, UNIT_HEIGHT, VectorCopy, and VectorInterpolation.

Referenced by RT_FindOpeningCeiling().

static int RT_FindOpeningFloor	(	mapTiles_t *	mapTiles,
		const vec3_t	start,
		const vec3_t	end,
		const actorSizeEnum_t	actorSize,
		const int	startingHeight,
		const int	floorLimit,
		const char **	list
	)			`[static]`

Performs traces to find the approximate floor of a passage.

Parameters:

`[in]`	start	The starting coordinate to search for a floor from.
`[in]`	end	The starting coordinate to search for a floor from.
`[in]`	actorSize	The actor's size.
`[in]`	startingHeight	The starting height for this downward trace.
`[in]`	floorLimit	The lowest limit of the found floor.

Returns:: The absolute height of the found floor in QUANT units.

Definition at line 762 of file routing.c.

References Com_Printf(), debugTrace, and RT_FindOpeningFloorFrac().

Referenced by RT_TraceOpening().

static int RT_FindOpeningFloorFrac	(	mapTiles_t *	mapTiles,
		const vec3_t	start,
		const vec3_t	end,
		const actorSizeEnum_t	actorSize,
		const float	frac,
		const int	startingHeight,
		const char **	list
	)			`[static]`

Performs a trace to find the floor of a passage a fraction of the way from start to end.

Parameters:

`[in]`	start	The starting coordinate to search for a floor from.
`[in]`	end	The starting coordinate to search for a floor from.
`[in]`	actorSize	The actor's size.
`[in]`	frac	The fraction of the distance traveled from start to end, using (0.0 to 1.0).
`[in]`	startingHeight	The starting height for this upward trace.

Returns:: The absolute height of the found floor in QUANT units.

< Midpoint line to trace across

< Tracing box extents

Definition at line 697 of file routing.c.

References ACTOR_SIZE_NORMAL, Com_Printf(), debugTrace, DIST_EPSILON, trace_s::endpos, ModelFloorToQuant, QUANT, QuantToModel, VectorCopy, and VectorInterpolation.

Referenced by RT_FindOpeningFloor().

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

static int RT_MicroTrace	(	mapTiles_t *	mapTiles,
		const routing_t *	map,
		const actorSizeEnum_t	actorSize,
		place_t *	from,
		const int	ax,
		const int	ay,
		const int	az,
		const int	stairwaySituation,
		opening_t *	opening,
		const char **	list
	)			`[static]`

Performs small traces to find places when an actor can step up.

Parameters:

`[in]`	map	The map's routing data
`[in]`	actorSize	The actor's size
`[in]`	from	Starting place
`[in]`	ax	Ending x coordinate
`[in]`	ay	Ending y coordinate
`[in]`	az	Ending z coordinate
`[in]`	stairwaySituation	whether we are standing in front of a stairway
`[out]`	opening	descriptor of the opening found, if any

Returns:: The change in floor height in QUANT units because of the additional trace.

< Just above the bottom of the found passage

Note:: This for loop is bi-directional: i may be decremented to retrace prior steps.

< Was originally -CELL_HEIGHT, but stepup is needed to go UP, not down.

Note:: This for loop is bi-directional: i may be decremented to retrace prior steps.

< Note that for this part of the code, this is the LOWEST i.

< Was originally -CELL_HEIGHT, but stepup is needed to go UP, not down.

Definition at line 1019 of file routing.c.

References opening_s::base, place_s::cell, CELL_HEIGHT, Com_Printf(), debugTrace, DIST_EPSILON, place_s::floor, opening_s::invstepup, ModelFloorToQuant, PATHFINDING_MICROSTEP_SIZE, PATHFINDING_MICROSTEP_SKIP, PATHFINDING_MIN_STEPUP, pos, QUANT, QuantToModel, RT_FLOOR, opening_s::size, SizedPosToVec, opening_s::stepup, UNIT_SIZE, and VectorSet.

Referenced by RT_TraceOnePassage().

static trace_t RT_ObstructedTrace	(	mapTiles_t *	mapTiles,
		const vec3_t	start,
		const vec3_t	end,
		actorSizeEnum_t	actorSize,
		int	hi,
		int	lo,
		const char **	list
	)			`[static]`

Helper function to trace for walls.

Parameters:

`[in]`	start	The starting point of the trace, at the FLOOR'S CENTER.
`[in]`	end	The end point of the trace, centered x and y at the destination but at the same height as start.
`[in]`	actorSize	The actor's size in cell units.
`[in]`	hi	The upper height ABOVE THE FLOOR of the bounding box.
`[in]`	lo	The lower height ABOVE THE FLOOR of the bounding box.

< Tracing box extents

Definition at line 674 of file routing.c.

References DIST_EPSILON, box_s::maxs, box_s::mins, QuantToModel, UNIT_SIZE, VectorSet, and WALL_SIZE.

Referenced by RT_TraceOpening().

static qboolean RT_PlaceDoesIntersectEnough	(	const place_t *	p,
		const place_t *	other
	)			`[inline, static]`

Definition at line 97 of file routing.c.

References place_s::ceiling, place_s::floor, and PATHFINDING_MIN_OPENING.

Referenced by RT_TracePassage().

static void RT_PlaceInit	(	const routing_t *	map,
		const actorSizeEnum_t	actorSize,
		place_t *	p,
		const int	x,
		const int	y,
		const int	z
	)			`[inline, static]`

Definition at line 80 of file routing.c.

References place_s::ceiling, place_s::cell, CELL_HEIGHT, place_s::floor, place_s::floorZ, PATHFINDING_MIN_OPENING, qfalse, qtrue, RT_CEILING, RT_FLOOR, and place_s::usable.

Referenced by RT_TracePassage().

static int RT_PlaceIsShifted	(	const place_t *	p,
		const place_t *	other
	)			`[inline, static]`

This function detects a special stairway situation, where one place is right in front of a stairway and has a floor at eg. 1 and a ceiling at eg. 16. The other place has the beginning of the stairway, so the floor is at eg. 6 and the ceiling is that of the higher level, eg. 32.

Definition at line 108 of file routing.c.

References place_s::ceiling, place_s::floor, and RT_PlaceIsUsable().

Referenced by RT_TraceOnePassage().

static qboolean RT_PlaceIsUsable ( const place_t * p ) [inline, static]

Definition at line 92 of file routing.c.

References place_s::usable.

Referenced by RT_PlaceIsShifted(), and RT_TracePassage().

static int RT_TraceOnePassage	(	mapTiles_t *	mapTiles,
		const routing_t *	map,
		const actorSizeEnum_t	actorSize,
		place_t *	from,
		place_t *	to,
		opening_t *	opening,
		const char **	list
	)			`[static]`

Performs traces to find a passage between two points given an upper and lower bound.

Parameters:

`[in]`	map	The map's routing data
`[in]`	actorSize	The actor's size
`[in]`	from	Starting place
`[in]`	to	Ending place
`[out]`	opening	descriptor of the opening found, if any

Returns:: The size in QUANT units of the detected opening.

< absolute ceiling of the passage found.

< z height of the actor after moving in this direction.

Todo:: CELL_HEIGHT can be replaced with the largest actor height.

Definition at line 1214 of file routing.c.

References opening_s::base, place_s::ceiling, place_s::cell, CELL_HEIGHT, Com_Printf(), debugTrace, place_s::floor, place_s::floorZ, opening_s::invstepup, PATHFINDING_BIG_STEPDOWN, PATHFINDING_BIG_STEPUP, PATHFINDING_MAX_STEPUP, PATHFINDING_MIN_OPENING, PATHFINDING_MIN_STEPUP, PATHFINDING_NO_STEPUP, RT_FindOpening(), RT_FLOOR, RT_MicroTrace(), RT_NO_OPENING, RT_PlaceIsShifted(), opening_s::size, and opening_s::stepup.

Referenced by RT_TracePassage().

static int RT_TraceOpening	(	mapTiles_t *	mapTiles,
		const routing_t *	map,
		const actorSizeEnum_t	actorSize,
		const vec3_t	start,
		const vec3_t	end,
		const int	ax,
		const int	ay,
		const int	bottom,
		const int	top,
		int	lo,
		int	hi,
		int *	lo_val,
		int *	hi_val,
		const char **	list
	)			`[static]`

Performs actual trace to find a passage between two points given an upper and lower bound.

Parameters:

`[in]`	map	The map's routing data
`[in]`	actorSize	The actor's size
`[in]`	start	Starting trace coordinate
`[in]`	end	Ending trace coordinate
`[in]`	ax	Ending x coordinate
`[in]`	ay	Ending y coordinate
`[in]`	bottom	Actual height of the starting floor.
`[in]`	top	Actual height of the starting ceiling.
`[in]`	lo	Actual height of the bottom of the slice trace.
`[in]`	hi	Actual height of the top of the slice trace.
`[out]`	lo_val	Actual height of the bottom of the found passage.
`[out]`	hi_val	Actual height of the top of the found passage.

Returns:: The new z value of the actor after traveling in this direction from the starting location.

Definition at line 875 of file routing.c.

References Com_Printf(), debugTrace, trace_s::fraction, PATHFINDING_MIN_OPENING, RT_CalcNewZ(), RT_FindOpeningCeiling(), RT_FindOpeningFloor(), RT_NO_OPENING, and RT_ObstructedTrace().

Referenced by RT_FindOpening().

static void RT_TracePassage	(	mapTiles_t *	mapTiles,
		const routing_t *	map,
		const actorSizeEnum_t	actorSize,
		const int	x,
		const int	y,
		const int	z,
		const int	ax,
		const int	ay,
		opening_t *	opening,
		const char **	list
	)			`[static]`

Performs traces to find a passage between two points given an upper and lower bound.

Parameters:

`[in]`	map	The map's routing data
`[in]`	actorSize	The actor's size
`[in]`	x	Starting x coordinate
`[in]`	y	Starting y coordinate
`[in]`	z	Starting z coordinate
`[in]`	ax	Ending x coordinate
`[in]`	ay	Ending y coordinate
`[out]`	opening	descriptor of the opening found, if any

we don't need the cell below the adjacent cell because we should have already checked it

Definition at line 1299 of file routing.c.

References opening_s::base, place_s::ceiling, CELL_HEIGHT, Com_Printf(), debugTrace, place_s::floor, opening_s::invstepup, PATHFINDING_HEIGHT, PATHFINDING_MIN_OPENING, PATHFINDING_NO_STEPUP, RT_CEILING, RT_PlaceDoesIntersectEnough(), RT_PlaceInit(), RT_PlaceIsUsable(), RT_TraceOnePassage(), opening_s::size, and opening_s::stepup.

Referenced by RT_UpdateConnection().

static int RT_UpdateConnection	(	mapTiles_t *	mapTiles,
		routing_t *	map,
		const actorSizeEnum_t	actorSize,
		const int	x,
		const int	y,
		const int	ax,
		const int	ay,
		const int	z,
		const int	dir,
		const char **	list
	)			`[static]`

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]`	ax	The x of the adjacent cell
`[in]`	ay	The y of the adjacent cell
`[in]`	z	The z position in the routing arrays (0 to PATHFINDING_HEIGHT - 1)
`[in]`	dir	The direction to test for a connection through

the opening between the two cells

Note:: OK, simple test here. We know both cells have a ceiling, so they are both open. If the absolute ceiling of one is below the absolute floor of the other, then there is no intersection.

Definition at line 1382 of file routing.c.

References opening_s::base, CELL_HEIGHT, Com_Printf(), debugTrace, opening_s::invstepup, PATHFINDING_BIG_STEPDOWN, PATHFINDING_BIG_STEPUP, PATHFINDING_HEIGHT, PATHFINDING_NO_STEPUP, RT_CEILING, RT_CONN, RT_FillPassageData(), RT_FLOOR, RT_STEPUP, RT_TracePassage(), opening_s::size, and opening_s::stepup.

Referenced by RT_UpdateConnectionColumn().

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

< The current z value that we are testing.

< The last z value processed by the tracing function.

Definition at line 1477 of file routing.c.

References ACTOR_MAX_SIZE, ACTOR_SIZE_INVALID, Com_Printf(), debugTrace, dvecs, PATHFINDING_HEIGHT, PATHFINDING_NO_STEPUP, PATHFINDING_WIDTH, RT_CONN, RT_CONN_TEST, RT_STEPUP, and RT_UpdateConnection().

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

void RT_WriteCSVFiles	(	const routing_t *	map,
		const char *	baseFilename,
		const ipos3_t	mins,
		const ipos3_t	maxs
	)

Definition at line 1522 of file routing.c.

References ACTOR_MAX_SIZE, Com_DefaultExtension(), qFILE_s::f, f, FILE_WRITE, FS_CloseFile(), FS_OpenFile(), FS_Printf(), MAX_OSPATH, RT_CEILING, 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_FLOOR, 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

const box_t actor1x1Box [static]

Initial value:

 {{-half1x1Width, -half1x1Width, 0},
                            { half1x1Width,  half1x1Width, 0}}

Definition at line 57 of file routing.c.

const box_t actor2x2Box [static]

Initial value:

 {{-half2x2Width, -half2x2Width, 0},
                            { half2x2Width,  half2x2Width, 0}}

Definition at line 59 of file routing.c.

qboolean debugTrace = qfalse

Definition at line 37 of file routing.c.

Referenced by DoRouting(), RT_CalcNewZ(), RT_CheckCell(), RT_FillPassageData(), RT_FindOpening(), RT_FindOpeningCeiling(), RT_FindOpeningCeilingFrac(), RT_FindOpeningFloor(), RT_FindOpeningFloorFrac(), RT_MicroTrace(), RT_TraceOnePassage(), RT_TraceOpening(), RT_TracePassage(), RT_UpdateConnection(), and RT_UpdateConnectionColumn().

const box_t footBox [static]

Initial value:

 {{-halfMicrostepSize, -halfMicrostepSize, 0},
                        { halfMicrostepSize,  halfMicrostepSize, 0}}

Definition at line 50 of file routing.c.

routing.c File Reference

Data Structures

Defines

Typedefs

Functions

Variables

Detailed Description

Define Documentation

Typedef Documentation

Function Documentation

Variable Documentation