From: Alexis Laferrière <alexis.laf@xymus.net>
Date: Sun, 4 May 2014 13:23:23 +0000 (-0400)
Subject: lib/a_star: find alternative targets on path
X-Git-Tag: v0.6.9~13^2~2
X-Git-Url: http://nitlanguage.org

lib/a_star: find alternative targets on path

Signed-off-by: Alexis Laferrière <alexis.laf@xymus.net>
---

diff --git a/lib/a_star.nit b/lib/a_star.nit
index c6f6329..125b053 100644
--- a/lib/a_star.nit
+++ b/lib/a_star.nit
@@ -96,6 +96,13 @@ class Node
 	# Main functionnality, returns path from `self` to `dest`
 	fun path_to(dest: N, max_cost: Int, context: PathContext): nullable Path[N]
 	do
+		return path_to_alts(dest, max_cost, context, null)
+	end
+
+	# Find a path to a possible `destination` or a node accepted by `alt_targets`
+	fun path_to_alts(destination: nullable N, max_cost: Int, context: PathContext,
+		alt_targets: nullable TargetCondition[N]): nullable Path[N]
+	do
 		var cost = 0
 
 		var nbr_buckets = context.worst_cost + context.worst_heuristic_cost + 1
@@ -142,7 +149,8 @@ class Node
 				return null
 
 			# at destination
-			else if frontier_node == dest then
+			else if frontier_node == destination or
+			     (alt_targets != null and alt_targets.accept(frontier_node)) then
 				debug "picked {frontier_node}, is destination"
 
 				var path = new Path[N](cost)
@@ -168,13 +176,18 @@ class Node
 					   (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 est_cost
+						if destination != null then
+							est_cost = peek_node.best_cost_up_to + context.heuristic_cost(peek_node, destination)
+						else if alt_targets != null then
+							est_cost = peek_node.best_cost_up_to + alt_targets.heuristic_cost(peek_node, link)
+						else est_cost = 0
+
 						var at_bucket = buckets[est_cost % nbr_buckets]
 						at_bucket.add(peek_node)
 
@@ -333,3 +346,12 @@ class WeightedLink
 		self.weight = weight
 	end
 end
+
+# Advanced path conditions with customizable accept states
+class TargetCondition[N: Node]
+	# Should the pathfinding accept `node` as a goal?
+	fun accept(node: N): Bool is abstract
+
+	# Approximate cost from `node` to an accept state
+	fun heuristic_cost(node: N, link: Link): Int is abstract
+end