routing.cpp File Reference

grid pathfinding and routing More...

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

Go to the source code of this file.

Data Structures
class	RoutingData
	RT_data_s contains the essential data that is passed to most of the RT_* functions. More...
struct	place_s
	A 'place' is a part of a grid column where an actor can exist Unlike for a grid-cell, floor and ceiling are absolute values. More...
struct	opening_s
	An 'opening' describes the connection between two adjacent spaces where an actor can exist in a cell. More...

Macros
#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
	A 'place' is a part of a grid column where an actor can exist Unlike for a grid-cell, floor and ceiling are absolute values. More...
typedef struct opening_s	opening_t
	An 'opening' describes the connection between two adjacent spaces where an actor can exist in a cell. More...

Functions
static const AABB	footBox (-halfMicrostepSize,-halfMicrostepSize, 0, halfMicrostepSize, halfMicrostepSize, 0)
static const AABB	actor1x1Box (-half1x1Width,-half1x1Width, 0, half1x1Width, half1x1Width, 0)
static const AABB	actor2x2Box (-half2x2Width,-half2x2Width, 0, half2x2Width, half2x2Width, 0)
static void	RT_StepupSet (RoutingData *rtd, const int x, const int y, const int z, const int dir, const int val)
static void	RT_ConnSetNoGo (RoutingData *rtd, const int x, const int y, const int z, const int dir)
static void	RT_PlaceInit (const Routing &routing, const actorSizeEnum_t actorSize, place_t *p, const int x, const int y, const int z)
static bool	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. 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_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_AllCellsBelowAreFilled (const Routing &routing, const int actorSize, const pos3_t pos)
	Check if pos is on solid ground. More...
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...
static int	RT_FillPassageData (RoutingData *rtd, 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. More...
static trace_t	RT_ObstructedTrace (const RoutingData *rtd, const Line &traceLine, int hi, int lo)
	Helper function to trace for walls. More...
static int	RT_FindOpeningFloorFrac (const RoutingData *rtd, const vec3_t start, const vec3_t end, const float frac, const int startingHeight)
	Performs a trace to find the floor of a passage a fraction of the way from start to end. More...
static int	RT_FindOpeningCeilingFrac (const RoutingData *rtd, const vec3_t start, const vec3_t end, const float frac, const int startingHeight)
	Performs a trace to find the ceiling of a passage a fraction of the way from start to end. More...
static int	RT_FindOpeningFloor (const RoutingData *rtd, const vec3_t start, const vec3_t end, const int startingHeight, const int floorLimit)
	Performs traces to find the approximate floor of a passage. More...
static int	RT_FindOpeningCeiling (const RoutingData *rtd, const vec3_t start, const vec3_t end, const int startingHeight, const int ceilLimit)
	Performs traces to find the approximate ceiling of a passage. More...
static int	RT_CalcNewZ (const RoutingData *rtd, const int ax, const int ay, const int top, const int hi)
static int	RT_TraceOpening (const RoutingData *rtd, 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 *foundLow, int *foundHigh)
	Performs actual trace to find a passage between two points given an upper and lower bound. More...
static int	RT_FindOpening (RoutingData *rtd, const place_t *from, const int ax, const int ay, const int bottom, const int top, int *foundLow, int *foundHigh)
	Performs traces to find a passage between two points given an upper and lower bound. More...
static int	RT_MicroTrace (RoutingData *rtd, const place_t *from, const int ax, const int ay, const int az, const int stairwaySituation, opening_t *opening)
	Performs small traces to find places when an actor can step up. More...
static int	RT_TraceOnePassage (RoutingData *rtd, const place_t *from, const place_t *to, opening_t *opening)
	Performs traces to find a passage between two points given an upper and lower bound. More...
static void	RT_TracePassage (RoutingData *rtd, const int x, const int y, const int z, const int ax, const int ay, opening_t *opening)
	Performs traces to find a passage between two points. More...
static int	RT_UpdateConnection (RoutingData *rtd, const int x, const int y, const int ax, const int ay, const int z, const int dir)
	Routing Function to update the connection between two fields. More...
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. More...
void	RT_WriteCSVFiles (const Routing &routing, const char *baseFilename, const GridBox &box)

Variables
bool	debugTrace = false

Detailed Description

grid pathfinding and routing

Definition in file routing.cpp.

Macro Definition Documentation

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

Definition at line 54 of file routing.cpp.

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

Definition at line 55 of file routing.cpp.

#define halfMicrostepSize   (PATHFINDING_MICROSTEP_SIZE / 2 - DIST_EPSILON)

Definition at line 49 of file routing.cpp.

Referenced by RT_CheckCell().

#define RT_NO_OPENING   -1

Definition at line 46 of file routing.cpp.

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

A 'place' is a part of a grid column where an actor can exist Unlike for a grid-cell, floor and ceiling are absolute values.

Function Documentation

static const AABB actor1x1Box ( -  half1x1Width, -  half1x1Width, 0  , half1x1Width  , half1x1Width  , 0    )

static

Referenced by RT_FindOpening(), RT_FindOpeningCeilingFrac(), and RT_FindOpeningFloorFrac().

static const AABB actor2x2Box ( -  half2x2Width, -  half2x2Width, 0  , half2x2Width  , half2x2Width  , 0    )

static

Referenced by RT_FindOpening(), RT_FindOpeningCeilingFrac(), and RT_FindOpeningFloorFrac().

static const AABB footBox ( -  halfMicrostepSize, -  halfMicrostepSize, 0  , halfMicrostepSize  , halfMicrostepSize  , 0    )

static

Referenced by RT_CheckCell(), and RT_MicroTrace().

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.

static int RT_CalcNewZ ( const RoutingData *  rtd, 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 737 of file routing.cpp.

References RoutingData::actorSize, CELL_HEIGHT, Routing::getFloor(), PATHFINDING_HEIGHT, PATHFINDING_MIN_OPENING, PATHFINDING_MIN_STEPUP, RoutingData::routing, and RT_NO_OPENING.

Referenced by RT_FindOpening(), and RT_TraceOpening().

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

static void RT_ConnSetNoGo ( RoutingData *  rtd, const int  x, const int  y, const int  z, const int  dir  )

inlinestatic

Definition at line 103 of file routing.cpp.

References RoutingData::actorSize, PATHFINDING_NO_STEPUP, RoutingData::routing, Routing::setConn(), and Routing::setStepup().

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

static int RT_FillPassageData ( RoutingData *  rtd, 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]	rtd	The essential routing data with map, actorsize, ents
[in]	dir	Direction of movement
[in]	x,y,z	Grid coordinates of the starting position
[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 541 of file routing.cpp.

References RoutingData::actorSize, CELL_HEIGHT, Routing::getFloor(), i, PATHFINDING_HEIGHT, RoutingData::routing, RT_ConnSetNoGo(), RT_StepupSet(), and Routing::setConn().

Referenced by RT_UpdateConnection().

static int RT_FindOpening ( RoutingData *  rtd, const place_t *  from, const int  ax, const int  ay, const int  bottom, const int  top, int *  foundLow, int *  foundHigh  )

static

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

Parameters

[in]	rtd	The essential routing data with map, actorsize, ents
[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]	foundLow	Actual height of the bottom of the found passage.
[out]	foundHigh	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 812 of file routing.cpp.

References actor1x1Box(), actor2x2Box(), ACTOR_SIZE_NORMAL, RoutingData::actorSize, place_s::ceiling, place_s::cell, CELL_HEIGHT, trace_s::endpos, Routing::getCeiling(), RoutingData::list, RoutingData::mapTiles, ModelFloorToQuant, PATHFINDING_HEIGHT, PATHFINDING_MIN_OPENING, PATHFINDING_MIN_STEPUP, QuantToModel, RoutingData::routing, RT_CalcNewZ(), RT_NO_OPENING, RT_TraceOpening(), SizedPosToVec, tr, UNIT_HEIGHT, VectorCopy, VectorInterpolation, and VectorSet.

Referenced by RT_TraceOnePassage().

static int RT_FindOpeningCeiling ( const RoutingData *  rtd, const vec3_t  start, const vec3_t  end, const int  startingHeight, const int  ceilLimit  )

static

Performs traces to find the approximate ceiling of a passage.

Parameters

[in]	rtd	The essential routing data with map, actorsize, ents
[in]	start	The starting coordinate to search for a ceiling from.
[in]	end	The starting coordinate to search for a ceiling from.
[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 715 of file routing.cpp.

References RT_FindOpeningCeilingFrac().

Referenced by RT_TraceOpening().

static int RT_FindOpeningCeilingFrac ( const RoutingData *  rtd, const vec3_t  start, const vec3_t  end, const float  frac, const int  startingHeight  )

static

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

Parameters

[in]	rtd	The essential routing data with map, actorsize, ents
[in]	start	The starting coordinate to search for a ceiling from.
[in]	end	The starting coordinate to search for a ceiling from.
[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 655 of file routing.cpp.

References actor1x1Box(), actor2x2Box(), ACTOR_SIZE_NORMAL, RoutingData::actorSize, DIST_EPSILON, trace_s::endpos, RoutingData::list, RoutingData::mapTiles, ModelCeilingToQuant, PATHFINDING_HEIGHT, QUANT, QuantToModel, tr, UNIT_HEIGHT, VectorCopy, and VectorInterpolation.

Referenced by RT_FindOpeningCeiling().

static int RT_FindOpeningFloor ( const RoutingData *  rtd, const vec3_t  start, const vec3_t  end, const int  startingHeight, const int  floorLimit  )

static

Performs traces to find the approximate floor of a passage.

Parameters

[in]	rtd	The essential routing data with map, actorsize, ents
[in]	start	The starting coordinate to search for a floor from.
[in]	end	The starting coordinate to search for a floor from.
[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 683 of file routing.cpp.

References RT_FindOpeningFloorFrac().

Referenced by RT_TraceOpening().

static int RT_FindOpeningFloorFrac ( const RoutingData *  rtd, const vec3_t  start, const vec3_t  end, const float  frac, const int  startingHeight  )

static

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

Parameters

[in]	rtd	The essential routing data with map, actorsize, ents
[in]	start	The starting coordinate to search for a floor from.
[in]	end	The starting coordinate to search for a floor from.
[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 626 of file routing.cpp.

References actor1x1Box(), actor2x2Box(), ACTOR_SIZE_NORMAL, RoutingData::actorSize, DIST_EPSILON, trace_s::endpos, RoutingData::list, RoutingData::mapTiles, ModelFloorToQuant, QUANT, QuantToModel, tr, VectorCopy, and VectorInterpolation.

Referenced by RT_FindOpeningFloor().

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

static int RT_MicroTrace ( RoutingData *  rtd, const place_t *  from, const int  ax, const int  ay, const int  az, const int  stairwaySituation, opening_t *  opening  )

static

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

Parameters

[in]	rtd	The essential routing data with map, actorsize, ents
[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 900 of file routing.cpp.

References RoutingData::actorSize, opening_s::base, place_s::cell, CELL_HEIGHT, Com_Printf(), debugTrace, DIST_EPSILON, place_s::floor, footBox(), Routing::getFloor(), i, opening_s::invstepup, RoutingData::list, RoutingData::mapTiles, ModelFloorToQuant, PATHFINDING_MICROSTEP_SIZE, PATHFINDING_MICROSTEP_SKIP, PATHFINDING_MIN_STEPUP, QUANT, QuantToModel, RoutingData::routing, opening_s::size, SizedPosToVec, opening_s::stepup, tr, UNIT_SIZE, and VectorSet.

Referenced by RT_TraceOnePassage().

static trace_t RT_ObstructedTrace ( const RoutingData *  rtd, const Line &  traceLine, int  hi, int  lo  )

static

Helper function to trace for walls.

Parameters

[in]	rtd	The essential routing data with map, actorsize, ents
[in]	traceLine	The starting point of the trace is at the FLOOR'S CENTER. The end point of the trace is centered x and y at the destination but at the same height as start.
[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 603 of file routing.cpp.

References RoutingData::actorSize, DIST_EPSILON, RoutingData::list, RoutingData::mapTiles, AABB::maxs, AABB::mins, QuantToModel, UNIT_SIZE, VectorSet, and WALL_SIZE.

Referenced by RT_TraceOpening().

static bool RT_PlaceDoesIntersectEnough ( const place_t *  p, const place_t *  other  )

inlinestatic

Definition at line 138 of file routing.cpp.

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

Referenced by RT_TracePassage().

static void RT_PlaceInit ( const Routing &  routing, const actorSizeEnum_t  actorSize, place_t *  p, const int  x, const int  y, const int  z  )

inlinestatic

Definition at line 126 of file routing.cpp.

References place_s::ceiling, place_s::cell, CELL_HEIGHT, place_s::floor, place_s::floorZ, Routing::getCeiling(), Routing::getFloor(), PATHFINDING_MIN_OPENING, and place_s::usable.

Referenced by RT_TracePassage().

static int RT_PlaceIsShifted ( const place_t *  p, const place_t *  other  )

inlinestatic

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 149 of file routing.cpp.

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

Referenced by RT_TraceOnePassage().

static void RT_StepupSet ( RoutingData *  rtd, const int  x, const int  y, const int  z, const int  dir, const int  val  )

inlinestatic

Definition at line 98 of file routing.cpp.

References RoutingData::actorSize, RoutingData::routing, and Routing::setStepup().

Referenced by RT_FillPassageData().

static int RT_TraceOnePassage ( RoutingData *  rtd, const place_t *  from, const place_t *  to, opening_t *  opening  )

static

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

Parameters

[in]	rtd	The essential routing data with map, actorsize, ents
[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.

Definition at line 1092 of file routing.cpp.

References ACTOR_MAX_HEIGHT, RoutingData::actorSize, opening_s::base, place_s::ceiling, place_s::cell, CELL_HEIGHT, place_s::floor, place_s::floorZ, Routing::getFloor(), opening_s::invstepup, PATHFINDING_BIG_STEPDOWN, PATHFINDING_BIG_STEPUP, PATHFINDING_MAX_STEPUP, PATHFINDING_MIN_OPENING, PATHFINDING_MIN_STEPUP, PATHFINDING_NO_STEPUP, RoutingData::routing, RT_FindOpening(), RT_MicroTrace(), RT_NO_OPENING, RT_PlaceIsShifted(), opening_s::size, and opening_s::stepup.

Referenced by RT_TracePassage().

static int RT_TraceOpening ( const RoutingData *  rtd, 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 *  foundLow, int *  foundHigh  )

static

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

Parameters

[in]	rtd	The essential routing data with map, actorsize, ents
[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]	foundLow	Actual height of the bottom of the found passage.
[out]	foundHigh	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 774 of file routing.cpp.

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

Referenced by RT_FindOpening().

static void RT_TracePassage ( RoutingData *  rtd, const int  x, const int  y, const int  z, const int  ax, const int  ay, opening_t *  opening  )

static

Performs traces to find a passage between two points.

Parameters

[in]	rtd	The essential routing data with map, actorsize, ents
[in]	x,y,z	Starting coordinates
[in]	ax,ay	Ending coordinates (adjacent cell)
[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 1169 of file routing.cpp.

References RoutingData::actorSize, opening_s::base, place_s::ceiling, CELL_HEIGHT, place_s::floor, Routing::getCeiling(), opening_s::invstepup, place_s::isUsable(), PATHFINDING_HEIGHT, PATHFINDING_MIN_OPENING, PATHFINDING_NO_STEPUP, RoutingData::routing, RT_PlaceDoesIntersectEnough(), RT_PlaceInit(), RT_TraceOnePassage(), opening_s::size, and opening_s::stepup.

Referenced by RT_UpdateConnection().

static int RT_UpdateConnection ( RoutingData *  rtd, const int  x, const int  y, const int  ax, const int  ay, const int  z, const int  dir  )

static

Routing Function to update the connection between two fields.

Parameters

[in]	rtd	The essential routing data with map, actorsize, ents
[in]	x,y	The x/y position in the routing arrays (0 to PATHFINDING_WIDTH - actorSize)
[in]	ax,ay	The x/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

test if the adjacent cell and the cell above it are blocked by a loaded model

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.

Find an opening.

the opening between the two cells

Apply the data to the routing table. We always call the fill function. If the passage cannot be traveled, the function fills it in as unpassable.

Definition at line 1240 of file routing.cpp.

References RoutingData::actorSize, opening_s::base, CELL_HEIGHT, Routing::getCeiling(), Routing::getFloor(), PATHFINDING_HEIGHT, RoutingData::routing, RT_ConnSetNoGo(), RT_FillPassageData(), RT_TracePassage(), opening_s::size, and opening_s::stepup.

Referenced by RT_UpdateConnectionColumn().

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 = false

Definition at line 38 of file routing.cpp.

Referenced by DoRouting(), and RT_MicroTrace().