Atrinik Server  4.0
Macros | Functions | Variables
pathfinder.c File Reference
#include <global.h>
#include <toolkit/string.h>
#include <arch.h>
#include <player.h>
#include <object.h>
#include <exit.h>
#include <toolkit/clioptions.h>

Go to the source code of this file.

Macros

#define TIME_PATHFINDING   0
 
#define VISUALIZE_PATHFINDING   0
 
#define PATHFINDER_QUEUE_SIZE   100
 
#define PATHFINDER_NODEBUF   1000
 
#define PATH_COST   1.0
 
#define PATH_COST_DIAG   1.01
 
#define PATH_COST_LEVEL   1000.
 

Functions

 CASSERT_ARRAY (algo_modifiers, PATH_ALGO_NUM)
 
 CASSERT_ARRAY (algo_strs, PATH_ALGO_NUM)
 
 TOOLKIT_API (IMPORTS(clioptions), DEPENDS(logger))
 
static bool clioptions_option_pathfinder_algorithm (const char *arg, char **errmsg)
 
static bool clioptions_option_pathfinder_greed (const char *arg, char **errmsg)
 
 TOOLKIT_INIT_FUNC (pathfinder)
 
TOOLKIT_INIT_FUNC_FINISH TOOLKIT_DEINIT_FUNC (pathfinder)
 
static
TOOLKIT_DEINIT_FUNC_FINISH
bool 
pathfinder_queue_enqueue (object *waypoint)
 
static objectpathfinder_queue_dequeue (tag_t *count)
 
void path_request (object *waypoint)
 
objectpath_get_next_request (void)
 
static path_node_tpath_node_new (mapstruct *map, int16_t x, int16_t y, double cost, path_node_t *start, path_node_t *goal, path_node_t *parent)
 
static void path_node_remove (path_node_t *node, path_node_t **list)
 
static void path_node_insert (path_node_t *node, path_node_t **list)
 
static void path_node_insert_priority (path_node_t *node, path_node_t **list)
 
static int tile_is_blocked (object *op, mapstruct *map, int x, int y)
 
shstr * path_encode (path_node_t *path)
 
int path_get_next (shstr *buf, int16_t *off, shstr **mappath, mapstruct **map, int *x, int *y, uint32_t *flags)
 
path_node_tpath_compress (path_node_t *path)
 
void path_visualize (path_visualization_t **visualization, path_visualizer_t **visualizer)
 
path_node_tpath_find (object *op, mapstruct *map1, int x, int y, mapstruct *map2, int x2, int y2, path_visualizer_t **visualizer)
 

Variables

struct {
   object *   waypoint
 Waypoint object.
 
   tag_t   wp_count
 Waypoint's ID.
 
pathfinder_queue [PATHFINDER_QUEUE_SIZE]
 
static int pathfinder_queue_first = 0
 
static int pathfinder_queue_last = 0
 
static path_node_t pathfinder_nodebuf [PATHFINDER_NODEBUF]
 
static int pathfinder_nodebuf_next = 0
 
static const double algo_modifiers []
 
static const char *const algo_strs []
 
static path_algo_t path_algo = PATH_ALGO_ASTAR
 
static double path_greed = 1.0
 
static const char * clioptions_option_pathfinder_algorithm_desc
 
static const char * clioptions_option_pathfinder_greed_desc
 

Detailed Description

Pathfinding related code.

Good pathfinding resources:

Author
Alex Tokar - new A* algorithm and heuristics
Bjorn Axelsson (gecko.nosp@m.@acc.nosp@m..umu..nosp@m.se) - original algorithm, functions and structures

Definition in file pathfinder.c.

Macro Definition Documentation

#define PATH_COST   1.0

Path cost when moving in a straight line.

Definition at line 71 of file pathfinder.c.

#define PATH_COST_DIAG   1.01

Path cost when moving diagonally.

Definition at line 76 of file pathfinder.c.

#define PATH_COST_LEVEL   1000.

Path cost per z level.

Definition at line 81 of file pathfinder.c.

#define PATHFINDER_NODEBUF   1000

Maximum number of node buffers.

Definition at line 66 of file pathfinder.c.

#define PATHFINDER_QUEUE_SIZE   100

Size of the pathfinder queue.

Definition at line 61 of file pathfinder.c.

#define TIME_PATHFINDING   0

Turns pathfinding profiling on/off.

Definition at line 51 of file pathfinder.c.

#define VISUALIZE_PATHFINDING   0

Whether to visualize pathfinding.

Definition at line 56 of file pathfinder.c.

Function Documentation

static bool clioptions_option_pathfinder_algorithm ( const char *  arg,
char **  errmsg 
)
static

Definition at line 145 of file pathfinder.c.

static bool clioptions_option_pathfinder_greed ( const char *  arg,
char **  errmsg 
)
static

Definition at line 178 of file pathfinder.c.

path_node_t* path_compress ( path_node_t path)

Compress a path by removing redundant segments.

Current implementation removes segments that can be traversed by walking in a single direction.

Something advanced could be to use a Hough transform / or something smart with cross products.

Rules:

