lib/a_star/tests/test_a_star.nit

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