diff --git a/src/simutrans/script/api/api_pathfinding.cc b/src/simutrans/script/api/api_pathfinding.cc index 48be4e001..2cc17f3dd 100644 --- a/src/simutrans/script/api/api_pathfinding.cc +++ b/src/simutrans/script/api/api_pathfinding.cc @@ -13,6 +13,7 @@ #include "../api_function.h" #include "../../builder/brueckenbauer.h" #include "../../builder/wegbauer.h" +#include "../../dataobj/koord3d.h" #include "../../dataobj/settings.h" #include "../../descriptor/bridge_desc.h" #include "../../descriptor/way_desc.h" @@ -122,6 +123,118 @@ bool way_builder_is_allowed_step(way_builder_t *bob, grund_t *from, grund_t *to) } +/** + * A script may leave the bridge and the tunnel out, but param<>::get raises an error on + * anything that is not an instance, null included. @p ok is cleared when something was + * supplied and could not be read, so that the caller does not return a route and swallow + * the error that was raised. + */ +template static const D *optional_desc(HSQUIRRELVM vm, SQInteger index, bool &ok) +{ + if( sq_gettop(vm) < index || sq_gettype(vm, index) == OT_NULL ) { + return NULL; + } + const D *desc = param::get(vm, index); + ok = ok && desc != NULL; + return desc; +} + + +/** + * Plans a way and hands the route to the script as plain coordinates. + * + * The builder lives on the stack and dies with this call: what the script gets is a + * copy, so no later call can change a route handed out earlier, and nothing of the + * builder's state outlives the call. The world is not touched, see way_builder_t::build() + * for what building would add on top. + * + * Construction type, tunnel and bridge follow tool_build_way_t::calc_route(), so the route + * comes from the same internal planner the way tool uses. It can still differ from what + * command_x.build_way() builds, as the tool does its own preprocessing around the two + * clicked tiles. Terraforming is left out on purpose, so that a planned route does not + * depend on ground the script has not asked to change. + * + * prefer_parallel is the builder's own flag, the one the way tool guesses from the tiles + * around the two clicks. The script says it instead of guessing, because it knows whether + * it is asking for a second track. + * + * An empty array means "no route". A bad argument raises an error instead, so that a script + * cannot mistake one for the other. + */ +static SQInteger way_planner_find_route(HSQUIRRELVM vm) // class, player, start, end, way [, straight, keep_city_roads, bridge, tunnel, prefer_parallel] +{ + player_t *player = param::get(vm, 2); + const koord3d start = param::get(vm, 3); + const koord3d end = param::get(vm, 4); + const way_desc_t *way = param::get(vm, 5); + const bool straight = sq_gettop(vm) >= 6 && param::get(vm, 6); + const bool keep_city_roads = sq_gettop(vm) >= 7 && param::get(vm, 7); + bool desc_ok = true; + const bridge_desc_t *bridge = optional_desc(vm, 8, desc_ok); + const tunnel_desc_t *tunnel = optional_desc(vm, 9, desc_ok); + const bool prefer_parallel = sq_gettop(vm) >= 10 && param::get(vm, 10); + + if( !desc_ok ) { + return SQ_ERROR; // param<>::get already said which class it expected + } + if( player == NULL ) { + return sq_raise_error(vm, "find_route: there is no such player"); + } + if( way == NULL ) { + return sq_raise_error(vm, "find_route: no way descriptor provided"); + } + + vector_tpl planned; + + if( welt->lookup(start) == NULL || welt->lookup(end) == NULL ) { + return param >::push(vm, planned); + } + + // type of construction, as tool_build_way_t::calc_route derives it from the descriptor + way_builder_t::bautyp_t bautyp = (way_builder_t::bautyp_t)way->get_wtyp(); + if( way->is_tram() ) { + bautyp = way_builder_t::schiene_tram; + } + if( way->get_styp() == type_elevated && way->get_wtyp() != air_wt ) { + bautyp |= way_builder_t::elevated_flag; + } + + way_builder_t bob(player); + bob.init_builder( bautyp, way, tunnel, bridge ); + // straight and keep_city_roads reach the tool as the ctrl and shift flags of a click + if( straight && !keep_city_roads ) { + bob.set_keep_existing_ways( false ); + } + else { + bob.set_keep_existing_faster_ways( true ); + } + if( keep_city_roads && way->get_styp() == type_flat && way->get_wtyp() == road_wt ) { + bob.set_keep_city_roads( true ); + } + // the way tool guesses this one from the surroundings of the two clicks, a script says it + bob.set_prefer_parallel( prefer_parallel ); + + if( straight ) { + bob.calc_straight_route( start, end ); + } + else { + bob.calc_route( start, end ); + } + + const koord3d_vector_t &route = bob.get_route(); + if( route.get_count() >= 2 ) { + // the A* search stores the route from the target backwards, calc_straight_route + // stores it forwards; the script always gets it from start to end + const uint32 last = route.get_count() - 1; + const bool reversed = koord_distance( route[0], start ) > koord_distance( route[last], start ); + for( uint32 i = 0; i <= last; i++ ) { + planned.append( route[ reversed ? last - i : i ] ); + } + } + return param >::push(vm, planned); +} + + /** * Highest length a script may ask for: bridge_builder_t::find_end_pos counts the * tested lengths in an uint8, so 255 would never terminate. @@ -242,6 +355,42 @@ void export_pathfinding(HSQUIRRELVM vm) */ register_method(vm, way_builder_is_allowed_step, "is_allowed_step", true); + /** + * Plans a way from @p start to @p end with the internal way builder and returns the + * route it found, without building anything: no ground is changed, nothing is paid + * for and nothing is reserved. It is safe to call it as often as wanted. + * + * A planned route is a proposal, not a reservation: the map can change before the + * script gets to build it, and then the route may no longer be buildable. + * + * The arguments are the ones of @ref command_x::build_way, plus the bridge and the + * tunnel the planner may use to cross what it cannot walk over. A route crossing one + * of them shows up as a jump of more than one tile between two consecutive entries. + * + * This uses the same internal route planner as the way tool, although tool-specific + * preprocessing can still make the result differ in some situations. + * + * An empty array means that no route was found. A player that does not exist or a + * missing way descriptor raise an error instead. + * + * @param pl who wants to build the way + * @param start start tile + * @param end end tile + * @param way descriptor of the way to plan + * @param straight (optional parameter) if true then only a straight route is looked for. Defaults to false. + * @param keep_city_roads (optional parameter) if true then city roads are not replaced. Defaults to false. + * @param bridge (optional parameter) bridge the route may use, null for none. Defaults to null. + * @param tunnel (optional parameter) tunnel the route may use, null for none. Defaults to null. + * @param prefer_parallel (optional parameter) if true then the route runs next to existing ways + * instead of on top of them, as when adding a second track. Defaults to false. + * @returns array of the tiles of the route, from @p start to @p end, empty if there is no route + * @typemask array(player_x,coord3d,coord3d,way_desc_x,bool,bool,bridge_desc_x,tunnel_desc_x,bool) + */ + STATIC register_function(vm, way_planner_find_route, "find_route", -5 /* at least 5 parameters */, + ".t|x|yt|x|yt|x|yt|x|ybbt|x|y|ot|x|y|ob", true /* static */); + + log_squirrel_type("way_planner_x", "find_route", "array(player_x, coord3d, coord3d, way_desc_x)"); + end_class(vm); /** diff --git a/src/simutrans/script/api/changelog.h b/src/simutrans/script/api/changelog.h index 0cf6da01a..43773be66 100644 --- a/src/simutrans/script/api/changelog.h +++ b/src/simutrans/script/api/changelog.h @@ -15,6 +15,7 @@ * * @section api-trunk Current trunk * + * - Added @ref way_planner_x::find_route to get the route of the internal way builder without building it * - Changed @ref bridge_planner_x::find_end which accepts two optional parameters now, to search for longer bridges and for ends on flat ground * - Added @ref command_x::grid_lower, @ref command_x::grid_raise * - Added @ref settings::has_double_slopes, @ref settings::get_way_height_clearance diff --git a/tests/all_tests.nut b/tests/all_tests.nut index 94e38e778..be522d658 100644 --- a/tests/all_tests.nut +++ b/tests/all_tests.nut @@ -33,6 +33,7 @@ include("tests/test_way_bridge") include("tests/test_way_bridge_maintenance") include("tests/test_way_bridge_maintenance_auto") include("tests/test_way_elevated") +include("tests/test_way_planner") include("tests/test_way_road") include("tests/test_way_runway") include("tests/test_way_tram") @@ -225,6 +226,16 @@ all_tests <- [ test_way_bridge_maintenance_auto, test_way_bridge_maintenance_auto_equals_manual, test_way_bridge_maintenance_auto_off, + test_way_planner_straight_route, + test_way_planner_route_with_bend, + test_way_planner_no_route, + test_way_planner_repeated_call, + test_way_planner_changes_nothing, + test_way_planner_calls_are_independent, + test_way_planner_matches_built_way, + test_way_planner_bridge_crosses_water, + test_way_planner_prefer_parallel, + test_way_planner_prefer_parallel_matches_tool, test_way_road_build_single_tile, test_way_road_build_straight, test_way_road_build_bend, diff --git a/tests/tests/test_way_planner.nut b/tests/tests/test_way_planner.nut new file mode 100644 index 000000000..19a04ed08 --- /dev/null +++ b/tests/tests/test_way_planner.nut @@ -0,0 +1,350 @@ +// +// This file is part of the Simutrans project under the Artistic License. +// (see LICENSE.txt) +// + +// way_planner_x.find_route() runs the internal way builder and hands the route to the +// script as plain coordinates. It must not touch the world, and two calls must not see +// anything of each other. + +function wayplanner_road() +{ + local road = way_desc_x.get_available_ways(wt_road, st_flat)[0] + ASSERT_TRUE(road != null) + return road +} + + +function wayplanner_str(route) +{ + local s = "" + foreach (pos in route) { + s += pos.tostring() + } + return s +} + + +// every step of a route is one tile, so a longer step is a bridge or a tunnel +function wayplanner_longest_step(route) +{ + local worst = 0 + for (local i = 1; i < route.len(); ++i) { + local d = abs(route[i].x - route[i-1].x) + abs(route[i].y - route[i-1].y) + if (d > worst) { + worst = d + } + } + return worst +} + + +function wayplanner_clear(route) +{ + local remover = command_x(tool_remover) + foreach (pos in route) { + remover.work(player_x(0), pos) + } +} + + +function wayplanner_row(y, x0, x1) +{ + local tiles = [] + for (local x = x0; x <= x1; ++x) { + tiles.append(coord3d(x, y, 0)) + } + return tiles +} + + +function test_way_planner_straight_route() +{ + local pl = player_x(0) + local route = way_planner_x.find_route(pl, coord3d(2, 2, 0), coord3d(5, 2, 0), wayplanner_road()) + + ASSERT_EQUAL(route.len(), 4) + ASSERT_EQUAL(route[0].tostring(), coord3d(2, 2, 0).tostring()) + ASSERT_EQUAL(route[3].tostring(), coord3d(5, 2, 0).tostring()) + ASSERT_EQUAL(wayplanner_longest_step(route), 1) + + // the straight search fills the route in the other order internally, and the + // script must not notice: on a straight line both give the same tiles + local straight = way_planner_x.find_route(pl, coord3d(2, 2, 0), coord3d(5, 2, 0), wayplanner_road(), true) + ASSERT_EQUAL(wayplanner_str(straight), wayplanner_str(route)) + + RESET_ALL_PLAYER_FUNDS() +} + + +function test_way_planner_route_with_bend() +{ + local pl = player_x(0) + local route = way_planner_x.find_route(pl, coord3d(2, 2, 0), coord3d(5, 5, 0), wayplanner_road()) + + // three tiles east and three south, plus the tile it starts on + ASSERT_EQUAL(route.len(), 7) + ASSERT_EQUAL(route[0].tostring(), coord3d(2, 2, 0).tostring()) + ASSERT_EQUAL(route[6].tostring(), coord3d(5, 5, 0).tostring()) + ASSERT_EQUAL(wayplanner_longest_step(route), 1) + + RESET_ALL_PLAYER_FUNDS() +} + + +function test_way_planner_no_route() +{ + local pl = player_x(0) + local setclimate = command_x(tool_set_climate) + local moat = [coord3d(7, 8, 0), coord3d(9, 8, 0), coord3d(8, 7, 0), coord3d(8, 9, 0)] + + foreach (pos in moat) { + ASSERT_EQUAL(setclimate.work(pl, pos, pos, "" + cl_water), null) + } + + // no road can reach a tile with water on all four sides + local route = way_planner_x.find_route(pl, coord3d(2, 2, 0), coord3d(8, 8, 0), wayplanner_road()) + ASSERT_EQUAL(route.len(), 0) + + // a tile outside the map is not a route either + local outside = way_planner_x.find_route(pl, coord3d(2, 2, 0), coord3d(2, 200, 0), wayplanner_road()) + ASSERT_EQUAL(outside.len(), 0) + + // but a bad argument must not look like "no route": it raises instead + ASSERT_FALSE(player_x(5).is_valid()) + local raised = false + try { + way_planner_x.find_route(player_x(5), coord3d(2, 2, 0), coord3d(5, 2, 0), wayplanner_road()) + } + catch (err) { + raised = true + } + ASSERT_TRUE(raised) + + foreach (pos in moat) { + ASSERT_EQUAL(setclimate.work(pl, pos, pos, "" + cl_mediterran), null) + } + + RESET_ALL_PLAYER_FUNDS() +} + + +function test_way_planner_repeated_call() +{ + local pl = player_x(0) + local road = wayplanner_road() + + local first = way_planner_x.find_route(pl, coord3d(2, 2, 0), coord3d(5, 5, 0), road) + local second = way_planner_x.find_route(pl, coord3d(2, 2, 0), coord3d(5, 5, 0), road) + + ASSERT_TRUE(first.len() > 0) + ASSERT_EQUAL(wayplanner_str(first), wayplanner_str(second)) + + RESET_ALL_PLAYER_FUNDS() +} + + +function test_way_planner_changes_nothing() +{ + local pl = player_x(0) + local cash = pl.get_current_cash() + + local route = way_planner_x.find_route(pl, coord3d(2, 2, 0), coord3d(5, 5, 0), wayplanner_road()) + ASSERT_TRUE(route.len() > 0) + + // planning is free and builds nothing + ASSERT_EQUAL(pl.get_current_cash(), cash) + ASSERT_EQUAL(pl.get_current_maintenance(), 0) + foreach (pos in route) { + local tile = square_x(pos.x, pos.y).get_tile_at_height(pos.z) + ASSERT_TRUE(tile != null) + ASSERT_FALSE(tile.has_ways()) + } + + RESET_ALL_PLAYER_FUNDS() +} + + +function test_way_planner_calls_are_independent() +{ + local pl = player_x(0) + local road = wayplanner_road() + + local first = way_planner_x.find_route(pl, coord3d(2, 2, 0), coord3d(5, 5, 0), road) + local kept = wayplanner_str(first) + + // a second, different plan in between must leave the first one alone + local other = way_planner_x.find_route(pl, coord3d(10, 2, 0), coord3d(13, 9, 0), road) + ASSERT_TRUE(other.len() > 0) + ASSERT_TRUE(wayplanner_str(other) != kept) + ASSERT_EQUAL(wayplanner_str(first), kept) + + local again = way_planner_x.find_route(pl, coord3d(2, 2, 0), coord3d(5, 5, 0), road) + ASSERT_EQUAL(wayplanner_str(again), kept) + + RESET_ALL_PLAYER_FUNDS() +} + + +function test_way_planner_matches_built_way() +{ + local pl = player_x(0) + local road = wayplanner_road() + local start = coord3d(2, 10, 0) + local end = coord3d(6, 13, 0) + + local route = way_planner_x.find_route(pl, start, end, road) + ASSERT_TRUE(route.len() > 0) + + // the tool plans the same route and builds it + ASSERT_EQUAL(command_x.build_way(pl, start, end, road, false), null) + + local planned = {} + foreach (pos in route) { + planned[pos.tostring()] <- true + local tile = square_x(pos.x, pos.y).get_tile_at_height(pos.z) + ASSERT_TRUE(tile != null) + ASSERT_TRUE(tile.has_way(wt_road)) + } + // and nothing outside the plan was built + for (local x = 2; x <= 6; ++x) { + for (local y = 10; y <= 13; ++y) { + local tile = square_x(x, y).get_tile_at_height(0) + if (tile != null && tile.has_way(wt_road)) { + ASSERT_TRUE(coord3d(x, y, 0).tostring() in planned) + } + } + } + + wayplanner_clear(route) + RESET_ALL_PLAYER_FUNDS() +} + + +function test_way_planner_bridge_crosses_water() +{ + local pl = player_x(0) + local road = wayplanner_road() + local bridge = bridge_desc_x.get_available_bridges(wt_road)[0] + ASSERT_TRUE(bridge != null) + + // a channel from edge to edge: there is no way around it + local setclimate = command_x(tool_set_climate) + for (local y = 0; y < 16; ++y) { + ASSERT_EQUAL(setclimate.work(pl, coord3d(8, y, 0), coord3d(8, y, 0), "" + cl_water), null) + } + + // without a bridge there is no route at all + local dry = way_planner_x.find_route(pl, coord3d(6, 5, 0), coord3d(10, 5, 0), road) + ASSERT_EQUAL(dry.len(), 0) + + // with one the planner crosses, and the crossing shows up as a step of more than one tile + local over = way_planner_x.find_route(pl, coord3d(6, 5, 0), coord3d(10, 5, 0), road, false, false, bridge) + ASSERT_TRUE(over.len() > 0) + ASSERT_EQUAL(over[0].tostring(), coord3d(6, 5, 0).tostring()) + ASSERT_EQUAL(over[over.len()-1].tostring(), coord3d(10, 5, 0).tostring()) + ASSERT_TRUE(wayplanner_longest_step(over) > 1) + + for (local y = 0; y < 16; ++y) { + ASSERT_EQUAL(setclimate.work(pl, coord3d(8, y, 0), coord3d(8, y, 0), "" + cl_mediterran), null) + } + + RESET_ALL_PLAYER_FUNDS() +} + + +function test_way_planner_prefer_parallel() +{ + local pl = player_x(0) + local road = wayplanner_road() + local start = coord3d(2, 6, 0) + local end = coord3d(13, 6, 0) + local line = wayplanner_row(5, 2, 13) + + // an existing line to plan a second one beside + ASSERT_EQUAL(command_x.build_way(pl, line[0], line[line.len()-1], road, true), null) + local cash = pl.get_current_cash() + local maintenance = pl.get_current_maintenance() + + // without the flag an existing way is the cheapest ground there is, so the planner + // climbs onto the line instead of running beside it + local off = way_planner_x.find_route(pl, start, end, road, false, false, null, null, false) + ASSERT_TRUE(off.len() > 0) + local shared = 0 + foreach (pos in off) { + if (pos.y == 5) { + shared++ + } + } + ASSERT_TRUE(shared > 0) + + // with it the route stays on its own row + local on = way_planner_x.find_route(pl, start, end, road, false, false, null, null, true) + ASSERT_EQUAL(on.len(), 12) + foreach (pos in on) { + ASSERT_EQUAL(pos.y, 6) + } + ASSERT_TRUE(wayplanner_str(on) != wayplanner_str(off)) + + // still from start to end, in that order + ASSERT_EQUAL(on[0].tostring(), start.tostring()) + ASSERT_EQUAL(on[on.len()-1].tostring(), end.tostring()) + + // leaving the argument out is the call of the previous version, and gives what it gave + local omitted = way_planner_x.find_route(pl, start, end, road) + ASSERT_EQUAL(wayplanner_str(omitted), wayplanner_str(off)) + + // and asking twice gives the same route + local again = way_planner_x.find_route(pl, start, end, road, false, false, null, null, true) + ASSERT_EQUAL(wayplanner_str(again), wayplanner_str(on)) + + // planning is still free and builds nothing + ASSERT_EQUAL(pl.get_current_cash(), cash) + ASSERT_EQUAL(pl.get_current_maintenance(), maintenance) + foreach (pos in on) { + local tile = square_x(pos.x, pos.y).get_tile_at_height(pos.z) + ASSERT_TRUE(tile != null) + ASSERT_FALSE(tile.has_ways()) + } + + wayplanner_clear(line) + RESET_ALL_PLAYER_FUNDS() +} + + +function test_way_planner_prefer_parallel_matches_tool() +{ + local pl = player_x(0) + local rail = way_desc_x.get_available_ways(wt_rail, st_flat)[0] + ASSERT_TRUE(rail != null) + local start = coord3d(2, 11, 0) + local end = coord3d(13, 11, 0) + local line = wayplanner_row(10, 2, 13) + + ASSERT_EQUAL(command_x.build_way(pl, line[0], line[line.len()-1], rail, true), null) + + // the way tool derives the flag from the tiles around the two clicks; both of them sit + // next to the existing line here, which is the case it derives it to be true + local route = way_planner_x.find_route(pl, start, end, rail, false, false, null, null, true) + ASSERT_TRUE(route.len() > 0) + ASSERT_EQUAL(command_x.build_way(pl, start, end, rail, false), null) + + local planned = {} + foreach (pos in route) { + planned[pos.tostring()] <- true + local tile = square_x(pos.x, pos.y).get_tile_at_height(pos.z) + ASSERT_TRUE(tile != null) + ASSERT_TRUE(tile.has_way(wt_rail)) + } + // and the tool built nothing beside the plan, apart from the line that was already there + for (local x = 2; x <= 13; ++x) { + local tile = square_x(x, 11).get_tile_at_height(0) + if (tile != null && tile.has_way(wt_rail)) { + ASSERT_TRUE(coord3d(x, 11, 0).tostring() in planned) + } + } + + wayplanner_clear(route) + wayplanner_clear(line) + RESET_ALL_PLAYER_FUNDS() +}