tests: fix test errors for engine nitc

[nit.git] / lib / a_star.nit

diff --git a/lib/a_star.nit b/lib/a_star.nit
index 98a905f..c0c0962 100644 (file)
--- a/lib/a_star.nit
+++ b/lib/a_star.nit
@@ -35,20 +35,21 @@
 #    var nd = new Node(graph)
 #    var ne = new Node(graph)
 #
-#    var lab = new WeigthedLink[Node](graph, na, nb, 2)
-#    var lac = new WeigthedLink[Node](graph, na, nc, 3)
-#    var lbd = new WeigthedLink[Node](graph, nb, nd, 1)
-#    var lcd = new WeigthedLink[Node](graph, nc, nd, 3)
-#    var lde = new WeigthedLink[Node](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[Node, WeigthedLink[Node]](graph)
+#    var context = new WeightedPathContext(graph)
 #
 #    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
@@ -89,21 +90,17 @@ class Node
        # lifetime limited to evocation of path_to
        private var open: Bool = false
 
-       # Heuristic, to redef
-       protected fun cost_to(other: N): Int do return 1
 
        # 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 + 1 # graph.max_heuristic_cost
+               var nbr_buckets = context.worst_cost + context.worst_heuristic_cost + 1
                var buckets = new Array[List[Node]].with_capacity(nbr_buckets)
 
-               for i in [0 .. nbr_buckets [ do
-                       var l = new List[Node]
-                       buckets.add(l)
-                       #print l.hash
+               for i in [0 .. nbr_buckets[ do
+                       buckets.add(new List[Node])
                end
 
                graph.pathfinding_current_evocation += 1
@@ -114,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
@@ -126,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
@@ -174,17 +172,15 @@ class Node
                                                peek_node.best_cost_up_to = cost + context.cost(link)
                                                peek_node.best_source = frontier_node
 
-                                               var at_bucket = buckets[(peek_node.best_cost_up_to+peek_node.cost_to(dest)) % nbr_buckets]
+                                               var est_cost = peek_node.best_cost_up_to+context.heuristic_cost(link.from, peek_node)
+                                               var at_bucket = buckets[est_cost % nbr_buckets]
                                                at_bucket.add(peek_node)
 
-                                               debug "u putting {peek_node} at {peek_node.best_cost_up_to+peek_node.cost_to(dest)} -> {(peek_node.best_cost_up_to+peek_node.cost_to(dest)) % nbr_buckets} {at_bucket.hash}, {cost}+{context.cost(link)}"
+                                               debug "u putting {peek_node} at {est_cost} -> {est_cost % nbr_buckets} {at_bucket.hash}, {cost}+{context.cost(link)}"
                                        end
                                end
                        end
                end
-
-               # costs over max
-               return null
        end
 
        # Find closes node with matching caracteristic
@@ -222,6 +218,7 @@ class Node
        end
 end
 
+# Link between two nodes and associated to a graph
 class Link
        type N: Node
        type L: Link
@@ -302,13 +299,13 @@ class PathContext
        fun worst_cost: Int is abstract
 
        # Get cost of a link
-       fun cost(link: Link): Int is abstract
+       fun cost(link: L): Int is abstract
 
        # Is that link blocked?
-       fun is_blocked(link: Link): Bool is abstract
+       fun is_blocked(link: L): Bool is abstract
 
        # Heuristic
-       fun heuristic_cost(a, b: Node): Int is abstract
+       fun heuristic_cost(a, b: N): Int is abstract
 
        fun worst_heuristic_cost: Int is abstract
 end
@@ -349,7 +346,6 @@ class WeightedPathContext
        redef var worst_cost: Int
 
        redef fun cost(l) do
-               assert l isa L
                return l.weight
        end
        redef fun is_blocked(l) do return false