pathfinder Class Reference

Finds paths through maps. More...

#include <th_pathfind.h>

Public Member Functions
	pathfinder ()
	~pathfinder ()
void	set_default_map (const level_map *pMap)
bool	find_path (const level_map *pMap, int iStartX, int iStartY, int iEndX, int iEndY)
bool	find_idle_tile (const level_map *pMap, int iStartX, int iStartY, int iN, int parcelId)
bool	find_path_to_hospital (const level_map *pMap, int iStartX, int iStartY)
bool	visit_objects (const level_map *pMap, int iStartX, int iStartY, object_type eTHOB, int iMaxDistance, lua_State *L, int iVisitFunction, bool anyObjectType)
int	get_path_length () const
bool	get_path_end (int *pX, int *pY) const
void	push_result (lua_State *L) const
void	persist (lua_persist_writer *pWriter) const
void	depersist (lua_persist_reader *pReader)
void	allocate_node_cache (int iWidth, int iHeight)
	Allocate node cache for all tiles of the map.
path_node *	pop_from_open_heap ()
void	push_to_open_heap (path_node *pNode)
void	open_heap_promote (path_node *pNode)

Public Attributes
const level_map *	default_map
std::vector< path_node >	nodes
	2D array of nodes, one for each map cell
path_node **	dirty_node_list
	Array of "dirty" nodes which need to be reset before the next path find.
std::vector< path_node * >	open_heap
	Heap of not yet evaluated nodes as a 0-based array.
path_node *	destination
int	node_cache_width
int	node_cache_height
int	dirty_node_count

Detailed Description

Finds paths through maps.

A pathfinder is used for finding a path through a map. A single pathfinder instance is not reentrant, but separate instances are. Users of the class should call find_path() to test if there is a path between two points on a map, and then use get_path_length() and/or push_result() to get the actual path.

Internally, the A* search algorithm is used. The open set is implemented as a heap in open_heap, and there is no explicit closed set. For each cell of the map, a path_node structure is created (and cached between searches if the map size is constant), which holds information about said map cell in the current search. The algorithm is implemented in such a way that most path find operations do not need to allocate (or free) any memory.

Constructor & Destructor Documentation

pathfinder()

pathfinder::pathfinder

(

)

~pathfinder()

pathfinder::~pathfinder

(

)

Member Function Documentation

allocate_node_cache()

void pathfinder::allocate_node_cache	(	int	iWidth,
		int	iHeight
	)

Allocate node cache for all tiles of the map.

Parameters

iWidth	Width of the map.
iHeight	Height of the map.

depersist()

void pathfinder::depersist

(

lua_persist_reader *

pReader

)

find_idle_tile()

bool pathfinder::find_idle_tile ( const level_map *  pMap, int  iStartX, int  iStartY, int  iN, int  parcelId  )

inline

find_path()

bool pathfinder::find_path ( const level_map *  pMap, int  iStartX, int  iStartY, int  iEndX, int  iEndY  )

inline

find_path_to_hospital()

bool pathfinder::find_path_to_hospital ( const level_map *  pMap, int  iStartX, int  iStartY  )

inline

get_path_end()

bool pathfinder::get_path_end	(	int *	pX,
		int *	pY
	)		const

get_path_length()

int pathfinder::get_path_length

(

)

const

open_heap_promote()

void pathfinder::open_heap_promote

(

path_node *

pNode

)

persist()

void pathfinder::persist

(

lua_persist_writer *

pWriter

)

const

pop_from_open_heap()

path_node * pathfinder::pop_from_open_heap

(

)

push_result()

void pathfinder::push_result

(

lua_State *

L

)

const

push_to_open_heap()

void pathfinder::push_to_open_heap

(

path_node *

pNode

)

set_default_map()

void pathfinder::set_default_map

(

const level_map *

pMap

)

visit_objects()

bool pathfinder::visit_objects ( const level_map *  pMap, int  iStartX, int  iStartY, object_type  eTHOB, int  iMaxDistance, lua_State *  L, int  iVisitFunction, bool  anyObjectType  )

inline

Member Data Documentation

default_map

const level_map* pathfinder::default_map

destination

path_node* pathfinder::destination

dirty_node_count

int pathfinder::dirty_node_count

dirty_node_list

path_node** pathfinder::dirty_node_list

Array of "dirty" nodes which need to be reset before the next path find.

This array is always large enough to hold every single node, and dirty_node_count holds the number of items currently in the array.

node_cache_height

int pathfinder::node_cache_height

node_cache_width

int pathfinder::node_cache_width

nodes

std::vector<path_node> pathfinder::nodes

2D array of nodes, one for each map cell

open_heap

std::vector<path_node*> pathfinder::open_heap

Heap of not yet evaluated nodes as a 0-based array.

This array conforms to the conditions: value(i) <= value(i * 2 + 1) value(i) <= value(i * 2 + 2) This causes the array to be a minimum binary heap.

---

The documentation for this class was generated from the following files:

• /home/runner/work/CorsixTH/CorsixTH/CorsixTH/Src/th_pathfind.h
• /home/runner/work/CorsixTH/CorsixTH/CorsixTH/Src/th_pathfind.cpp