1

/* $Id$ */

     2

     3

/**

     4

 * An AyStar implementation.

     5

 *  It solves graphs by finding the fastest route from one point to the other.

     6

 */

     7

class AyStar

     8

{

    10

	_cost_callback = null;

    11

	_estimate_callback = null;

    12

	_neighbours_callback = null;

    13

	_cost_callback_param = null;

    14

	_estimate_callback_param = null;

    15

	_neighbours_callback_param = null;

    16

	_open = null;

    17

	_closed = null;

    18

	_goals = null;

    19

    20

	/**

    21

	 * @param cost_callback A function that returns the cost of a path. It

    22

	 *  should accept three parameters, old_path, new_node and

    23

	 *  cost_callback_param. old_path is an instance of AyStar.Path, and

    24

	 *  new_node is the new node that is added to that path. It should return

    25

	 *  the cost of the path including new_node.

    26

	 * @param estimate_callback A function that returns an estimate from a node

    27

	 *  to the goal node. It should accept three parameters, node, goal_nodes and

    28

	 *  estimate_callback_param. It should return an estimate to the cost from

    29

	 *  the lowest cost between node and any node out of goal_nodes. Note that

    30

	 *  this estimate is not allowed to be higher than the real cost between node

    31

	 *  and any of goal_nodes. A lower value is fine, however the closer it is to

    32

	 *  the real value, the better the performance.

    33

	 * @param neighbours_callback A function that returns all neighbouring nodes

    34

	 *  from a given node. It should accept three parameters, current_path, node

    35

	 *  and neighbours_callback_param. It should return an array containing all

    36

	 *  neighbouring nodes.

    37

	 * @param cost_callback_param This parameters will be passed to cost_callback

    38

	 *  as third parameter. Useful to send is an instance of an object.

    39

	 * @param estimate_callback_param This parameters will be passed to

    40

	 *  estimate_callback as third parameter. Useful to send is an instance of an

    41

	 *  object.

    42

	 * @param neighbours_callback_param This parameters will be passed to

    43

	 *  neighbours_callback as third parameter. Useful to send is an instance of

    44

	 *  an object.

    45

	 */

    46

	constructor(cost_callback, estimate_callback, neighbours_callback, cost_callback_param = null,

    47

	            estimate_callback_param = null, neighbours_callback_param = null)

    48

	{

    49

		if (typeof(cost_callback) != "function") throw("'cost_callback' has be a function-pointer.");

    50

		if (typeof(estimate_callback) != "function") throw("'estimate_callback' has be a function-pointer.");

    51

		if (typeof(neighbours_callback) != "function") throw("'neighbours_callback' has be a function-pointer.");

    52

    53

		this._cost_callback = cost_callback;

    54

		this._estimate_callback = estimate_callback;

    55

		this._neighbours_callback = neighbours_callback;

    56

		this._cost_callback_param = cost_callback_param;

    57

		this._estimate_callback_param = estimate_callback_param;

    58

		this._neighbours_callback_param = neighbours_callback_param;

    59

	}

    60

    61

	/**

    62

	 * Initialize a path search between sources and goals.

    63

	 * @param sources The source nodes.

    64

	 * @param goals The target nodes.

    65

	 */

    66

	function InitializePath(sources, goals);

    67

    68

	/**

    69

	 * Try to find the path as indicated with InitializePath with the lowest cost.

    70

	 * @param iterations After how many iterations it should abort for a moment.

    71

	 *  This value should either be -1 for infinite, or > 0. Any other value

    72

	 *  aborts immediatly and will never find a path.

    73

	 * @return A route if one was found, or false if the amount of iterations was

    74

	 *  reached, or null if no path was found.

    75

	 *  You can call this function over and over as long as it returns false,

    76

	 *  which is an indication it is not yet done looking for a route.

    77

	 */

    78

	function FindPath(iterations);

    79

}

    80

    81

function AyStar::InitializePath(sources, goals)

    82

{

    83

	if (typeof(sources) != "array" || sources.len() == 0) throw("sources has be a non-empty array.");

    84

	if (typeof(goals) != "array" || goals.len() == 0) throw("goals has be a non-empty array.");

    85

    87

	this._closed = AIList();

    88

    89

	foreach (node in sources) {

    90

		local new_path = this.Path(null, node, this._cost_callback, this._cost_callback_param);

    91

		this._open.Insert(new_path, new_path.GetCost() + this._estimate_callback(node, goals, this._estimate_callback_param));

    92

	}

    93

    94

	this._goals = goals;

    95

}

    96

    97

function AyStar::FindPath(iterations)

    98

{

    99

	if (this._open == null) throw("can't execute over an uninitialized path");

   100

   101

	while (this._open.Count() > 0 && (iterations == -1 || iterations-- > 0)) {

   102

		/* Get the path with the best score so far */

   103

		local path = this._open.Pop();

   104

		local cur_node = path.GetNode();

   105

		/* Make sure we didn't already passed it */

   106

		if (this._closed.HasItem(cur_node)) continue;

   107

		/* Check if we found the end */

   108

		foreach (node in this._goals) {

   109

			if (cur_node == node) {

   110

				this._CleanPath();

   111

				return path;

   112

			}

   113

		}

   114

		this._closed.AddItem(cur_node, 0);

   115

		/* Scan all neighbours */

   116

		local neighbours = this._neighbours_callback(path, cur_node, this._neighbours_callback_param);

   117

		foreach (node in neighbours) {

   118

			if (this._closed.HasItem(node)) continue;

   119

			/* Calculate the new paths and add them to the open list */

   120

			local new_path = this.Path(path, node, this._cost_callback, this._cost_callback_param);

   121

			this._open.Insert(new_path, new_path.GetCost() + this._estimate_callback(node, this._goals, this._estimate_callback_param));

   122

		}

   123

	}

   124

   125

	if (this._open.Count() > 0) return false;

   126

	this._CleanPath();

   127

	return null;

   128

}

   129

   130

function AyStar::_CleanPath()

   131

{

   132

	this._closed = null;

   133

	this._open = null;

   134

	this._goals = null;

   135

}

   136

   137

/**

   138

 * The path of the AyStar algorithm.

   139

 *  It is reversed, that is, the first entry is more close to the goal-nodes

   140

 *  than his GetParent(). You can walk this list to find the whole path.

   141

 *  The last entry has a GetParent() of null.

   142

 */

   143

class AyStar.Path

   144

{

   145

	_prev = null;

   146

	_node = null;

   147

	_cost = null;

   148

   149

	constructor(old_path, new_node, cost_callback, cost_callback_param)

   150

	{

   151

		this._prev = old_path;

   152

		this._node = new_node;

   153

		this._cost = cost_callback(old_path, new_node, cost_callback_param);

   154

	};

   155

   156

	/**

   157

	 * Return the node where this (partial-)path ends.

   158

	 */

   159

	function GetNode() { return this._node; }

   160

   161

	/**

   162

	 * Return an instance of this class leading to the previous node.

   163

	 */

   164

	function GetParent() { return this._prev; }

   165

   166

	/**

   167

	 * Return the cost of this (partial-)path from the beginning up to this node.

   168

	 */

   169

	function GetCost() { return this._cost; }

   170

}