1

/* $Id$ */

     2

     3

/** @file yapf_base.hpp Base classes for YAPF. */

     4

     5

#ifndef  YAPF_BASE_HPP

     6

#define  YAPF_BASE_HPP

     7

     8

#include "../debug.h"

     9

#include "../settings_type.h"

    10

    11

extern int _total_pf_time_us;

    12

    13

/** CYapfBaseT - A-star type path finder base class.

    14

 *  Derive your own pathfinder from it. You must provide the following template argument:

    15

 *    Types      - used as collection of local types used in pathfinder

    16

 *

    17

 * Requirements for the Types struct:

    18

 *  ----------------------------------

    19

 *  The following types must be defined in the 'Types' argument:

    20

 *    - Types::Tpf - your pathfinder derived from CYapfBaseT

    21

 *    - Types::NodeList - open/closed node list (look at CNodeList_HashTableT)

    22

 *  NodeList needs to have defined local type Titem - defines the pathfinder node type.

    23

 *  Node needs to define local type Key - the node key in the collection ()

    24

 *

    25

 *  For node list you can use template class CNodeList_HashTableT, for which

    26

 *  you need to declare only your node type. Look at test_yapf.h for an example.

    27

 *

    28

 *

    29

 *  Requrements to your pathfinder class derived from CYapfBaseT:

    30

 *  -------------------------------------------------------------

    31

 *  Your pathfinder derived class needs to implement following methods:

    32

 *    FORCEINLINE void PfSetStartupNodes()

    33

 *    FORCEINLINE void PfFollowNode(Node& org)

    34

 *    FORCEINLINE bool PfCalcCost(Node& n)

    35

 *    FORCEINLINE bool PfCalcEstimate(Node& n)

    36

 *    FORCEINLINE bool PfDetectDestination(Node& n)

    37

 *

    38

 *  For more details about those methods, look at the end of CYapfBaseT

    39

 *  declaration. There are some examples. For another example look at

    40

 *  test_yapf.h (part or unittest project).

    41

 */

    42

template <class Types>

    43

class CYapfBaseT {

    44

public:

    45

	typedef typename Types::Tpf Tpf;           ///< the pathfinder class (derived from THIS class)

    46

	typedef typename Types::TrackFollower TrackFollower;

    47

	typedef typename Types::NodeList NodeList; ///< our node list

    48

	typedef typename NodeList::Titem Node;     ///< this will be our node type

    49

	typedef typename Node::Key Key;            ///< key to hash tables

    50

    51

    52

	NodeList             m_nodes;              ///< node list multi-container

    53

protected:

    54

	Node                *m_pBestDestNode;      ///< pointer to the destination node found at last round

    55

	Node                *m_pBestIntermediateNode; ///< here should be node closest to the destination if path not found

    56

	const YAPFSettings  *m_settings;           ///< current settings (_settings_game.yapf)

    57

	int                  m_max_search_nodes;   ///< maximum number of nodes we are allowed to visit before we give up

    58

	const Vehicle       *m_veh;                ///< vehicle that we are trying to drive

    59

    60

	int                  m_stats_cost_calcs;   ///< stats - how many node's costs were calculated

    61

	int                  m_stats_cache_hits;   ///< stats - how many node's costs were reused from cache

    62

    63

public:

    64

	CPerformanceTimer    m_perf_cost;          ///< stats - total CPU time of this run

    65

	CPerformanceTimer    m_perf_slope_cost;    ///< stats - slope calculation CPU time

    66

	CPerformanceTimer    m_perf_ts_cost;       ///< stats - GetTrackStatus() CPU time

    67

	CPerformanceTimer    m_perf_other_cost;    ///< stats - other CPU time

    68

    69

public:

    70

	int                  m_num_steps;          ///< this is there for debugging purposes (hope it doesn't hurt)

    71

    72

public:

    73

	/// default constructor

    74

	FORCEINLINE CYapfBaseT()

    75

		: m_pBestDestNode(NULL)

    76

		, m_pBestIntermediateNode(NULL)

    77