  • always leave first and last path nodes
  • if the movement direction of node n to n+1 is the same as for n-1 to n, then remove node n.
Parameters
pathPath node.
Returns
'path' with redundant segments removed.

Definition at line 759 of file pathfinder.c.

shstr* path_encode ( path_node_t path)

Generate a string representation of a path.

Ideas on how to store paths:

  • a) Store path as real waypoint objects (might be a lot of objects...)
  • b) Store path as field in waypoints
    • b1) Linked list in i.e. ob->enemy (needs special free() call when removing object).
    • b2) In ASCII in waypoint->msg (will even be saved out).
      • b2.1) Direction list (e.g. 1234155532, compact but fragile)
      • b2.2) Map / coordinate list: (/dev/testmaps:13,12 14,12 ...) (human-readable (and editable), complex parsing) Approx: 600 steps in one 4096 bytes msg field
      • b2.2.1) Hex (/dev/testmaps/xxx D,C E,C ...) (harder to read and write, more compact) Approx: 1000 steps in one 4096 bytes msg field
Parameters
pathPath node.
Returns
Encoded path as a shared string.

Definition at line 589 of file pathfinder.c.

path_node_t* path_find ( object op,
mapstruct map1,
int  x,
int  y,
mapstruct map2,
int  x2,
int  y2,
path_visualizer_t **  visualizer 
)

Find a path for op from location on map1 to location on map2.

Parameters
opObject.
map1From map.
x1From X position.
y1From Y position.
map2To map.
x2To X position.
y2To Y position.
visualizer[out]Visualizer pointer where to store visited/closed nodes. Can be NULL, otherwise the pointer MUST be initialized to NULL.
Returns
Found path.

Definition at line 859 of file pathfinder.c.

int path_get_next ( shstr *  buf,
int16_t *  off,
shstr **  mappath,
mapstruct **  map,
int *  x,
int *  y,
uint32_t *  flags 
)

Get the next location from a textual path description (generated by path_encode()) starting from the character index indicated by off.

Example text path description:

  • /dev/testmaps/testmap_waypoints 17,7 17,10 18,11 19,10 20,10
  • /dev/testmaps/testmap_waypoints2 8,22
  • /dev/testmaps/testmap_waypoints3 0,22 1,23
  • /dev/testmaps/testmap_waypoints4 1,1 2,2
    Parameters
    bufBuffer.
    offOffset.
    mappathMap path.
    mapMap. Should be initialized with whatever map the object we are working on currently lives on (to handle paths without map strings).
    xX position.
    yY position.
    flagsFlags.
    Returns
    If a location is found, will return 1 and update map, x, y and off (off will be set to the index to use for the next call to this function). Otherwise 0 will be returned and the values of map, x and y will be undefined and off will not be touched.

Definition at line 652 of file pathfinder.c.

object* path_get_next_request ( void  )

Get the next (valid) waypoint for which a path is requested.

Returns
Waypoint, NULL if there isn't any left.

Definition at line 303 of file pathfinder.c.

static void path_node_insert ( path_node_t node,
path_node_t **  list 
)
static

Insert a node into a list.

Parameters
nodeNode to insert.
[out]listList to insert into.

Definition at line 477 of file pathfinder.c.

static void path_node_insert_priority ( path_node_t node,
path_node_t **  list 
)
static

