UFO: Alien Invasion
Loading...
Searching...
No Matches
routing.cpp File Reference

grid pathfinding and routing More...

#include "tracing.h"
#include "routing.h"
#include "common.h"
Include dependency graph for routing.cpp:

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_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...
struct  opening_t
 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)

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.
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.
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.
bool RT_AllCellsBelowAreFilled (const Routing &routing, const int actorSize, const pos3_t pos)
 Check if pos is on solid ground.
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.
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.
static trace_t RT_ObstructedTrace (const RoutingData *rtd, const Line &traceLine, int hi, int lo)
 Helper function to trace for walls.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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

◆ half1x1Width

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

Definition at line 54 of file routing.cpp.

Referenced by actor1x1Box().

◆ half2x2Width

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

Definition at line 55 of file routing.cpp.

Referenced by actor2x2Box().

◆ halfMicrostepSize

#define halfMicrostepSize   (PATHFINDING_MICROSTEP_SIZE / 2 - DIST_EPSILON)

Definition at line 49 of file routing.cpp.

Referenced by footBox(), and RT_CheckCell().

◆ RT_NO_OPENING

#define RT_NO_OPENING   -1

Definition at line 46 of file routing.cpp.

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

Function Documentation

◆ actor1x1Box()

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

References half1x1Width.

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

◆ actor2x2Box()

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

References half2x2Width.

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

◆ footBox()

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

References halfMicrostepSize.

Referenced by RT_CheckCell(), and RT_MicroTrace().

◆ RT_AllCellsBelowAreFilled()

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

Check if pos is on solid ground.

Parameters
[in]routingThe map's routing data
[in]actorSizeThe size of the actor along the X and Y axis in cell units
[in]posThe 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.

◆ RT_CalcNewZ()

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

◆ RT_CanActorStandHere()

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

◆ RT_CheckCell()

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]mapTilesList of tiles the current (RMA-)map is composed of
[in]routingThe map's routing data
[in]actorSizeThe size of the actor along the X and Y axis in cell units
[in]x,yThe x/y position in the routing arrays (0 - PATHFINDING_WIDTH-1)
[in]zThe z position in the routing arrays (0 - PATHFINDING_HEIGHT-1)
[in]listThe 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, footBox(), Routing::getFloor(), halfMicrostepSize, i, mapTiles, 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().

◆ RT_ConnSetNoGo()

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

◆ RT_FillPassageData()

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]rtdThe essential routing data with map, actorsize, ents
[in]dirDirection of movement
[in]x,y,zGrid coordinates of the starting position
[in]openingSizeAbsolute height in QUANT units of the opening.
[in]openingBaseAbsolute height in QUANT units of the bottom of the opening.
[in]stepupRequired 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().

◆ RT_FindOpening()

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]rtdThe essential routing data with map, actorsize, ents
[in]fromStarting place
[in]axEnding x coordinate
[in]ayEnding y coordinate
[in]bottomActual height of the starting floor.
[in]topActual height of the starting ceiling.
[out]foundLowActual height of the bottom of the found passage.
[out]foundHighActual 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_t::ceiling, place_t::cell, CELL_HEIGHT, 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().

◆ RT_FindOpeningCeiling()

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]rtdThe essential routing data with map, actorsize, ents
[in]startThe starting coordinate to search for a ceiling from.
[in]endThe starting coordinate to search for a ceiling from.
[in]startingHeightThe starting height for this upward trace.
[in]ceilLimitThe 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().

◆ RT_FindOpeningCeilingFrac()

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]rtdThe essential routing data with map, actorsize, ents
[in]startThe starting coordinate to search for a ceiling from.
[in]endThe starting coordinate to search for a ceiling from.
[in]fracThe fraction of the distance traveled from start to end, using (0.0 to 1.0).
[in]startingHeightThe 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, RoutingData::list, RoutingData::mapTiles, ModelCeilingToQuant, PATHFINDING_HEIGHT, QUANT, QuantToModel, tr, UNIT_HEIGHT, VectorCopy, and VectorInterpolation.

Referenced by RT_FindOpeningCeiling().

◆ RT_FindOpeningFloor()

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]rtdThe essential routing data with map, actorsize, ents
[in]startThe starting coordinate to search for a floor from.
[in]endThe starting coordinate to search for a floor from.
[in]startingHeightThe starting height for this downward trace.
[in]floorLimitThe 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().

◆ RT_FindOpeningFloorFrac()

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]rtdThe essential routing data with map, actorsize, ents
[in]startThe starting coordinate to search for a floor from.
[in]endThe starting coordinate to search for a floor from.
[in]fracThe fraction of the distance traveled from start to end, using (0.0 to 1.0).
[in]startingHeightThe 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, RoutingData::list, RoutingData::mapTiles, ModelFloorToQuant, QUANT, QuantToModel, tr, VectorCopy, and VectorInterpolation.

Referenced by RT_FindOpeningFloor().

◆ RT_GetMapSize()

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]mapTilesList of tiles the current (RMA-)map is composed of
[out]mapBoxThe 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_t::fraction, i, mapTiles, 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().