		, m_settings(&_settings_game.pf.yapf)

    78

		, m_max_search_nodes(PfGetSettings().max_search_nodes)

    79

		, m_veh(NULL)

    80

		, m_stats_cost_calcs(0)

    81

		, m_stats_cache_hits(0)

    82

		, m_num_steps(0)

    83

	{

    84

	}

    85

    86

	/// default destructor

    87

	~CYapfBaseT() {}

    88

    89

protected:

    90

	/// to access inherited path finder

    91

	FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);}

    92

    93

public:

    94

	/// return current settings (can be custom - player based - but later)

    95

	FORCEINLINE const YAPFSettings& PfGetSettings() const

    96

	{

    97

		return *m_settings;

    98

	}

    99

   100

	/** Main pathfinder routine:

   101

	 *   - set startup node(s)

   102

	 *   - main loop that stops if:

   103

	 *      - the destination was found

   104

	 *      - or the open list is empty (no route to destination).

   105

	 *      - or the maximum amount of loops reached - m_max_search_nodes (default = 10000)

   106

	 * @return true if the path was found */

   107

	inline bool FindPath(const Vehicle *v)

   108

	{

   109

		m_veh = v;

   110

   111

#ifndef NO_DEBUG_MESSAGES

   112

		CPerformanceTimer perf;

   113

		perf.Start();

   114

#endif /* !NO_DEBUG_MESSAGES */

   115

   116

		Yapf().PfSetStartupNodes();

   117

   118

		while (true) {

   119

			m_num_steps++;

   120

			Node *n = m_nodes.GetBestOpenNode();

   121

			if (n == NULL)

   122

				break;

   123

   124

			// if the best open node was worse than the best path found, we can finish

   125

			if (m_pBestDestNode != NULL && m_pBestDestNode->GetCost() < n->GetCostEstimate())

   126

				break;

   127

   128

			Yapf().PfFollowNode(*n);

   129

			if (m_max_search_nodes == 0 || m_nodes.ClosedCount() < m_max_search_nodes) {

   130

				m_nodes.PopOpenNode(n->GetKey());

   131

				m_nodes.InsertClosedNode(*n);

   132

			} else {

   133

				m_pBestDestNode = m_pBestIntermediateNode;

   134

				break;

   135

			}

   136

		}

   137

   138

		bool bDestFound = (m_pBestDestNode != NULL) && (m_pBestDestNode != m_pBestIntermediateNode);

   139

   140

#ifndef NO_DEBUG_MESSAGES

   141

		perf.Stop();

   142

		if (_debug_yapf_level >= 2) {

   143

			int t = perf.Get(1000000);

   144

			_total_pf_time_us += t;

   145

   146

			if (_debug_yapf_level >= 3) {

   147

				UnitID veh_idx = (m_veh != NULL) ? m_veh->unitnumber : 0;

   148

				char ttc = Yapf().TransportTypeChar();

   149

				float cache_hit_ratio = (m_stats_cache_hits == 0) ? 0.0f : ((float)m_stats_cache_hits / (float)(m_stats_cache_hits + m_stats_cost_calcs) * 100.0f);

   150

				int cost = bDestFound ? m_pBestDestNode->m_cost : -1;

   151

				int dist = bDestFound ? m_pBestDestNode->m_estimate - m_pBestDestNode->m_cost : -1;

   152

   153

				DEBUG(yapf, 3, "[YAPF%c]%c%4d- %d us - %d rounds - %d open - %d closed - CHR %4.1f%% - c%d(sc%d, ts%d, o%d) -- ",

   154

				  ttc, bDestFound ? '-' : '!', veh_idx, t, m_num_steps, m_nodes.OpenCount(), m_nodes.ClosedCount(),

   155

				  cache_hit_ratio, cost, dist, m_perf_cost.Get(1000000), m_perf_slope_cost.Get(1000000),

   156

				  m_perf_ts_cost.Get(1000000), m_perf_other_cost.Get(1000000)

   157

				);

   158

			}

   159

		}

   160

#endif /* !NO_DEBUG_MESSAGES */

   161

		return bDestFound;

   162

	}

   163

   164

	/** If path was found return the best node that has reached the destination. Otherwise

   165

	 *  return the best visited node (which was nearest to the destination).

   166

	 */

   167

	FORCEINLINE Node* GetBestNode()

   168

	{

   169

		return (m_pBestDestNode != NULL) ? m_pBestDestNode : m_pBestIntermediateNode;

   170

	}

   171

   172

	/** Calls NodeList::CreateNewNode() - allocates new node that can be filled and used

   173

	 *  as argument for AddStartupNode() or AddNewNode()

   174

	 */

   175

	FORCEINLINE Node& CreateNewNode()

   176

	{

   177

		Node& node = *m_nodes.CreateNewNode();

   178

		return node;

   179

	}

   180

   181

	/** Add new node (created by CreateNewNode and filled with data) into open list */

   182

	FORCEINLINE void AddStartupNode(Node& n)

   183

	{

   184

		Yapf().PfNodeCacheFetch(n);

   185

		// insert the new node only if it is not there

   186

		if (m_nodes.FindOpenNode(n.m_key) == NULL) {

   187

			m_nodes.InsertOpenNode(n);

   188

		} else {

   189

			// if we are here, it means that node is already there - how it is possible?

   190

			//   probably the train is in the position that both its ends point to the same tile/exit-dir

   191

			//   very unlikely, but it happened

   192

		}

   193

	}

   194

   195

	/** add multiple nodes - direct children of the given node */

   196

	FORCEINLINE void AddMultipleNodes(Node* parent, const TrackFollower &tf)

   197

	{

   198

		bool is_choice = (KillFirstBit(tf.m_new_td_bits) != TRACKDIR_BIT_NONE);

   199

		for (TrackdirBits rtds = tf.m_new_td_bits; rtds != TRACKDIR_BIT_NONE; rtds = KillFirstBit(rtds)) {

   200

			Trackdir td = (Trackdir)FindFirstBit2x64(rtds);

   201

			Node& n = Yapf().CreateNewNode();

   202

			n.Set(parent, tf.m_new_tile, td, is_choice);

   203

			Yapf().AddNewNode(n, tf);

   204

		}

   205

	}

   206

   207

	/** AddNewNode() - called by Tderived::PfFollowNode() for each child node.

   208

	 *  Nodes are evaluated here and added into open list */

   209

	void AddNewNode(Node &n, const TrackFollower &tf)

   210

	{

   211

		// evaluate the node

   212

		bool bCached = Yapf().PfNodeCacheFetch(n);

   213

		if (!bCached) {

   214

			m_stats_cost_calcs++;

   215

		} else {

   216

			m_stats_cache_hits++;

   217

		}

   218

   219

		bool bValid = Yapf().PfCalcCost(n, &tf);

   220

   221

		if (bCached) {

   222

			Yapf().PfNodeCacheFlush(n);

   223

		}

   224

   225

		if (bValid) bValid = Yapf().PfCalcEstimate(n);

   226

   227

		// have the cost or estimate callbacks marked this node as invalid?

   228

		if (!bValid) return;

   229

   230

		// detect the destination

   231

		bool bDestination = Yapf().PfDetectDestination(n);

   232

		if (bDestination) {

   233

			if (m_pBestDestNode == NULL || n < *m_pBestDestNode) {

   234

				m_pBestDestNode = &n;

   235

			}

   236

			m_nodes.FoundBestNode(n);

   237

			return;

   238

		}

   239

   240

		if (m_max_search_nodes > 0 && (m_pBestIntermediateNode == NULL || (m_pBestIntermediateNode->GetCostEstimate() - m_pBestIntermediateNode->GetCost()) > (n.GetCostEstimate() - n.GetCost()))) {

   241

			m_pBestIntermediateNode = &n;

   242

		}

   243

   244

		// check new node against open list

   245

		Node* openNode = m_nodes.FindOpenNode(n.GetKey());

   246

		if (openNode != NULL) {

   247

			// another node exists with the same key in the open list

   248

			// is it better than new one?

   249

			if (n.GetCostEstimate() < openNode->GetCostEstimate()) {

   250

				// update the old node by value from new one

   251

				m_nodes.PopOpenNode(n.GetKey());

   252

				*openNode = n;

   253

				// add the updated old node back to open list

   254

				m_nodes.InsertOpenNode(*openNode);

   255

			}

   256

			return;

   257

		}

   258

   259

		// check new node against closed list

   260

		Node* closedNode = m_nodes.FindClosedNode(n.GetKey());

   261

		if (closedNode != NULL) {

   262

			// another node exists with the same key in the closed list

   263

			// is it better than new one?

   264

			int node_est = n.GetCostEstimate();

   265

			int closed_est = closedNode->GetCostEstimate();

   266

			if (node_est < closed_est) {

   267

				// If this assert occurs, you have probably problem in

   268

				// your Tderived::PfCalcCost() or Tderived::PfCalcEstimate().

   269

				// The problem could be:

   270

				//  - PfCalcEstimate() gives too large numbers

   271

				//  - PfCalcCost() gives too small numbers

   272

				//  - You have used negative cost penalty in some cases (cost bonus)

   273

				assert(0);

   274

   275

				return;

   276

			}

   277

			return;

   278

		}

   279

		// the new node is really new

   280

		// add it to the open list

   281

		m_nodes.InsertOpenNode(n);

   282

	}

   283

   284

	const Vehicle * GetVehicle() const {return m_veh;}

   285

   286

	void DumpBase(DumpTarget &dmp) const

   287

	{

   288

		dmp.WriteStructT("m_nodes", &m_nodes);

   289

		dmp.WriteLine("m_num_steps = %d", m_num_steps);

   290

	}

   291

   292

	// methods that should be implemented at derived class Types::Tpf (derived from CYapfBaseT)

   293

   294