Insert a node in a sorted list (lowest path_node_t::sum first in list).

Parameters
nodeNode to insert.
listList to insert into.
Todo:
Make more efficient by using skip list or heaps.

Definition at line 502 of file pathfinder.c.

static path_node_t* path_node_new ( mapstruct map,
int16_t  x,
int16_t  y,
double  cost,
path_node_t start,
path_node_t goal,
path_node_t parent 
)
static

Allocate and initialize a node.

Also calculates the appropriate heuristics from 'start' and 'goal' parameters.

Parameters
mapMap.
xX position.
yY position.
costCost.
startStarting node.
goalGoal node.
parentParent node.
Returns
New node.

Definition at line 359 of file pathfinder.c.

static void path_node_remove ( path_node_t node,
path_node_t **  list 
)
static

Remove a node from a list.

Parameters
nodeNode to remove.
[out]listList to remove from.

Definition at line 445 of file pathfinder.c.

void path_request ( object waypoint)

Request a new path.

Parameters
waypointWaypoint.

Definition at line 275 of file pathfinder.c.

void path_visualize ( path_visualization_t **  visualization,
path_visualizer_t **  visualizer 
)

Build a visualization hash table out of a list of visited/closed nodes.

Parameters
[out]visualizationHash table to use. Must be initialized to NULL.
[out]visualizerList of the visited/closed nodes.

Definition at line 811 of file pathfinder.c.

static object* pathfinder_queue_dequeue ( tag_t *  count)
static

Get the first waypoint from the queue.

Parameters
[out]countWaypoint's ID if there is a valid waypoint.
Returns
The waypoint, NULL if the queue is empty.

Definition at line 250 of file pathfinder.c.

static TOOLKIT_DEINIT_FUNC_FINISH bool pathfinder_queue_enqueue ( object waypoint)
static

Enqueue a waypoint for path computation.

Parameters
waypointWaypoint.
Returns
True on success, false on failure.

Definition at line 221 of file pathfinder.c.

static int tile_is_blocked ( object op,
mapstruct map,
int  x,
int  y 
)
static

Check if the specified tile is blocked.

Parameters
opObject.
mapMap.
xX coordinate.
yY coordinate.
Returns
0 if the tile is not blocked, non-zero otherwise.

Definition at line 554 of file pathfinder.c.

Variable Documentation

const double algo_modifiers[]
static
Initial value:
= {
0, 0.5, 1.0,
}

Used to avoid branching when computing sum of node cost/heuristic depending on selected algorithm.

Definition at line 113 of file pathfinder.c.

const char* const algo_strs[]
static
Initial value:
= {
"BFS", "A*", "Dijkstra",
}

Text representation of the algorithms.

Definition at line 121 of file pathfinder.c.

const char* clioptions_option_pathfinder_algorithm_desc
static
Initial value:
=
"Changes the algorithm used for pathfinding.\n\n"
"Available algorithms: BFS, A*, Dijkstra"

Description of the –pathfinder_algorithm command.

Definition at line 140 of file pathfinder.c.

const char* clioptions_option_pathfinder_greed_desc
static
Initial value:
=
"Sets the pathfinding heuristics greed modifier."

Description of the –pathfinder_greed command.

Definition at line 174 of file pathfinder.c.

path_algo_t path_algo = PATH_ALGO_ASTAR
static

Currently selected algorithm.

Definition at line 129 of file pathfinder.c.

double path_greed = 1.0
static

Heuristic greed modifier.

Definition at line 134 of file pathfinder.c.

path_node_t pathfinder_nodebuf[PATHFINDER_NODEBUF]
static

The node buffers. Used to avoid lots of mallocs.

Definition at line 103 of file pathfinder.c.

int pathfinder_nodebuf_next = 0
static

Next node buf.

Definition at line 107 of file pathfinder.c.

struct { ... } pathfinder_queue[PATHFINDER_QUEUE_SIZE]

The pathfinder queue.

int pathfinder_queue_first = 0
static

First in the queue.

Definition at line 94 of file pathfinder.c.

int pathfinder_queue_last = 0
static

Last in the queue.

Definition at line 98 of file pathfinder.c.