From 6f7629ddffbad3affd36c348904874b468b11b55 Mon Sep 17 00:00:00 2001 From: Tor Andersson Date: Thu, 4 Jan 2024 12:40:25 +0100 Subject: Memoize (successful) supply searches. Use the hex number AND the pathing state for the memo cache. NOTE: Unsuccessful searches cannot be memoized, because we may be approaching the hex in the opposite direction of supply. Since the search never backtracks we would record an (incorrectly) negative result. TODO: direction of approach and "supply_visit" is also part of state that should be part of the memo key for accuracy. --- rules.js | 20 +++++++++++++++++--- 1 file changed, 17 insertions(+), 3 deletions(-) diff --git a/rules.js b/rules.js index 119022c..226850f 100644 --- a/rules.js +++ b/rules.js @@ -1142,6 +1142,7 @@ function shuffle_cards() { 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_memo = new Array(hexcount * 8).fill(0) // PASS 1: Forward scan from source to compute potential supply net and valid hex side crossings. // Simple uniform cost search. @@ -1333,6 +1334,13 @@ function backward_supply_next_move_type(here_move, road) { } function trace_unit_supply_line(path, here, here_move, ssrc) { + let memo_idx = (here << 3) + here_move + if (supply_memo[memo_idx]) { + for (let x of path) + supply_line[x] = 2 + return true + } + supply_visited[here] = 1 let supplied = false @@ -1417,8 +1425,10 @@ function trace_unit_supply_line(path, here, here_move, ssrc) { } supply_visited[here] = 0 - if (supplied) + if (supplied) { supply_net[here] = 2 + supply_memo[memo_idx] = 1 + } return supplied } @@ -1464,10 +1474,13 @@ function trace_supply_network(start) { // Pass 2: Filter hexes that have actual supply lines from units. supply_visited.fill(0) + supply_memo.fill(0) let path = [] - for (let x of search_order) - if (supply_friendly[x] > 0 && x !== start) + 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 @@ -1487,6 +1500,7 @@ function trace_fortress_network(fortress, ss) { // Pass 2: Filter hexes that have actual supply lines from units. supply_visited.fill(0) + supply_memo.fill(0) let path = [] for (let u = 0; u < unit_count; ++u) { if (unit_supply(u) === ss) { -- cgit v1.2.3