General graph node

Introduced properties

type N: Node

a_star :: Node :: N

Type of the others nodes in the graph
init defaultinit(graph: Graph[N, Link])

a_star :: Node :: defaultinit

fun find_closest(max_cost: Int, context: PathContext, cond: nullable TargetCondition[N]): nullable N

a_star :: Node :: find_closest

Find the closest node accepted by cond under max_cost
fun graph: Graph[N, Link]

a_star :: Node :: graph

parent graph
protected fun graph=(graph: Graph[N, Link])

a_star :: Node :: graph=

parent graph
fun path_to(dest: N, max_cost: Int, context: PathContext): nullable AStarPath[N]

a_star :: Node :: path_to

Main functionality, returns path from self to dest
fun path_to_alts(destination: nullable N, max_cost: Int, context: PathContext, alt_targets: nullable TargetCondition[N]): nullable AStarPath[N]

a_star :: Node :: path_to_alts

Find a path to a possible destination or a node accepted by alt_targets

Redefined properties

redef type SELF: Node

a_star $ Node :: SELF

Type of this instance, automatically specialized in every class
redef fun core_serialize_to(serializer: Serializer)

a_star $ Node :: core_serialize_to

We customize the serialization process to avoid problems with recursive
redef init from_deserializer(deserializer: Deserializer)

a_star $ Node :: from_deserializer

Create an instance of this class from the deserializer
redef init init

a_star $ Node :: init

All properties

fun !=(other: nullable Object): Bool

core :: Object :: !=

Have self and other different values?
fun ==(other: nullable Object): Bool

core :: Object :: ==

Have self and other the same value?
type CLASS: Class[SELF]

core :: Object :: CLASS

The type of the class of self.
type N: Node

a_star :: Node :: N

Type of the others nodes in the graph
type SELF: Object

core :: Object :: SELF

Type of this instance, automatically specialized in every class
protected fun accept_json_serializer(v: JsonSerializer)

serialization :: Serializable :: accept_json_serializer

Refinable service to customize the serialization of this class to JSON
protected fun accept_msgpack_attribute_counter(v: AttributeCounter)

serialization :: Serializable :: accept_msgpack_attribute_counter

Hook to customize the behavior of the AttributeCounter
protected fun accept_msgpack_serializer(v: MsgPackSerializer)

serialization :: Serializable :: accept_msgpack_serializer

Hook to customize the serialization of this class to MessagePack
protected fun add_to_bundle(bundle: NativeBundle, key: JavaString)

serialization :: Serializable :: add_to_bundle

Called by []= to dynamically choose the appropriate method according
protected fun class_factory(name: String): CLASS

core :: Object :: class_factory

Implementation used by get_class to create the specific class.
fun class_name: String

core :: Object :: class_name

The class name of the object.
fun core_serialize_to(serializer: Serializer)

serialization :: Serializable :: core_serialize_to

Actual serialization of self to serializer
init defaultinit(graph: Graph[N, Link])

a_star :: Node :: defaultinit

fun find_closest(max_cost: Int, context: PathContext, cond: nullable TargetCondition[N]): nullable N

a_star :: Node :: find_closest

Find the closest node accepted by cond under max_cost
init from_deserializer(deserializer: Deserializer)

serialization :: Serializable :: from_deserializer

Create an instance of this class from the deserializer
fun get_class: CLASS

core :: Object :: get_class

The meta-object representing the dynamic type of self.
fun graph: Graph[N, Link]

a_star :: Node :: graph

parent graph
protected fun graph=(graph: Graph[N, Link])

a_star :: Node :: graph=

parent graph
fun hash: Int

core :: Object :: hash

The hash code of the object.
init init

core :: Object :: init

fun inspect: String

core :: Object :: inspect

Developer readable representation of self.
protected fun inspect_head: String

core :: Object :: inspect_head

Return "CLASSNAME:#OBJECTID".
intern fun is_same_instance(other: nullable Object): Bool

core :: Object :: is_same_instance

Return true if self and other are the same instance (i.e. same identity).
fun is_same_serialized(other: nullable Object): Bool

core :: Object :: is_same_serialized

Is self the same as other in a serialization context?
intern fun is_same_type(other: Object): Bool

core :: Object :: is_same_type

Return true if self and other have the same dynamic type.
protected fun msgpack_extra_array_items: Int

serialization :: Serializable :: msgpack_extra_array_items

Hook to request a larger than usual metadata array
intern fun object_id: Int

core :: Object :: object_id

An internal hash code for the object based on its identity.
fun output

core :: Object :: output

Display self on stdout (debug only).
intern fun output_class_name

core :: Object :: output_class_name

Display class name on stdout (debug only).
fun path_to(dest: N, max_cost: Int, context: PathContext): nullable AStarPath[N]

a_star :: Node :: path_to

Main functionality, returns path from self to dest
fun path_to_alts(destination: nullable N, max_cost: Int, context: PathContext, alt_targets: nullable TargetCondition[N]): nullable AStarPath[N]

a_star :: Node :: path_to_alts

Find a path to a possible destination or a node accepted by alt_targets
fun serialization_hash: Int

core :: Object :: serialization_hash

Hash value use for serialization
fun serialize_msgpack(plain: nullable Bool): Bytes

serialization :: Serializable :: serialize_msgpack

Serialize self to MessagePack bytes
fun serialize_to(serializer: Serializer)

serialization :: Serializable :: serialize_to

Serialize self to serializer
fun serialize_to_json(plain: nullable Bool, pretty: nullable Bool): String

serialization :: Serializable :: serialize_to_json

Serialize self to JSON
intern fun sys: Sys

core :: Object :: sys

Return the global sys object, the only instance of the Sys class.
fun to_json: String

serialization :: Serializable :: to_json

