📄 pathfinding.h
字号:
// Arguments: p_map: the map
// p_x, p_y: starting coordinates
// p_gx, p_gy: goal coordinates
// Return Value: None
// ----------------------------------------------------------------
void PathSimpleHeuristic( Array2D<Cell>& p_map,
int p_x, int p_y,
int p_gx, int p_gy )
{
Coordinate c;
int x, y;
int ax, ay;
int dir;
float distance;
static Heap<Coordinate> queue( QUEUESIZE, CompareCoordinatesDescending );
queue.m_count = 0;
// clear the cells first.
ClearCells( p_map );
// enqueue the starting cell in the queue
c.x = p_x;
c.y = p_y;
queue.Enqueue( c );
// start the main loop
while( queue.m_count != 0 )
{
// pull the first cell off the queue and process it.
x = queue.Item().x;
y = queue.Item().y;
queue.Dequeue();
// make sure the node isn't already marked. If it is, do
// nothing.
if( p_map.Get( x, y ).m_marked == false )
{
// mark the cell as it is pulled off the queue.
p_map.Get( x, y ).m_marked = true;
// quit out if the goal has been reached.
if( x == p_gx && y == p_gy )
break;
// loop through each direction.
for( dir = 0; dir < 8; dir++ )
{
// retrieve the coordinates of the current adjacent cell
ax = x + DIRTABLE[dir][0];
ay = y + DIRTABLE[dir][1];
// check to see if the adjacent cell is a valid index,
// passable, and not marked.
if( ax >= 0 && ax < p_map.Width() &&
ay >= 0 && ay < p_map.Height() &&
p_map.Get( ax, ay ).m_passable == true &&
p_map.Get( ax, ay ).m_marked == false )
{
// calculate the distance to get into this cell.
// this is calulated as:
// distance of the current cell plus
// the weight of the adjacent cell times the distance
// of the cell.
// diagonal cell's cost is around 1.4 times the cost of
// a horizontal or vertical cell.
distance = p_map.Get( x, y ).m_distance +
p_map.Get( ax, ay ).m_weight * DISTTABLE[dir];
// check if the node has already been calculated before
if( p_map.Get( ax, ay ).m_lastx != -1 )
{
// the node has already been calculated, see if the
// new distance is shorter. If so, update the links.
if( distance < p_map.Get( ax, ay ).m_distance )
{
// the new distance is shorter, update the links
p_map.Get( ax, ay ).m_lastx = x;
p_map.Get( ax, ay ).m_lasty = y;
p_map.Get( ax, ay ).m_distance = distance;
// add the cell to the queue.
c.x = ax;
c.y = ay;
c.heuristic = SimpleHeuristic( x, y,
p_gx, p_gy,
dir );
queue.Enqueue( c );
}
}
else
{
// set the links and the distance
p_map.Get( ax, ay ).m_lastx = x;
p_map.Get( ax, ay ).m_lasty = y;
p_map.Get( ax, ay ).m_distance = distance;
// add the cell to the queue.
c.x = ax;
c.y = ay;
c.heuristic = SimpleHeuristic( x, y,
p_gx, p_gy,
dir );
queue.Enqueue( c );
}
}
}
}
}
}
// ----------------------------------------------------------------
// Name: ComplexHeuristic
// Description: calculates a complex heuristic
// Arguments: x, y: coordinates of the current cell
// gx, gy: goal coordinates
// dir: direction of the target cell
// Return Value: the heuristic
// ----------------------------------------------------------------
float ComplexHeuristic( int x, int y, int gx, int gy, int dir )
{
// calculate the coordinates of the target cell
x = x + DIRTABLE[dir][0];
y = y + DIRTABLE[dir][1];
// find the distance from the target to the goal
return CellDistance( x, y, gx, gy );
}
// ----------------------------------------------------------------
// Name: PathComplexHeuristic
// Description: pathfinder that uses a complex heuristic
// Arguments: p_map: the map
// p_x, p_y: starting coordinates
// p_gx, p_gy: goal coordinates
// Return Value: None
// ----------------------------------------------------------------
void PathComplexHeuristic( Array2D<Cell>& p_map,
int p_x, int p_y,
int p_gx, int p_gy )
{
Coordinate c;
int x, y;
int ax, ay;
int dir;
float distance;
static Heap<Coordinate> queue( QUEUESIZE, CompareCoordinatesDescending );
queue.m_count = 0;
// clear the cells first.
ClearCells( p_map );
// enqueue the starting cell in the queue
c.x = p_x;
c.y = p_y;
queue.Enqueue( c );
// start the main loop
while( queue.m_count != 0 )
{
// pull the first cell off the queue and process it.
x = queue.Item().x;
y = queue.Item().y;
queue.Dequeue();
// make sure the node isn't already marked. If it is, do
// nothing.
if( p_map.Get( x, y ).m_marked == false )
{
// mark the cell as it is pulled off the queue.
p_map.Get( x, y ).m_marked = true;
// quit out if the goal has been reached.
if( x == p_gx && y == p_gy )
break;
// loop through each direction.
for( dir = 0; dir < 8; dir++ )
{
// retrieve the coordinates of the current adjacent cell
ax = x + DIRTABLE[dir][0];
ay = y + DIRTABLE[dir][1];
// check to see if the adjacent cell is a valid index,
// passable, and not marked.
if( ax >= 0 && ax < p_map.Width() &&
ay >= 0 && ay < p_map.Height() &&
p_map.Get( ax, ay ).m_passable == true &&
p_map.Get( ax, ay ).m_marked == false )
{
// calculate the distance to get into this cell.
// this is calulated as:
// distance of the current cell plus
// the weight of the adjacent cell times the distance
// of the cell.
// diagonal cell's cost is around 1.4 times the cost of
// a horizontal or vertical cell.
distance = p_map.Get( x, y ).m_distance +
p_map.Get( ax, ay ).m_weight * DISTTABLE[dir];
// check if the node has already been calculated before
if( p_map.Get( ax, ay ).m_lastx != -1 )
{
// the node has already been calculated, see if the
// new distance is shorter. If so, update the links.
if( distance < p_map.Get( ax, ay ).m_distance )
{
// the new distance is shorter, update the links
p_map.Get( ax, ay ).m_lastx = x;
p_map.Get( ax, ay ).m_lasty = y;
p_map.Get( ax, ay ).m_distance = distance;
// add the cell to the queue.
c.x = ax;
c.y = ay;
c.heuristic = ComplexHeuristic( x, y,
p_gx, p_gy,
dir );
queue.Enqueue( c );
}
}
else
{
// set the links and the distance
p_map.Get( ax, ay ).m_lastx = x;
p_map.Get( ax, ay ).m_lasty = y;
p_map.Get( ax, ay ).m_distance = distance;
// add the cell to the queue.
c.x = ax;
c.y = ay;
c.heuristic = ComplexHeuristic( x, y,
p_gx, p_gy,
dir );
queue.Enqueue( c );
}
}
}
}
}
}
// ----------------------------------------------------------------
// Name: AStarHeuristic
// Description: calculates the A* heuristic
// Arguments: x, y: coordinates of the current cell
// gx, gy: goal coordinates
// dir: direction of the target cell
// Return Value: the heuristic
// ----------------------------------------------------------------
float AStarHeuristic( int x, int y, int gx, int gy, int dir )
{
x = x + DIRTABLE[dir][0];
y = y + DIRTABLE[dir][1];
return CellDistance( x, y, gx, gy );
}
// ----------------------------------------------------------------
// Name: PathAStar
// Description: pathfinder that uses the A* heuristic
// Arguments: p_map: the map
// p_x, p_y: starting coordinates
// p_gx, p_gy: goal coordinates
// Return Value: None
// ----------------------------------------------------------------
void PathAStar( Array2D<Cell>& p_map,
int p_x, int p_y,
int p_gx, int p_gy )
{
Coordinate c;
int x, y;
int ax, ay;
int dir;
float distance;
static Heap<Coordinate> queue( QUEUESIZE, CompareCoordinatesDescending );
queue.m_count = 0;
// clear the cells first.
ClearCells( p_map );
// enqueue the starting cell in the queue
c.x = p_x;
c.y = p_y;
queue.Enqueue( c );
// start the main loop
while( queue.m_count != 0 )
{
// pull the first cell off the queue and process it.
x = queue.Item().x;
y = queue.Item().y;
queue.Dequeue();
// make sure the node isn't already marked. If it is, do
// nothing.
if( p_map.Get( x, y ).m_marked == false )
{
// mark the cell as it is pulled off the queue.
p_map.Get( x, y ).m_marked = true;
// quit out if the goal has been reached.
if( x == p_gx && y == p_gy )
break;
// loop through each direction.
for( dir = 0; dir < 8; dir++ )
{
// retrieve the coordinates of the current adjacent cell
ax = x + DIRTABLE[dir][0];
ay = y + DIRTABLE[dir][1];
// check to see if the adjacent cell is a valid index,
// passable, and not marked.
if( ax >= 0 && ax < p_map.Width() &&
ay >= 0 && ay < p_map.Height() &&
p_map.Get( ax, ay ).m_passable == true &&
p_map.Get( ax, ay ).m_marked == false )
{
// calculate the distance to get into this cell.
// this is calulated as:
// distance of the current cell plus
// the weight of the adjacent cell times the distance
// of the cell.
// diagonal cell's cost is around 1.4 times the cost of
// a horizontal or vertical cell.
distance = p_map.Get( x, y ).m_distance +
p_map.Get( ax, ay ).m_weight * DISTTABLE[dir];
// check if the node has already been calculated before
if( p_map.Get( ax, ay ).m_lastx != -1 )
{
// the node has already been calculated, see if the
// new distance is shorter. If so, update the links.
if( distance < p_map.Get( ax, ay ).m_distance )
{
// the new distance is shorter, update the links
p_map.Get( ax, ay ).m_lastx = x;
p_map.Get( ax, ay ).m_lasty = y;
p_map.Get( ax, ay ).m_distance = distance;
// add the cell to the queue.
c.x = ax;
c.y = ay;
c.heuristic = distance +
AStarHeuristic( x, y,
p_gx, p_gy,
dir );
queue.Enqueue( c );
}
}
else
{
// set the links and the distance
p_map.Get( ax, ay ).m_lastx = x;
p_map.Get( ax, ay ).m_lasty = y;
p_map.Get( ax, ay ).m_distance = distance;
// add the cell to the queue.
c.x = ax;
c.y = ay;
c.heuristic = distance +
AStarHeuristic( x, y,
p_gx, p_gy,
dir );
queue.Enqueue( c );
}
}
}
}
}
}
#endif
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -