Autoexplore improvement


Although the central place for design discussion is ##crawl-dev on freenode, some may find it helpful to discuss requests and suggestions here first.

Lair Larrikin

Posts: 18

Joined: Tuesday, 14th January 2014, 20:24

Post Tuesday, 14th January 2014, 20:35

Autoexplore improvement

As you already know, autoexplore is not terribly efficient, and I think that a minor tweak could greatly improve its efficiency : Whenever autoexplore has to chose between two (or more) unexplored tiles, it should choose the farther away from the center of the map.

This way, it would more or less make a spiral from the edges to the center of the map, and reduce useless movements across the map.

Mines Malingerer

Posts: 36

Joined: Saturday, 26th October 2013, 03:36

Post Tuesday, 14th January 2014, 21:47

Re: Autoexplore improvement

Until a bit of exploration is done, it isn't always obvious which direction is towards or away from the center of the map.
I assume auto explore shouldn't be deciding which way to go based on info the player doesn't have. So you'd need to consider the currently explored portion and have an algorithm to determine where the center of the map appears to be to the player... right?
User avatar

Dungeon Master

Posts: 4031

Joined: Thursday, 16th December 2010, 20:37

Location: France

Post Tuesday, 14th January 2014, 21:48

Re: Autoexplore improvement

But the player doesn't know where the center is, so neither does autoexplore. Once you've explored enough, you can guess where the borders are and what is the direction of the center, but I don't see how autoexplore could do that without cheating.
<+Grunt> You dereference an invalid pointer! Ouch! That really hurt! The game dies...

Lair Larrikin

Posts: 18

Joined: Tuesday, 14th January 2014, 20:24

Post Tuesday, 14th January 2014, 21:49

Re: Autoexplore improvement

You already have this information by looking at the map, and I don't think that knowing the position of the center of the map would really help the player anyway.

edit: you don't have this information, my mistake. So is the indirect knowledge of this information really a problem ?
User avatar

Dungeon Master

Posts: 4031

Joined: Thursday, 16th December 2010, 20:37

Location: France

Post Tuesday, 14th January 2014, 22:06

Re: Autoexplore improvement

yes it is
<+Grunt> You dereference an invalid pointer! Ouch! That really hurt! The game dies...

Mines Malingerer

Posts: 45

Joined: Wednesday, 23rd October 2013, 00:00

Post Tuesday, 14th January 2014, 22:20

Re: Autoexplore improvement

galehar wrote:yes it is


What if point of reference was not Map center but Minimap center? That is known.

Lair Larrikin

Posts: 18

Joined: Tuesday, 14th January 2014, 20:24

Post Tuesday, 14th January 2014, 22:22

Re: Autoexplore improvement

