The Tavern

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.

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?

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.

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 ?

yes it is

galehar wrote:yes it is

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

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).

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

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.

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.

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?

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.

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

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.

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 } }

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?

It was set to a default value of 10 when introduced, before being disabled. So I'd say it's a good start.

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.

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.

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.

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.

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).

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?

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

Add a configuration to default tab to work like autoexplore when no enemies are visible.

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

Auto explore in slime helps me find stairs down.

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.

The Tavern

Autoexplore improvement

Autoexplore improvement

Re: Autoexplore improvement

Re: Autoexplore improvement

Re: Autoexplore improvement

Re: Autoexplore improvement

Re: Autoexplore improvement

Re: Autoexplore improvement

Re: Autoexplore improvement

Re: Autoexplore improvement

Re: Autoexplore improvement

Re: Autoexplore improvement

Re: Autoexplore improvement

Re: Autoexplore improvement

Re: Autoexplore improvement

Re: Autoexplore improvement

Re: Autoexplore improvement

Re: Autoexplore improvement

Re: Autoexplore improvement

Re: Autoexplore improvement

Re: Autoexplore improvement

Re: Autoexplore improvement

Re: Autoexplore improvement

Re: Autoexplore improvement

Re: Autoexplore improvement

Re: Autoexplore improvement

Re: Autoexplore improvement

Re: Autoexplore improvement