The purpose of this article is to describe the behavior of auto-explore as implemented in t-engine, and to help module developers add auto-explore to their own games. I'm still tinkering with the auto-explore algorithm in the engine, so it may not perfectly reflect what is written below. I will work to fix this. Although the focus is not how to implement auto-explore from scratch, if you are doing so this article should still be very helpful. And, finally, this forum is, of course, a place to facilitate feedback, suggestions, and answering questions.
Legend
The following are common roguelike elements:
Code: Select all
. - floor
# - wall
$ - object
^ - trap
+ - closed door
> - exit
? - unknown tile
Targets of Exploration
Exploring is more than just moving around randomly. Some targets are higher priority than others, and after seeing or reaching a target, auto-explore may seek out a new target. Below are the possible targets listed from highest to lowest priority.
Objects
Objects on the floor or in a wall are top priority, and AE will go to objects even if there are closer unknown tiles (within reason).
-- don't target objects on map grids with "obj_seen" attribute.
-- go to objects in walls. If AE stops or begins when adjacent to object in wall, then set "obj_seen" attribute so we don't keep running to it.
-- if objects are automatically picked up (or are picked up by an NPC or destroyed while on the ground), then AE will seek a new target.
-- otherwise, stop when object is reached.
Unknown Tiles
To explore more cleanly and efficiently, certain unknown tiles are given higher priority and will be explored even if there are closer unknown tiles (within reason).
Solitary unknown tile
Code: Select all
,,,
,?, (where ',' are known tiles)
,,,
Code: Select all
?#
#.
Code: Select all
#?#
...

Once an unknown tile is explored, AE will choose a new target.
Doors
Opening a door always poses a risk, so AE only opens doors in very specific cases, and it tries to do so safely. We categorize a door in two ways: (1) Unexplored, which is adjacent to an unknown tile, and (2) Explored, in which all adjacent tiles are known.
Unexplored
Code: Select all
##?
.+?
##?
-- do not open the door when first approached.
-- only open the door when the player initiates AE while adjacent to the target door.
Explored
Code: Select all
##.
.+.
##.
Safety
Code: Select all
@****&.. <-- move to '&' to open the door more safely
#####+##
Exits
Exits are module-specific and can be ways to the next level, previous level, worldmap, etc. AE will target these when no other targets exits (that is, when the accessible level is fully explored).
-- if on an exit when AE is initiated, then go to a different exit
-- if interrupted on the way to an exit, then initiating AE again will go to the same target exit
While Exploring
Ambush
There is a common configuration for which the player (and AE) can take advantage of asymmetric LoS to prevent being ambushed:
Code: Select all
&*.
@#?
Traps
Known traps are avoided if at all possible while exploring. Only after exploring all other areas will AE try to move through a trap. Whether it should move onto the trap or stop before it moves onto it is up for debate

If a trap is discovered while exploring, it will also be avoided if possible.
Automated Actions and Borgs
It may be desirable to automate actions other than moving while performing auto-explore, and this is possible within the current framework. For example, the only place this is currently utilized is when opening doors: an instant action action that requires bumping into a door tile. Other possible examples include picking up items, periodically using talents, using talents in specific situations (such as disarming nearby trap), or bump-attacking lesser foes. It is conceivable that an ambitious module designer could create a fully-automated borg that can play the game with no or minimal user input.
How to Add Auto-Explore to Your Module
Currently, the best approach is to copy the file "engine/interface/PlayerExplore.lua" to your own module and then make the necessary modifications. Further development may be done at some point to make the file extensible, so copying the entire file won't be necessary.
-- add a way to check for exits and other targets as necessary.
-- add a way to check for closed doors (and uncomment door-specific code).
-- also add a way to check for open doors in "checkAutoExplore" to verify we opened the door.
-- if opening a door takes a turn (i.e., uses energy), then remove "no_energy = true" from "running.busy" table in "checkAutoExplore".
-- extra logic may be desired if auto-explore should--or shouldn't--be interrupted by things such as interesting terrain (it uses the same "runCheck" function as with running with the mouse).
-- automated behavior should probably go in "checkAutoExplore" (creating the table "self.running.busy" keeps auto-explore from moving or updating its counter)..
-- if terrain can have different movement costs (such as moving up a ladder is slow or down a chute is fast) or if moving diagonally takes takes more energy than moving cardinally, then you most likely want to copy the core functions used for the flood-fill in "modules/tome/class/interface/PlayerExplore.lua".
-- code any other behavior you want!
An Efficient Floodfill Algorithm
A floodfill algorithm is used to calculate the number of moves it will take to get to any given target tile, and it is used to calculate the best path. This or similar algorithms can also be known as pathfinding, breadth-first search, wavefront, wave propagation, monster flow; as well as Dijksra's, Akers', Lee's, Hadlock's, and Soukup's Algorithms. I call it floodfill for simplicity.
Right now the floodfill is done in lua, even though it could be done faster in C, as there are more advanced tricks we could utilize in C. If you've looked at the code, you may be wondering why there are 500 lines for functions that list adjacent tiles in different ways. Overkill? Perhaps. But, it does make the algorithm noticeably faster for large maps. Each tile may have 8 adjacent tiles, and we need to check if each of these tiles is in-bounds. We can make that task more efficient if we only list adjacent tiles that may not have been iterated over yet, and we do this by storing the direction from which the current tile was explored. For example, if the current tile was explored from a cardinal direction, then it only has 3 new tiles to iterate over! If it was explored from a diagonal direction, then it has 5 new tiles to iterate over. Even creating a list of all adjacent tiles is faster when utilizing directional information, because fewer conditionals are needed to check whether a given tile is in-bounds.
Code: Select all
nw n ne
\|/ 789
w--@--e <---> 4@6
/|\ 123
sw s se
....9 7....
-->@6 4@<--
....3 1....
.789 .../
..@6 7./.
./.3 4@..
/... 123.
That's it for now... I hope this was helpful and that you are enjoying auto-explore!
