Merge remote-tracking branch 'lucas/string_integration'

[nit.git] / lib / a_star.nit

diff --git a/lib/a_star.nit b/lib/a_star.nit
index 1f25f00..5613cec 100644 (file)
--- a/lib/a_star.nit
+++ b/lib/a_star.nit
@@ -46,9 +46,10 @@
 #    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
@@ -93,7 +94,7 @@ class Node
        # Main functionnality, returns path from `self` to `dest`
        fun path_to(dest: Node, max_cost: Int, context: PathContext): nullable Path[N]
        do
-               var cost: Int = 0
+               var cost = 0
 
                var nbr_buckets = context.worst_cost + context.worst_heuristic_cost + 1
                var buckets = new Array[List[Node]].with_capacity(nbr_buckets)
@@ -110,7 +111,7 @@ class Node
                self.last_pathfinding_evocation = graph.pathfinding_current_evocation
                self.best_cost_up_to = 0
 
-               while cost < max_cost do
+               loop
                        var frontier_node: nullable Node = null
 
                        var bucket_searched: Int = 0
@@ -122,6 +123,7 @@ class Node
                                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
@@ -179,46 +181,10 @@ class Node
                                end
                        end
                end
-
-               # costs over max
-               return null
-       end
-
-       # Find closes node with matching caracteristic
-       # TODO remove closures
-       fun find_closest(max_to_search: Int): nullable N !with(n: N): Bool
-       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
-
-                       i += 1
-                       if i > max_to_search then return null
-               end
-
-               return null
        end
 end
 
+# Link between two nodes and associated to a graph
 class Link
        type N: Node
        type L: Link