lib/a_star.nit

   1 # This file is part of NIT (http://www.nitlanguage.org).
   2 #
   3 # Copyright 2011-2013 Alexis Laferrière <alexis.laf@xymus.net>
   4 #
   5 # Licensed under the Apache License, Version 2.0 (the "License");
   6 # you may not use this file except in compliance with the License.
   7 # You may obtain a copy of the License at
   8 #
   9 #     http://www.apache.org/licenses/LICENSE-2.0
  10 #
  11 # Unless required by applicable law or agreed to in writing, software
  12 # distributed under the License is distributed on an "AS IS" BASIS,
  13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14 # See the License for the specific language governing permissions and
  15 # limitations under the License.
  16
  17 # A* pathfinding in graphs
  18 #
  19 # A single graph may have different properties according to the `PathContext` used
  20 #
  21 # Usage:
  22 #
  23 # ~~~
  24 # # Weighted graph (letters are nodes, digits are weights):
  25 # #
  26 # #     a -2- b
  27 # #    /     /
  28 # #   3     1
  29 # #  /     /
  30 # # c -3- d -8- e
  31 # #
  32 # var graph = new Graph[Node,WeightedLink]
  33 #
  34 # var na = new Node(graph)
  35 # var nb = new Node(graph)
  36 # var nc = new Node(graph)
  37 # var nd = new Node(graph)
  38 # var ne = new Node(graph)
  39 #
  40 # var lab = new WeightedLink(graph, na, nb, 2)
  41 # var lac = new WeightedLink(graph, na, nc, 3)
  42 # var lbd = new WeightedLink(graph, nb, nd, 1)
  43 # var lcd = new WeightedLink(graph, nc, nd, 3)
  44 # var lde = new WeightedLink(graph, nd, ne, 8)
  45 #
  46 # var context = new WeightedPathContext(graph)
  47 #
  48 # var path = na.path_to(ne, 100, context)
  49 # assert path != null else print "No possible path"
  50 #
  51 # assert path.step == nb
  52 # assert path.step == nd
  53 # assert path.step == ne
  54 # assert path.at_end_of_path
  55 # ~~~
  56 module a_star
  57
  58 import serialization
  59
  60 # General graph node
  61 class Node
  62         super Serializable
  63
  64         # Type of the others nodes in the `graph`
  65         type N: Node
  66
  67         # parent graph
  68         var graph: Graph[N, Link]
  69
  70         init
  71         do
  72                 graph.add_node(self)
  73         end
  74
  75         # adjacent nodes
  76         var links: Set[Link] = new HashSet[Link]
  77
  78         # used to check if node has been searched in one pathfinding
  79         private var last_pathfinding_evocation: Int = 0
  80
  81         # cost up to in current evocation
  82         # lifetime limited to evocation of `path_to`
  83         private var best_cost_up_to: Int = 0
  84
  85         # source node
  86         # lifetime limited to evocation of `path_to`
  87         private var best_source: nullable N = null
  88
  89         # is in frontier or buckets
  90         # lifetime limited to evocation of `path_to`
  91         private var open: Bool = false
  92
  93         # Main functionnality, returns path from `self` to `dest`
  94         fun path_to(dest: N, max_cost: Int, context: PathContext): nullable AStarPath[N]
  95         do
  96                 return path_to_alts(dest, max_cost, context, null)
  97         end
  98
  99         # Find a path to a possible `destination` or a node accepted by `alt_targets`
 100         fun path_to_alts(destination: nullable N, max_cost: Int, context: PathContext,
 101                 alt_targets: nullable TargetCondition[N]): nullable AStarPath[N]
 102         do
 103                 var cost = 0
 104
 105                 var nbr_buckets = context.worst_cost + context.worst_heuristic_cost + 1
 106                 var buckets = new Array[List[N]].with_capacity(nbr_buckets)
 107
 108                 for i in [0 .. nbr_buckets[ do
 109                         buckets.add(new List[N])
 110                 end
 111
 112                 graph.pathfinding_current_evocation += 1
 113
 114                 # open source node
 115                 buckets[0].add(self)
 116                 open = true
 117                 self.last_pathfinding_evocation = graph.pathfinding_current_evocation
 118                 self.best_cost_up_to = 0
 119
 120                 loop
 121                         var frontier_node: nullable N = null
 122
 123                         var bucket_searched = 0
 124
 125                         # find next valid node in frontier/buckets
 126                         loop
 127                                 var current_bucket = buckets[cost % nbr_buckets]
 128
 129                                 if current_bucket.is_empty then # move to next bucket
 130                                         cost += 1
 131                                         if cost > max_cost then return null
 132                                         bucket_searched += 1
 133
 134                                         if bucket_searched > nbr_buckets then break
 135                                 else # found a node
 136                                         frontier_node = current_bucket.pop
 137
 138                                         if frontier_node.open then break
 139                                 end
 140                         end
 141
 142                         # no path possible
 143                         if frontier_node == null then
 144                                 return null
 145
 146                         # at destination
 147                         else if frontier_node == destination or
 148                              (alt_targets != null and alt_targets.accept(frontier_node)) then
 149
 150                                 var path = new AStarPath[N](cost)
 151
 152                                 while frontier_node != self do
 153                                         path.nodes.unshift(frontier_node)
 154                                         frontier_node = frontier_node.best_source
 155                                         assert frontier_node != null
 156                                 end
 157
 158                                 return path
 159
 160                         # adds all next nodes to frontier/buckets
 161                         else
 162                                 frontier_node.open = false
 163
 164                                 for link in frontier_node.links do
 165                                         var peek_node = link.to
 166                                         if not context.is_blocked(link) and
 167                                          (peek_node.last_pathfinding_evocation != graph.pathfinding_current_evocation or
 168                                            (peek_node.open and
 169                                              peek_node.best_cost_up_to > cost + context.cost(link)))
 170                                         then
 171                                                 peek_node.open = true
 172                                                 peek_node.last_pathfinding_evocation = graph.pathfinding_current_evocation
 173                                                 peek_node.best_cost_up_to = cost + context.cost(link)
 174                                                 peek_node.best_source = frontier_node
 175
 176                                                 var est_cost
 177                                                 if destination != null then
 178                                                         est_cost = peek_node.best_cost_up_to + context.heuristic_cost(peek_node, destination)
 179                                                 else if alt_targets != null then
 180                                                         est_cost = peek_node.best_cost_up_to + alt_targets.heuristic_cost(peek_node, link)
 181                                                 else est_cost = 0
 182
 183                                                 var at_bucket = buckets[est_cost % nbr_buckets]
 184                                                 at_bucket.add(peek_node)
 185                                         end
 186                                 end
 187                         end
 188                 end
 189         end
 190
 191         # We customize the serialization process to avoid problems with recursive
 192         # serialization engines. These engines, such as `JsonSerializer`,
 193         # are at danger to serialize the graph as a very deep tree.
 194         # With a large graph it can cause a stack overflow.
 195         #
 196         # Instead, we serialize the nodes first and then the links.
 197         redef fun core_serialize_to(serializer)
 198         do
 199                 serializer.serialize_attribute("graph", graph)
 200         end
 201
 202         redef init from_deserializer(deserializer)
 203         do
 204                 deserializer.notify_of_creation self
 205
 206                 var graph = deserializer.deserialize_attribute("graph")
 207                 assert graph isa Graph[N, Link]
 208                 self.graph = graph
 209         end
 210 end
 211
 212 # Link between two nodes and associated to a graph
 213 class Link
 214         serialize
 215
 216         # Type of the nodes in `graph`
 217         type N: Node
 218
 219         # Type of the other links in `graph`
 220         type L: Link
 221
 222         # The graph to which belongs `self`
 223         var graph: Graph[N, L]
 224
 225         # Origin of this link
 226         var from: N
 227
 228         # Endpoint of this link
 229         var to: N
 230
 231         init
 232         do
 233                 graph.add_link(self)
 234         end
 235 end
 236
 237 # General graph
 238 class Graph[N: Node, L: Link]
 239         super Serializable
 240
 241         # Nodes in this graph
 242         var nodes: Set[N] = new HashSet[N]
 243
 244         # Links in this graph
 245         var links: Set[L] = new HashSet[L]
 246
 247         # Add a `node` to this graph
 248         fun add_node(node: N): N
 249         do
 250                 nodes.add(node)
 251
 252                 return node
 253         end
 254
 255         # Add a `link` to this graph
 256         fun add_link(link: L): L
 257         do
 258                 links.add(link)
 259
 260                 link.from.links.add(link)
 261
 262                 return link
 263         end
 264
 265         # Used to check if nodes have been searched in one pathfinding
 266         private var pathfinding_current_evocation: Int = 0
 267
 268         redef fun core_serialize_to(serializer)
 269         do
 270                 serializer.serialize_attribute("nodes", nodes)
 271                 serializer.serialize_attribute("links", links)
 272         end
 273
 274         redef init from_deserializer(deserializer)
 275         do
 276                 deserializer.notify_of_creation self
 277
 278                 var nodes = deserializer.deserialize_attribute("nodes")
 279                 assert nodes isa HashSet[N]
 280                 self.nodes = nodes
 281
 282                 var links = deserializer.deserialize_attribute("links")
 283                 assert links isa HashSet[L]
 284                 for link in links do add_link link
 285         end
 286 end
 287
 288 # Result from path finding and a walkable path
 289 class AStarPath[N]
 290         serialize
 291
 292         # Total cost of this path
 293         var total_cost: Int
 294
 295         # Nodes composing this path
 296         var nodes = new List[N]
 297
 298         private var at: Int = 0
 299
 300         # Step on the path and get the next node to travel
 301         fun step: N
 302         do
 303                 assert nodes.length >= at else print "a_star::AStarPath::step failed, is at_end_of_path"
 304
 305                 var s = nodes[at]
 306                 at += 1
 307
 308                 return s
 309         end
 310
 311         # Peek at the next step of the path
 312         fun peek_step: N do return nodes[at]
 313
 314         # Are we at the end of this path?
 315         fun at_end_of_path: Bool do return at >= nodes.length
 316 end
 317
 318 # Context related to an evocation of pathfinding
 319 abstract class PathContext
 320         serialize
 321
 322         # Type of the nodes in `graph`
 323         type N: Node
 324
 325         # Type of the links in `graph`
 326         type L: Link
 327
 328         # Graph to which is associated `self`
 329         var graph: Graph[N, L]
 330
 331         # Worst cost of all the link's costs
 332         fun worst_cost: Int is abstract
 333
 334         # Get cost of a link
 335         fun cost(link: L): Int is abstract
 336
 337         # Is that link blocked?
 338         fun is_blocked(link: L): Bool is abstract
 339
 340         # Heuristic
 341         fun heuristic_cost(a, b: N): Int is abstract
 342
 343         # The worst cost suggested by the heuristic
 344         fun worst_heuristic_cost: Int is abstract
 345 end
 346
 347 #
 348 ### Additionnal classes, may be useful
 349 #
 350
 351 # Simple context with constant cost on each links
 352 # Warning: A* is not optimize for such a case
 353 class ConstantPathContext
 354         super PathContext
 355         serialize
 356
 357         redef fun worst_cost do return 1
 358         redef fun cost(l) do return 1
 359         redef fun is_blocked(l) do return false
 360         redef fun heuristic_cost(a, b) do return 0
 361         redef fun worst_heuristic_cost do return 0
 362 end
 363
 364 # A `PathContext` for graphs with `WeightedLink`
 365 class WeightedPathContext
 366         super PathContext
 367         serialize
 368
 369         redef type L: WeightedLink
 370
 371         init
 372         do
 373                 super
 374
 375                 var worst_cost = 0
 376                 for l in graph.links do
 377                         var cost = l.weight
 378                         if cost >= worst_cost then worst_cost = cost + 1
 379                 end
 380                 self.worst_cost = worst_cost
 381         end
 382
 383         redef var worst_cost is noinit
 384
 385         redef fun cost(l) do
 386                 return l.weight
 387         end
 388         redef fun is_blocked(l) do return false
 389         redef fun heuristic_cost(a, b) do return 0
 390         redef fun worst_heuristic_cost do return 0
 391 end
 392
 393 # A `Link` with a `weight`
 394 class WeightedLink
 395         super Link
 396         serialize
 397
 398         # The `weight`, or cost, of this link
 399         var weight: Int
 400 end
 401
 402 # Advanced path conditions with customizable accept states
 403 abstract class TargetCondition[N: Node]
 404         serialize
 405
 406         # Should the pathfinding accept `node` as a goal?
 407         fun accept(node: N): Bool is abstract
 408
 409         # Approximate cost from `node` to an accept state
 410         fun heuristic_cost(node: N, link: Link): Int is abstract
 411 end