#if 0

   295

	/** Example: PfSetStartupNodes() - set source (origin) nodes */

   296

	FORCEINLINE void PfSetStartupNodes()

   297

	{

   298

		// example:

   299

		Node& n1 = *base::m_nodes.CreateNewNode();

   300

		.

   301

		. // setup node members here

   302

		.

   303

		base::m_nodes.InsertOpenNode(n1);

   304

	}

   305

   306

	/** Example: PfFollowNode() - set following (child) nodes of the given node */

   307

	FORCEINLINE void PfFollowNode(Node& org)

   308

	{

   309

		for (each follower of node org) {

   310

			Node& n = *base::m_nodes.CreateNewNode();

   311

			.

   312

			. // setup node members here

   313

			.

   314

			n.m_parent   = &org; // set node's parent to allow back tracking

   315

			AddNewNode(n);

   316

		}

   317

	}

   318

   319

	/** Example: PfCalcCost() - set path cost from origin to the given node */

   320

	FORCEINLINE bool PfCalcCost(Node& n)

   321

	{

   322

		// evaluate last step cost

   323

		int cost = ...;

   324

		// set the node cost as sum of parent's cost and last step cost

   325

		n.m_cost = n.m_parent->m_cost + cost;

   326

		return true; // true if node is valid follower (i.e. no obstacle was found)

   327

	}

   328

   329

	/** Example: PfCalcEstimate() - set path cost estimate from origin to the target through given node */

   330

	FORCEINLINE bool PfCalcEstimate(Node& n)

   331

	{

   332

		// evaluate the distance to our destination

   333

		int distance = ...;

   334

		// set estimate as sum of cost from origin + distance to the target

   335

		n.m_estimate = n.m_cost + distance;

   336

		return true; // true if node is valid (i.e. not too far away :)

   337

	}

   338

   339

	/** Example: PfDetectDestination() - return true if the given node is our destination */

   340

	FORCEINLINE bool PfDetectDestination(Node& n)

   341

	{

   342

		bool bDest = (n.m_key.m_x == m_x2) && (n.m_key.m_y == m_y2);

   343

		return bDest;

   344

	}

   345

#endif

   346

};

   347

   348

#endif /* YAPF_BASE_HPP */