From 8ad387fbbdc6ee0aed05ea38451966d463e4892c Mon Sep 17 00:00:00 2001
From: Tor Andersson <tor@ccxvii.net>
Date: Mon, 9 Dec 2024 20:38:03 +0100
Subject: Start supply line search at the root instead of at the leaves.

This prunes the search space effectively.
---
 rules.js | 81 +++++++++++++++++++++++++++++++---------------------------------
 1 file changed, 39 insertions(+), 42 deletions(-)

diff --git a/rules.js b/rules.js
index 888cff3..deef1a5 100644
--- a/rules.js
+++ b/rules.js
@@ -1337,7 +1337,7 @@ function backward_supply_next_move_type(here_move, road) {
 	return BACK_ABORT
 }
 
-function trace_supply_chains(output, path, here, here_move, ssrc) {
+function trace_supply_chains(path, here, here_move, ssrc) {
 	supply_n++
 	supply_visited[here] = 1
 	for (let s = 0; s < 6; ++s) {
@@ -1368,16 +1368,13 @@ function trace_supply_chains(output, path, here, here_move, ssrc) {
 
 		// reached supply source or another supply chain
 		if (next === ssrc || supply_friendly[next] > 1) {
-			let links = map_get(output, next, null)
-			if (!links)
-				map_set(output, next, links = [])
-			links.push(path.slice())
+			add_supply_chain(path, next)
 		} else {
 			// 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
 
-			trace_supply_chains(output, path, next, next_move, ssrc)
+			trace_supply_chains(path, next, next_move, ssrc)
 		}
 
 		path.pop()
@@ -1385,63 +1382,63 @@ function trace_supply_chains(output, path, here, here_move, ssrc) {
 	supply_visited[here] = 0
 }
 
+function add_supply_chain(path, end) {
+	var tail = map_get(supply_chains, end)
+	if (!tail)
+		map_set(supply_chains, end, tail = [])
+	tail.push(path.slice())
+}
+
 // PASS 3: Filter network to only include valid supply lines.
 // This is a recursive search to find _all_ possible paths,
 // searching through the network of possible supply chains.
 
-function add_supply_lines(path_list) {
-	var i, n, a, b, path
-	for (path of path_list) {
-		a = path[0]
-		supply_net[a] = 2
-		for (i = 1, n = path.length; i < n; ++i) {
-			b = path[i]
-			supply_net[b] = 2
-			supply_line[to_side_id(a, b)] = 2
-			a = b
-		}
+function mark_supply_line(path) {
+	var i, n, a, b
+	a = path[0]
+	supply_net[a] = 2
+	for (i = 1, n = path.length; i < n; ++i) {
+		b = path[i]
+		supply_net[b] = 2
+		supply_line[to_side_id(a, b)] = 2
+		a = b
 	}
 }
 
-function trace_supply_lines(source, here) {
-	var i, n, chains, next, paths, result
+function trace_supply_lines(here) {
+	var paths, path, save, next
 	supply_n++
 	supply_visited[here] = 1
-	chains = map_get(supply_chains, here)
-	result = false
-	for (i = 0, n = chains.length; i < n; i += 2) {
-		next = chains[i]
-		paths = chains[i+1]
-		if (next === source) {
-			add_supply_lines(paths)
-			result = true
-		} else if (!supply_visited[next]) {
-			if (trace_supply_lines(source, next)) {
-				add_supply_lines(paths)
-				result = true
+	paths = map_get(supply_chains, here, null)
+	save = -1
+	if (paths) {
+		for (path of paths) {
+			next = path[0]
+			if (!supply_visited[next]) {
+				mark_supply_line(path)
+				if (next !== save)
+					trace_supply_lines(next)
 			}
+			save = next
 		}
 	}
 	supply_visited[here] = 0
-	return result
 }
 
 function trace_supply_network_2(source, hexes) {
 	var i, chains, head
 
-	supply_chains = []
 	supply_visited.fill(0)
 
-	// PASS 2: Search potential supply chains.
-	for (head of hexes) {
-		chains = []
-		trace_supply_chains(chains, [head], head, BACK_HEAD, source)
-		map_set(supply_chains, head, chains)
-	}
-
-	// PASS 3: Search all possible supply links using the chains.
+	// PASS 2: List all potential supply chains.
+	supply_n = 0
+	supply_chains = []
 	for (head of hexes)
-		trace_supply_lines(source, head)
+		trace_supply_chains([head], head, BACK_HEAD, source)
+
+	// PASS 3: Find all possible supply lines using the chains.
+	supply_n = 0
+	trace_supply_lines(source)
 
 	// PASS 4: Keep only used supply lines in the network.
 	for (i = 0; i < sidecount; ++i) {
-- 
cgit v1.2.3