X-Git-Url: http://nitlanguage.org diff --git a/tests/test_a_star.nit b/tests/test_a_star.nit index cf63598..25936f4 100644 --- a/tests/test_a_star.nit +++ b/tests/test_a_star.nit @@ -6,14 +6,15 @@ import a_star # redef fun debug_a_star do return true #end +# Simple node with a name class NamedNode super Node - redef type E: NamedNode + redef type N: NamedNode var name: String - init(graph: Graph[E, Link[E]], name: String) + init(graph: Graph[N, Link], name: String) do self.name = name super @@ -22,7 +23,75 @@ class NamedNode redef fun to_s do return "node:{name}" end -fun print_path(path: nullable Path[NamedNode]) do if path == null then +# Node with a name and position +class PositionedNamedNode + super NamedNode + + redef type N: PositionedNamedNode + + var x: Int + var y: Int + + init(graph: Graph[N, Link], name: String, x, y: Int) + do + super + + self.x = x + self.y = y + end + + redef fun to_s do return "{super}-at-({x},{y})" + + fun dist_with(o: PositionedNamedNode): Int + do + var dx = o.x - x + var dy = o.y - y + var d2 = dx*dx + dy*dy + return d2.sqrt + end +end + +# Link for nodes with a position +class PositionedLink + super Link + + redef type N: PositionedNamedNode +end + +# Context for a graph with positions +class PositionPathContext + super PathContext + + redef type N: PositionedNamedNode + redef type L: PositionedLink + + init(graph: Graph[N,L]) + do + super + + for l in graph.links do + var this_cost = cost(l) + if this_cost > worst_cost then worst_cost = this_cost + end + end + + redef var worst_cost = 0 + + redef fun cost(link) do return link.from.dist_with(link.to) + + redef fun is_blocked(link) do return false + + redef fun heuristic_cost(a, b) + do + var cost = a.dist_with(b) + if cost > 100 then return 100 + return cost + end + + redef fun worst_heuristic_cost do return 100 +end + +fun print_path(path: nullable AStarPath[NamedNode]) do if path == null then print "null path" else var names = new Array[String] @@ -39,7 +108,7 @@ end # c - d - e fun case_simple do - var graph = new Graph[NamedNode,Link[NamedNode]] + var graph = new Graph[NamedNode, Link] var na = new NamedNode(graph, "a") var nb = new NamedNode(graph, "b") @@ -47,13 +116,13 @@ do var nd = new NamedNode(graph, "d") var ne = new NamedNode(graph, "e") - var lab = new Link[NamedNode](graph, na, nb) - var lac = new Link[NamedNode](graph, na, nc) - var lbd = new Link[NamedNode](graph, nb, nd) - var lcd = new Link[NamedNode](graph, nc, nd) - var lde = new Link[NamedNode](graph, nd, ne) + var lab = new Link(graph, na, nb) + var lac = new Link(graph, na, nc) + var lbd = new Link(graph, nb, nd) + var lcd = new Link(graph, nc, nd) + var lde = new Link(graph, nd, ne) - var context = new ConstantPathContext[NamedNode, Link[NamedNode]](graph) + var context = new ConstantPathContext(graph) var path = na.path_to(ne, 100, context) print_path(path) @@ -65,7 +134,7 @@ end # c - d e fun case_failed do - var graph = new Graph[NamedNode,Link[NamedNode]] + var graph = new Graph[NamedNode,Link] var na = new NamedNode(graph, "a") var nb = new NamedNode(graph, "b") @@ -73,24 +142,26 @@ do var nd = new NamedNode(graph, "d") var ne = new NamedNode(graph, "e") - var lab = new Link[NamedNode](graph, na, nb) - var lac = new Link[NamedNode](graph, na, nc) - var lbd = new Link[NamedNode](graph, nb, nd) - var lcd = new Link[NamedNode](graph, nc, nd) + var lab = new Link(graph, na, nb) + var lac = new Link(graph, na, nc) + var lbd = new Link(graph, nb, nd) + var lcd = new Link(graph, nc, nd) - var context = new ConstantPathContext[NamedNode, Link[NamedNode]](graph) + var context = new ConstantPathContext(graph) var path = na.path_to(ne, 100, context) print_path(path) end # Weighted graph -# a -2 b -# /3 /1 -# c -3 d -8 e +# a -2- b +# / / +# 3 1 +# / / +# c -3- d -8- e fun case_weighted do - var graph = new Graph[NamedNode,WeigthedLink[NamedNode]] + var graph = new Graph[NamedNode,WeightedLink] var na = new NamedNode(graph, "a") var nb = new NamedNode(graph, "b") @@ -98,25 +169,27 @@ do var nd = new NamedNode(graph, "d") var ne = new NamedNode(graph, "e") - var lab = new WeigthedLink[NamedNode](graph, na, nb, 2) - var lac = new WeigthedLink[NamedNode](graph, na, nc, 3) - var lbd = new WeigthedLink[NamedNode](graph, nb, nd, 1) - var lcd = new WeigthedLink[NamedNode](graph, nc, nd, 3) - var lde = new WeigthedLink[NamedNode](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[NamedNode, WeigthedLink[NamedNode]](graph) + var context = new WeightedPathContext(graph) var path = na.path_to(ne, 100, context) print_path(path) end # Weighted graph -# a -2 b -# /3 /1 -# c -3 d -8 e +# a -2- b +# / / +# 3 1 +# / / +# c -3- d -8- e fun case_weighted_too_long do - var graph = new Graph[NamedNode,WeigthedLink[NamedNode]] + var graph = new Graph[NamedNode,WeightedLink] var na = new NamedNode(graph, "a") var nb = new NamedNode(graph, "b") @@ -124,19 +197,103 @@ do var nd = new NamedNode(graph, "d") var ne = new NamedNode(graph, "e") - var lab = new WeigthedLink[NamedNode](graph, na, nb, 2) - var lac = new WeigthedLink[NamedNode](graph, na, nc, 3) - var lbd = new WeigthedLink[NamedNode](graph, nb, nd, 1) - var lcd = new WeigthedLink[NamedNode](graph, nc, nd, 3) - var lde = new WeigthedLink[NamedNode](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[NamedNode, WeigthedLink[NamedNode]](graph) + var context = new WeightedPathContext(graph) var path = na.path_to(ne, 5, context) print_path(path) end +# "Big" weighted graph +# +# a -2- b -1- f -1- g +# / / \ / +# 3 1 4 1 +# / / \ / +# c -3- d -8- e -2- h -2- i -3- j +# +fun case_weighted_big +do + var graph = new Graph[NamedNode,WeightedLink] + + var na = new NamedNode(graph, "a") + var nb = new NamedNode(graph, "b") + var nc = new NamedNode(graph, "c") + var nd = new NamedNode(graph, "d") + var ne = new NamedNode(graph, "e") + var nf = new NamedNode(graph, "f") + var ng = new NamedNode(graph, "g") + var nh = new NamedNode(graph, "h") + var ni = new NamedNode(graph, "i") + var nj = new NamedNode(graph, "j") + + 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 lbf = new WeightedLink(graph, nb, nf, 1) + var lfg = new WeightedLink(graph, nf, ng, 1) + var leh = new WeightedLink(graph, ne, nh, 2) + var lhi = new WeightedLink(graph, nh, ni, 2) + var lij = new WeightedLink(graph, ni, nj, 3) + var lfh = new WeightedLink(graph, nf, nh, 4) + var lgh = new WeightedLink(graph, ng, nh, 1) + + var context = new WeightedPathContext(graph) + + var path = na.path_to(nj, 100, context) + print_path(path) +end + +# Double-edge graph with coordinates on nodes +# +# a--b--d--e +# \ | +# c------f +# +fun cases_with_positions_and_heuristic +do + var graph = new Graph[PositionedNamedNode,PositionedLink] + + var na = new PositionedNamedNode(graph, "a", 0, 0) + var nb = new PositionedNamedNode(graph, "b", 2, 0) + var nc = new PositionedNamedNode(graph, "c", 2, 2) + var nd = new PositionedNamedNode(graph, "d", 5, 0) + var ne = new PositionedNamedNode(graph, "e", 8, 0) + var nf = new PositionedNamedNode(graph, "f", 8, 2) + + var lab = new PositionedLink(graph, na, nb) + var lac = new PositionedLink(graph, na, nc) + var lbd = new PositionedLink(graph, nb, nd) + var lde = new PositionedLink(graph, nd, ne) + var lef = new PositionedLink(graph, ne, nf) + var lcf = new PositionedLink(graph, nc, nf) + + # inverted + var lba = new PositionedLink(graph, nb, na) + var lca = new PositionedLink(graph, nc, na) + var ldb = new PositionedLink(graph, nd, nb) + var led = new PositionedLink(graph, ne, nd) + var lfe = new PositionedLink(graph, nf, ne) + var lfc = new PositionedLink(graph, nf, nc) + + var context = new PositionPathContext(graph) + + print_path(na.path_to(nf, 100, context)) + print_path(nf.path_to(na, 100, context)) + print_path(nc.path_to(ne, 100, context)) + print_path(nd.path_to(nc, 100, context)) +end + case_simple case_failed case_weighted case_weighted_too_long +case_weighted_big +cases_with_positions_and_heuristic