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)