The Anatomy of Auto-explore in T-Engine

Moderator: Moderator

Post Reply
Message
Author
tiger_eye
Perspiring Physicist
Posts: 889
Joined: Thu Feb 17, 2011 5:20 am

The Anatomy of Auto-explore in T-Engine

#1 Post by tiger_eye »

Introduction
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
The engine includes all of the above except closed doors and exits. Since doors and exits are common to roguelikes, the auto-explore algorithm in the engine includes logic to handle them.

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)
,,,
A probable corner

Code: Select all

?#
#.
A probable wall

Code: Select all

#?#
...
We could let the AE algorithm cheat and have it check whether the latter two cases are actually walls, but where's the fun in that? ;-)

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

##?
.+?
##?
-- go to the nearest unexplored door only after all other unknown tiles and objects have been explored.
-- 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

##.
.+.
##.
Explored doors are deemed safe and may be opened on the way to a different target. They are never directly targeted.

Safety

Code: Select all

@****&..  <-- move to '&' to open the door more safely
#####+##
Opening a door with enemies behind it can be dangerous. AE will always try to approach all doors squarely--and more safely--from a cardinal direction, which gives the player a better view of what is behind the door. However, it will not step on a trap to do this.

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

&*.
@#?
Moving onto '*' puts us adjacent to an unknown tile, '?', which may be an ambush. Moving to '&' instead (if it isn't a trap) lets the player asymmetrically see tile '?'.

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.
A node consists of x, y, c (a unique index key), and the direction from which the node was explored (1-9). A node in the ToME module also holds the total movement cost for moving to that tile, which makes it more robust.

That's it for now... I hope this was helpful and that you are enjoying auto-explore! :-D

Post Reply