Serialize self to plain JSON
abstract fun to_jvalue(env: JniEnv): JValue

core :: Object :: to_jvalue

fun to_pretty_json: String

serialization :: Serializable :: to_pretty_json

Serialize self to plain pretty JSON
fun to_s: String

core :: Object :: to_s

User readable representation of self.
package_diagram a_star::Node Node serialization::Serializable Serializable a_star::Node->serialization::Serializable core::Object Object serialization::Serializable->core::Object ...core::Object ... ...core::Object->core::Object a_star::NamedNode NamedNode a_star::NamedNode->a_star::Node a_star::PositionedNamedNode PositionedNamedNode a_star::PositionedNamedNode->a_star::NamedNode a_star::PositionedNamedNode... ... a_star::PositionedNamedNode...->a_star::PositionedNamedNode

Ancestors

interface Object

core :: Object

The root of the class hierarchy.

Parents

interface Serializable

serialization :: Serializable

Instances of this class can be passed to Serializer::serialize

Children

class NamedNode

a_star :: NamedNode

Simple node with a name

Descendants

class PositionedNamedNode

a_star :: PositionedNamedNode

Node with a name and position

Class definitions

a_star $ Node
# General graph node
class Node
	super Serializable

	# Type of the others nodes in the `graph`
	type N: Node

	# parent graph
	var graph: Graph[N, Link]

	init
	do
		graph.add_node(self)
	end

	# adjacent nodes
	var links: Set[Link] = new HashSet[Link]

	# used to check if node has been searched in one pathfinding
	private var last_pathfinding_evocation: Int = 0

	# cost up to in current evocation
	# lifetime limited to evocation of `path_to`
	private var best_cost_up_to: Int = 0

	# source node
	# lifetime limited to evocation of `path_to`
	private var best_source: nullable N = null

	# is in frontier or buckets
	# lifetime limited to evocation of `path_to`
	private var open: Bool = false

	# Main functionality, returns path from `self` to `dest`
	fun path_to(dest: N, max_cost: Int, context: PathContext): nullable AStarPath[N]
	do
		return path_to_alts(dest, max_cost, context, null)
	end

	# Find a path to a possible `destination` or a node accepted by `alt_targets`
	fun path_to_alts(destination: nullable N, max_cost: Int, context: PathContext,
		alt_targets: nullable TargetCondition[N]): nullable AStarPath[N]
	do
		var cost = 0

		var nbr_buckets = context.worst_cost + context.worst_heuristic_cost + 1
		var buckets = new Array[List[N]].with_capacity(nbr_buckets)

		for i in [0 .. nbr_buckets[ do
			buckets.add(new List[N])
		end

		graph.pathfinding_current_evocation += 1

		# open source node
		buckets[0].add(self)
		open = true
		self.last_pathfinding_evocation = graph.pathfinding_current_evocation
		self.best_cost_up_to = 0

		loop
			var frontier_node: nullable N = null

			var bucket_searched = 0

			# find next valid node in frontier/buckets
			loop
				var current_bucket = buckets[cost % nbr_buckets]

				if current_bucket.is_empty then # move to next bucket
					cost += 1
					if cost > max_cost then return null
					bucket_searched += 1

					if bucket_searched > nbr_buckets then break
				else # found a node
					frontier_node = current_bucket.pop

					if frontier_node.open then break
				end
			end

			# no path possible
			if frontier_node == null then
				return null

			# at destination
			else if frontier_node == destination or
			     (alt_targets != null and alt_targets.accept(frontier_node)) then

				var path = new AStarPath[N](cost)

				while frontier_node != self do
					path.nodes.unshift(frontier_node)
					frontier_node = frontier_node.best_source
					assert frontier_node != null
				end

				return path

			# adds all next nodes to frontier/buckets
			else
				frontier_node.open = false

				for link in frontier_node.links do
					var peek_node = link.to
					if not context.is_blocked(link) and
					 (peek_node.last_pathfinding_evocation != graph.pathfinding_current_evocation or
					   (peek_node.open and
					     peek_node.best_cost_up_to > cost + context.cost(link)))
					then
						peek_node.open = true
						peek_node.last_pathfinding_evocation = graph.pathfinding_current_evocation
						peek_node.best_cost_up_to = cost + context.cost(link)
						peek_node.best_source = frontier_node

						var est_cost
						if destination != null then
							est_cost = peek_node.best_cost_up_to + context.heuristic_cost(peek_node, destination)
						else if alt_targets != null then
							est_cost = peek_node.best_cost_up_to + alt_targets.heuristic_cost(peek_node, link)
						else est_cost = 0

						var at_bucket = buckets[est_cost % nbr_buckets]
						at_bucket.add(peek_node)
					end
				end
			end
		end
	end

	# Find the closest node accepted by `cond` under `max_cost`
	fun find_closest(max_cost: Int, context: PathContext, cond: nullable TargetCondition[N]): nullable N
	do
		var path = path_to_alts(null, max_cost, context, cond)
		if path == null then return null
		return path.nodes.last
	end

	# We customize the serialization process to avoid problems with recursive
	# serialization engines. These engines, such as `JsonSerializer`,
	# are at danger to serialize the graph as a very deep tree.
	# With a large graph it can cause a stack overflow.
	#
	# Instead, we serialize the nodes first and then the links.
	redef fun core_serialize_to(serializer)
	do
		serializer.serialize_attribute("graph", graph)
	end

	redef init from_deserializer(deserializer)
	do
		deserializer.notify_of_creation self

		var graph = deserializer.deserialize_attribute("graph", (new GetName[Graph[N, Link]]).to_s)
		if not graph isa Graph[N, Link] then graph = new Graph[N, Link]
		self.graph = graph
	end
end
lib/a_star/a_star.nit:60,1--218,3