X-Git-Url: http://nitlanguage.org diff --git a/lib/a_star.nit b/lib/a_star.nit index 2f18583..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,23 +55,20 @@ # ~~~ module a_star -redef class Object - protected fun debug_a_star: Bool do return false - private fun debug(msg: String) do if debug_a_star then - stderr.write "a_star debug: {msg}\n" - end -end +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 @@ -93,8 +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 AStarPath[N] do var cost = 0 @@ -116,21 +120,19 @@ 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 var current_bucket = buckets[cost % nbr_buckets] if current_bucket.is_empty then # move to next bucket - debug "b {cost} {cost % nbr_buckets} {buckets[cost % nbr_buckets].hash}" cost += 1 if cost > max_cost then return null bucket_searched += 1 if bucket_searched > nbr_buckets then break else # found a node - debug "c {cost}" frontier_node = current_bucket.pop if frontier_node.open then break @@ -142,14 +144,15 @@ class Node return null # at destination - else if frontier_node == dest then - debug "picked {frontier_node}, is destination" + 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 @@ -158,59 +161,98 @@ class Node else frontier_node.open = false - debug "w exploring adjacents of {frontier_node}" - for link in frontier_node.links do var peek_node = link.to - debug "v {context.is_blocked(link)} {peek_node.last_pathfinding_evocation != graph.pathfinding_current_evocation} {peek_node.best_cost_up_to > frontier_node.best_cost_up_to + context.cost(link)}, {peek_node.best_cost_up_to} > {frontier_node.best_cost_up_to} + {context.cost(link)}" 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 = peek_node.best_cost_up_to+context.heuristic_cost(link.from, peek_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) - - debug "u putting {peek_node} at {est_cost} -> {est_cost % nbr_buckets} {at_bucket.hash}, {cost}+{context.cost(link)}" 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 # 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) @@ -218,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) @@ -227,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 @@ -251,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 @@ -275,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 @@ -286,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 @@ -294,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 @@ -311,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 @@ -321,15 +402,22 @@ 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 +end - init(graph: Graph[N, L], from, to: N, weight: Int) - do - super +# Advanced path conditions with customizable accept states +abstract class TargetCondition[N: Node] + serialize - self.weight = weight - end + # Should the pathfinding accept `node` as a goal? + fun accept(node: N): Bool is abstract + + # Approximate cost from `node` to an accept state + fun heuristic_cost(node: N, link: Link): Int is abstract end