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.

1 files 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) {