From d459948cef28e17a4008352da97eeb43dd58f93e Mon Sep 17 00:00:00 2001 From: zelgadis Date: Mon, 17 Dec 2007 10:03:47 +0000 Subject: Experimental "improved" explore algorithm which can be turned on by adding "explore_improved=true" to crawlrc. The intent is to reduce backtracking and zig-zagging during auto-explore. Currently only works with non-greedy explore since I can't yet figure out how to intelligently combine it with greediness. git-svn-id: https://crawl-ref.svn.sourceforge.net/svnroot/crawl-ref/trunk@3084 c06c8d41-db1a-0410-9941-cceddc491573 --- crawl-ref/source/acr.cc | 8 +++++++ crawl-ref/source/externs.h | 9 ++++++++ crawl-ref/source/files.cc | 4 ++++ crawl-ref/source/initfile.cc | 6 +++++ crawl-ref/source/player.cc | 17 +++++++++++++++ crawl-ref/source/travel.cc | 52 +++++++++++++++++++++++++++++++++++++++++++- 6 files changed, 95 insertions(+), 1 deletion(-) (limited to 'crawl-ref/source') diff --git a/crawl-ref/source/acr.cc b/crawl-ref/source/acr.cc index 5297da5f0d..117f9bd7df 100644 --- a/crawl-ref/source/acr.cc +++ b/crawl-ref/source/acr.cc @@ -3661,6 +3661,7 @@ static void move_player(int move_x, int move_y) { move_x = random2(3) - 1; move_y = random2(3) - 1; + you.reset_prev_move(); } const int new_targ_x = you.x_pos + move_x; @@ -3755,6 +3756,9 @@ static void move_player(int move_x, int move_y) if (!move_player_to_grid(targ_x, targ_y, true, false, swap)) return; + you.prev_move_x = move_x; + you.prev_move_y = move_y; + move_x = 0; move_y = 0; @@ -3766,7 +3770,11 @@ static void move_player(int move_x, int move_y) // BCR - Easy doors single move if (targ_grid == DNGN_CLOSED_DOOR && Options.easy_open && !attacking) + { open_door(move_x, move_y, false); + you.prev_move_x = move_x; + you.prev_move_y = move_y; + } else if (!targ_pass && !attacking) { stop_running(); diff --git a/crawl-ref/source/externs.h b/crawl-ref/source/externs.h index e97594c863..14707eeeb2 100644 --- a/crawl-ref/source/externs.h +++ b/crawl-ref/source/externs.h @@ -552,6 +552,9 @@ public: int x_pos; int y_pos; + int prev_move_x; + int prev_move_y; + int hunger; FixedVector equip; @@ -740,6 +743,9 @@ public: // changing x_pos and y_pos directly. void moveto(int x, int y); void moveto(const coord_def &c); + + coord_def prev_move() const; + void reset_prev_move(); bool in_water() const; bool can_swim() const; @@ -1643,6 +1649,9 @@ public: // How much more eager greedy-explore is for items than to explore. int explore_item_greed; + + // Some experimental improvments to explore + bool explore_improved; std::vector sound_mappings; std::vector menu_colour_mappings; diff --git a/crawl-ref/source/files.cc b/crawl-ref/source/files.cc index 1cd9febc60..049f410a39 100644 --- a/crawl-ref/source/files.cc +++ b/crawl-ref/source/files.cc @@ -909,6 +909,10 @@ bool load( dungeon_feature_type stair_taken, load_mode_type load_mode, you.transit_stair, stair_taken, DNGN_UNSEEN); unwind_bool ylev(you.entering_level, true, false); + // Going up/down stairs, going through a portal, or being banished + // means the previous x/y movement direction is no longer valid. + you.reset_prev_move(); + const bool make_changes = (load_mode != LOAD_RESTART_GAME && load_mode != LOAD_VISITOR); diff --git a/crawl-ref/source/initfile.cc b/crawl-ref/source/initfile.cc index 5e66290cc5..9a8242cef9 100644 --- a/crawl-ref/source/initfile.cc +++ b/crawl-ref/source/initfile.cc @@ -684,6 +684,8 @@ void game_options::reset_options() explore_item_greed = 10; explore_greedy = false; + + explore_improved = false; target_zero_exp = false; target_wrap = true; @@ -2412,6 +2414,10 @@ void game_options::read_option_line(const std::string &str, bool runscript) { explore_greedy = read_bool(field, explore_greedy); } + else if (key == "explore_improved") + { + explore_improved = read_bool(field, explore_improved); + } else if (key == "stash_tracking") { stash_tracking = diff --git a/crawl-ref/source/player.cc b/crawl-ref/source/player.cc index 2cfa244719..bc36fa055c 100644 --- a/crawl-ref/source/player.cc +++ b/crawl-ref/source/player.cc @@ -5271,6 +5271,9 @@ void player::init() x_pos = 0; y_pos = 0; + prev_move_x = 0; + prev_move_y = 0; + running.clear(); travel_x = 0; travel_y = 0; @@ -6227,7 +6230,21 @@ void player::moveto(const coord_def &c) crawl_view.set_player_at(c); if (real_move) + { + you.reset_prev_move(); dungeon_events.fire_position_event(DET_PLAYER_MOVED, c); + } +} + +coord_def player::prev_move() const +{ + return coord_def(prev_move_x, prev_move_y); +} + +void player::reset_prev_move() +{ + prev_move_x = 0; + prev_move_y = 0; } bool player::asleep() const diff --git a/crawl-ref/source/travel.cc b/crawl-ref/source/travel.cc index 750201af37..83c9cd1268 100644 --- a/crawl-ref/source/travel.cc +++ b/crawl-ref/source/travel.cc @@ -850,7 +850,57 @@ static int find_explore_status(const travel_pathfind &tp) static void explore_find_target_square() { travel_pathfind tp; - tp.set_floodseed(coord_def(you.x_pos, you.y_pos), true); + coord_def seed = you.pos(); + + // "Improved" explore: keep moving in a line along the same + // direction as the previous move, stop if we hit a barrier or + // something that would slow us down, and use *that* as the + // floodout seed. This is meant to: + // + // 1) Prevent explore from sticking its head in a room and then + // backing out even though the room has unexplored corners + // because there are unexplored squares closer than the corners. + // + // 2) Similarly, prevent the bevahior of going a little bit down + // a long, straight corridor only to back out of it because + // the nearest unexplored square in that corridor is + // LOS_RADIUS + 1 squares away, which is further away than + // another unexplored square which is in the opposite direction. + // + // 3) Prevent the annoying zig-zag when exploring open spaces. + // + // We stop at squres that would slow us down so that we won't slog + // across a bunch of shallow water just for the sake of going in + // a straight line. + // + // Not yet used with greedy explore because I can't figure out + // how to combined it with greediness in a way that won't display + // weird or uninuitive behavior. + if (you.running != RMODE_EXPLORE_GREEDY && Options.explore_improved + && (you.prev_move_x || you.prev_move_y)) + { + coord_def prev_move_delta = you.prev_move(); + + dungeon_feature_type feature; + do { + seed += prev_move_delta; + feature = grd(seed); + } while (is_travelsafe_square(seed.x, seed.y) + && is_traversable(feature) + && feature_traverse_cost(feature) == 1); + + seed -= prev_move_delta; + + // Has moving along the straight line found an unexplored + // square? If so, just use that square as the target. + if (!is_terrain_seen(seed + prev_move_delta) && seed != you.pos()) + { + you.running.x = seed.x; + you.running.y = seed.y; + return; + } + } + tp.set_floodseed(seed, true); coord_def whereto = tp.pathfind( static_cast(you.running.runmode) ); -- cgit v1.2.3-54-g00ecf