From a31218a1b9a010fc7d9cca533bd679cc7336b490 Mon Sep 17 00:00:00 2001 From: zelgadis Date: Wed, 19 Dec 2007 08:23:59 +0000 Subject: The first algorithm I tried for improving auto-explore simply increased the time taken to explore a level (and didn't reduce zig-zagging, like I thought it did). The next two algorithms I tried didn't work either; looks like avoiding back-tracking doesn't speed up auto-explore. So I got rid of all of that and concentrated just on reducing zig-zagging, which altough it has no in-game problems is visually annoying (to me, at least). Stats: For most level types the increase in the number of turns auto-explore takes is no more than 1%, but on "city" like leves (as in the Vaults) and in the Shaols the increase can be from 7% to 13%; in the Swamps it doesn't make any difference. git-svn-id: https://crawl-ref.svn.sourceforge.net/svnroot/crawl-ref/trunk@3094 c06c8d41-db1a-0410-9941-cceddc491573 --- crawl-ref/source/travel.cc | 156 ++++++++++++++++++++++++++++++--------------- 1 file changed, 103 insertions(+), 53 deletions(-) (limited to 'crawl-ref/source') diff --git a/crawl-ref/source/travel.cc b/crawl-ref/source/travel.cc index f95bbf0a75..7040fe1994 100644 --- a/crawl-ref/source/travel.cc +++ b/crawl-ref/source/travel.cc @@ -847,60 +847,35 @@ static int find_explore_status(const travel_pathfind &tp) return (explore_status); } +static int prev_travel_moves[2] = {-1, -1}; +static int prev_travel_index = 0; + +static struct coord_def prev_explore_target = coord_def(-30000, -30000); + +static int anti_zigzag_dir = -1; + +static void reset_zigzag_info() +{ + prev_explore_target = coord_def(-30000, -30000); + + prev_travel_moves[0] = -1; + prev_travel_moves[1] = -1; + prev_travel_index = 0; + anti_zigzag_dir = -1; +} + +static void set_target_square(const coord_def &target) +{ + you.running.x = target.x; + you.running.y = target.y; + + prev_explore_target = target; +} + static void explore_find_target_square() { travel_pathfind tp; - 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 behavior 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 squares 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 unintuitive 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); + tp.set_floodseed(you.pos(), true); coord_def whereto = tp.pathfind( static_cast(you.running.runmode) ); @@ -915,8 +890,63 @@ static void explore_find_target_square() if (whereto.x || whereto.y) { - you.running.x = whereto.x; - you.running.y = whereto.y; + // Anti-zigzag turned off, or found a greedy target so we + // don't need anti-zigzaging. + if (!Options.explore_improved || whereto != tp.unexplored_square()) + { + set_target_square(whereto); + reset_zigzag_info(); + return; + } + + // If the two previous travel moves are perpendicular to each + // other and the two previous explore targets are close to each + // other, then we're probably zigzaging. + if (prev_travel_moves[0] != -1 + && prev_travel_moves[1] != -1 + && (abs(prev_travel_moves[1] - prev_travel_moves[0]) % 4) == 2 + && grid_distance(prev_explore_target.x, prev_explore_target.y, + whereto.x, whereto.y) <= (LOS_RADIUS + 1)) + { + // Try moving along the line that bisects the right angle. + if (abs(prev_travel_moves[0] - prev_travel_moves[1]) == 6) + anti_zigzag_dir = 0; + else + anti_zigzag_dir = std::min(prev_travel_moves[0], + prev_travel_moves[1]) + 1; + + } + + // anti_zigzag_dir might have just been set, or might have + // persisted from the previous call to + // explore_find_target_square(). + if (anti_zigzag_dir != -1) + { + coord_def target = you.pos(); + coord_def delta = Compass[anti_zigzag_dir]; + + dungeon_feature_type feature; + do { + target += delta; + feature = grd(target); + } while (is_travelsafe_square(target.x, target.y) + && is_traversable(feature) + && feature_traverse_cost(feature) == 1); + + target -= delta; + + // Has moving along the straight line found an unexplored + // square? + if (!is_terrain_seen(target + delta) && target != you.pos()) + { + set_target_square(target); + return; + } + else + anti_zigzag_dir = -1; + } + + set_target_square(whereto); } else { @@ -959,7 +989,10 @@ void explore_pickup_event(int did_pickup, int tried_pickup) you.running == RMODE_EXPLORE_GREEDY? ES_GREEDY_PICKUP : ES_PICKUP; if ((Options.explore_stop & estop) && prompt_stop_explore(estop)) + { stop_delay(); + reset_zigzag_info(); + } } // Greedy explore has no good way to deal with an item that we can't @@ -986,6 +1019,7 @@ void explore_pickup_event(int did_pickup, int tried_pickup) } explore_stopped_pos = you.pos(); stop_delay(); + reset_zigzag_info(); } } @@ -1082,6 +1116,18 @@ command_type travel() // we turn off travel (find_travel_pos does that automatically). find_travel_pos(you.x_pos, you.y_pos, move_x, move_y); + if (you.running < 0 && (*move_x || *move_y)) + { + const int delta_to_dir[9] = { + 7, 0, 1, + 6, -1, 2, + 5, 4, 3 + }; + prev_travel_moves[prev_travel_index] = + delta_to_dir[(*move_x + 1) + 3 * (*move_y + 1)]; + prev_travel_index = !prev_travel_index; + } + if ((*move_x || *move_y) && you.running == RMODE_EXPLORE_GREEDY) { // Greedy explore should cut off on reaching an item. We can't @@ -3773,6 +3819,8 @@ void runrest::stop() if (need_redraw) viewwindow(true, false); + + reset_zigzag_info(); } bool runrest::is_rest() const @@ -3797,6 +3845,8 @@ void runrest::clear() runmode = RMODE_NOT_RUNNING; x = y = 0; mp = hp = 0; + + reset_zigzag_info(); } void runrest::check_hp() -- cgit v1.2.3-54-g00ecf