From 419f978d09f713e852ab165b5b5c128c3d433257 Mon Sep 17 00:00:00 2001 From: Tor Andersson Date: Sat, 23 Sep 2023 14:13:08 +0200 Subject: Path finding with visible path in client. --- rules.js | 232 +++++++++++++++++++++++++++++++++++++++++++++++---------------- 1 file changed, 173 insertions(+), 59 deletions(-) (limited to 'rules.js') diff --git a/rules.js b/rules.js index 901c5a0..988a959 100644 --- a/rules.js +++ b/rules.js @@ -23,6 +23,9 @@ const last_hex = 1000 + (data.map.rows - 1) * 100 + (data.map.cols - 1) var move_seen = new Array(last_hex - 999).fill(0) var move_cost = new Array(last_hex - 999).fill(0) +var move_flip = new Array(last_hex - 999).fill(0) +var move_from = [] +var move_from_road = [] var zoc_valid = false var zoc_cache = new Array(data.map.rows * 100).fill(0) @@ -751,11 +754,15 @@ states.place_detachment_where = { search_detachment(game.who, game.target) + view.move_from = move_from + view.move_from_road = move_from_road + for (let row = 0; row < data.map.rows; ++row) { for (let col = 0; col < data.map.cols; ++col) { let x = 1000 + row * 100 + col - if (move_seen[x-1000] && !is_friendly_zoc_or_zoi(x) && !hex_has_any_piece(x, friendly_detachments())) - gen_action_hex(x) + if (move_seen[x-1000]) + if (!is_friendly_zoc_or_zoi(x) && !hex_has_any_piece(x, friendly_detachments())) + gen_action_hex(x) } } }, @@ -1093,16 +1100,17 @@ states.movement_to = { update_zoc() search_move(game.who) + view.move_from = move_from + view.move_from_road = move_from_road for (let row = 0; row < data.map.rows; ++row) { for (let col = 0; col < data.map.cols; ++col) { let x = 1000 + row * 100 + col - let m = move_seen[x-1000] - if (m & 1) { - if (m & 2) - gen_action_hex(x) - else + if (move_seen[x-1000]) { + if (move_flip[x-1000]) gen_action_stop_hex(x) + else + gen_action_hex(x) } } } @@ -1127,7 +1135,7 @@ states.movement_to = { log("C: P" + game.who + " moved to " + x) // must flip (stream without road, or enter zoc) - if (!(move_seen[x-1000] & 2)) + if (move_flip[x-1000]) set_piece_mode(game.who, 1) // flip all enemy inf in zoc @@ -1219,6 +1227,9 @@ function can_trace_detachment(here, next) { function search_detachment(who, hq) { move_seen.fill(0) + move_from.length = 0 + move_from_road.length = 0 + search_detachment_normal(piece_hex(hq), piece_command_range(hq)) if (!piece_mode(hq)) @@ -1230,20 +1241,23 @@ function search_detachment(who, hq) { search_detachment_normal(piece_hex(pp), 4) } -function search_detachment_normal(start, range) { +function search_detachment_normal(start, ma) { + let queue = [ (start << 8) | (ma) ] move_cost.fill(0) - move_cost[start-1000] = range + move_cost[start-1000] = 1 move_seen[start-1000] = 1 - let queue = [ start ] while (queue.length > 0) { - let here = queue.shift() + let item = queue.shift() + let here = item >> 8 + let mp = item & 255 for_each_adjacent(here, next => { - if (can_trace_detachment(here, next)) { - let mp = move_cost[here-1000] - 1 - move_seen[next-1000] = 1 - if (mp > move_cost[next-1000]) { - move_cost[next-1000] = mp - queue.push(next) + if (!move_cost[next-1000]) { + if (can_trace_detachment(here, next)) { + map_set(move_from, next, here) + move_cost[next-1000] = 1 + move_seen[next-1000] = 1 + if (mp > 1) + queue.push((next << 8) | (mp - 1)) } } }) @@ -1251,51 +1265,71 @@ function search_detachment_normal(start, range) { } function search_detachment_road(start, range) { + let queue = [ start ] + move_cost.fill(0) move_cost[start-1000] = range move_seen[start-1000] = 1 - let queue = [ start ] + while (queue.length > 0) { let here = queue.shift() for (let [road_id, k] of data_roads[here-1000]) { let road = data.map.roads[road_id] if (k + 1 < road.length) - search_detachment_road_segment(queue, road, k, 1) + search_detachment_road_segment(queue, here, road, k, 1) if (k > 0) - search_detachment_road_segment(queue, road, k, -1) + search_detachment_road_segment(queue, here, road, k, -1) } } } -function search_detachment_road_segment(queue, road, cur, dir) { - let here = road[cur] +function search_detachment_road_segment(queue, here, road, cur, dir) { let mp = move_cost[here-1000] + let qq = false cur += dir + while (mp > 0 && cur >= 0 && cur < road.length) { let next = road[cur] + if (!can_trace_detachment(here, next)) return - move_seen[next-1000] = 1 - here = next + + let next_mp = mp - 1 + + let seen_mp = move_cost[next-1000] + if (seen_mp === 255 || next_mp > seen_mp) { + map_set(move_from_road, next, here) + move_seen[next-1000] = 1 + move_cost[next-1000] = next_mp + qq = (next_mp > 0) + } else { + return + } + cur += dir - mp -- + here = next + mp = next_mp } - if (mp > move_cost[here-1000]) { - move_cost[here-1000] = mp + + if (qq) queue.push(here) - } } function search_move(p) { move_seen.fill(0) + move_flip.fill(1) + move_from.length = 0 + move_from_road.length = 0 + let x = piece_hex(p) let m = piece_movement_allowance(p) let u = 0 if (x === REINFORCEMENTS) { x = find_reinforcement_hex(p) u = 1 - move_seen[x-1000] = 3 + move_seen[x-1000] = 1 } + for (let hq of data.pieces[p].hq) { let hq_hex = piece_hex(hq) if (is_map_hex(hq_hex)) { @@ -1308,67 +1342,102 @@ function search_move(p) { } function search_move_normal(start, ma, hq_hex, hq_range, is_cav) { - move_cost.fill(0) - move_cost[start-1000] = ma let queue = [ start ] + + move_cost.fill(255) + move_cost[start-1000] = ma + while (queue.length > 0) { let here = queue.shift() + let mp = move_cost[here-1000] + for_each_adjacent(here, next => { - if (can_move_into(here, next, hq_hex, hq_range, is_cav)) { - let mp = move_cost[here-1000] - 1 - move_seen[next-1000] |= 1 - if (!must_stop_stream(here, next) && !must_flip_zoc(here, next, is_cav)) - move_seen[next-1000] |= 2 - else - mp = 0 - if (must_stop_zoc_zoi(here, next, is_cav)) - mp = 0 - if (mp > move_cost[next-1000]) { - move_cost[next-1000] = mp + if (!can_move_into(here, next, hq_hex, hq_range, is_cav)) + return + + let next_mp = mp - 1 + if (must_stop_stream(here, next)) + next_mp = -1 + else if (must_flip_zoc(here, next, is_cav)) + next_mp = -1 + else if (must_stop_zoc_zoi(here, next, is_cav)) + next_mp = 0 + + let seen_mp = move_cost[next-1000] + if (seen_mp === 255 || next_mp > seen_mp) { + map_set(move_from, next, here) + move_seen[next-1000] = 1 + move_cost[next-1000] = next_mp + + // can move without flipping! + if (next_mp >= 0) + move_flip[next-1000] = 0 + + // can continue + if (next_mp > 0) queue.push(next) - } } }) } } function search_move_road(start, ma, hq_hex, hq_range, is_cav) { - move_cost.fill(0) - move_cost[start-1000] = ma let queue = [ start ] + + move_cost.fill(255) + move_cost[start-1000] = ma + move_seen[start-1000] = 1 + while (queue.length > 0) { let here = queue.shift() for (let [road_id, k] of data_roads[here-1000]) { let road = data.map.roads[road_id] if (k + 1 < road.length) - search_move_road_segment(queue, road, k, 1, hq_hex, hq_range, is_cav) + search_move_road_segment(queue, here, road, k, 1, hq_hex, hq_range, is_cav) if (k > 0) - search_move_road_segment(queue, road, k, -1, hq_hex, hq_range, is_cav) + search_move_road_segment(queue, here, road, k, -1, hq_hex, hq_range, is_cav) } } } -function search_move_road_segment(queue, road, cur, dir, hq_hex, hq_range, is_cav) { - let here = road[cur] +function search_move_road_segment(queue, here, road, cur, dir, hq_hex, hq_range, is_cav) { let mp = move_cost[here-1000] + let qq = false cur += dir + while (mp > 0 && cur >= 0 && cur < road.length) { let next = road[cur] + if (!can_move_into(here, next, hq_hex, hq_range, is_cav)) return - move_seen[next-1000] |= 1 - if (!must_flip_zoc(here, next, is_cav)) - move_seen[next-1000] |= 2 - if (must_stop_zoc_zoi(here, next, is_cav)) + + let next_mp = mp - 1 + if (must_flip_zoc(here, next, is_cav)) + next_mp = -1 + else if (must_stop_zoc_zoi(here, next, is_cav)) + next_mp = 0 + + let seen_mp = move_cost[next-1000] + if (seen_mp === 255 || next_mp > seen_mp) { + map_set(move_from_road, next, here) + move_seen[next-1000] = 1 + move_cost[next-1000] = next_mp + + if (next_mp >= 0) + move_flip[next-1000] = 0 + + qq = (next_mp > 0) + } else { return - here = next + } + cur += dir - mp -- + here = next + mp = next_mp } - if (mp > move_cost[here-1000]) { - move_cost[here-1000] = mp + + if (qq) queue.push(here) - } } function search_withdrawal(here) { @@ -2307,6 +2376,15 @@ function array_insert(array, index, item) { array[index] = item } +function array_insert_pair(array, index, key, value) { + for (let i = array.length; i > index; i -= 2) { + array[i] = array[i-2] + array[i+1] = array[i-1] + } + array[index] = key + array[index+1] = value +} + // Set as plain sorted array function set_has(set, item) { @@ -2357,3 +2435,39 @@ function set_delete(set, item) { } } } + +// Map as plain sorted array of key/value pairs + +function map_has(map, key) { + let a = 0 + let b = (map.length >> 1) - 1 + while (a <= b) { + let m = (a + b) >> 1 + let x = map[m<<1] + if (key < x) + b = m - 1 + else if (key > x) + a = m + 1 + else + return true + } + return false +} + +function map_set(map, key, value) { + let a = 0 + let b = (map.length >> 1) - 1 + while (a <= b) { + let m = (a + b) >> 1 + let x = map[m<<1] + if (key < x) + b = m - 1 + else if (key > x) + a = m + 1 + else { + map[(m<<1)+1] = value + return + } + } + array_insert_pair(map, a<<1, key, value) +} -- cgit v1.2.3