From a2169a1761148e8dd219f46d1b17ae356d45e18f Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= <jeremy@asynk.ch>
Date: Sun, 13 Sep 2020 17:03:44 +0200
Subject: FLNBot : build shortest paths
---
lib/colonial_twilight/fln_bot.rb | 32 +++++++++++++++++++++++++++-----
1 file changed, 27 insertions(+), 5 deletions(-)
diff --git a/lib/colonial_twilight/fln_bot.rb b/lib/colonial_twilight/fln_bot.rb
index 4964433..1b8b6a3 100644
--- a/lib/colonial_twilight/fln_bot.rb
+++ b/lib/colonial_twilight/fln_bot.rb
@@ -338,12 +338,13 @@ module ColonialTwilight
return conducted_action
end
- def _paths dst, want, &cond
+ def _paths dst, want
ws = dst.adjacents.map {|s| @board.spaces[s].wilaya }.uniq! # adjacent Wilayas allowed
spaces = @board.search{|s| s != dst and ws.include? s.wilaya } # corresponding spaces
puts "DST : #{dst}\nWilayas : #{ws.inspect}\n" + spaces.collect{|s| s.name }.join(' :: ') if @debug
- tree = build_tree dst, ws, spaces, want
+ paths, tree = build_paths dst, ws, spaces, want
tree.sort{|(x,a),(y,b)| a[:d]<=>b[:d]}.each{|k,v| puts "\t#{v[:d]} #{v[:fln][:max]}:#{v[:fln][:ok]} #{k.name} :: #{v[:adjs].map{|s| s.name}.join(' - ')}" }
+ paths.each{|p| puts p.collect{|s| s.name}.join ' -> '}
end
##### RALLY OPERATION #####
@@ -633,7 +634,7 @@ module ColonialTwilight
( (to.support? or from.country?) and (flns + to.gov_cubes + (from.country? ? @board.border_zone_track : 0)) > 3 )
end
- def build_tree dst, ws, spaces, want
+ def build_paths dst, ws, spaces, want
tree = ([dst] + spaces).inject({}) do |h,s|
# filter out adjacents : dst OR adjacent to dst OR same wilaya
a = s.adjacents.map{|n| @board.spaces[n]}.select{|a| a == dst or (spaces.include?(a) and (s.wilaya == a.wilaya or s == dst))}
@@ -654,7 +655,11 @@ module ColonialTwilight
end
end
end
- # filter out wilayas that have no eligible FLN
+ # filter_out dst, ws, tree
+ build_shortest_paths tree
+ end
+
+ def filter_out dst, ws, tree
ws.each do |w|
h = tree.select{|s,h| s != dst and s.wilaya == w}
next if h.inject(false) {|b,(s,h)| b||h[:fln][:ok]}
@@ -663,7 +668,24 @@ module ColonialTwilight
tree[dst][:adjs].delete s
}
end
- tree
+ end
+
+ def build_shortest_paths tree
+ paths = []
+ def dfs s, tree, paths, path
+ l = tree[s][:adjs].sort{|a,b| tree[a][:d] <=> tree[b][:d]}
+ d = tree[l[0]][:d]
+ if d == 0
+ paths << (path << l[0])
+ else
+ l.each do |a|
+ break if tree[a][:d] > d
+ dfs a, tree, paths, path.clone << a
+ end
+ end
+ end
+ tree.select{|k,v| v[:fln][:ok]}.each{|k,v| dfs k, tree, paths, [k] }
+ [paths, tree]
end
def can_march_from s, want, with={}
--
cgit v1.1-2-g2b99