index : advtrains.git	atcjit departureboard doc l10n luaatcdebug master new-ks new-ks-orwell profiler route_prog_rework techage trainhud-unifont unittests-srht
	Advtrains mod for minetest.	orwell

aboutsummaryrefslogtreecommitdiff

log msg author committer range

path: root/advtrains_interlocking/train_sections.lua

	Commit message (Expand)	Author	Age
*	Fix crashes:	orwell96	2018-12-10
*	Shunt signals (not exactly Ks), along with fixes in other components that tho...	orwell96	2018-12-08
*	Miscellaneous routesetting fixes	orwell96	2018-10-29
*	Add signal safety control override, restructure control system	orwell96	2018-10-10

generated by cgit v1.2.3 (git 2.25.1) at 2024-07-02 04:27:28 +0000

/*
Minetest
Copyright (C) 2013 sapier, sapier at gmx dot net

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation; either version 2.1 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/

#ifndef PATHFINDER_H_
#define PATHFINDER_H_

/******************************************************************************/
/* Includes                                                                   */
/******************************************************************************/
#include <vector>

#include "irr_v3d.h"


/******************************************************************************/
/* Forward declarations                                                       */
/******************************************************************************/

class ServerEnvironment;

/******************************************************************************/
/* Typedefs and macros                                                        */
/******************************************************************************/

//#define PATHFINDER_DEBUG

typedef enum {
	DIR_XP,
	DIR_XM,
	DIR_ZP,
	DIR_ZM
} path_directions;

/** List of supported algorithms */
typedef enum {
	DIJKSTRA,           /**< Dijkstra shortest path algorithm             */
	A_PLAIN,            /**< A* algorithm using heuristics to find a path */
	A_PLAIN_NP          /**< A* algorithm without prefetching of map data */
} algorithm;

/******************************************************************************/
/* declarations                                                               */
/******************************************************************************/

/** c wrapper function to use from scriptapi */
std::vector<v3s16> get_Path(ServerEnvironment* env,
							v3s16 source,
							v3s16 destination,
							unsigned int searchdistance,
							unsigned int max_jump,
							unsigned int max_drop,
							algorithm algo);

/** representation of cost in specific direction */
class path_cost {
public:

	/** default constructor */
	path_cost();

	/** copy constructor */
	path_cost(const path_cost& b);

	/** assignment operator */
	path_cost& operator= (const path_cost& b);

	bool valid;              /**< movement is possible         */
	int  value;              /**< cost of movement             */
	int  direction;          /**< y-direction of movement      */
	bool updated;            /**< this cost has ben calculated */

};


/** representation of a mapnode to be used for pathfinding */
class path_gridnode {

public:
	/** default constructor */
	path_gridnode();

	/** copy constructor */
	path_gridnode(const path_gridnode& b);

	/**
	 * assignment operator
	 * @param b node to copy
	 */
	path_gridnode& operator= (const path_gridnode& b);

	/**
	 * read cost in a specific direction
	 * @param dir direction of cost to fetch
	 */
	path_cost get_cost(v3s16 dir);

	/**
	 * set cost value for movement
	 * @param dir direction to set cost for
	 * @cost cost to set
	 */
	void      set_cost(v3s16 dir,path_cost cost);

	bool      valid;               /**< node is on surface                    */
	bool      target;              /**< node is target position               */
	bool      source;              /**< node is stating position              */
	int       totalcost;           /**< cost to move here from starting point */
	v3s16     sourcedir;           /**< origin of movement for current cost   */
	int       surfaces;            /**< number of surfaces with same x,z value*/
	v3s16     pos;                 /**< real position of node                 */
	path_cost directions[4];       /**< cost in different directions          */

	/* debug values */
	bool      is_element;          /**< node is element of path detected      */
	char      type;                /**< type of node                          */
};

/** class doing pathfinding */
class pathfinder {

public:
	/**
	 * default constructor
	 */
	pathfinder();

	/**
	 * path evaluation function
	 * @param env environment to look for path
	 * @param source origin of path
	 * @param destination end position of path
	 * @param searchdistance maximum number of nodes to look in each direction
	 * @param max_jump maximum number of blocks a path may jump up
	 * @param max_drop maximum number of blocks a path may drop
	 * @param algo algorithm to use for finding a path
	 */
	std::vector<v3s16> get_Path(ServerEnvironment* env,
			v3s16 source,
			v3s16 destination,
			unsigned int searchdistance,
			unsigned int max_jump,
			unsigned int max_drop,
			algorithm algo);

private:
	/** data struct for storing internal information */
	struct limits {
		struct limit {
			int min;
			int max;
		};

		limit X;
		limit Y;
		limit Z;
	};

	/* helper functions */

	/**
	 * transform index pos to mappos
	 * @param ipos a index position
	 * @return map position
	 */
	v3s16          getRealPos(v3s16 ipos);

	/**
	 * transform mappos to index pos
	 * @param pos a real pos
	 * @return index position
	 */
	v3s16          getIndexPos(v3s16 pos);

	/**
	 * get gridnode at a specific index position
	 * @param ipos index position
	 * @return gridnode for index
	 */
	path_gridnode& getIndexElement(v3s16 ipos);

	/**
	 * invert a 3d position
	 * @param pos 3d position
	 * @return pos *-1
	 */
	v3s16          invert(v3s16 pos);

	/**
	 * check if a index is within current search area
	 * @param index position to validate
	 * @return true/false
	 */
	bool           valid_index(v3s16 index);

	/**
	 * translate position to float position
	 * @param pos integer position
	 * @return float position
	 */
	v3f            tov3f(v3s16 pos);


	/* algorithm functions */

	/**
	 * calculate 2d manahttan distance to target
	 * @param pos position to calc distance
	 * @return integer distance
	 */
	int           get_manhattandistance(v3s16 pos);

	/**
	 * get best direction based uppon heuristics
	 * @param directions list of unchecked directions
	 * @param g_pos mapnode to start from
	 * @return direction to check
	 */
	v3s16         get_dir_heuristic(std::vector<v3s16>& directions,path_gridnode& g_pos);

	/**
	 * build internal data representation of search area
	 * @return true/false if costmap creation was successfull
	 */
	bool          build_costmap();

	/**
	 * calculate cost of movement
	 * @param pos real world position to start movement