Merge remote-tracking branch 'alexis/game_framework'
authorJean Privat <jean@pryen.org>
Thu, 14 Nov 2013 12:02:26 +0000 (07:02 -0500)
committerJean Privat <jean@pryen.org>
Thu, 14 Nov 2013 12:02:26 +0000 (07:02 -0500)
lib/a_star.nit [new file with mode: 0644]
lib/bucketed_game.nit [new file with mode: 0644]
lib/mnit_linux/linux_opengles1.nit.args
lib/standard/collection/range.nit
lib/standard/math.nit
tests/sav/test_a_star.res [new file with mode: 0644]
tests/sav/test_for_times.sav [new file with mode: 0644]
tests/test_a_star.nit [new file with mode: 0644]
tests/test_for_times.nit [new file with mode: 0644]

diff --git a/lib/a_star.nit b/lib/a_star.nit
new file mode 100644 (file)
index 0000000..c0c0962
--- /dev/null
@@ -0,0 +1,367 @@
+# This file is part of NIT (http://www.nitlanguage.org).
+#
+# Copyright 2011-2013 Alexis Laferrière <alexis.laf@xymus.net>
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+# Services related to pathfinding of graphs using A*
+# A single graph may have different properties according to the `PathContext` used
+#
+# Usage:
+#
+#    # Weighted graph (letters are nodes, digits are weights):
+#    #
+#    #     a -2- b
+#    #    /     /
+#    #   3     1
+#    #  /     /
+#    # c -3- d -8- e
+#    #
+#    var graph = new Graph[Node,WeigthedLink[Node]]
+#
+#    var na = new Node(graph)
+#    var nb = new Node(graph)
+#    var nc = new Node(graph)
+#    var nd = new Node(graph)
+#    var ne = new Node(graph)
+#
+#    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(graph)
+#
+#    var path = na.path_to(ne, 100, context)
+#    assert path != null else print "No possible path"
+#
+#    assert path.step == nb
+#    assert path.step == nd
+#    assert path.step == ne
+#    assert path.at_end_of_path
+module a_star
+
+redef class Object
+       protected fun debug_a_star: Bool do return false
+       private fun debug(msg: String) do if debug_a_star then
+               stderr.write "a_star debug: {msg}\n"
+       end
+end
+
+# General graph node
+class Node
+       type N: Node
+
+       # parent graph
+       var graph: Graph[N, Link]
+
+       init(graph: Graph[N, Link])
+       do
+               self.graph = graph
+               graph.add_node(self)
+       end
+
+       # adjacent nodes
+       var links: Set[Link] = new HashSet[Link]
+
+       # used to check if node has been searched in one pathfinding
+       private var last_pathfinding_evocation: Int = 0
+
+       # cost up to in current evocation
+       # lifetime limited to evocation of path_to
+       private var best_cost_up_to: Int = 0
+
+       # source node
+       # lifetime limited to evocation of path_to
+       private var best_source: nullable N = null
+
+       # is in frontier or buckets
+       # lifetime limited to evocation of path_to
+       private var open: Bool = false
+
+
+       # Main functionnality, returns path from `self` to `dest`
+       fun path_to(dest: Node, max_cost: Int, context: PathContext): nullable Path[N]
+       do
+               var cost = 0
+
+               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
+                       buckets.add(new List[Node])
+               end
+
+               graph.pathfinding_current_evocation += 1
+
+               # open source node
+               buckets[0].add(self)
+               open = true
+               self.last_pathfinding_evocation = graph.pathfinding_current_evocation
+               self.best_cost_up_to = 0
+
+               loop
+                       var frontier_node: nullable Node = null
+
+                       var bucket_searched: Int = 0
+
+                       # find next valid node in frontier/buckets
+                       loop
+                               var current_bucket = buckets[cost % nbr_buckets]
+
+                               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
+                               else # found a node
+                                       debug "c {cost}"
+                                       frontier_node = current_bucket.pop
+
+                                       if frontier_node.open then break
+                               end
+                       end
+
+                       # no path possible
+                       if frontier_node == null then
+                               return null
+
+                       # at destination
+                       else if frontier_node == dest then
+                               debug "picked {frontier_node}, is destination"
+
+                               var path = new Path[N](cost)
+
+                               while frontier_node != self do
+                                       path.nodes.unshift(frontier_node)
+                                       frontier_node = frontier_node.best_source.as(not null)
+                               end
+
+                               return path
+
+                       # adds all next nodes to frontier/buckets
+                       else
+                               frontier_node.open = false
+
+                               debug "w exploring adjacents of {frontier_node}"
+
+                               for link in frontier_node.links do
+                                       var peek_node = link.to
+                                       debug "v {context.is_blocked(link)} {peek_node.last_pathfinding_evocation != graph.pathfinding_current_evocation} {peek_node.best_cost_up_to > frontier_node.best_cost_up_to + context.cost(link)}, {peek_node.best_cost_up_to} > {frontier_node.best_cost_up_to} + {context.cost(link)}"
+                                       if not context.is_blocked(link) and
+                                        (peek_node.last_pathfinding_evocation != graph.pathfinding_current_evocation or
+                                          (peek_node.open and
+                                            peek_node.best_cost_up_to > cost + context.cost(link)))
+                                       then
+
+                                               peek_node.open = true
+                                               peek_node.last_pathfinding_evocation = graph.pathfinding_current_evocation
+                                               peek_node.best_cost_up_to = cost + context.cost(link)
+                                               peek_node.best_source = frontier_node
+
+                                               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 {est_cost} -> {est_cost % nbr_buckets} {at_bucket.hash}, {cost}+{context.cost(link)}"
+                                       end
+                               end
+                       end
+               end
+       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
+
+       var graph: Graph[N, L]
+
+       var from: N
+       var to: N
+
+       init(graph: Graph[N, L], from, to: N)
+       do
+               self.graph = graph
+               self.from = from
+               self.to = to
+
+               graph.add_link(self)
+       end
+end
+
+# General graph
+class Graph[N: Node, L: Link]
+       var nodes: Set[N] = new HashSet[N]
+       var links: Set[L] = new HashSet[L]
+
+       fun add_node(node: N): N
+       do
+               nodes.add(node)
+
+               return node
+       end
+
+       fun add_link(link: L): L
+       do
+               links.add(link)
+
+               link.from.links.add(link)
+
+               return link
+       end
+
+       # used to check if nodes have been searched in one pathfinding
+       var pathfinding_current_evocation: Int = 0
+end
+
+# Result from pathfinding, a walkable path
+class Path[N]
+
+       var total_cost: Int
+
+       var nodes = new List[N]
+
+       init (cost: Int) do total_cost = cost
+
+       var at: Int = 0
+       fun step: N
+       do
+               assert nodes.length >= at else print "a_star::Path::step failed, is at_end_of_path"
+
+               var s = nodes[at]
+               at += 1
+
+               return s
+       end
+
+       fun peek_step: N do return nodes[at]
+
+       fun at_end_of_path: Bool do return at >= nodes.length
+end
+
+# Context related to an evocation of pathfinding
+class PathContext
+       type N: Node
+       type L: Link
+
+       var graph: Graph[N, L]
+
+       # Worst cost of all the link's costs
+       fun worst_cost: Int is abstract
+
+       # Get cost of a link
+       fun cost(link: L): Int is abstract
+
+       # Is that link blocked?
+       fun is_blocked(link: L): Bool is abstract
+
+       # Heuristic
+       fun heuristic_cost(a, b: N): Int is abstract
+
+       fun worst_heuristic_cost: Int is abstract
+end
+
+#
+### Additionnal classes, may be useful
+#
+
+# Simple context with constant cost on each links
+# Warning: A* is not optimize for such a case
+class ConstantPathContext
+       super PathContext
+
+       redef fun worst_cost do return 1
+       redef fun cost(l) do return 1
+       redef fun is_blocked(l) do return false
+       redef fun heuristic_cost(a, b) do return 0
+       redef fun worst_heuristic_cost do return 0
+end
+
+class WeightedPathContext
+       super PathContext
+
+       redef type L: WeightedLink
+
+       init(graph: Graph[N, L])
+       do
+               super
+
+               var worst_cost = 0
+               for l in graph.links do
+                       var cost = l.weight
+                       if cost >= worst_cost then worst_cost = cost + 1
+               end
+               self.worst_cost = worst_cost
+       end
+
+       redef var worst_cost: Int
+
+       redef fun cost(l) do
+               return l.weight
+       end
+       redef fun is_blocked(l) do return false
+       redef fun heuristic_cost(a, b) do return 0
+       redef fun worst_heuristic_cost do return 0
+end
+
+class WeightedLink
+       super Link
+
+       var weight: Int
+
+       init(graph: Graph[N, L], from, to: N, weight: Int)
+       do
+               super
+
+               self.weight = weight
+       end
+end
diff --git a/lib/bucketed_game.nit b/lib/bucketed_game.nit
new file mode 100644 (file)
index 0000000..409b549
--- /dev/null
@@ -0,0 +1,171 @@
+# This file is part of NIT (http://www.nitlanguage.org).
+#
+# Copyright 2011-2013 Alexis Laferrière <alexis.laf@xymus.net>
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+# Provides basic game logic utilities using buckets to coordinate and
+# optimize actions on game turn ends. Supports both action at each
+# end of turn as well as actions on some end of turns.
+#
+# Allows for fast support of a large number of entities with rare actions,
+# such as a forest with many individual trees.
+module bucketed_game
+
+# Something acting on the game
+class Turnable[G: Game]
+       fun do_turn(turn: GameTurn[G]) is abstract
+end
+
+# Something acting on the game from time to time
+class Bucketable[G: Game]
+       super Turnable[G]
+       private var act_at: Int = 0
+end
+
+# Optiomized organization of `Bucketable` instances
+class Buckets[G: Game]
+       super Turnable[G]
+       type BUCKET: HashSet[Bucketable[G]]
+
+       private var buckets: Array[BUCKET]
+
+       private var next_bucket: nullable BUCKET = null
+       private var current_bucket_key: Int = -1
+
+       init
+       do
+               var n_buckets = 100
+               buckets = new Array[BUCKET].with_capacity(n_buckets)
+
+               for b in [0 .. n_buckets [do
+                       buckets[b] = new HashSet[Bucketable[G]]
+               end
+       end
+
+       fun add_at(e: Bucketable[G], at_tick: Int)
+       do
+               var at_key = key_for_tick(at_tick)
+
+               if at_key == current_bucket_key then
+                       next_bucket.as(not null).add(e)
+               else
+                       buckets[at_key].add(e)
+               end
+
+               e.act_at = at_tick
+       end
+
+       private fun key_for_tick(at_tick: Int): Int
+       do
+               return at_tick % buckets.length
+       end
+
+       redef fun do_turn(turn: GameTurn[G])
+       do
+               current_bucket_key = key_for_tick(turn.tick)
+               var current_bucket = buckets[current_bucket_key]
+
+               next_bucket = new HashSet[Bucketable[G]]
+
+               for e in current_bucket do
+                       if e.act_at == turn.tick then
+                               e.do_turn(turn)
+                       else if e.act_at > turn.tick and
+                               key_for_tick(e.act_at) == current_bucket_key
+                       then
+                               next_bucket.as(not null).add(e)
+                       end
+               end
+
+               buckets[current_bucket_key] = next_bucket.as(not null)
+       end
+end
+
+# Game related event
+interface GameEvent
+       fun apply( game : ThinGame ) is abstract
+end
+
+# Event raised at the first turn
+class FirstTurnEvent
+       super GameEvent
+end
+
+# Game logic on the client
+class ThinGame
+       var tick: Int protected writable = 0
+end
+
+# Game turn on the client
+class ThinGameTurn[G: ThinGame]
+       var tick: Int protected writable = 0
+
+       var events: List[GameEvent] protected writable = new List[GameEvent]
+
+       init (t: Int) do tick = t
+end
+
+# Game turn on the full logic
+class GameTurn[G: Game]
+       super ThinGameTurn[G]
+       var game: G
+
+       init (g: G)
+       do
+               super(g.tick)
+               game = g
+       end
+
+       fun act_next(e: Bucketable[G])
+       do
+               game.buckets.add_at(e, tick + 1)
+       end
+
+       fun act_in(e: Bucketable[G], t: Int)
+       do
+               game.buckets.add_at(e, tick + t)
+       end
+
+       fun add_event( event : GameEvent )
+       do
+               event.apply( game )
+               events.add( event )
+       end
+end
+
+# Full game logic
+class Game
+       super ThinGame
+       type G: Game
+
+       var buckets: Buckets[G] = new Buckets[G]
+
+       init do end
+
+       fun do_turn: GameTurn[G]
+       do
+               var turn = new GameTurn[G](self)
+
+               do_pre_turn(turn)
+               buckets.do_turn(turn)
+               do_post_turn(turn)
+
+               tick += 1
+
+               return turn
+       end
+
+       fun do_pre_turn(turn: GameTurn[G]) do end
+       fun do_post_turn(turn: GameTurn[G]) do end
+end
index f54a1ce..938ee9a 100644 (file)
@@ -1 +1 @@
---cc-lib-name EGL --cc-lib-name GLESv1_CM
+--cc-lib-name EGL --cc-lib-name GLESv1_CM --cc-lib-name X11
index f356c6f..1b4d5bb 100644 (file)
@@ -100,3 +100,11 @@ class IteratorRange[E: Discrete]
                _item = r.first
        end
 end
+
+redef class Discrete
+       # Returns the range from 0 to `self-1`, is used to do:
+       #
+       #    for i in 3.times do print "Cool"
+       #    for i in 100.times do print "{i}/100"
+       fun times: Range[OTHER] do return new Range[OTHER](0, self-1)
+end
index a9a0c89..eaaf2e6 100644 (file)
@@ -21,6 +21,9 @@ redef class Int
        fun bin_and(i: Int): Int is extern "kernel_Int_Int_binand_0"
        fun bin_or(i: Int): Int is extern "kernel_Int_Int_binor_0"
        fun bin_xor(i: Int): Int is extern "kernel_Int_Int_binxor_0"
+       fun sqrt : Int is extern `{ return sqrtl(recv); `}
+       fun sin : Int is extern `{ return sinl(recv); `}
+       fun cos : Int is extern `{ return cosl(recv); `}
 end
 
 redef class Float
