146 lines
5.2 KiB
C
146 lines
5.2 KiB
C
//---
|
|
// pathfinding: Methods to find short enough paths to move around the map
|
|
//---
|
|
|
|
#pragma once
|
|
|
|
#include "map.h"
|
|
#include "geometry.h"
|
|
#include "comp/entity.h"
|
|
|
|
//---
|
|
// Pathfinding on the grid (pfg)
|
|
//---
|
|
|
|
/* Direction field indicating shortest paths from all nodes to one node. */
|
|
typedef struct {
|
|
/* Map in which this field is located */
|
|
map_t const *map;
|
|
/* Location of the destination node */
|
|
uint8_t x, y;
|
|
/* For all nodes except the targeted one, direction to follow. The size of
|
|
this array is map->width * map->height. */
|
|
int8_t *direction;
|
|
/* For all nodes, distance to the center. */
|
|
int16_t *distance;
|
|
|
|
} pfg_all2one_t;
|
|
|
|
/* Free heap data associated with the flow map. */
|
|
void pfg_all2one_free(pfg_all2one_t *field);
|
|
|
|
/* Path in the grid. */
|
|
typedef struct {
|
|
/* Map in which this path is located */
|
|
map_t const *map;
|
|
/* Number of horizontal or vertical edges in the path. */
|
|
int length;
|
|
/* Points along the path, including start and end points; indexes are
|
|
0 ... length (both included), each edge i is from points[i] to
|
|
points[i+1] (i = 0...length-1). */
|
|
ivec2 *points;
|
|
|
|
} pfg_path_t;
|
|
|
|
/* Free heap data associated with the path. */
|
|
void pfg_path_free(pfg_path_t *grid_path);
|
|
|
|
/* pfg_dijkstra(): Dijkstra's algorithm to generate all paths to a center node
|
|
|
|
This function runs Dijkstra's algorithm and determines the shortest path
|
|
from all points of the map to the specified center point. The returned
|
|
structure should be freed by a call to pfg_all2one_free().
|
|
|
|
By default, the cost of each cell is 1, making this function identical to a
|
|
BFS. If [occupation] is not NULL, it is taken as a row-major array
|
|
indicating the number of entities on each tile of the map. The cost of cells
|
|
is increased in proportion with this rate so that the path will avoid
|
|
running into other entities when possible to spread options out. */
|
|
pfg_all2one_t pfg_dijkstra(map_t const *map, ivec2 center,uint8_t *occupation);
|
|
|
|
/* pfg_inwards(), pfg_outwards(): Determine paths after BFS/Dijkstra
|
|
|
|
These functions simply use a pfg_all2one_t result to generate a path in the
|
|
grid. Inwards paths lead from the source point to the center. Outwards paths
|
|
lead from the center to the destination point. */
|
|
pfg_path_t pfg_inwards(pfg_all2one_t const *field, ivec2 from);
|
|
pfg_path_t pfg_outwards(pfg_all2one_t const *field, ivec2 to);
|
|
|
|
//---
|
|
// Raycasting tools
|
|
//---
|
|
|
|
/* raycast_clear(): Check collisions with the map for a straight ray
|
|
|
|
This function checks if the straight-line path from [start] to [end] is
|
|
clear of collisions with walls. It checks all tile transitions to ensure
|
|
that no solid tile is crossed. This function checks movement only for a ray
|
|
of no width, which is suitable for objects that do not collide with walls.
|
|
|
|
TODO: Use tile hitboxes rather than simply checking if the tile is solid.
|
|
|
|
When hitting diagonal corners perfectly, this functions moves up/down before
|
|
moving left/right and ignores the other possibility.
|
|
|
|
Returns [true] if the path is clear, [false] otherwise. */
|
|
bool raycast_clear(map_t const *map, vec2 start, vec2 end);
|
|
|
|
/* raycast_clear_hitbox(): Check collisions with the map for a hitbox
|
|
|
|
This function is similar to raycast_clear(), but it accounts for the width
|
|
of the hitbox being moved. The hitbox should be centered around (0,0) so
|
|
that the path brings that center from [start] to [end].
|
|
|
|
This function simply checks raycast_clear() for two separate rays at the
|
|
opposite corners of the hitbox, perpendicular to the direction of the
|
|
movement. In addition, collisions at the start and end point are tested.
|
|
|
|
TODO: Currently, raycast_clear_hitbox() does not work if the hitbox if
|
|
larger than the obstacles to avoid (as it casts rays only at the
|
|
corners of the hitbox, not in the middle).
|
|
|
|
Returns [true] if the path is clear, [false] otherwise. */
|
|
bool raycast_clear_hitbox(map_t const *map, vec2 start, vec2 end,
|
|
rect hitbox);
|
|
|
|
//---
|
|
// Pathfinding in continuous space (pfc)
|
|
//---
|
|
|
|
/* Path in continuous space. */
|
|
typedef struct {
|
|
/* Map in which this path is located */
|
|
map_t const *map;
|
|
/* Number of segments in the path. */
|
|
int length;
|
|
/* Points along the path, including start and end points; indexes are
|
|
0 ... length (both included), each segment i is from points[i] to
|
|
points[i+1] (i = 0...length-1). */
|
|
vec2 *points;
|
|
|
|
} pfc_path_t;
|
|
|
|
/* Free heap data associated with the path. */
|
|
void pfc_path_free(pfc_path_t *continuous_path);
|
|
|
|
/* pfc_shortcut_full(): Shortcut a grid-based path into continuous segments
|
|
The start and end points should match the endpoints of the grid path,
|
|
otherwise there might not be solutions. */
|
|
pfc_path_t pfc_shortcut_full(pfg_path_t const *path, vec2 start,
|
|
vec2 end, rect hitbox);
|
|
|
|
/* pfc_shortcut_one(): First segment of the shortcut path
|
|
Returns the first point of the shortcut path (start excluded). This can be
|
|
used for greedy AIs or situations where paths are recomputed every frame.
|
|
Returns the start point if a path cannot be found. */
|
|
vec2 pfc_shortcut_one(pfg_path_t const *path, vec2 start,
|
|
vec2 end, rect hitbox);
|
|
|
|
//---
|
|
// Auto-aiming
|
|
//---
|
|
|
|
struct game;
|
|
vec2 pathfinding_autoaim(struct game const *game, entity_t *origin,
|
|
map_t const *map);
|