X-Git-Url: http://nitlanguage.org diff --git a/lib/a_star.nit b/lib/a_star.nit index 0c81a48..7b7ce02 100644 --- a/lib/a_star.nit +++ b/lib/a_star.nit @@ -14,60 +14,61 @@ # See the License for the specific language governing permissions and # limitations under the License. -# Services related to pathfinding of graphs using A* +# A* pathfinding in graphs +# # A single graph may have different properties according to the `PathContext` used # # Usage: # -# # Weighted graph (letters are nodes, digits are weights): -# # -# # a -2- b -# # / / -# # 3 1 -# # / / -# # c -3- d -8- e -# # -# var graph = new Graph[Node,WeigthedLink[Node]] +# ~~~ +# # Weighted graph (letters are nodes, digits are weights): +# # +# # a -2- b +# # / / +# # 3 1 +# # / / +# # c -3- d -8- e +# # +# var graph = new Graph[Node,WeightedLink] # -# var na = new Node(graph) -# var nb = new Node(graph) -# var nc = new Node(graph) -# var nd = new Node(graph) -# var ne = new Node(graph) +# var na = new Node(graph) +# var nb = new Node(graph) +# var nc = new Node(graph) +# var nd = new Node(graph) +# var ne = new Node(graph) # -# var lab = new WeightedLink(graph, na, nb, 2) -# var lac = new WeightedLink(graph, na, nc, 3) -# var lbd = new WeightedLink(graph, nb, nd, 1) -# var lcd = new WeightedLink(graph, nc, nd, 3) -# var lde = new WeightedLink(graph, nd, ne, 8) +# var lab = new WeightedLink(graph, na, nb, 2) +# var lac = new WeightedLink(graph, na, nc, 3) +# var lbd = new WeightedLink(graph, nb, nd, 1) +# var lcd = new WeightedLink(graph, nc, nd, 3) +# var lde = new WeightedLink(graph, nd, ne, 8) # -# var context = new WeightedPathContext(graph) +# var context = new WeightedPathContext(graph) # -# var path = na.path_to(ne, 100, context) -# assert path != null else print "No possible path" +# var path = na.path_to(ne, 100, context) +# assert path != null else print "No possible path" # -# while not path.at_end_of_path do -# print path.step -# end +# assert path.step == nb +# assert path.step == nd +# assert path.step == ne +# assert path.at_end_of_path +# ~~~ 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 @@ -78,28 +79,34 @@ class Node private var last_pathfinding_evocation: Int = 0 # cost up to in current evocation - # lifetime limited to evocation of path_to + # lifetime limited to evocation of `path_to` private var best_cost_up_to: Int = 0 # source node - # lifetime limited to evocation of path_to + # 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 + # lifetime limited to evocation of `path_to` private var open: Bool = false - # Main functionnality, returns path from `self` to `dest` - fun path_to(dest: Node, max_cost: Int, context: PathContext): nullable Path[N] + 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[Node]].with_capacity(nbr_buckets) + var buckets = new Array[List[N]].with_capacity(nbr_buckets) for i in [0 .. nbr_buckets[ do - buckets.add(new List[Node]) + buckets.add(new List[N]) end graph.pathfinding_current_evocation += 1 @@ -111,23 +118,21 @@ class Node self.best_cost_up_to = 0 loop - var frontier_node: nullable Node = null + 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 @@ -139,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 @@ -155,92 +161,90 @@ 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 closes node with matching caracteristic - # TODO remove closures - fun find_closest(max_to_search: Int): nullable N !with(n: N): Bool + # 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 - if with(self) then return self - - var frontier = new List[N] - graph.pathfinding_current_evocation += 1 - var current_evocation = graph.pathfinding_current_evocation - - frontier.add(self) - self.last_pathfinding_evocation = current_evocation - - var i = 0 - while not frontier.is_empty do - var node = frontier.shift - - for link in node.links do - var to = link.to - if to.last_pathfinding_evocation != current_evocation then - if with(to) then return to - - frontier.add(to) - to.last_pathfinding_evocation = current_evocation - end - end + serializer.serialize_attribute("graph", graph) + end - i += 1 - if i > max_to_search then return null - end + redef init from_deserializer(deserializer) + do + deserializer.notify_of_creation self - return null + var graph = deserializer.deserialize_attribute("graph") + assert graph isa 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] + super Serializable + + # Nodes in this graph var nodes: Set[N] = new HashSet[N] + + # Links in this graph var links: Set[L] = new HashSet[L] + # Add a `node` to this graph fun add_node(node: N): N do nodes.add(node) @@ -248,6 +252,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) @@ -257,23 +262,45 @@ 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") + assert nodes isa HashSet[N] + self.nodes = nodes + + var links = deserializer.deserialize_attribute("links") + assert links isa HashSet[L] + 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 @@ -281,16 +308,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 @@ -305,6 +340,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 @@ -316,6 +352,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 @@ -324,12 +361,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 @@ -341,7 +380,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 @@ -351,15 +390,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