X-Git-Url: http://nitlanguage.org diff --git a/lib/a_star.nit b/lib/a_star.nit index 4108268..9ea68e8 100644 --- a/lib/a_star.nit +++ b/lib/a_star.nit @@ -14,9 +14,9 @@ # See the License for the specific language governing permissions and # limitations under the License. -# Services related to pathfinding of graphs using A* -# A single graph may have different properties according to the `PathContext` used +# A* pathfinding in graphs # +# A single graph may have different properties according to the `PathContext` used # # Usage: # @@ -55,16 +55,20 @@ # ~~~ module a_star +import serialization + # 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(graph: Graph[N, Link]) + init do - self.graph = graph graph.add_node(self) end @@ -86,15 +90,15 @@ class Node # lifetime limited to evocation of `path_to` private var open: Bool = false - # Main functionnality, returns path from `self` to `dest` - fun path_to(dest: N, max_cost: Int, context: PathContext): nullable Path[N] + # 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 Path[N] + alt_targets: nullable TargetCondition[N]): nullable AStarPath[N] do var cost = 0 @@ -116,7 +120,7 @@ class Node loop var frontier_node: nullable N = null - var bucket_searched: Int = 0 + var bucket_searched = 0 # find next valid node in frontier/buckets loop @@ -143,11 +147,12 @@ class Node else if frontier_node == destination or (alt_targets != null and alt_targets.accept(frontier_node)) then - var path = new Path[N](cost) + var path = new AStarPath[N](cost) while frontier_node != self do path.nodes.unshift(frontier_node) - frontier_node = frontier_node.best_source.as(not null) + frontier_node = frontier_node.best_source + assert frontier_node != null end return path @@ -182,33 +187,72 @@ class Node 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 # Link between two nodes and associated to a graph class Link + serialize + + # Type of the nodes in `graph` type N: Node + + # Type of the other links in `graph` type L: Link + # The graph to which belongs `self` var graph: Graph[N, L] + # Origin of this link var from: N + + # Endpoint of this link var to: N - init(graph: Graph[N, L], from, to: N) + init do - self.graph = graph - self.from = from - self.to = to - graph.add_link(self) end end # General graph class Graph[N: Node, L: Link] - var nodes: Set[N] = new HashSet[N] - var links: Set[L] = new HashSet[L] + super Serializable + # Nodes in this graph + var nodes = new Set[N] + + # Links in this graph + var links = new Set[L] + + # Add a `node` to this graph fun add_node(node: N): N do nodes.add(node) @@ -216,6 +260,7 @@ class Graph[N: Node, L: Link] return node end + # Add a `link` to this graph fun add_link(link: L): L do links.add(link) @@ -225,23 +270,49 @@ class Graph[N: Node, L: Link] return link end - # used to check if nodes have been searched in one pathfinding - var pathfinding_current_evocation: Int = 0 + # Used to check if nodes have been searched in one pathfinding + private var pathfinding_current_evocation: Int = 0 + + redef fun core_serialize_to(serializer) + do + serializer.serialize_attribute("nodes", nodes) + serializer.serialize_attribute("links", links) + end + + redef init from_deserializer(deserializer) + do + deserializer.notify_of_creation self + + var nodes = deserializer.deserialize_attribute("nodes", (new GetName[Set[N]]).to_s) + if deserializer.deserialize_attribute_missing then + deserializer.errors.add new AttributeMissingError(self, "nodes") + end + if nodes isa Set[N] then self.nodes = nodes + + var links = deserializer.deserialize_attribute("links", (new GetName[Set[L]]).to_s) + if deserializer.deserialize_attribute_missing then + deserializer.errors.add new AttributeMissingError(self, "links") + end + if links isa Set[L] then for link in links do add_link link + end end -# Result from pathfinding, a walkable path -class Path[N] +# Result from path finding and a walkable path +class AStarPath[N] + serialize + # Total cost of this path var total_cost: Int + # Nodes composing this path var nodes = new List[N] - init (cost: Int) do total_cost = cost + private var at: Int = 0 - var at: Int = 0 + # Step on the path and get the next node to travel fun step: N do - assert nodes.length >= at else print "a_star::Path::step failed, is at_end_of_path" + assert nodes.length >= at else print "a_star::AStarPath::step failed, is at_end_of_path" var s = nodes[at] at += 1 @@ -249,16 +320,24 @@ class Path[N] return s end + # Peek at the next step of the path fun peek_step: N do return nodes[at] + # Are we at the end of this path? fun at_end_of_path: Bool do return at >= nodes.length end # Context related to an evocation of pathfinding -class PathContext +abstract class PathContext + serialize + + # Type of the nodes in `graph` type N: Node + + # Type of the links in `graph` type L: Link + # Graph to which is associated `self` var graph: Graph[N, L] # Worst cost of all the link's costs @@ -273,6 +352,7 @@ class PathContext # Heuristic fun heuristic_cost(a, b: N): Int is abstract + # The worst cost suggested by the heuristic fun worst_heuristic_cost: Int is abstract end @@ -284,6 +364,7 @@ end # Warning: A* is not optimize for such a case class ConstantPathContext super PathContext + serialize redef fun worst_cost do return 1 redef fun cost(l) do return 1 @@ -292,12 +373,14 @@ class ConstantPathContext redef fun worst_heuristic_cost do return 0 end +# A `PathContext` for graphs with `WeightedLink` class WeightedPathContext super PathContext + serialize redef type L: WeightedLink - init(graph: Graph[N, L]) + init do super @@ -309,7 +392,7 @@ class WeightedPathContext self.worst_cost = worst_cost end - redef var worst_cost: Int + redef var worst_cost is noinit redef fun cost(l) do return l.weight @@ -319,21 +402,19 @@ class WeightedPathContext redef fun worst_heuristic_cost do return 0 end +# A `Link` with a `weight` class WeightedLink super Link + serialize + # The `weight`, or cost, of this link var weight: Int - - init(graph: Graph[N, L], from, to: N, weight: Int) - do - super - - self.weight = weight - end end # Advanced path conditions with customizable accept states -class TargetCondition[N: Node] +abstract class TargetCondition[N: Node] + serialize + # Should the pathfinding accept `node` as a goal? fun accept(node: N): Bool is abstract