diff options
| -rw-r--r-- | rules.js | 403 |
1 files changed, 266 insertions, 137 deletions
@@ -11,10 +11,15 @@ const max = Math.max const min = Math.min const abs = Math.abs -const TIMEOUT = 500 +const TIMEOUT = 250 var timeout = 0 +function check_timeout() { + if (Date.now() > timeout) + throw new Error("timeout (too many withdrawal options)") +} + var states = {} var game = null var view = null @@ -120,6 +125,8 @@ const INFANTRY = 1 const ANTITANK = 2 const ARTILLERY = 3 +const TRAIL = 1 +const TRACK = 2 const HIGHWAY = 4 const SUPPLY_RANGE = [ 1, 2, 3, 0, 3 ] @@ -1133,151 +1140,273 @@ function shuffle_cards() { // === SUPPLY NETWORK === -var supply_defender, supply_defender_sides, supply_friendly, supply_enemy, supply_net, supply_line +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_src = new Array(hexcount).fill(0) +// PASS 1: Forward scan from source to compute potential supply net and valid hex side crossings. +// Simple uniform cost search. + +// NOTE: trace direction is from supply to unit function is_supply_line_blocked(here, next, side) { // impassable hexside if (side_limit[side] === 0) return true - // undisrupted (only) enemies may block supply lines - if (supply_enemy[next] > 1) { - if (supply_friendly[next] > 1) { - // 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 { - // into enemy hex + // into enemy hex + if (supply_enemy[next] > 1 && supply_friendly[next] === 0) + return true + + // into battle hex + if (is_battle_hex(next)) { + // through friendly hex sides + if (!set_has(supply_friendly_sides, side)) return true - } } // out of battle hex - // can only cannot trace out through friendly sides - if (supply_friendly[here] > 0 && supply_enemy[here] > 0) { - if (set_has(game.axis_hexes, here) || set_has(game.allied_hexes, here)) - if (!set_has(supply_defender_sides, side)) - return true + if (is_battle_hex(here)) { + // only defender (own control) + if (!set_has(supply_friendly_hexes, here)) + return true + // through friendly hex sides + if (!set_has(supply_friendly_sides, side)) + return true } return false } -function check_timeout() { - if (Date.now() > timeout) - throw new Error("timeout (supply lines are too complicated)") -} +const TRACE_HIGHWAY = 0 +const TRACE_TRACK_1 = 1 +const TRACE_TRACK_2 = 2 +const TRACE_TRAIL_1 = 3 +const TRACE_STOP = 7 +const TRACE_ABORT = 8 + +// from supply source outwards +function forward_supply_next_move_type(here_move, road) { + if (here_move === TRACE_HIGHWAY) { + if (road === HIGHWAY) return TRACE_HIGHWAY + if (road === TRACK) return TRACE_TRACK_1 + if (road === TRAIL) return TRACE_TRAIL_1 + return TRACE_STOP + } + else if (here_move === TRACE_TRACK_1) { + if (road === HIGHWAY) return TRACE_TRACK_2 + if (road === TRACK) return TRACE_TRACK_2 + if (road === TRAIL) return TRACE_STOP + return TRACE_ABORT + } + else if (here_move === TRACE_TRAIL_1) { + if (road === HIGHWAY) return TRACE_STOP + if (road === TRACK) return TRACE_STOP + if (road === TRAIL) return TRACE_STOP + return TRACE_ABORT + } + else if (here_move === TRACE_TRACK_2) { + if (road === HIGHWAY) return TRACE_STOP + if (road === TRACK) return TRACE_STOP + if (road === TRAIL) return TRACE_ABORT + return TRACE_ABORT + } + return TRACE_ABORT +} + +function trace_supply_network_1(start) +{ + supply_net[start] = 1 -function trace_supply_highway(here, v) { - if (supply_src[here]) - return true + supply_visited.fill(8) - check_timeout() + let queue = [ (start << 3) | TRACE_HIGHWAY ] - let has_supply = false + while (queue.length > 0) { + let item = queue.shift() + let here = item >> 3 + let here_move = item & 7 - let save_v = supply_visited[here] - supply_visited[here] = v + for (let s = 0; s < 6; ++s) { + let next = here + hexnext[s] - for (let s = 0; s < 6; ++s) { - let next = here + hexnext[s] + // can't go off-map + if (next < first_hex || next > last_hex || !hex_exists[next]) + continue - if (next < first_hex || next > last_hex || !hex_exists[next]) - continue + let side = to_side(here, next, s) + if (is_supply_line_blocked(here, next, side)) + continue - let next_v = supply_visited[next] - if (next_v === v || (next_v > 0 && supply_friendly[next] > 1)) - continue + let next_move = forward_supply_next_move_type(here_move, side_road[side]) + if (next_move === TRACE_ABORT) + continue - let side = to_side(here, next, s) - if (is_supply_line_blocked(here, next, side)) - continue + if (side_road[side] === HIGHWAY) + supply_line[side] = 1 + else + supply_line[side] = 1 - let road = side_road[side] - if (road === HIGHWAY) { - if (supply_friendly[next] > 1) { - if (supply_net[next] || trace_supply_chain(next, 0, 3, v+1)) { - supply_line[side] = 1 - has_supply = true - } - } else { - if (trace_supply_highway(next, v)) { - supply_line[side] = 1 - has_supply = true - } - } + // already seen + if (next_move >= supply_visited[next]) + continue + + // new supply chain at undisrupted friendly unit + if (supply_friendly[next] > 1) + next_move = TRACE_HIGHWAY + + supply_visited[next] = next_move + if (side_road[side] === HIGHWAY) + supply_net[next] = 1 + else + supply_net[next] = 1 + + if (next_move !== TRACE_STOP) + queue.push((next << 3) | next_move) } } +} - supply_visited[here] = save_v +// PASS 2: Filter net to only include supply lines used by units. +// This is a recursive search to find _all_ possible paths. - if (has_supply) - supply_net[here] = 1 +const BACK_HEAD = 0 +const BACK_STOP = 7 +const BACK_ABORT = 8 - return has_supply -} +const BACK_HIGHWAY_1 = 1 +const BACK_HIGHWAY_2 = 2 +const BACK_HIGHWAY_3 = 3 -function trace_supply_chain(here, n, range, v) { - if (supply_src[here]) - return true +const BACK_TRACK_1 = 4 +const BACK_TRACK_2 = 5 +const BACK_TRACK_3 = BACK_STOP - check_timeout() +const BACK_TRAIL_1 = 6 +const BACK_TRAIL_2 = BACK_STOP +const BACK_TRAIL_3 = BACK_ABORT - let has_supply = false +// from unit back to supply source +// TODO - double check all! +function backward_supply_next_move_type(here_move, road) { + if (here_move === BACK_HEAD) { + if (road === HIGHWAY) return BACK_HIGHWAY_1 + if (road === TRACK) return BACK_TRACK_1 + if (road === TRAIL) return BACK_TRAIL_1 + return BACK_STOP + } + if (here_move === BACK_HIGHWAY_1) { + if (road === HIGHWAY) return BACK_HIGHWAY_2 + if (road === TRACK) return BACK_TRACK_2 + if (road === TRAIL) return BACK_TRAIL_2 + return BACK_ABORT + } + if (here_move === BACK_HIGHWAY_2) { + if (road === HIGHWAY) return BACK_HIGHWAY_3 + if (road === TRACK) return BACK_TRACK_3 + if (road === TRAIL) return BACK_TRAIL_3 + return BACK_ABORT + } + if (here_move === BACK_HIGHWAY_3) { + if (road === HIGHWAY) return BACK_HIGHWAY_3 + if (road === TRACK) return BACK_ABORT + if (road === TRAIL) return BACK_ABORT + return BACK_ABORT + } + if (here_move === BACK_TRACK_1) { + if (road === HIGHWAY) return BACK_TRACK_2 + if (road === TRACK) return BACK_TRACK_2 + if (road === TRAIL) return BACK_TRAIL_2 + return BACK_ABORT + } + if (here_move === BACK_TRACK_2) { + if (road === HIGHWAY) return BACK_TRACK_3 + if (road === TRACK) return BACK_TRACK_3 + if (road === TRAIL) return BACK_TRAIL_3 + return BACK_ABORT + } + if (here_move === BACK_TRAIL_1) { + if (road === HIGHWAY) return BACK_TRAIL_2 + if (road === TRACK) return BACK_TRAIL_2 + if (road === TRAIL) return BACK_TRAIL_2 + return BACK_ABORT + } + return BACK_ABORT +} - let save_v = supply_visited[here] - supply_visited[here] = v +function trace_unit_supply_line(path, here, here_move, ssrc) { + supply_visited[here] = 1 + let supplied = false for (let s = 0; s < 6; ++s) { let next = here + hexnext[s] - if (next < first_hex || next > last_hex || !hex_exists[next]) + + // can't go off-map + if (next < first_hex || next > last_hex) + continue + + // already seen + if (supply_visited[next]) continue - let next_v = supply_visited[next] - if (next_v === v || (next_v > 0 && supply_friendly[next] > 1)) + // not part of supply network (from pass 1) + if (!supply_net[next]) continue + // supply line blocked (from pass 1) let side = to_side(here, next, s) - if (is_supply_line_blocked(here, next, side)) + if (!supply_line[side]) continue - let road = side_road[side] - if (road === HIGHWAY) { - if (trace_supply_highway(next, v)) { - supply_line[side] = 1 - has_supply = true - } - } + let next_move = backward_supply_next_move_type(here_move, side_road[side]) + if (next_move === TRACE_ABORT) + continue - let next_range = min(range, SUPPLY_RANGE[road]) - if (n + 1 <= next_range) { - if (supply_friendly[next] > 1) { - if (supply_net[next] || trace_supply_chain(next, 0, 3, v+1)) { - supply_line[side] = 1 - has_supply = true - } - } else { - if (trace_supply_chain(next, n + 1, next_range, v)) { - supply_line[side] = 1 - has_supply = true - } - } + // reached supply source, or reached supplied highway (that we searched before) + /* if (next === ssrc) -- fallback without short cut in case the optimization below is wrong... */ + if (next === ssrc || (hex_road[next] === HIGHWAY && supply_net[next] === 2)) { + for (let x of path) + supply_line[x] = 2 + supply_line[side] = 2 + supply_net[next] = 2 + supplied = true + continue } + + // new supply chain at undisrupted friendly unit + if (supply_friendly[next] > 1) + next_move = BACK_HEAD + + // 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 + + path.push(side) + if (trace_unit_supply_line(path, next, next_move, ssrc)) + supplied = true + path.pop() } + supply_visited[here] = 0 - supply_visited[here] = save_v + if (supplied) + supply_net[here] = 2 - if (has_supply) - supply_net[here] = 1 + return supplied +} - return has_supply +// finalize state after pass 2 +function trace_supply_network_3() { + for (let i = 0; i < sidecount; ++i) { + if (supply_line[i] === 2) + supply_line[i] = 1 + else + supply_line[i] = 0 + } + for (let i = 0; i < hexcount; ++i) { + if (supply_net[i] === 2) + supply_net[i] = 1 + else + supply_net[i] = 0 + } } function all_hexes_sorted_by_distance_to_base(x) { @@ -1292,47 +1421,55 @@ const all_hexes_for_axis_supply = all_hexes_sorted_by_distance_to_base(EL_AGHEI const all_hexes_for_allied_supply = all_hexes_sorted_by_distance_to_base(ALEXANDRIA) function trace_supply_network(start) { + check_timeout() + let search_order = (start === EL_AGHEILA ? all_hexes_for_axis_supply : all_hexes_for_allied_supply) - supply_visited.fill(0) - supply_src.fill(0) supply_net.fill(0) supply_line.fill(0) - supply_src[start] = 1 - supply_net[start] = 1 + // Pass 1: Find hexes that are in supply range. - for (let x of search_order) { - if (supply_friendly[x] > 0 && x !== start) { - if (supply_friendly[x] > 1 && supply_net[x]) - continue - trace_supply_chain(x, 0, 3, 1) - } - } + trace_supply_network_1(start) + + // Pass 2: Filter hexes that have actual supply lines from units. + supply_visited.fill(0) + let path = [] + 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 } function trace_fortress_network(fortress, ss) { - supply_visited.fill(0) - supply_src.fill(0) + check_timeout() + supply_net.fill(0) supply_line.fill(0) if (supply_enemy[fortress] > 1 && supply_friendly[fortress] <= 1) return - supply_src[fortress] = 1 - supply_net[fortress] = 1 + // Pass 1: Find hexes that could hold units supplied by fortress. + trace_supply_network_1(fortress) + // Pass 2: Filter hexes that have actual supply lines from units. + supply_visited.fill(0) + let path = [] for (let u = 0; u < unit_count; ++u) { if (unit_supply(u) === ss) { let x = unit_hex(u) if (is_map_hex(x) && x !== fortress) { - if (supply_friendly[x] > 1 && supply_net[x]) - continue - trace_supply_chain(x, 0, 3, 1) + //if (supply_friendly[x] > 1 && supply_net[x]) continue + trace_unit_supply_line(path, x, BACK_HEAD, fortress) } } } + + trace_supply_network_3() + supply_net[fortress] = 1 } function init_trace_supply(net, line, friendly) { @@ -1341,31 +1478,28 @@ function init_trace_supply(net, line, friendly) { supply_net = net supply_line = line if (friendly === AXIS) { - supply_defender = game.axis_hexes - supply_defender_sides = game.axis_sides + supply_friendly_hexes = game.axis_hexes + supply_friendly_sides = game.axis_sides supply_friendly = presence_axis supply_enemy = presence_allied } else { - supply_defender = game.allied_hexes - supply_defender_sides = game.allied_sides + supply_friendly_hexes = game.allied_hexes + supply_friendly_sides = game.allied_sides supply_friendly = presence_allied supply_enemy = presence_axis } } -// For repeated supplied hex checks during deployment and fortress assignment -function init_trace_supply_to_base_or_fortress() { +// For supplied hex checks during deployment and fortress assignment +function trace_supply_to_base_or_fortress(source) { init_trace_supply(supply_temp_network, supply_temp_line, game.active) supply_net.fill(0) + supply_line.fill(0) + trace_supply_network_1(source) } -function can_trace_supply_to_base_or_fortress(base, from) { - if (from === base) - return true - supply_visited.fill(0) - supply_src.fill(0) - supply_src[base] = 1 - return trace_supply_chain(from, 0, 3, 1, 1) +function can_trace_supply_to_base_or_fortress(from) { + return supply_net[from] > 0 } function update_axis_supply() { @@ -2662,10 +2796,10 @@ function end_fortress_supply() { function list_fortress_supply_candidates(fortress) { let dist = distance_to[fortress] let list = [] - init_trace_supply_to_base_or_fortress() + trace_supply_to_base_or_fortress(fortress) for_each_friendly_unit_on_map(u => { if (is_unit_unsupplied(u)) - if (can_trace_supply_to_base_or_fortress(fortress, unit_hex(u))) + if (can_trace_supply_to_base_or_fortress(unit_hex(u))) list.push(u) }) list.sort((a,b) => dist[unit_hex(a)] - dist[unit_hex(b)]) @@ -6690,11 +6824,8 @@ function goto_free_deployment() { game.summary = {} } -function is_valid_deployment_hex(base, x, n) { - // we've already seen this hex during a previous supplied hex check this go - if (supply_temp_network[x] > 0) - return true - if (can_trace_supply_to_base_or_fortress(base, x)) +function is_valid_deployment_hex(x, n) { + if (can_trace_supply_to_base_or_fortress(x)) return true if (x === TOBRUK) return count_friendly_units_in_hex(x) + n <= 5 @@ -6722,8 +6853,7 @@ states.free_deployment = { gen_action('end_deployment') if (game.selected.length > 0) { - let base = friendly_base() - init_trace_supply_to_base_or_fortress() + trace_supply_to_base_or_fortress(friendly_base()) for (let x of (axis ? scenario.axis_deployment : scenario.allied_deployment)) { if (!is_enemy_hex(x)) { @@ -6731,7 +6861,7 @@ states.free_deployment = { if (scenario.deployment_limit) limit = scenario.deployment_limit[x] | 0 if (!limit || count_friendly_units_in_hex(x) + game.selected.length <= limit) { - if (is_valid_deployment_hex(base, x, game.selected.length)) + if (is_valid_deployment_hex(x, game.selected.length)) gen_action_hex(x) } } @@ -7578,7 +7708,6 @@ exports.resign = function (state, current) { exports.action = function (state, current, action, arg) { timeout = Date.now() + TIMEOUT // don't think too long! load_state(state) - // Object.seal(game) // XXX: don't allow adding properties let S = states[game.state] if (S && action in S) { S[action](arg, current) |