From 609a7d051dba455b9f37bc68ab8ab15059f45fa6 Mon Sep 17 00:00:00 2001
From: Tor Andersson <tor@ccxvii.net>
Date: Fri, 3 Mar 2023 12:44:18 +0100
Subject: Withdraw moves must follow own supply lines.

Search through supply net for own lines when doing withdrawal moves.
---
 rules.js | 87 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 81 insertions(+), 6 deletions(-)

(limited to 'rules.js')

diff --git a/rules.js b/rules.js
index 0126372..dfacafe 100644
--- a/rules.js
+++ b/rules.js
@@ -1563,6 +1563,49 @@ function query_friendly_supply_network(src) {
 
 // === PATHING ===
 
+const own_seen = new Array(hexcount)
+const own_supply_line = new Array(sidecount)
+
+function search_own_supply_line(here, ssrc, sline, sdist) {
+	own_seen.fill(0)
+	own_supply_line.fill(0)
+	search_own_supply_line_rec([], here, ssrc, sline, sdist)
+}
+
+function search_own_supply_line_rec(path, here, ssrc, sline, sdist) {
+	own_seen[here] = 1
+	for (let s = 0; s < 6; ++s) {
+		let next = here + hexnext[s]
+
+		// can't go off-map
+		if (next < first_hex || next > last_hex)
+			continue
+
+		// already seen
+		if (own_seen[next])
+			continue
+
+		let side = to_side(here, next, s)
+
+		// must follow supply line
+		if (sline[side] === 0)
+			continue
+
+		// reached supply source
+		if (next === ssrc) {
+			for (let x of path)
+				own_supply_line[x] = 1
+			own_supply_line[side] = 1
+			continue
+		}
+
+		path.push(side)
+		search_own_supply_line_rec(path, next, ssrc, sline, sdist)
+		path.pop()
+	}
+	own_seen[here] = 0
+}
+
 const path_from = [ new Array(hexcount), new Array(hexcount), new Array(hexcount), null, new Array(hexcount) ]
 const path_cost = [ new Array(hexcount), new Array(hexcount), new Array(hexcount), null, new Array(hexcount) ]
 const path_valid = new Array(hexcount)
@@ -1588,28 +1631,50 @@ function search_move_retreat(start, speed) {
 	search_path_bfs(path_from[4], path_cost[4], start, 4, speed + 4, true, null, null)
 }
 
-function search_withdraw(who, bonus) {
+function search_withdraw_fast(who, bonus) {
 	let sline = unit_supply_line(who)
 	let sdist = unit_supply_distance(who)
 	let speed = unit_speed[who] + bonus
 	let start = unit_hex(who)
 
+	// This is a fast variant that allows following any supply line.
+	// Only used when iterating all withdrawal permutations to find
+	// possible valid group/regroup moves.
+
 	search_path_bfs(path_from[0], path_cost[0], start, 0, speed, false, sline, sdist)
 	search_path_bfs(path_from[1], path_cost[1], start, 1, speed + 1, false, sline, sdist)
 	search_path_bfs(path_from[2], path_cost[2], start, 2, speed + 2, false, sline, sdist)
 	search_path_bfs(path_from[4], path_cost[4], start, 4, speed + 4, false, sline, sdist)
 }
 
+function search_withdraw(who, bonus) {
+	let ssrc = unit_supply_source(who)
+	let sline = unit_supply_line(who)
+	let sdist = unit_supply_distance(who)
+	let speed = unit_speed[who] + bonus
+	let start = unit_hex(who)
+
+	search_own_supply_line(start, ssrc, sline, sdist)
+
+	search_path_bfs(path_from[0], path_cost[0], start, 0, speed, false, own_supply_line, sdist)
+	search_path_bfs(path_from[1], path_cost[1], start, 1, speed + 1, false, own_supply_line, sdist)
+	search_path_bfs(path_from[2], path_cost[2], start, 2, speed + 2, false, own_supply_line, sdist)
+	search_path_bfs(path_from[4], path_cost[4], start, 4, speed + 4, false, own_supply_line, sdist)
+}
+
 function search_withdraw_retreat(who, bonus) {
+	let ssrc = unit_supply_source(who)
 	let sline = unit_supply_line(who)
 	let sdist = unit_supply_distance(who)
 	let speed = unit_speed[who] + bonus
 	let start = unit_hex(who)
 
-	search_path_bfs(path_from[0], path_cost[0], start, 0, speed, true, sline, sdist)
-	search_path_bfs(path_from[1], path_cost[1], start, 1, speed + 1, true, sline, sdist)
-	search_path_bfs(path_from[2], path_cost[2], start, 2, speed + 2, true, sline, sdist)
-	search_path_bfs(path_from[4], path_cost[4], start, 4, speed + 4, true, sline, sdist)
+	search_own_supply_line(start, ssrc, sline, sdist)
+
+	search_path_bfs(path_from[0], path_cost[0], start, 0, speed, true, own_supply_line, sdist)
+	search_path_bfs(path_from[1], path_cost[1], start, 1, speed + 1, true, own_supply_line, sdist)
+	search_path_bfs(path_from[2], path_cost[2], start, 2, speed + 2, true, own_supply_line, sdist)
+	search_path_bfs(path_from[4], path_cost[4], start, 4, speed + 4, true, own_supply_line, sdist)
 }
 
 function search_redeploy(start) {
@@ -2182,7 +2247,17 @@ function list_withdrawal_permutations(src, maybe) {
 						let from = hexes[i]
 						let who = slowest_undisrupted_friendly_unit(from)
 						let speed = unit_speed[who]
-						search_withdraw(who, 1 + rommel1)
+
+						// NOTE: Inaccurate withdrawal search...
+						// It may yield false positives that will result
+						// in having to undo if you pick an option that
+						// required withdrawal along supply lines not
+						// one's own. This should be very unlikely.
+						if (true)
+							search_withdraw_fast(who, 1 + rommel1)
+						else
+							search_withdraw(who, 1 + rommel1)
+
 						for (let to = 0; to < hexcount; ++to)
 							if (!can_move_to(to, speed + 1 + rommel1))
 								path_valid[to] = 0
-- 
cgit v1.2.3