◆ RT_MicroTrace()

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]rtdThe essential routing data with map, actorsize, ents
[in]fromStarting place
[in]axEnding x coordinate
[in]ayEnding y coordinate
[in]azEnding z coordinate
[in]stairwaySituationwhether we are standing in front of a stairway
[out]openingdescriptor 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_t::base, place_t::cell, CELL_HEIGHT, Com_Printf(), debugTrace, DIST_EPSILON, place_t::floor, footBox(), Routing::getFloor(), i, opening_t::invstepup, RoutingData::list, RoutingData::mapTiles, ModelFloorToQuant, PATHFINDING_MICROSTEP_SIZE, PATHFINDING_MICROSTEP_SKIP, PATHFINDING_MIN_STEPUP, QUANT, QuantToModel, RoutingData::routing, opening_t::size, SizedPosToVec, opening_t::stepup, tr, UNIT_SIZE, and VectorSet.

Referenced by RT_TraceOnePassage().

◆ RT_ObstructedTrace()

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

Helper function to trace for walls.

Parameters
[in]rtdThe essential routing data with map, actorsize, ents
[in]traceLineThe 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]hiThe upper height ABOVE THE FLOOR of the bounding box.
[in]loThe 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().

◆ RT_PlaceDoesIntersectEnough()

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

Definition at line 138 of file routing.cpp.

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

Referenced by RT_TracePassage().

◆ RT_PlaceInit()

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_t::ceiling, place_t::cell, CELL_HEIGHT, place_t::floor, place_t::floorZ, Routing::getCeiling(), Routing::getFloor(), PATHFINDING_MIN_OPENING, and place_t::usable.

Referenced by RT_TracePassage().

◆ RT_PlaceIsShifted()

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_t::ceiling, place_t::floor, and place_t::isUsable().

Referenced by RT_TraceOnePassage().

◆ RT_StepupSet()

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

◆ RT_TraceOnePassage()

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]rtdThe essential routing data with map, actorsize, ents
[in]fromStarting place
[in]toEnding place
[out]openingdescriptor 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_t::base, place_t::ceiling, place_t::cell, CELL_HEIGHT, place_t::floor, place_t::floorZ, Routing::getFloor(), opening_t::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_t::size, and opening_t::stepup.

Referenced by RT_TracePassage().

◆ RT_TraceOpening()

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]rtdThe essential routing data with map, actorsize, ents
[in]startStarting trace coordinate
[in]endEnding trace coordinate
[in]axEnding x coordinate
[in]ayEnding y coordinate
[in]bottomActual height of the starting floor.
[in]topActual height of the starting ceiling.
[in]loActual height of the bottom of the slice trace.
[in]hiActual height of the top of the slice trace.
[out]foundLowActual height of the bottom of the found passage.
[out]foundHighActual 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 PATHFINDING_MIN_OPENING, RT_CalcNewZ(), RT_FindOpeningCeiling(), RT_FindOpeningFloor(), RT_NO_OPENING, RT_ObstructedTrace(), and tr.

Referenced by RT_FindOpening().

◆ RT_TracePassage()

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]rtdThe essential routing data with map, actorsize, ents
[in]x,y,zStarting coordinates
[in]ax,ayEnding coordinates (adjacent cell)
[out]openingdescriptor 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_t::base, place_t::ceiling, CELL_HEIGHT, place_t::floor, Routing::getCeiling(), opening_t::invstepup, place_t::isUsable(), PATHFINDING_HEIGHT, PATHFINDING_MIN_OPENING, PATHFINDING_NO_STEPUP, RoutingData::routing, RT_PlaceDoesIntersectEnough(), RT_PlaceInit(), RT_TraceOnePassage(), opening_t::size, and opening_t::stepup.

Referenced by RT_UpdateConnection().

◆ RT_UpdateConnection()

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]rtdThe essential routing data with map, actorsize, ents
[in]x,yThe x/y position in the routing arrays (0 to PATHFINDING_WIDTH - actorSize)
[in]ax,ayThe x/y of the adjacent cell
[in]zThe z position in the routing arrays (0 to PATHFINDING_HEIGHT - 1)
[in]dirThe 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_t::base, CELL_HEIGHT, Routing::getCeiling(), Routing::getFloor(), PATHFINDING_HEIGHT, RoutingData::routing, RT_ConnSetNoGo(), RT_FillPassageData(), RT_TracePassage(), opening_t::size, and opening_t::stepup.

Referenced by RT_UpdateConnectionColumn().

◆ 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]mapTilesList of tiles the current (RMA-)map is composed of
[in]routingRouting table of the current loaded map
[in]actorSizeThe size of the actor, in units
[in]x,yThe position in the routing arrays (0 to PATHFINDING_WIDTH - actorSize)
[in]dirThe direction to test for a connection through
[in]listThe local models list (a local model has a name starting with * followed by the model number)
[in]minZ,maxZLimit 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, mapTiles, PATHFINDING_WIDTH, RT_ConnSetNoGo(), and RT_UpdateConnection().

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

◆ RT_WriteCSVFiles()

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

Definition at line 1330 of file routing.cpp.

References ACTOR_MAX_SIZE, baseFilename, 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

◆ debugTrace

bool debugTrace = false

Definition at line 38 of file routing.cpp.

Referenced by DoRouting(), and RT_MicroTrace().