1 # This file is part of NIT (http://www.nitlanguage.org).
3 # Copyright 2011-2013 Alexis Laferrière <alexis.laf@xymus.net>
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
9 # http://www.apache.org/licenses/LICENSE-2.0
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.
17 # A* pathfinding in graphs
19 # A single graph may have different properties according to the `PathContext` used
24 # # Weighted graph (letters are nodes, digits are weights):
32 # var graph = new Graph[Node,WeightedLink]
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)
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)
46 # var context = new WeightedPathContext(graph)
48 # var path = na.path_to(ne, 100, context)
49 # assert path != null else print "No possible path"
51 # assert path.step == nb
52 # assert path.step == nd
53 # assert path.step == ne
54 # assert path.at_end_of_path
64 # Type of the others nodes in the `graph`
68 var graph
: Graph[N
, Link]
76 var links
: Set[Link] = new HashSet[Link]
78 # used to check if node has been searched in one pathfinding
79 private var last_pathfinding_evocation
: Int = 0
81 # cost up to in current evocation
82 # lifetime limited to evocation of `path_to`
83 private var best_cost_up_to
: Int = 0
86 # lifetime limited to evocation of `path_to`
87 private var best_source
: nullable N
= null
89 # is in frontier or buckets
90 # lifetime limited to evocation of `path_to`
91 private var open
: Bool = false
93 # Main functionality, returns path from `self` to `dest`
94 fun path_to
(dest
: N
, max_cost
: Int, context
: PathContext): nullable AStarPath[N
]
96 return path_to_alts
(dest
, max_cost
, context
, null)
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
]
105 var nbr_buckets
= context
.worst_cost
+ context
.worst_heuristic_cost
+ 1
106 var buckets
= new Array[List[N
]].with_capacity
(nbr_buckets
)
108 for i
in [0 .. nbr_buckets
[ do
109 buckets
.add
(new List[N
])
112 graph
.pathfinding_current_evocation
+= 1
117 self.last_pathfinding_evocation
= graph
.pathfinding_current_evocation
118 self.best_cost_up_to
= 0
121 var frontier_node
: nullable N
= null
123 var bucket_searched
= 0
125 # find next valid node in frontier/buckets
127 var current_bucket
= buckets
[cost
% nbr_buckets
]
129 if current_bucket
.is_empty
then # move to next bucket
131 if cost
> max_cost
then return null
134 if bucket_searched
> nbr_buckets
then break
136 frontier_node
= current_bucket
.pop
138 if frontier_node
.open
then break
143 if frontier_node
== null then
147 else if frontier_node
== destination
or
148 (alt_targets
!= null and alt_targets
.accept
(frontier_node
)) then
150 var path
= new AStarPath[N
](cost
)
152 while frontier_node
!= self do
153 path
.nodes
.unshift
(frontier_node
)
154 frontier_node
= frontier_node
.best_source
155 assert frontier_node
!= null
160 # adds all next nodes to frontier/buckets
162 frontier_node
.open
= false
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
169 peek_node
.best_cost_up_to
> cost
+ context
.cost
(link
)))
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
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
)
183 var at_bucket
= buckets
[est_cost
% nbr_buckets
]
184 at_bucket
.add
(peek_node
)
191 # Find the closest node accepted by `cond` under `max_cost`
192 fun find_closest
(max_cost
: Int, context
: PathContext, cond
: nullable TargetCondition[N
]): nullable N
194 var path
= path_to_alts
(null, max_cost
, context
, cond
)
195 if path
== null then return null
196 return path
.nodes
.last
199 # We customize the serialization process to avoid problems with recursive
200 # serialization engines. These engines, such as `JsonSerializer`,
201 # are at danger to serialize the graph as a very deep tree.
202 # With a large graph it can cause a stack overflow.
204 # Instead, we serialize the nodes first and then the links.
205 redef fun core_serialize_to
(serializer
)
207 serializer
.serialize_attribute
("graph", graph
)
210 redef init from_deserializer
(deserializer
)
212 deserializer
.notify_of_creation
self
214 var graph
= deserializer
.deserialize_attribute
("graph", (new GetName[Graph[N
, Link]]).to_s
)
215 if not graph
isa Graph[N
, Link] then graph
= new Graph[N
, Link]
220 # Link between two nodes and associated to a graph
224 # Type of the nodes in `graph`
227 # Type of the other links in `graph`
230 # The graph to which belongs `self`
231 var graph
: Graph[N
, L
]
233 # Origin of this link
236 # Endpoint of this link
246 class Graph[N
: Node, L
: Link]
249 # Nodes in this graph
250 var nodes
= new Set[N
]
252 # Links in this graph
253 var links
= new Set[L
]
255 # Add a `node` to this graph
256 fun add_node
(node
: N
): N
263 # Add a `link` to this graph
264 fun add_link
(link
: L
): L
268 link
.from
.links
.add
(link
)
273 # Used to check if nodes have been searched in one pathfinding
274 private var pathfinding_current_evocation
: Int = 0
276 redef fun core_serialize_to
(serializer
)
278 serializer
.serialize_attribute
("nodes", nodes
)
279 serializer
.serialize_attribute
("links", links
)
282 redef init from_deserializer
(deserializer
)
284 deserializer
.notify_of_creation
self
286 var nodes
= deserializer
.deserialize_attribute
("nodes", (new GetName[Set[N
]]).to_s
)
287 if deserializer
.deserialize_attribute_missing
then
288 deserializer
.errors
.add
new AttributeMissingError(self, "nodes")
290 if nodes
isa Set[N
] then self.nodes
= nodes
292 var links
= deserializer
.deserialize_attribute
("links", (new GetName[Set[L
]]).to_s
)
293 if deserializer
.deserialize_attribute_missing
then
294 deserializer
.errors
.add
new AttributeMissingError(self, "links")
296 if links
isa Set[L
] then for link
in links
do add_link link
300 # Result from path finding and a walkable path
304 # Total cost of this path
307 # Nodes composing this path
308 var nodes
= new List[N
]
310 private var at
: Int = 0
312 # Step on the path and get the next node to travel
315 assert nodes
.length
>= at
else print
"a_star::AStarPath::step failed, is at_end_of_path"
323 # Peek at the next step of the path
324 fun peek_step
: N
do return nodes
[at
]
326 # Are we at the end of this path?
327 fun at_end_of_path
: Bool do return at
>= nodes
.length
330 # Context related to an evocation of pathfinding
331 abstract class PathContext
334 # Type of the nodes in `graph`
337 # Type of the links in `graph`
340 # Graph to which is associated `self`
341 var graph
: Graph[N
, L
]
343 # Worst cost of all the link's costs
344 fun worst_cost
: Int is abstract
347 fun cost
(link
: L
): Int is abstract
349 # Is that link blocked?
350 fun is_blocked
(link
: L
): Bool is abstract
353 fun heuristic_cost
(a
, b
: N
): Int is abstract
355 # The worst cost suggested by the heuristic
356 fun worst_heuristic_cost
: Int is abstract
360 ### Additionnal classes, may be useful
363 # Simple context with constant cost on each links
364 # Warning: A* is not optimize for such a case
365 class ConstantPathContext
369 redef fun worst_cost
do return 1
370 redef fun cost
(l
) do return 1
371 redef fun is_blocked
(l
) do return false
372 redef fun heuristic_cost
(a
, b
) do return 0
373 redef fun worst_heuristic_cost
do return 0
376 # A `PathContext` for graphs with `WeightedLink`
377 class WeightedPathContext
381 redef type L
: WeightedLink
388 for l
in graph
.links
do
390 if cost
>= worst_cost
then worst_cost
= cost
+ 1
392 self.worst_cost
= worst_cost
395 redef var worst_cost
is noinit
400 redef fun is_blocked
(l
) do return false
401 redef fun heuristic_cost
(a
, b
) do return 0
402 redef fun worst_heuristic_cost
do return 0
405 # A `Link` with a `weight`
410 # The `weight`, or cost, of this link
414 # Advanced path conditions with customizable accept states
415 abstract class TargetCondition[N
: Node]
418 # Should the pathfinding accept `node` as a goal?
419 fun accept
(node
: N
): Bool is abstract
421 # Approximate cost from `node` to an accept state
422 fun heuristic_cost
(node
: N
, link
: Link): Int is abstract