From 134fc1af7665829244da1a1cdaa93fe2b6b49448 Mon Sep 17 00:00:00 2001 From: Tor Andersson Date: Fri, 2 Sep 2022 18:28:46 +0200 Subject: Optimize supply network calculations. --- rules.js | 145 +++++++++++++++++++++++++++++++++------------------------------ 1 file 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) -- cgit v1.2.3