diff --git a/tests/sav/test_a_star.res b/tests/sav/test_a_star.res
new file mode 100644 (file)
index 0000000..68d57f4
--- /dev/null
@@ -0,0 +1,9 @@
+c, d, e
+null path
+b, d, e
+null path
+b, f, g, h, i, j
+c, f
+c, a
+f, e
+b, a, c
diff --git a/tests/sav/test_for_times.sav b/tests/sav/test_for_times.sav
new file mode 100644 (file)
index 0000000..75c6ff0
--- /dev/null
@@ -0,0 +1,13 @@
+Cool
+Cool
+Cool
+0
+1
+2
+3
+4
+5
+6
+7
+8
+9
diff --git a/tests/test_a_star.nit b/tests/test_a_star.nit
new file mode 100644 (file)
index 0000000..7293d99
--- /dev/null
@@ -0,0 +1,299 @@
+module test_a_star
+
+import a_star
+
+#redef class Object
+#      redef fun debug_a_star do return true
+#end
+
+# Simple node with a name
+class NamedNode
+       super Node
+
+       redef type N: NamedNode
+
+       var name: String
+
+       init(graph: Graph[N, Link], name: String)
+       do
+               self.name = name
+               super
+       end
+
+       redef fun to_s do return "node:{name}"
+end
+
+# 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 Path[NamedNode]) do if path == null then
+       print "null path"
+else
+       var names = new Array[String]
+       while not path.at_end_of_path do
+               var step = path.step
+               names.add(step.name)
+       end
+       print names.join(", ")
+end
+
+# Graph
+#   a - b
+#  /   /
+# c - d - e
+fun case_simple
+do
+       var graph = new Graph[NamedNode, Link]
+
+       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 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(graph)
+
+       var path = na.path_to(ne, 100, context)
+       print_path(path)
+end
+
+# Graph
+#   a - b
+#  /   /
+# c - d    e
+fun case_failed
+do
+       var graph = new Graph[NamedNode,Link]
+
+       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 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(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
+fun case_weighted
+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 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(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
+fun case_weighted_too_long
+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 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(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
diff --git a/tests/test_for_times.nit b/tests/test_for_times.nit
new file mode 100644 (file)
index 0000000..81c504c
--- /dev/null
@@ -0,0 +1,4 @@
+module test_for_times
+
+for i in 3.times do print "Cool"
+for i in 10.times do print i