It could also be always the same direction (for example first north, then when it's not possible to go north anymore east, then south, and west).

Zot Zealot

Posts: 1031

Joined: Friday, 26th April 2013, 19:52

Location: AZ, USA

Post Tuesday, 14th January 2014, 23:01

Re: Autoexplore improvement

A better question is whether the suggestion of picking the point furthest from the center is even an improvement period.

Lair Larrikin

Posts: 18

Joined: Tuesday, 14th January 2014, 20:24

Post Tuesday, 14th January 2014, 23:21

Re: Autoexplore improvement

It seems to me that autoexplore loses a lot of time going from on side to the other of the map to get the last unexplored tiles.

If it chooses to do check all the tiles in a given direction, it will avoid a lot of these movements.

Slime Squisher

Posts: 354

Joined: Tuesday, 14th January 2014, 23:33

Post Wednesday, 15th January 2014, 00:41

Re: Autoexplore improvement

Have you tried playing with the autoexplore options that exist? It sounds like some wall bias would go a long way towards solving/reducing your problem.

I happen to have my own problem with autoexplore, which is the tendency to put the player in bad positions. While usually not severe, an extra couple steps to break LOS is frequently a detriment, and on rare occasions it can put you in a deadly situation that would otherwise have been easily avoidable (entering a room incorrectly is fine and dandy until you happen upon the room that has Grinder and 2 orc priests).

Explore_wall_bias helps with this somewhat, as hugging walls keeps you closer to the corners and hallways that are paramount to survival, but it still often gives monsters free turns they wouldn't get if the player had explored a bit more carefully (albeit in different situations and for different reasons than default autoexplore), and it is of course reckless about running straight into narrow entranceways rather than standing back from them and peeking inside first.

So my suggestion is a sort of "distance bias", not unlike the movement patterns used by monsters with ranged attacks. It would favor standing in spaces farther from unexplored territory, preferring newly revealed spaces to be on the edge of LOS. I'm sure this would often be less efficient use of turns, but that's kind of the point (the logical extreme "ideal" version of this would mean moving such that only 1 new space was explored each turn, always at the edge of LOS, thus minimizing possible danger) and I don't use autoexplore when I am worried about turncount anyway.

For this message the author TheDefiniteArticle has received thanks: 3
and into, DracheReborn, Sar

Swamp Slogger

Posts: 147

Joined: Thursday, 29th August 2013, 02:22

Post Wednesday, 15th January 2014, 05:41

Re: Autoexplore improvement

what about if we add a [shift] or [ctrl] modifier to autoexplore that toggles "safe-exploration" along the lines of what the post above me describes but retains the original functionality without the modifier?
User avatar

Dungeon Master

Posts: 4031

Joined: Thursday, 16th December 2010, 20:37

Location: France

Post Wednesday, 15th January 2014, 12:34

Re: Autoexplore improvement

Let me explain how the autoexplore algorithm works. Starting from the player position, it "floods" the level. That is, a recursive function find all reachable cells in order of proximity to the player. As soon as it finds an unexplored cell, it is set as a travel destination, and the player moves toward it until it is seen. This is the basics.
Now, we have greedy explore, to handle autopickup. When an unexplored cell is found, it is stored as a possible destination, but the flooding continue in search for greedy cells (containing autopickup items or unvisited stacks). Autoexplore will go pick items even if they are farther than unexplored cells. How much farther is configured with explore_item_greed (default:10). explore_wall_bias works in a similar way and gives a higher weight to cells adjacent to walls. The goal is to force autoexplore to finish visiting a room before moving on. Tests were not very conclusive when this was introduced, and it also had a number of issues, which is why it's disabled by default.

So maybe you could put a negative bias to cells in the direction of the center of the known map, but that doesn't sound very simple and I'm not sure if it would be really better. Regarding the "careful" explore idea, it's more about travel than exploration actually. There is already a little hack to prevent travel from cutting unexplored corners to reduce the risk for ambush. Maybe some similar stuff could be added for doors, but that doesn't sound easy. Tweaking travel to minimize the rate of cells coming into LOS seems a bit overkill and hard.
<+Grunt> You dereference an invalid pointer! Ouch! That really hurt! The game dies...

For this message the author galehar has received thanks: 2
battaile, WalkerBoh

Tomb Titivator

Posts: 853

Joined: Thursday, 29th August 2013, 18:39

Post Wednesday, 15th January 2014, 15:56

Re: Autoexplore improvement

Just prove P=NP and solve travelling salesman(with incomplete information) already.

Slime Squisher

Posts: 354

Joined: Tuesday, 14th January 2014, 23:33

Post Wednesday, 15th January 2014, 21:30

Re: Autoexplore improvement

galehar wrote:There is already a little hack to prevent travel from cutting unexplored corners to reduce the risk for ambush.

I'd be interested in more information about this, if you have it.
User avatar

Dungeon Master

Posts: 4031

Joined: Thursday, 16th December 2010, 20:37

Location: France

Post Wednesday, 15th January 2014, 23:23

Re: Autoexplore improvement

There. As you can see, there's quite a bit of logic involved even for such a simple case.
edit: seems the link doesn't work. It's line 1833.

  Code:
    // Check whether this step puts us adjacent to any grid we haven't ever
    // seen or any non-wall grid we cannot currently see.
    //
    // .tx      Moving onto t puts us adjacent to an unseen grid.
    // ?#@      --> Pick x instead.

    // Only applies to diagonal moves.
    if (rmode == RMODE_TRAVEL && *move_x != 0 && *move_y != 0)
    {
        coord_def unseen = coord_def();
        for (adjacent_iterator ai(dest); ai; ++ai)
            if (!you.see_cell(*ai)
                && (!env.map_knowledge(*ai).seen()
                    || !feat_is_wall(env.map_knowledge(*ai).feat())))
            {
                unseen = *ai;
                break;
            }

        if (unseen != coord_def())
        {
            // If so, try to use an orthogonally adjacent grid that is
            // safe to enter.
            if (youpos.x == unseen.x)
                new_dest.y = youpos.y;
            else if (youpos.y == unseen.y)
                new_dest.x = youpos.x;

            // If the new grid cannot be entered, reset to dest.
            // This means that autoexplore will still sometimes move you
            // next to a previously unseen monster but the same would
            // happen by manual movement, so I don't think we need to worry
            // about this. (jpeg)
            if (!_is_travelsafe_square(new_dest)
                || !feat_is_traversable_now(env.map_knowledge(new_dest).feat()))
            {
                new_dest = dest;
            }
#ifdef DEBUG_SAFE_EXPLORE
            mprf(MSGCH_DIAGNOSTICS, "youpos: (%d, %d), dest: (%d, %d), unseen: (%d, %d), "
                 "new_dest: (%d, %d)",
                 youpos.x, youpos.y, dest.x, dest.y, unseen.x, unseen.y,
                 new_dest.x, new_dest.y);
            more();
#endif
        }
    }
<+Grunt> You dereference an invalid pointer! Ouch! That really hurt! The game dies...
User avatar

Ziggurat Zagger

Posts: 4478

Joined: Wednesday, 23rd October 2013, 07:56

Post Thursday, 16th January 2014, 10:51

Re: Autoexplore improvement

galehar wrote:explore_wall_bias works in a similar way and gives a higher weight to cells adjacent to walls.

What kind of values are usable for this? The Options Guide says
  Code:
 Adjusts how much autoexplore favours attempting to discover room
perimeters and corners. At higher values, autoexplore will more
heavily favour visiting squares that are next to walls; at 0 it
will not favour them at all.

What should I try for higher values: 1, 10, 100, something else?
DCSS: 97:...MfCj}SpNeBaEEGrFE{HaAKTrCK}DsFESpHu{FoArNaBe}
FeEE{HOIEMiAE}GrGlHuWrGnWrNaAKBaFi{MiDeMfDe}{DrAKTrAMGhEnGnWz}
{PaBeDjFi}OgAKPaCAGnCjOgCKMfAEAtCKSpCjDEEE{HOSu
Bloat: 17: RaRoPrPh{GuStGnCa}{ArEtZoNb}KiPaAnDrBXDBQOApDaMeAGBiOCNKAsFnFlUs{RoBoNeWi
User avatar

Dungeon Master

Posts: 4031

Joined: Thursday, 16th December 2010, 20:37

Location: France

Post Thursday, 16th January 2014, 11:05

Re: Autoexplore improvement

It was set to a default value of 10 when introduced, before being disabled. So I'd say it's a good start.
<+Grunt> You dereference an invalid pointer! Ouch! That really hurt! The game dies...

For this message the author galehar has received thanks: 2
rchandra, Sprucery
User avatar

Dungeon Master

Posts: 162

Joined: Sunday, 29th May 2011, 10:18

Post Monday, 20th January 2014, 01:28

Re: Autoexplore improvement

johlstei wrote:Just prove P=NP and solve travelling salesman(with incomplete information) already.


If you want to walk on every square, exploring the crawl map is the Canadian traveller problem (CTP).

Suppose you want to merely wish to observe every square with minimal cost and you have full knowledge of the map. Since crawl has line of sight, when you stand on a particular square, you observe several squares. If you traveled via teleportation, this would be a version of the set cover problem, with a restriction on set composition. If you have to walk between squares to make your observations, it starts to look like some perverse version of the warehouse location problem.

For this message the author brendan has received thanks: 3
Arrhythmia, johlstei, MIC132

Slime Squisher

Posts: 354

Joined: Tuesday, 14th January 2014, 23:33

Post Monday, 20th January 2014, 18:17

Re: Autoexplore improvement

Sprucery wrote:
galehar wrote:explore_wall_bias works in a similar way and gives a higher weight to cells adjacent to walls.

What kind of values are usable for this? The Options Guide says
  Code:
 Adjusts how much autoexplore favours attempting to discover room
perimeters and corners. At higher values, autoexplore will more
heavily favour visiting squares that are next to walls; at 0 it
will not favour them at all.

What should I try for higher values: 1, 10, 100, something else?

If I read the code correctly, it ranges from 0 to 1000. Currently my preference is for 200. It's hard to say anything really helpful though, as the behaviour can seem strange/unexpected until you get a handle on it. I'm still playing around with different numbers and it's all rather unscientific because as this thread demonstrates nobody cares about crawl's autoexplore.
User avatar

Dungeon Master

Posts: 4031

Joined: Thursday, 16th December 2010, 20:37

Location: France

Post Monday, 20th January 2014, 22:19

Re: Autoexplore improvement

TheDefiniteArticle wrote:If I read the code correctly, it ranges from 0 to 1000. Currently my preference is for 200. It's hard to say anything really helpful though, as the behaviour can seem strange/unexpected until you get a handle on it. I'm still playing around with different numbers and it's all rather unscientific because as this thread demonstrates nobody cares about crawl's autoexplore.

There's a wizmode command (&O) to benchmark autoexplore. Improving the efficiency of autoexplore isn't a priority, but it's still good. Testing the wall bias option, suggesting a default value and pointing out at its flaws would be helpful.
200 seems huge though. It's a distance, 200 is 5 times the maximum width of a level. The value for greedy pickup is 10.
<+Grunt> You dereference an invalid pointer! Ouch! That really hurt! The game dies...

Bim

Crypt Cleanser

Posts: 700

Joined: Wednesday, 5th January 2011, 15:51

Post Monday, 20th January 2014, 23:53

Re: Autoexplore improvement

Not to throw on problems, but my biggest problem with autoexplore is with electric eels. If you use autoexplore, you can often end up with an eel being able to get one hit in, which can be quite deadly for fragile chars.
I know the idea is not to use AE as much, but it still annoys me somewhat.
2012 Winner of fewest proposed ideas implemented by devs.
User avatar

Tomb Titivator

Posts: 778

Joined: Thursday, 13th March 2014, 20:15

Post Monday, 31st March 2014, 13:23

Re: Autoexplore improvement

galehar wrote:
TheDefiniteArticle wrote:If I read the code correctly, it ranges from 0 to 1000. Currently my preference is for 200. It's hard to say anything really helpful though, as the behaviour can seem strange/unexpected until you get a handle on it. I'm still playing around with different numbers and it's all rather unscientific because as this thread demonstrates nobody cares about crawl's autoexplore.

There's a wizmode command (&O) to benchmark autoexplore. Improving the efficiency of autoexplore isn't a priority, but it's still good. Testing the wall bias option, suggesting a default value and pointing out at its flaws would be helpful.
200 seems huge though. It's a distance, 200 is 5 times the maximum width of a level. The value for greedy pickup is 10.


Looks like ~70 is the highest value for explore_wall_bias (tried with 1000, 200, 100, 90, 80, 70, 60, 40, 20, 0).
At higher values autoexplore path is kinda "smarter". For my options I use explore_wall_bias = 35.

Maybe this option helps for autoexplore improvement
  Code:
explore_improved = false
        If set to true explore will attempt to reduce zig-zagging during
        auto-explore. On average it increases the number of turns taken
        by about 0.9%, sometimes actually speeding it up slightly and
        sometimes increasing the turns taken by up to 5%, with
        pathological cases causing a 13% increase.
I keep it true. But I guess you can adjust it when entering new dlvl (if level is an open area then set true, if level is with a lot of hallways and rooms set to false).
Last edited by Eyesburn on Tuesday, 1st April 2014, 01:53, edited 1 time in total.
~online scoring~

Pig's in zen
Pig is nude
Unashamed

For this message the author Eyesburn has received thanks:
galehar
User avatar

Dungeon Master

Posts: 4031

Joined: Thursday, 16th December 2010, 20:37

Location: France

Post Monday, 31st March 2014, 13:48

Re: Autoexplore improvement

Eyesburn wrote:Looks like ~70 is the highest value for explore_wall_bias (tried with 1000, 200, 100, 90, 80, 70, 60, 40, 20, 0).
At higher values autoexplore path is kinda "smarter". For my options I use explore_wall_bias = 35.

Interesting. Have you tested it in unusual levels, like Abyss, Shoals or Slime?
<+Grunt> You dereference an invalid pointer! Ouch! That really hurt! The game dies...
User avatar

Ziggurat Zagger

Posts: 4478

Joined: Wednesday, 23rd October 2013, 07:56

Post Monday, 31st March 2014, 14:04

Re: Autoexplore improvement

That makes me curious: does someone use autoexplore in Abyss or Slime?
DCSS: 97:...MfCj}SpNeBaEEGrFE{HaAKTrCK}DsFESpHu{FoArNaBe}
FeEE{HOIEMiAE}GrGlHuWrGnWrNaAKBaFi{MiDeMfDe}{DrAKTrAMGhEnGnWz}
{PaBeDjFi}OgAKPaCAGnCjOgCKMfAEAtCKSpCjDEEE{HOSu
Bloat: 17: RaRoPrPh{GuStGnCa}{ArEtZoNb}KiPaAnDrBXDBQOApDaMeAGBiOCNKAsFnFlUs{RoBoNeWi
User avatar

Ziggurat Zagger

Posts: 5832

Joined: Thursday, 10th February 2011, 18:30

Post Monday, 31st March 2014, 14:09

Re: Autoexplore improvement

Add a configuration to default tab to work like autoexplore when no enemies are visible.
"Be aware that a lot of people on this forum, such as mageykun and XuaXua, have a habit of making things up." - minmay a.k.a. duvessa
Did I make a lame complaint? Check for Bingo!
Totally gracious CSDC Season 2 Division 4 Champeen!
User avatar

Ziggurat Zagger

Posts: 5832

Joined: Thursday, 10th February 2011, 18:30

Post Monday, 31st March 2014, 14:10

Re: Autoexplore improvement

Sprucery wrote:That makes me curious: does someone use autoexplore in Abyss or Slime?


Auto explore in slime helps me find stairs down.
"Be aware that a lot of people on this forum, such as mageykun and XuaXua, have a habit of making things up." - minmay a.k.a. duvessa
Did I make a lame complaint? Check for Bingo!
Totally gracious CSDC Season 2 Division 4 Champeen!
User avatar

Tomb Titivator

Posts: 778

Joined: Thursday, 13th March 2014, 20:15

Post Monday, 31st March 2014, 14:24

Re: Autoexplore improvement

galehar wrote:Interesting. Have you tested it in unusual levels, like Abyss, Shoals or Slime?
Oh, nope, I have not tried; Im not that familiar with wiz mod, Im kinda newbie in DCSS.
I was interested too in how to improve autoexplore so I've stumbled on this topic (while I was stumbling, I have learnt some other cool stuff :) ).

My observation on explore_wall_bias was mostly about autoexplore path and number of turns.
Values: 1000, 200, 100, 90, 80, 70, have same characteristics.
For values <70 those characteristics starts to change.
~online scoring~

Pig's in zen
Pig is nude
Unashamed

Return to Game Design Discussion

Who is online

Users browsing this forum: No registered users and 8 guests

cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software for PTF.