*/

void AyStar::Init(Hash_HashProc hash, uint num_buckets)

{

	/* Allocated the Hash for the OpenList and ClosedList */

	this->openlist_hash.Init(hash, num_buckets);

	this->closedlist_hash.Init(hash, num_buckets);

	/* Set up our sorting queue

	 *  BinaryHeap allocates a block of 1024 nodes

	 *  When that one gets full it reserves another one, till this number

	 *  That is why it can stay this high */

	this->openlist_queue.Init(102400);

}

 * %AyStar is a fast path finding routine and is used for things like AI path finding and Train path finding.

 * For more information about AyStar (A* Algorithm), you can look at

 * <A HREF='http://en.wikipedia.org/wiki/A-star_search_algorithm'>http://en.wikipedia.org/wiki/A-star_search_algorithm</A>.

 */

#ifndef AYSTAR_H

#define AYSTAR_H

#include "queue.h"

#include "../../tile_type.h"

#include "../../track_type.h"

/** Return status of #AyStar methods. */

enum AystarStatus {

	AYSTAR_FOUND_END_NODE, ///< An end node was found.

	AYSTAR_EMPTY_OPENLIST, ///< All items are tested, and no path has been found.

	AYSTAR_STILL_BUSY,     ///< Some checking was done, but no path found yet, and there are still items left to try.

	AYSTAR_NO_PATH,        ///< No path to the goal was found.

	AYSTAR_LIMIT_REACHED,  ///< The #AyStar::max_search_nodes limit has been reached, aborting search.

	AYSTAR_DONE,           ///< Not an end-tile, or wrong direction.

};

static const int AYSTAR_INVALID_NODE = -1; ///< Item is not valid (for example, not walkable).

 * This file is part of OpenTTD.

 * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.

 * OpenTTD 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 General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.

 */

/** @file pathfinder_type.h General types related to pathfinders. */

#ifndef PATHFINDER_TYPE_H

#define PATHFINDER_TYPE_H

#include "../tile_type.h"

/** Length (penalty) of one tile with NPF */

static const int NPF_TILE_LENGTH = 100;

/**

 * This penalty is the equivalent of "infinite", which means that paths that

 * get this penalty will be chosen, but only if there is no other route

 * without it. Be careful with not applying this penalty too often, or the

 * total path cost might overflow.

 */

static const int NPF_INFINITE_PENALTY = 1000 * NPF_TILE_LENGTH;

[SDT_VAR]

var      = pf.path_backoff_interval

type     = SLE_UINT8

from     = SLV_100

def      = 20

min      = 1

max      = 255

cat      = SC_EXPERT

[SDT_VAR]

var      = pf.npf.npf_max_search_nodes

type     = SLE_UINT

min      = 500

max      = 100000

cat      = SC_EXPERT

[SDT_VAR]

var      = pf.npf.npf_rail_firstred_penalty

type     = SLE_UINT

def      = 10 * NPF_TILE_LENGTH

min      = 0

max      = 100000

cat      = SC_EXPERT

cat      = SC_EXPERT

[SDT_BOOL]

var      = pf.yapf.disable_node_optimization

from     = SLV_28

def      = false

cat      = SC_EXPERT

[SDT_VAR]

var      = pf.yapf.max_search_nodes

type     = SLE_UINT

from     = SLV_28

min      = 500

max      = 1000000

cat      = SC_EXPERT

[SDT_BOOL]

var      = pf.yapf.rail_firstred_twoway_eol

from     = SLV_28

def      = true

cat      = SC_EXPERT

[SDT_VAR]

var      = pf.yapf.rail_firstred_penalty