Rewrite supply tracing code.

Two passes.

First a quick breadth first forward scan to find hexes
that can be reached from the supply source at all.

Second an exhaustive recursive search from each unit to
find the actual used supply lines and hexes. This uses the
results from the first search to quickly prune impossible
paths.

This also fixes a bug where some supply chains from
highways via mixed highway, track, and trail to another
bit of highway were missed.

1 files changed, 266 insertions, 137 deletions

diff --git a/rules.js b/rules.js
index fcb889a..308bd53 100644
--- a/rules.js
+++ b/rules.js
@@ -11,10 +11,15 @@ const max = Math.max
 const min = Math.min
 const abs = Math.abs
 
-const TIMEOUT = 500
+const TIMEOUT = 250
 
 var timeout = 0
 
+function check_timeout() {
+	if (Date.now() > timeout)
+		throw new Error("timeout (too many withdrawal options)")
+}
+
 var states = {}
 var game = null
 var view = null
@@ -120,6 +125,8 @@ const INFANTRY = 1
 const ANTITANK = 2
 const ARTILLERY = 3
 
+const TRAIL = 1
+const TRACK = 2
 const HIGHWAY = 4
 
 const SUPPLY_RANGE = [ 1, 2, 3, 0, 3 ]
@@ -1133,151 +1140,273 @@ function shuffle_cards() {
 
 // === SUPPLY NETWORK ===
 
-var supply_defender, supply_defender_sides, supply_friendly, supply_enemy, supply_net, supply_line
+var supply_friendly_hexes, supply_friendly_sides, supply_friendly, supply_enemy, supply_net, supply_line
 var supply_visited = new Array(hexcount).fill(0)
-var supply_src = new Array(hexcount).fill(0)
 
+// PASS 1: Forward scan from source to compute potential supply net and valid hex side crossings.
+// Simple uniform cost search.
+
+// NOTE: trace direction is from supply to unit
 function is_supply_line_blocked(here, next, side) {
 	// impassable hexside
 	if (side_limit[side] === 0)
 		return true
 
-	// undisrupted (only) enemies may block supply lines
-	if (supply_enemy[next] > 1) {
-		if (supply_friendly[next] > 1) {
-			// into battle hex
-			// can only trace into if defender
-			if (!set_has(supply_defender, next))
-				return true
-			// can only trace into through friendly sides
-			if (!set_has(supply_defender_sides, side))
-				return true
-		} else {
-			// into enemy hex
+	// into enemy hex
+	if (supply_enemy[next] > 1 && supply_friendly[next] === 0)
+		return true
+
+	// into battle hex
+	if (is_battle_hex(next)) {
+		// through friendly hex sides
+		if (!set_has(supply_friendly_sides, side))
 			return true
-		}
 	}
 
 	// out of battle hex
-	// can only cannot trace out through friendly sides
-	if (supply_friendly[here] > 0 && supply_enemy[here] > 0) {
-		if (set_has(game.axis_hexes, here) || set_has(game.allied_hexes, here))
-			if (!set_has(supply_defender_sides, side))
-				return true
+	if (is_battle_hex(here)) {
+		// only defender (own control)
+		if (!set_has(supply_friendly_hexes, here))
+			return true
+		// through friendly hex sides
+		if (!set_has(supply_friendly_sides, side))
+			return true
 	}
 
 	return false
 }
 
-function check_timeout() {
-	if (Date.now() > timeout)
-		throw new Error("timeout (supply lines are too complicated)")
-}
+const TRACE_HIGHWAY = 0
+const TRACE_TRACK_1 = 1
+const TRACE_TRACK_2 = 2
+const TRACE_TRAIL_1 = 3
+const TRACE_STOP = 7
+const TRACE_ABORT = 8
+
+// from supply source outwards
+function forward_supply_next_move_type(here_move, road) {
+	if (here_move === TRACE_HIGHWAY) {
+		if (road === HIGHWAY) return TRACE_HIGHWAY
+		if (road === TRACK) return TRACE_TRACK_1
+		if (road === TRAIL) return TRACE_TRAIL_1
+		return TRACE_STOP
+	}
+	else if (here_move === TRACE_TRACK_1) {
+		if (road === HIGHWAY) return TRACE_TRACK_2
+		if (road === TRACK) return TRACE_TRACK_2
+		if (road === TRAIL) return TRACE_STOP
+		return TRACE_ABORT
+	}
+	else if (here_move === TRACE_TRAIL_1) {
+		if (road === HIGHWAY) return TRACE_STOP
+		if (road === TRACK) return TRACE_STOP
+		if (road === TRAIL) return TRACE_STOP
+		return TRACE_ABORT
+	}
+	else if (here_move === TRACE_TRACK_2) {
+		if (road === HIGHWAY) return TRACE_STOP
+		if (road === TRACK) return TRACE_STOP
+		if (road === TRAIL) return TRACE_ABORT
+		return TRACE_ABORT
+	}
+	return TRACE_ABORT
+}
+
+function trace_supply_network_1(start)
+{
+	supply_net[start] = 1
 
-function trace_supply_highway(here, v) {
-	if (supply_src[here])
-		return true
+	supply_visited.fill(8)
 
-	check_timeout()
+	let queue = [ (start << 3) | TRACE_HIGHWAY ]
 
-	let has_supply = false
+	while (queue.length > 0) {
+		let item = queue.shift()
+		let here = item >> 3
+		let here_move = item & 7
 
-	let save_v = supply_visited[here]
-	supply_visited[here] = v
+		for (let s = 0; s < 6; ++s) {
+			let next = here + hexnext[s]
 
-	for (let s = 0; s < 6; ++s) {
-		let next = here + hexnext[s]
+			// can't go off-map
+			if (next < first_hex || next > last_hex || !hex_exists[next])
+				continue
 
-		if (next < first_hex || next > last_hex || !hex_exists[next])
-			continue
+			let side = to_side(here, next, s)
+			if (is_supply_line_blocked(here, next, side))
+				continue
 
-		let next_v = supply_visited[next]
-		if (next_v === v || (next_v > 0 && supply_friendly[next] > 1))
-			continue
+			let next_move = forward_supply_next_move_type(here_move, side_road[side])
+			if (next_move === TRACE_ABORT)
+				continue
 
-		let side = to_side(here, next, s)
-		if (is_supply_line_blocked(here, next, side))
-			continue
+			if (side_road[side] === HIGHWAY)
+				supply_line[side] = 1
+			else
+				supply_line[side] = 1
 
-		let road = side_road[side]
-		if (road === HIGHWAY) {
-			if (supply_friendly[next] > 1) {
-				if (supply_net[next] || trace_supply_chain(next, 0, 3, v+1)) {
-					supply_line[side] = 1
-					has_supply = true
-				}
-			} else {
-				if (trace_supply_highway(next, v)) {
-					supply_line[side] = 1
-					has_supply = true
-				}
-			}
+			// already seen
+			if (next_move >= supply_visited[next])
+				continue
+
+			// new supply chain at undisrupted friendly unit
+			if (supply_friendly[next] > 1)
+				next_move = TRACE_HIGHWAY
+
+			supply_visited[next] = next_move
+			if (side_road[side] === HIGHWAY)
+				supply_net[next] = 1
+			else
+				supply_net[next] = 1
+
+			if (next_move !== TRACE_STOP)
+				queue.push((next << 3) | next_move)
 		}
 	}
+}
 
-	supply_visited[here] = save_v
+// PASS 2: Filter net to only include supply lines used by units.
+// This is a recursive search to find _all_ possible paths.
 
-	if (has_supply)
-		supply_net[here] = 1
+const BACK_HEAD = 0
+const BACK_STOP = 7
+const BACK_ABORT = 8
 
-	return has_supply
-}
+const BACK_HIGHWAY_1 = 1
+const BACK_HIGHWAY_2 = 2
+const BACK_HIGHWAY_3 = 3
 
-function trace_supply_chain(here, n, range, v) {
-	if (supply_src[here])
-		return true
+const BACK_TRACK_1 = 4
+const BACK_TRACK_2 = 5
+const BACK_TRACK_3 = BACK_STOP
 
-	check_timeout()
+const BACK_TRAIL_1 = 6
+const BACK_TRAIL_2 = BACK_STOP
+const BACK_TRAIL_3 = BACK_ABORT
 
-	let has_supply = false
+// from unit back to supply source
+// TODO - double check all!
+function backward_supply_next_move_type(here_move, road) {
+	if (here_move === BACK_HEAD) {
+		if (road === HIGHWAY) return BACK_HIGHWAY_1
+		if (road === TRACK) return BACK_TRACK_1
+		if (road === TRAIL) return BACK_TRAIL_1
+		return BACK_STOP
+	}
+	if (here_move === BACK_HIGHWAY_1) {
+		if (road === HIGHWAY) return BACK_HIGHWAY_2
+		if (road === TRACK) return BACK_TRACK_2
+		if (road === TRAIL) return BACK_TRAIL_2
+		return BACK_ABORT
+	}
+	if (here_move === BACK_HIGHWAY_2) {
+		if (road === HIGHWAY) return BACK_HIGHWAY_3
+		if (road === TRACK) return BACK_TRACK_3
+		if (road === TRAIL) return BACK_TRAIL_3
+		return BACK_ABORT
+	}
+	if (here_move === BACK_HIGHWAY_3) {
+		if (road === HIGHWAY) return BACK_HIGHWAY_3
+		if (road === TRACK) return BACK_ABORT
+		if (road === TRAIL) return BACK_ABORT
+		return BACK_ABORT
+	}
+	if (here_move === BACK_TRACK_1) {
+		if (road === HIGHWAY) return BACK_TRACK_2
+		if (road === TRACK) return BACK_TRACK_2
+		if (road === TRAIL) return BACK_TRAIL_2
+		return BACK_ABORT
+	}
+	if (here_move === BACK_TRACK_2) {
+		if (road === HIGHWAY) return BACK_TRACK_3
+		if (road === TRACK) return BACK_TRACK_3
+		if (road === TRAIL) return BACK_TRAIL_3
+		return BACK_ABORT
+	}
+	if (here_move === BACK_TRAIL_1) {
+		if (road === HIGHWAY) return BACK_TRAIL_2
+		if (road === TRACK) return BACK_TRAIL_2
+		if (road === TRAIL) return BACK_TRAIL_2
+		return BACK_ABORT
+	}
+	return BACK_ABORT
+}
 
-	let save_v = supply_visited[here]
-	supply_visited[here] = v
+function trace_unit_supply_line(path, here, here_move, ssrc) {
+	supply_visited[here] = 1
+	let supplied = false
 
 	for (let s = 0; s < 6; ++s) {
 		let next = here + hexnext[s]
 
-		if (next < first_hex || next > last_hex || !hex_exists[next])
+
+		// can't go off-map
+		if (next < first_hex || next > last_hex)
+			continue
+
+		// already seen
+		if (supply_visited[next])
 			continue
 
-		let next_v = supply_visited[next]
-		if (next_v === v || (next_v > 0 && supply_friendly[next] > 1))
+		// not part of supply network (from pass 1)
+		if (!supply_net[next])
 			continue
 
+		// supply line blocked (from pass 1)
 		let side = to_side(here, next, s)
-		if (is_supply_line_blocked(here, next, side))
+		if (!supply_line[side])
 			continue
 
-		let road = side_road[side]
-		if (road === HIGHWAY) {
-			if (trace_supply_highway(next, v)) {
-				supply_line[side] = 1
-				has_supply = true
-			}
-		}
+		let next_move = backward_supply_next_move_type(here_move, side_road[side])
+		if (next_move === TRACE_ABORT)
+			continue
 
-		let next_range = min(range, SUPPLY_RANGE[road])
-		if (n + 1 <= next_range) {
-			if (supply_friendly[next] > 1) {
-				if (supply_net[next] || trace_supply_chain(next, 0, 3, v+1)) {
-					supply_line[side] = 1
-					has_supply = true
-				}
-			} else {
-				if (trace_supply_chain(next, n + 1, next_range, v)) {
-					supply_line[side] = 1
-					has_supply = true
-				}
-			}
+		// reached supply source, or reached supplied highway (that we searched before)
+		/* if (next === ssrc) -- fallback without short cut in case the optimization below is wrong... */
+		if (next === ssrc || (hex_road[next] === HIGHWAY && supply_net[next] === 2)) {
+			for (let x of path)
+				supply_line[x] = 2
+			supply_line[side] = 2
+			supply_net[next] = 2
+			supplied = true
+			continue
 		}
+
+		// new supply chain at undisrupted friendly unit
+		if (supply_friendly[next] > 1)
+			next_move = BACK_HEAD
+
+		// on highway but cannot depart from it (traveled too far on non-highway already)!
+		if (next_move === BACK_STOP && hex_road[next] === HIGHWAY)
+			next_move = BACK_HIGHWAY_3
+
+		path.push(side)
+		if (trace_unit_supply_line(path, next, next_move, ssrc))
+			supplied = true
+		path.pop()
 	}
+	supply_visited[here] = 0
 
-	supply_visited[here] = save_v
+	if (supplied)
+		supply_net[here] = 2
 
-	if (has_supply)
-		supply_net[here] = 1
+	return supplied
+}
 
-	return has_supply
+// finalize state after pass 2
+function trace_supply_network_3() {
+	for (let i = 0; i < sidecount; ++i) {
+		if (supply_line[i] === 2)
+			supply_line[i] = 1
+		else
+			supply_line[i] = 0
+	}
+	for (let i = 0; i < hexcount; ++i) {
+		if (supply_net[i] === 2)
+			supply_net[i] = 1
+		else
+			supply_net[i] = 0
+	}
 }
 
 function all_hexes_sorted_by_distance_to_base(x) {
@@ -1292,47 +1421,55 @@ const all_hexes_for_axis_supply =  all_hexes_sorted_by_distance_to_base(EL_AGHEI
 const all_hexes_for_allied_supply =  all_hexes_sorted_by_distance_to_base(ALEXANDRIA)
 
 function trace_supply_network(start) {
+	check_timeout()
+
 	let search_order = (start === EL_AGHEILA ? all_hexes_for_axis_supply : all_hexes_for_allied_supply)
 
-	supply_visited.fill(0)
-	supply_src.fill(0)
 	supply_net.fill(0)
 	supply_line.fill(0)
 
-	supply_src[start] = 1
-	supply_net[start] = 1
+	// Pass 1: Find hexes that are in supply range.
 
-	for (let x of search_order) {
-		if (supply_friendly[x] > 0 && x !== start) {
-			if (supply_friendly[x] > 1 && supply_net[x])
-				continue
-			trace_supply_chain(x, 0, 3, 1)
-		}
-	}
+	trace_supply_network_1(start)
+
+	// Pass 2: Filter hexes that have actual supply lines from units.
+	supply_visited.fill(0)
+	let path = []
+	for (let x of search_order)
+		if (supply_friendly[x] > 0 && x !== start)
+			trace_unit_supply_line(path, x, BACK_HEAD, start)
+
+	trace_supply_network_3()
+	supply_net[start] = 1
 }
 
 function trace_fortress_network(fortress, ss) {
-	supply_visited.fill(0)
-	supply_src.fill(0)
+	check_timeout()
+
 	supply_net.fill(0)
 	supply_line.fill(0)
 
 	if (supply_enemy[fortress] > 1 && supply_friendly[fortress] <= 1)
 		return
 
-	supply_src[fortress] = 1
-	supply_net[fortress] = 1
+	// Pass 1: Find hexes that could hold units supplied by fortress.
+	trace_supply_network_1(fortress)
 
+	// Pass 2: Filter hexes that have actual supply lines from units.
+	supply_visited.fill(0)
+	let path = []
 	for (let u = 0; u < unit_count; ++u) {
 		if (unit_supply(u) === ss) {
 			let x = unit_hex(u)
 			if (is_map_hex(x) && x !== fortress) {
-				if (supply_friendly[x] > 1 && supply_net[x])
-					continue
-				trace_supply_chain(x, 0, 3, 1)
+				//if (supply_friendly[x] > 1 && supply_net[x]) continue
+				trace_unit_supply_line(path, x, BACK_HEAD, fortress)
 			}
 		}
 	}
+
+	trace_supply_network_3()
+	supply_net[fortress] = 1
 }
 
 function init_trace_supply(net, line, friendly) {
@@ -1341,31 +1478,28 @@ function init_trace_supply(net, line, friendly) {
 	supply_net = net
 	supply_line = line
 	if (friendly === AXIS) {
-		supply_defender = game.axis_hexes
-		supply_defender_sides = game.axis_sides
+		supply_friendly_hexes = game.axis_hexes
+		supply_friendly_sides = game.axis_sides
 		supply_friendly = presence_axis
 		supply_enemy = presence_allied
 	} else {
-		supply_defender = game.allied_hexes
-		supply_defender_sides = game.allied_sides
+		supply_friendly_hexes = game.allied_hexes
+		supply_friendly_sides = game.allied_sides
 		supply_friendly = presence_allied
 		supply_enemy = presence_axis
 	}
 }
 
-// For repeated supplied hex checks during deployment and fortress assignment
-function init_trace_supply_to_base_or_fortress() {
+// For supplied hex checks during deployment and fortress assignment
+function trace_supply_to_base_or_fortress(source) {
 	init_trace_supply(supply_temp_network, supply_temp_line, game.active)
 	supply_net.fill(0)
+	supply_line.fill(0)
+	trace_supply_network_1(source)
 }
 
-function can_trace_supply_to_base_or_fortress(base, from) {
-	if (from === base)
-		return true
-	supply_visited.fill(0)
-	supply_src.fill(0)
-	supply_src[base] = 1
-	return trace_supply_chain(from, 0, 3, 1, 1)
+function can_trace_supply_to_base_or_fortress(from) {
+	return supply_net[from] > 0
 }
 
 function update_axis_supply() {
@@ -2662,10 +2796,10 @@ function end_fortress_supply() {
 function list_fortress_supply_candidates(fortress) {
 	let dist = distance_to[fortress]
 	let list = []
-	init_trace_supply_to_base_or_fortress()
+	trace_supply_to_base_or_fortress(fortress)
 	for_each_friendly_unit_on_map(u => {
 		if (is_unit_unsupplied(u))
-			if (can_trace_supply_to_base_or_fortress(fortress, unit_hex(u)))
+			if (can_trace_supply_to_base_or_fortress(unit_hex(u)))
 				list.push(u)
 	})
 	list.sort((a,b) => dist[unit_hex(a)] - dist[unit_hex(b)])
@@ -6690,11 +6824,8 @@ function goto_free_deployment() {
 	game.summary = {}
 }
 
-function is_valid_deployment_hex(base, x, n) {
-	// we've already seen this hex during a previous supplied hex check this go
-	if (supply_temp_network[x] > 0)
-		return true
-	if (can_trace_supply_to_base_or_fortress(base, x))
+function is_valid_deployment_hex(x, n) {
+	if (can_trace_supply_to_base_or_fortress(x))
 		return true
 	if (x === TOBRUK)
 		return count_friendly_units_in_hex(x) + n <= 5
@@ -6722,8 +6853,7 @@ states.free_deployment = {
 			gen_action('end_deployment')
 
 		if (game.selected.length > 0) {
-			let base = friendly_base()
-			init_trace_supply_to_base_or_fortress()
+			trace_supply_to_base_or_fortress(friendly_base())
 
 			for (let x of (axis ? scenario.axis_deployment : scenario.allied_deployment)) {
 				if (!is_enemy_hex(x)) {
@@ -6731,7 +6861,7 @@ states.free_deployment = {
 					if (scenario.deployment_limit)
 						limit = scenario.deployment_limit[x] | 0
 					if (!limit || count_friendly_units_in_hex(x) + game.selected.length <= limit) {
-						if (is_valid_deployment_hex(base, x, game.selected.length))
+						if (is_valid_deployment_hex(x, game.selected.length))
 							gen_action_hex(x)
 					}
 				}
@@ -7578,7 +7708,6 @@ exports.resign = function (state, current) {
 exports.action = function (state, current, action, arg) {
 	timeout = Date.now() + TIMEOUT // don't think too long!
 	load_state(state)
-	// Object.seal(game) // XXX: don't allow adding properties
 	let S = states[game.state]
 	if (S && action in S) {
 		S[action](arg, current)