#include <global.h>

Defines
#define	HEURISTIC_ERROR -666.
#define	PATHFINDER_QUEUE_SIZE 100
#define	PATHFINDER_NODEBUF 300
Functions
static int	pathfinder_queue_enqueue (object *waypoint)
static object *	pathfinder_queue_dequeue (int *count)
void	request_new_path (object *waypoint)
object *	get_next_requested_path ()
static path_node *	make_node (mapstruct map, sint16 x, sint16 y, uint16 cost, path_node parent)
static void	remove_node (path_node node, path_node *list)
static void	insert_node (path_node node, path_node *list)
static void	insert_priority_node (path_node node, path_node *list)
shstr *	encode_path (path_node *path)
int	get_path_next (shstr buf, sint16 off, shstr mappath, mapstruct map, int x, int y)
path_node *	compress_path (path_node *path)
static float	distance_heuristic (path_node start, path_node current, path_node *goal)
static int	find_neighbours (path_node node, path_node open_list, path_node start, path_node goal, object op, uint32 id)
path_node *	find_path (object op, mapstruct map1, int x1, int y1, mapstruct *map2, int x2, int y2)
Variables
static int	pathfinder_queue_first = 0
static int	pathfinder_queue_last = 0
struct {
object * waypoint
tag_t wp_count
}	pathfinder_queue [PATHFINDER_QUEUE_SIZE]
static int	pathfinder_nodebuf_next = 0
static path_node	pathfinder_nodebuf [PATHFINDER_NODEBUF]

Detailed Description

Pathfinding related code.

Good pathfinding resources:

Amit's Thoughts on Path-Finding and A-Star http://theory.stanford.edu/~amitp/GameProgramming/
Smart Moves: Intelligent Pathfinding http://www.gamasutra.com/view/feature/3317/smart_move_intelligent_.php

Possible enhancements (profile and identify need before spending time on):

Replace the open list with a binary heap or skip list. Will enhance insertion performance.

About monster-to-player paths:

use smaller max-number-of-nodes value (we don't want a mob running away across the map)

Author:: Bjorn Axelsson (gecko@acc.umu.se)

Definition in file pathfinder.c.

Define Documentation

#define HEURISTIC_ERROR -666.

Used to indicate an error in distance_heuristic().

Definition at line 45 of file pathfinder.c.

#define PATHFINDER_NODEBUF 300

This is used as static memory for search tree nodes (avoids lots of mallocs).

Definition at line 68 of file pathfinder.c.

#define PATHFINDER_QUEUE_SIZE 100

Size of the pathfinder queue.

Definition at line 52 of file pathfinder.c.

Function Documentation

path_node* compress_path ( path_node * 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 hughes transform / or something smart with cross products.

Parameters:

path	Path node.

Returns:: Compressed path node.

Definition at line 463 of file pathfinder.c.

static float distance_heuristic	(	path_node *	start,
		path_node *	current,
		path_node *	goal
	)		`[static]`

Heuristic used for A* search. Should return an estimate of the "cost" (number of moves) needed to get from current to goal.

If this function overestimates, we are not guaranteed an optimal path.

get_rangevector() can fail here if there is no maptile path between start and goal. If it does, we have to return an error value.

Parameters:

start	The initial starting position.
current	Current position.
goal	Goal position.

Returns:: Number of moves to get from current to goal.

Todo:: Cache the results from get_rangevector() for better efficiency?

Definition at line 531 of file pathfinder.c.

shstr* encode_path ( path_node * 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:

path	Path node.

Returns:: Encoded path, shared string.

Todo:: Buffer overflow checking.

Definition at line 327 of file pathfinder.c.

static int find_neighbours	(	path_node *	node,
		path_node **	open_list,
		path_node *	start,
		path_node *	goal,
		object *	op,
		uint32	id
	)		`[static]`

Find untraversed neighbors of the node and add to the open_list.

Parameters:

node	Node.
open_list	Open list.
start	Starting position.
goal	Goal position.
op	Object.
id	Traversal ID.

Returns:: Returns 0 if we ran into a limit of any kind and cannot continue, or 1 if everything was ok.

Definition at line 585 of file pathfinder.c.

path_node* find_path	(	object *	op,
		mapstruct *	map1,
		int	x1,
		int	y1,
		mapstruct *	map2,
		int	x2,
		int	y2
	)

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

Parameters:

op	Object.
map1	From map.
x1	From X position.
y1	From Y position.
map2	To map.
x2	To X position.
y2	To Y position.

Returns:: Found path.

Definition at line 667 of file pathfinder.c.

object* get_next_requested_path ( )

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

Definition at line 146 of file pathfinder.c.

int get_path_next	(	shstr *	buf,
		sint16 *	off,
		shstr **	mappath,
		mapstruct **	map,
		int *	x,
		int *	y
	)

Get the next location from a textual path description (generated by encode_path()) 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:

buf	Buffer.
off	Offset.
mappath	Map path.
map	Map. Should be initialized with whatever map the object we are working on currently lives on (to handle paths without map strings).
x	X position.
y	Y position.

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 368 of file pathfinder.c.

static void insert_node	(	path_node *	node,
		path_node **	list
	)		`[static]`

Insert a node into a list.

Parameters:

node	Node to insert.
list	List to insert into.

Definition at line 238 of file pathfinder.c.

static void insert_priority_node	(	path_node *	node,
		path_node **	list
	)		`[static]`

Insert a node in a sorted list (lowest heuristic first in list).

Parameters:

node	Node to insert.
list	List to insert into.

Todo:: Make more efficient by using skip list or heaps.

Definition at line 256 of file pathfinder.c.

static path_node* make_node	(	mapstruct *	map,
		sint16	x,
		sint16	y,
		uint16	cost,
		path_node *	parent
	)		`[static]`

Allocate and initialize a node.

Parameters:

map	Map.
x	X position.
y	Y position.
cost	Cost.
parent	Parent node.

Returns:: New node.

Definition at line 184 of file pathfinder.c.

static object* pathfinder_queue_dequeue ( int * count ) [static]

Get the first waypoint from the queue.

Parameters:

[out] count Waypoint's ID if there is a valid waypoint.

Returns:: The waypoint, NULL if the queue is empty.

Definition at line 101 of file pathfinder.c.

static int pathfinder_queue_enqueue ( object * waypoint ) [static]

Enqueue a waypoint for path computation.

Parameters:

waypoint Waypoint.

Returns:: 1 on success, 0 on failure.

Definition at line 78 of file pathfinder.c.

static void remove_node	(	path_node *	node,
		path_node **	list
	)		`[static]`

Remove a node from a list.

Parameters:

node	Node to remove.
list	List to remove from.

Definition at line 215 of file pathfinder.c.

void request_new_path ( object * waypoint )

Request a new path.

Parameters:

waypoint Waypoint.

Definition at line 125 of file pathfinder.c.

Variable Documentation

path_node pathfinder_nodebuf[PATHFINDER_NODEBUF] [static]

The node buffers.

Definition at line 72 of file pathfinder.c.

int pathfinder_nodebuf_next = 0 [static]

Next node buf.

Definition at line 70 of file pathfinder.c.

int pathfinder_queue_first = 0 [static]

First in the queue.

Definition at line 54 of file pathfinder.c.

int pathfinder_queue_last = 0 [static]

Last in the queue.

Definition at line 56 of file pathfinder.c.

object* waypoint

Waypoint object.

Definition at line 61 of file pathfinder.c.

tag_t wp_count

Waypoint's ID.

Definition at line 64 of file pathfinder.c.

Defines

Functions

Variables

Detailed Description

Define Documentation

Function Documentation

Variable Documentation