tests/test_a_star.nit

   1 module test_a_star
   2
   3 import a_star
   4
   5 #redef class Object
   6 #       redef fun debug_a_star do return true
   7 #end
   8
   9 # Simple node with a name
  10 class NamedNode
  11         super Node
  12
  13         redef type N: NamedNode
  14
  15         var name: String
  16
  17         init(graph: Graph[N, Link], name: String)
  18         do
  19                 self.name = name
  20                 super
  21         end
  22
  23         redef fun to_s do return "node:{name}"
  24 end
  25
  26 # Node with a name and position
  27 class PositionedNamedNode
  28         super NamedNode
  29
  30         redef type N: PositionedNamedNode
  31
  32         var x: Int
  33         var y: Int
  34
  35         init(graph: Graph[N, Link], name: String, x, y: Int)
  36         do
  37                 super
  38
  39                 self.x = x
  40                 self.y = y
  41         end
  42
  43         redef fun to_s do return "{super}-at-({x},{y})"
  44
  45         fun dist_with(o: PositionedNamedNode): Int
  46         do
  47                 var dx = o.x - x
  48                 var dy = o.y - y
  49                 var d2 = dx*dx + dy*dy
  50                 return d2.sqrt
  51         end
  52 end
  53
  54 # Link for nodes with a position
  55 class PositionedLink
  56         super Link
  57
  58         redef type N: PositionedNamedNode
  59 end
  60
  61 # Context for a graph with positions
  62 class PositionPathContext
  63         super PathContext
  64
  65         redef type N: PositionedNamedNode
  66         redef type L: PositionedLink
  67
  68         init(graph: Graph[N,L])
  69         do
  70                 super
  71
  72                 for l in graph.links do
  73                         var this_cost = cost(l)
  74                         if this_cost > worst_cost then worst_cost = this_cost
  75                 end
  76         end
  77
  78         redef var worst_cost = 0
  79
  80         redef fun cost(link) do return link.from.dist_with(link.to)
  81
  82         redef fun is_blocked(link) do return false
  83
  84         redef fun heuristic_cost(a, b)
  85         do
  86                 var cost = a.dist_with(b)
  87                 if cost > 100 then return 100
  88                 return cost
  89         end
  90
  91         redef fun worst_heuristic_cost do return 100
  92 end
  93
  94 fun print_path(path: nullable AStarPath[NamedNode]) do if path == null then
  95         print "null path"
  96 else
  97         var names = new Array[String]
  98         while not path.at_end_of_path do
  99                 var step = path.step
 100                 names.add(step.name)
 101         end
 102         print names.join(", ")
 103 end
 104
 105 # Graph
 106 #   a - b
 107 #  /   /
 108 # c - d - e
 109 fun case_simple
 110 do
 111         var graph = new Graph[NamedNode, Link]
 112
 113         var na = new NamedNode(graph, "a")
 114         var nb = new NamedNode(graph, "b")
 115         var nc = new NamedNode(graph, "c")
 116         var nd = new NamedNode(graph, "d")
 117         var ne = new NamedNode(graph, "e")
 118
 119         var lab = new Link(graph, na, nb)
 120         var lac = new Link(graph, na, nc)
 121         var lbd = new Link(graph, nb, nd)
 122         var lcd = new Link(graph, nc, nd)
 123         var lde = new Link(graph, nd, ne)
 124
 125         var context = new ConstantPathContext(graph)
 126
 127         var path = na.path_to(ne, 100, context)
 128         print_path(path)
 129 end
 130
 131 # Graph
 132 #   a - b
 133 #  /   /
 134 # c - d    e
 135 fun case_failed
 136 do
 137         var graph = new Graph[NamedNode,Link]
 138
 139         var na = new NamedNode(graph, "a")
 140         var nb = new NamedNode(graph, "b")
 141         var nc = new NamedNode(graph, "c")
 142         var nd = new NamedNode(graph, "d")
 143         var ne = new NamedNode(graph, "e")
 144
 145         var lab = new Link(graph, na, nb)
 146         var lac = new Link(graph, na, nc)
 147         var lbd = new Link(graph, nb, nd)
 148         var lcd = new Link(graph, nc, nd)
 149
 150         var context = new ConstantPathContext(graph)
 151
 152         var path = na.path_to(ne, 100, context)
 153         print_path(path)
 154 end
 155
 156 # Weighted graph
 157 #     a -2- b
 158 #    /     /
 159 #   3     1
 160 #  /     /
 161 # c -3- d -8- e
 162 fun case_weighted
 163 do
 164         var graph = new Graph[NamedNode,WeightedLink]
 165
 166         var na = new NamedNode(graph, "a")
 167         var nb = new NamedNode(graph, "b")
 168         var nc = new NamedNode(graph, "c")
 169         var nd = new NamedNode(graph, "d")
 170         var ne = new NamedNode(graph, "e")
 171
 172         var lab = new WeightedLink(graph, na, nb, 2)
 173         var lac = new WeightedLink(graph, na, nc, 3)
 174         var lbd = new WeightedLink(graph, nb, nd, 1)
 175         var lcd = new WeightedLink(graph, nc, nd, 3)
 176         var lde = new WeightedLink(graph, nd, ne, 8)
 177
 178         var context = new WeightedPathContext(graph)
 179
 180         var path = na.path_to(ne, 100, context)
 181         print_path(path)
 182 end
 183
 184 # Weighted graph
 185 #     a -2- b
 186 #    /     /
 187 #   3     1
 188 #  /     /
 189 # c -3- d -8- e
 190 fun case_weighted_too_long
 191 do
 192         var graph = new Graph[NamedNode,WeightedLink]
 193
 194         var na = new NamedNode(graph, "a")
 195         var nb = new NamedNode(graph, "b")
 196         var nc = new NamedNode(graph, "c")
 197         var nd = new NamedNode(graph, "d")
 198         var ne = new NamedNode(graph, "e")
 199
 200         var lab = new WeightedLink(graph, na, nb, 2)
 201         var lac = new WeightedLink(graph, na, nc, 3)
 202         var lbd = new WeightedLink(graph, nb, nd, 1)
 203         var lcd = new WeightedLink(graph, nc, nd, 3)
 204         var lde = new WeightedLink(graph, nd, ne, 8)
 205
 206         var context = new WeightedPathContext(graph)
 207
 208         var path = na.path_to(ne, 5, context)
 209         print_path(path)
 210 end
 211
 212 # "Big" weighted graph
 213 #
 214 #     a -2- b -1- f -1- g
 215 #    /     /       \   /
 216 #   3     1        4  1
 217 #  /     /         \ /
 218 # c -3- d -8- e -2- h -2- i -3- j
 219 #
 220 fun case_weighted_big
 221 do
 222         var graph = new Graph[NamedNode,WeightedLink]
 223
 224         var na = new NamedNode(graph, "a")
 225         var nb = new NamedNode(graph, "b")
 226         var nc = new NamedNode(graph, "c")
 227         var nd = new NamedNode(graph, "d")
 228         var ne = new NamedNode(graph, "e")
 229         var nf = new NamedNode(graph, "f")
 230         var ng = new NamedNode(graph, "g")
 231         var nh = new NamedNode(graph, "h")
 232         var ni = new NamedNode(graph, "i")
 233         var nj = new NamedNode(graph, "j")
 234
 235         var lab = new WeightedLink(graph, na, nb, 2)
 236         var lac = new WeightedLink(graph, na, nc, 3)
 237         var lbd = new WeightedLink(graph, nb, nd, 1)
 238         var lcd = new WeightedLink(graph, nc, nd, 3)
 239         var lde = new WeightedLink(graph, nd, ne, 8)
 240         var lbf = new WeightedLink(graph, nb, nf, 1)
 241         var lfg = new WeightedLink(graph, nf, ng, 1)
 242         var leh = new WeightedLink(graph, ne, nh, 2)
 243         var lhi = new WeightedLink(graph, nh, ni, 2)
 244         var lij = new WeightedLink(graph, ni, nj, 3)
 245         var lfh = new WeightedLink(graph, nf, nh, 4)
 246         var lgh = new WeightedLink(graph, ng, nh, 1)
 247
 248         var context = new WeightedPathContext(graph)
 249
 250         var path = na.path_to(nj, 100, context)
 251         print_path(path)
 252 end
 253
 254 # Double-edge graph with coordinates on nodes
 255 #
 256 # a--b--d--e
 257 #  \       |
 258 #   c------f
 259 #
 260 fun cases_with_positions_and_heuristic
 261 do
 262         var graph = new Graph[PositionedNamedNode,PositionedLink]
 263
 264         var na = new PositionedNamedNode(graph, "a", 0, 0)
 265         var nb = new PositionedNamedNode(graph, "b", 2, 0)
 266         var nc = new PositionedNamedNode(graph, "c", 2, 2)
 267         var nd = new PositionedNamedNode(graph, "d", 5, 0)
 268         var ne = new PositionedNamedNode(graph, "e", 8, 0)
 269         var nf = new PositionedNamedNode(graph, "f", 8, 2)
 270
 271         var lab = new PositionedLink(graph, na, nb)
 272         var lac = new PositionedLink(graph, na, nc)
 273         var lbd = new PositionedLink(graph, nb, nd)
 274         var lde = new PositionedLink(graph, nd, ne)
 275         var lef = new PositionedLink(graph, ne, nf)
 276         var lcf = new PositionedLink(graph, nc, nf)
 277
 278         # inverted
 279         var lba = new PositionedLink(graph, nb, na)
 280         var lca = new PositionedLink(graph, nc, na)
 281         var ldb = new PositionedLink(graph, nd, nb)
 282         var led = new PositionedLink(graph, ne, nd)
 283         var lfe = new PositionedLink(graph, nf, ne)
 284         var lfc = new PositionedLink(graph, nf, nc)
 285
 286         var context = new PositionPathContext(graph)
 287
 288         print_path(na.path_to(nf, 100, context))
 289         print_path(nf.path_to(na, 100, context))
 290         print_path(nc.path_to(ne, 100, context))
 291         print_path(nd.path_to(nc, 100, context))
 292 end
 293
 294 case_simple
 295 case_failed
 296 case_weighted
 297 case_weighted_too_long
 298 case_weighted_big
 299 cases_with_positions_and_heuristic