Optimize supply network calculations.

1 files changed, 76 insertions, 69 deletions

diff --git a/rules.js b/rules.js
index 314d7dc..ac40bde 100644
--- a/rules.js
+++ b/rules.js
@@ -112,7 +112,7 @@ const TRAIL = 1
 const TRACK = 2
 const HIGHWAY = 4
 
-const SUPPLY_RANGE = [ 1, 2, 3, -1, 3 ]
+const SUPPLY_RANGE = [ 1, 2, 3, 0, 3 ]
 
 const FIREPOWER_MATRIX = [
 	[ SF, DF, SF, TF ],
@@ -1129,6 +1129,8 @@ var supply_src = new Array(hexcount).fill(0)
 
 var trace_total
 
+var OPT = true
+
 function is_supply_line_blocked(here, next, side) {
 	// impassable hexside
 	if (side_limit[side] === 0)
@@ -1137,16 +1139,21 @@ function is_supply_line_blocked(here, next, side) {
 	// undisrupted (only) enemies may block supply lines
 	if (supply_enemy[next] > 1) {
 		if (supply_friendly[next] > 1) {
-			// battle hex, can only trace through if defender
+			// 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 {
-			// enemy hex
+			// into enemy hex
 			return true
 		}
 	}
 
-	// cannot trace through enemy hexsides
+	// out of battle hex
+	// can only cannot trace out through friendly sides
 	if (supply_friendly[here] && supply_enemy[here])
 		if (!set_has(supply_defender_sides, side))
 			return true
@@ -1175,28 +1182,32 @@ function trace_supply_highway(here, d) {
 		if (is_supply_line_blocked(here, next, side))
 			continue
 
+		if (supply_src[next]) {
+			ind(d, "!! source highway", next)
+			supply_line[side] = 1
+			has_supply = true
+			continue
+		}
+
 		let road = side_road[side]
 		if (road === HIGHWAY) {
 			if (supply_friendly[next] > 1) {
-				ind(d, "? highway head", next)
-				if (supply_src[next]) {
-					ind(d, "!! source highway chain", next)
+				//ind(d, "? highway chain head", next)
+				// XXX prevent loopback?
+				if (OPT && supply_net[next]) {
+					//console.log("already found", hex_name[next])
 					supply_line[side] = 1
 					has_supply = true
 				}
 				else
 				if (trace_supply_chain(next, d+1, 0, 3)) {
+					//console.log("found", hex_name[next])
 					ind(d, "< highway chain", here, next)
 					supply_line[side] = 1
 					has_supply = true
 				}
 			} else {
-				if (supply_src[next]) {
-					ind(d, "!! source highway", next)
-					supply_line[side] = 1
-					has_supply = true
-				}
-				else
+				//ind(d, "? highway tail", next)
 				if (trace_supply_highway(next, d+1)) {
 					ind(d, "< highway", here, next)
 					supply_line[side] = 1
@@ -1235,65 +1246,48 @@ function trace_supply_chain(here, d, n, range) {
 		if (is_supply_line_blocked(here, next, side))
 			continue
 
+		if (supply_src[next]) {
+			ind(d, "!! source chain", next)
+			supply_line[side] = 1
+			has_supply = true
+			continue
+		}
+
 		let road = side_road[side]
 		if (road === HIGHWAY) {
-			ind(d, "? chain highway", next)
+			//ind(d, "? chain highway", next)
+			if (trace_supply_highway(next, d+1)) {
+				ind(d, "< chain highway", here, next)
+				supply_line[side] = 1
+				has_supply = true
+			}
+		}
+
+		let next_range = min(range, SUPPLY_RANGE[road])
+		if (n + 1 <= next_range) {
 			if (supply_friendly[next] > 1) {
-				ind(d, "? chain highway head", next)
-				if (supply_src[next]) {
-					ind(d, "!! source highway chain head", next)
+				//ind(d, "? chain head", next)
+				// XXX prevent loopback?
+				if (OPT && supply_net[next]) {
+					//console.log("already found", hex_name[next])
 					supply_line[side] = 1
 					has_supply = true
 				}
 				else
 				if (trace_supply_chain(next, d+1, 0, 3)) {
+					//console.log("found", hex_name[next])
 					ind(d, "< highway chain", here, next)
 					supply_line[side] = 1
 					has_supply = true
 				}
 			} else {
-				if (supply_src[next]) {
-					ind(d, "!! source chain highway", next)
-					supply_line[side] = 1
-					has_supply = true
-				}
-				else
-				if (trace_supply_highway(next, d+1)) {
-					ind(d, "< chain highway", here, next)
+				//ind(d, "? chain tail", next)
+				if (trace_supply_chain(next, d+1, n+1, next_range)) {
+					ind(d, "< chain trail", here, next_range)
 					supply_line[side] = 1
 					has_supply = true
 				}
 			}
-		} else {
-			let next_range = min(range, SUPPLY_RANGE[road])
-			if (n + 1 <= next_range) {
-				if (supply_friendly[next] > 1) {
-					ind(d, "? chain head", next)
-					if (supply_src[next]) {
-						ind(d, "!! source highway chain", next)
-						supply_line[side] = 1
-						has_supply = true
-					}
-					else
-					if (trace_supply_chain(next, d+1, 0, 3)) {
-						ind(d, "< highway chain", here, next)
-						supply_line[side] = 1
-						has_supply = true
-					}
-				} else {
-					if (supply_src[next]) {
-						ind(d, "!! source highway chain", next_range)
-						supply_line[side] = 1
-						has_supply = true
-					}
-					else
-					if (trace_supply_chain(next, d+1, n+1, next_range)) {
-						ind(d, "< chain trail", here, next_range)
-						supply_line[side] = 1
-						has_supply = true
-					}
-				}
-			}
 		}
 	}
 
@@ -1305,7 +1299,22 @@ function trace_supply_chain(here, d, n, range) {
 	return has_supply
 }
 
+function all_hexes_sorted_by_distance_to_base(x) {
+	return all_hexes.slice().sort((a,b) => {
+		let da = distance_to[x][a]
+		let db = distance_to[x][b]
+		return db - da
+	})
+}
+
+const all_hexes_for_axis_supply =  all_hexes_sorted_by_distance_to_base(EL_AGHEILA)
+const all_hexes_for_allied_supply =  all_hexes_sorted_by_distance_to_base(ALEXANDRIA)
+
 function trace_supply_network(start) {
+	let search_order = (start === EL_AGHEILA ? all_hexes_for_axis_supply : all_hexes_for_allied_supply)
+
+	console.log("START", hex_name[start])
+
 	supply_visited.fill(0)
 	supply_src.fill(0)
 	supply_net.fill(0)
@@ -1315,9 +1324,12 @@ function trace_supply_network(start) {
 	supply_net[start] = 1
 
 	trace_total = 0
-	for (let x of all_hexes)
+	for (let x of search_order)
 		if (supply_friendly[x] > 0 && x !== start)
+		{
+			console.log("search from", hex_name[x])
 			trace_supply_chain(x, 0, 0, 3)
+		}
 
 	console.log("SUPPLY VISITS", trace_total)
 }
@@ -1334,9 +1346,9 @@ function trace_fortress_network(fortress, ss) {
 
 	trace_total = 0
 	for (let u = 0; u < unit_count; ++u) {
-		let x = unit_hex(u)
-		if (is_map_hex(x) && unit_supply(u) === ss) {
-			if (!supply_visited[x])
+		if (unit_supply(u) === ss) {
+			let x = unit_hex(u)
+			if (is_map_hex(x) && x !== fortress)
 				trace_supply_chain(x, 0, 0, 3)
 		}
 	}
@@ -2126,7 +2138,7 @@ function list_withdrawal_permutations(src, maybe) {
 
 	// impossible...
 	if (maybe.length < 2)
-		return
+		return {}
 
 	console.log("LIST WITHDRAWAL REGROUPS", maybe)
 
@@ -4189,6 +4201,7 @@ function can_select_refuse_battle_hex() {
 }
 
 function goto_refuse_battle() {
+	clear_undo()
 	set_passive_player()
 	if (can_select_refuse_battle_hex()) {
 		game.state = 'refuse_battle'
@@ -6309,19 +6322,13 @@ function bring_to_front(list, hex) {
 
 function sort_deployment_for_axis(list) {
 	list = list.slice()
-	list.reverse()
-	bring_to_front(list, BARDIA)
-	bring_to_front(list, TOBRUK)
-	bring_to_front(list, 88)
-	bring_to_front(list, 58) // Mechili
-	bring_to_front(list, 130) // Haraga
-	bring_to_front(list, 113) // Ft Maddalena
+	list.sort((a,b) => distance_to[EL_AGHEILA][b] - distance_to[EL_AGHEILA][a])
 	return list
 }
 
 function sort_deployment_for_allied(list) {
 	list = list.slice()
-	list.reverse()
+	list.sort((a,b) => distance_to[ALEXANDRIA][b] - distance_to[ALEXANDRIA][a])
 	return list
 }
 
@@ -7112,7 +7119,7 @@ exports.resign = function (state, current) {
 
 exports.action = function (state, current, action, arg) {
 	load_state(state)
-	Object.seal(game) // XXX: don't allow adding properties
+	// Object.seal(game) // XXX: don't allow adding properties
 	let S = states[game.state]
 	if (S && action in S) {
 		S[action](arg, current)