Pathfinding and Navigation.

[Bear]

In a game with large(ish) levels, autoexplore and pathfinding are very handy features.  But how ought they work?

Autoexplore is implementable as: First, find the nearest walkable known square that has a walkable unknown neighbor.  Second, plan the shortest walkable path to it and take a step on that path.  Rinse, repeat. 

That's not too much trouble, but while autoexploring by that algorithm, your guy will be making choices about which of several unknown areas to explore first, and is likely to do them in an inefficient order - leaving bits and pieces that he'll have to cross the whole level later to take a look at.   The 'obvious' fix, planning out an optimal route, uses map information that isn't revealed at the time the route is being planned.  The 'correct' fix, trying to optimize the route planned at each step based on only the information revealed by the time the step is to be taken, is Hard.

Here's another quandary.  In an autopath menu, one of your choices is 'downstairs', meaning find your way to a downstair.  If you don't know about any downstair, this would mean autoexplore until you find one, then go to it.  If you know the map of the whole level, this would mean going as directly as possible to a downstair.  Simple enough.

But there's that damnable inbetween state.  You know about a downstair (or whatever other navigation goal) that's on the far side of some unknown territory.  Should your autopath then assume that it can traverse that unknown territory, allow itself to be proven wrong, and keep rerouting as it discovers new squares it cannot traverse?  Or should it assume that it cannot traverse that unknown territory, plan a path through known walkable squares, and allow itself to be proven wrong and keep rerouting as it discovers new squares that it can traverse?  Should it warn 'cannot guarantee optimal path based on current knowledge of map' and allow the user to opt out?   

The first way could reveal more unexplored territory and wind up being a lot faster ... but then again, it could expose your character to more unknown risks and wind up being a "longer shortcut."  The second way minimizes unknown risks and puts an upperbound on route time, but might take a lot longer than necessary.  Either way might incidentally reveal a new downstair not previously known and if so, should divert pathfinding to the new target. 

Ultimately, these are all character decisions, and should be options the player can set in some kind of autoexplore/autopath submenu.  Do they matter enough for players to care about?  Would they matter enough if there were a 'speedrunner' subgame with a competition among players to produce runthroughs of given scenarios minimizing turncount?

[Kevin Granade]

Take a step back, why are your levels so big that you feel the need to have this feature?
This is only partially a rhetorical question, if the answer is "no reason", you should just shrink the levels and not have autoexplore.
If you have good reasons to have levels that big, those reasons will influence what the correct solution for your situation is.

One question I have enough context to respond to is the "find me a bla" question.  If you're searching for something, then exploring and potentially running into trouble is an expected outcome.  If routing to a known feature though, you're actually invoking a different feature that just happens to be implemented similarly, and I'd generally expect that the player isn't "looking for trouble" when invoking this feature.  However if they happen to notice a feature of the same kind along the way, rerouting to it is likely a good option.

[reaver]

I don't think it really matters if you superoptimize or just optimize, besides the personal problem-solving satisfaction My approach to stuff like that is code the solution the way you would do it in real life.

 

Ultimately, these are all character decisions, and should be options the player can set in some kind of autoexplore/autopath submenu.  Do they matter enough for players to care about?  Would they matter enough if there were a 'speedrunner' subgame with a competition among players to produce runthroughs of given scenarios minimizing turncount?

I don't really think players will care, unless in a speedrunner scenario which sounds like a nice subgame

[Bear]

Honestly, I would want autotravel/autoexplore features even if the levels were classic 78x20 claustrophobic Nethack levels. 

As to why the levels are the size they are....  Hm.  They're 80x80 for now.  And that's mostly because I just made a wild-assed guess how big they should be.  I could balance the game with smaller, I guess.  There are tradeoffs of course. 

With very small levels I'd worry more about game balance;  I strongly prefer persistent levels, meaning very limited item creation after the initial generation of the map.  But that means the player pretty much gets a smallish sample of what the random number generator gives, so you have to limit the randomness in order to be sure that the player can make a good kit for the endgame.  If the levels were very small I'd worry that the randomness of item generation would become so great as to compel the placement of some additional unvarying guaranteed items, or else in order to make a 'viable' kit likely, I'd have to cut out much of the potential variety of things generated.

[reaver]

Btw, I just realized that having devs in a competition for best autoexplore bots in a common framework with random maps and various map types/sizes with memory constraints, that would totally rock!

[Bear]

Is there still a "sharing code" area here? 

'Cos I've been working on navigation/pathfinding, and I *like* the code I've written over the last few days.  I'm kind of a fanatic about not repeating compute work like pathfinding searches unnecessarily, not checking monsters when it isn't their turn, etc, and it usually takes me a while to come up with a method I'm really pleased with.

It uses a "signpost" data structure that is essentially maps locations to the steppable distance to a goal.  So if you can see a signpost for a given goal, it's simple (constant time) to just follow it 'downhill' to the goal.  You can fill in the signposts using a breadth-first search (increasing radius from the goal) or using AStar (extending it until it covers the square of whatever is trying to pathfind to that goal at the moment).

The signposts have several neat properties that help them be general and efficient.

They can continue to exist between turns, so if you are still enroute to the same goal next turn you can continue to use the same signpost without doing another AStar search. 

They are shared among monsters, so different monsters trying to find their way to the same goal (at the same time or at different times) can use the same signpost assuming they have the same movement powers.

They can be extended after they are initially built.  If Ant 23 wants to pathfind to the nest center, it uses AStar to extend the 'nest center' signpost to cover Ant 23's location.  If Ant 34 later wants to pathfind to nest center, it can use the signpost and discover that Ant 34 is already in an area filled in when Ant 23 did its pathfinding, or it can use the signpost, discover that it needs to extend it - and efficiently reprioritize the frontier then do more AStar extending the signpost to cover its own location while taking advantage of any applicable work already done for Ant 23.

Finally, the 'goals' can be any arbitrary set of locations, so a signpost can give the shortest path to any downstair (or available food, or available weapon to pick up from the floor, etc) instead of the shortest path to a single location. This allows all monsters seeking a downstair (or food, or a weapon) to use the same signpost for it no matter where they are on the level.  AStar really shines here because it will efficiently fill in the area between the *nearest* goal square and the pathfinder seeking it. 

So, all around -- I'm thinking I found a very good, general, efficient way to handle goal seeking and pathfinding and I'm pleased with it.

I get annoyed about the way player pathfinding interacts with unknown squares though. Monsters don't have an unknown squares issue (it's their home after all), but for the player character it's different.  Uncovering a new square after a signpost has already been made assuming the player character can (or can't) navigate that square, and discovering that the assumption was wrong,  invalidates that signpost,  resulting in repeating searches. 

[reaver]

Your signposts then sound like local precalculated shortest-path queries. But how general are they? how different they are to http://www.roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps?

They assume monster knowledge of map and that it doesn't change, so you work with static data that you can apply any sort of precalculations to. What if the player starts mining? what if there is a tunnel collapse?

[Krice]

What if the player starts mining? what if there is a tunnel collapse?

Recalculate it. However I think autoexplore is way too complete solution for navigation. There are many other ways to make navigating easier and they are easier to implement, too. For example path to nearest item (or any object) (that the player can actually see).

[Bear]

I'm not assuming that the map doesn't change, but I'm still thinking about exactly how to handle it when that happens.  At worst, and for a first cut, I can just expire signposts whenever the map changes and eat the whole recalculation cost as various creatures call for signposts - it's no worse than many roguelikes do every turn anyway.  At best I am pretty sure that there is a way to recalculate exactly (and only) as much as needed to make the signpost consistent with the changed information.  But it's involved, has four different methods depending on what is changed (goal square added, goal square removed, wall added, or wall removed) and as frequently as the map doesn't change I may not code it.

Signposts, I guess, function very very much like Dijkstra Maps as far as pathfinding and routing.  But there are important differences.  The algorithm described for Dijkstra maps, if I'm reading it right, doesn't result in stepwise distance.  It results in some kind of approximation to it, but it's not really clear exactly what approximation from reading the description.  So when following a Dijkstra map you don't necessarily know exactly how many steps you will have to take to reach the goal.  Which could matter, I guess, though it certainly doesn't in my game now.  Finally the algorithm described assumes you're calculating all Dijkstra maps for the whole dungeon, whether you need all of them or every one of them or not.  The algorithm it gives is O(n^3) relative to the linear size of the dungeon, to do the same thing I'm doing with combining AStar searches. 

If a signpost actually covers the whole dungeon (by using AStar searches to reach out to each monster that needs access to it), it will have taken O(n^2) relative to the linear size of the dungeon to calculate, but one of the key properties of signposts is that they are computed incrementally - signposts are only extended as much as they need to be for the purpose they're being used for at a given moment, so it's highly unlikely that even half of that  N^2 would ever get sunk into calculating one, unless it were justified by literally every creature on the map needing to use it. And if every creature on the map is using it, then it is likely that they won't be using any others at all. 

[reaver]

Dijkstra maps are pretty much distance transforms over a grid that take obstacles into account. It doesn't have to be an approximation. The distance metric depends on whatever movement scheme you code in your roguelike: diagonal and horz/vert movement treated the same? metric is the maximum norm. diagonal costs 2 and horz/vert costs 1? metric is 1-norm (manhattan distance). diagonal costs sqrt(2)? metric is euclidean distance (even though you'd have to calculate it stepwise). When following the map, at each given point you know exactly the required movement cost to go to the goal point. The naive version is O(n^2), as you just process a part of the map per goal point.

If I understand the signposts correctly, they are and function exactly like dijkstra maps, but possibly using a different method to calculate.

[Bear]

Okay.  I'm perfectly willing to call signposts an implementation of Dijkstra maps.

But it's an implementation I'm *satisfied* with, because it doesn't waste effort on building maps that won't be needed, it doesn't waste effort on extending maps that will be needed to cover squares where they won't, and it visits each square ONCE when extending the signpost instead of a number of times proportional to the width of the dungeon map.

I had looked at the article on Dijkstra maps before, and I had more or less stopped reading at the point where it said I should build each one of them by iterating over the whole dungeon map a number of times proportional to the width of the whole dungeon map.  I realize I'm kind of fanatical or even a bit irrational on this point, but .... no.  If it's any kind of map, the right way to build it is by visiting each square ONCE.  Further, you shouldn't be mapping any squares whose values you won't actually use if you can help it.

[Pickledtezcat]

Interesting, that's the first time I've read about the Dijkstra maps and they sound very useful, though I agree with the idea that you'd not want to calculate them for the entire dungeon every turn.

Why not consider the following:

You can use a cropped square to limit the size of your Dijkstra maps. For example if you're only calculating an area 25x25 squares around the player it'll take much less processing time than a 80x80 grid. You could limit the size of the square to just a bit larger than the player's FOV as it doesn't really matter what monsters are doing when you can't see them. Though from reading a few posts here I think different people have different ideas about simulation vs approximation, and would like to see all monsters simulated whether they are visible or not. As far as I'm concerned a monster can stand staring at a brick wall for hours on end if I can't see him doing it, but others may disagree.

You could also try breaking the map up in to sections (perhaps 5x5 squares) and get an approximation of the contents of that section. Does it have a door? Does it have friendly monsters? Does it contain the player? These sections could then form the basis for a Dijkstra map at a lower resolution than a per tile calculation. An 80x80 map would need only 16x16 Dijkstra maps in this case. If you were going to do this it'd be best to take it in to account during the level generation algorithm, so that the level is generated at a 5x5 resolution. That'd stop sections containing parts of different rooms. My own game is designed this way, though I'm using 4x4 sections. This allows me to have a large map while many of my calculations (for FOV, pathfinding, etc...) can be carried out at a lower resolution, saving processing time.

I hope to use both these methods to ensure I have fairly intelligent monsters and fast pathfinding. It's worth mentioning that the first method can also be used when using A* as it's not usually necessary to add every tile from your map in to the graph, only a bounded box that contains the agent, the target and a small border to allow for the possibility of backtracking. You can also do a simple Bresenham's line check as a prelude to an A* search to save time or you can include this in your normal LOS/FOV routine.

[Bear]

Incremental expansion only as needed is already better than expanding a map within a cropped square. 

Breaking up the map into 5x5 "chunks" is an interesting idea, though; I encourage you to try it and see if it makes pathfinding a lot better.  It seems like you have to traverse the map at 1x1 scale to get your 5x5-scale grids, although that's a cost that could be shared over all pathfinding until the map changes.  It seems that even with 5x5 grids, there are already a wide variety of possible distinct classes of connectivity that your path search would need to understand. And it seems that each time a critter found its way into a particular 5x5 scale grid it would still have to traverse the grid at 1x1 scale in order to figure out what to do with the results from the 5x5-scale search.  On the other hand you'd get at least a tenfold increase (maximum of 25fold) in speed for covering area and building long-range paths while the information is cached.  So there are benefits and tradeoffs and it's worth testing IMO to see how well it works and whether it's worth the increased code complexity.

There are essentially three conventional notions of 'distance' on a roguelike square-gridded map.  Manhattan distance counts diagonals as costing 2 (or defines only orthogonal movement), and the 'radius' is essentially a diamond.  Chebyshev distance counts diagonals as costing 1, and the 'radius' is essentially a square.  Stepwise-euclidean treats diagonals as costing sqrt(2), and the radius is an octohedron with points at the orthogonals and diagonals.  Some games have monsters that play with the differences, like 'grid bugs' using Manhattan distances in nethack, where everything else including the player uses Chebyshev distances.  Others play with differences in other ways, like some creatures being able to fly over, burrow through, or unlock and open doors and other barriers.  Anyway, each monster that has different movement powers or costs needs its own set of signposts or Dijkstra maps that gives accurate distances or movement costs for that monster class. 

One thing I'm thinking of now, though, and will implement today, is using a map of added square traversal costs as an input when building a signpost.  The motivating scenario is that while signposts are supposed to give travel costs, basic movement cost for traversing a square may not be the main cost a given creature is concerned about.  A creature trying to 'flee' wants to reach a 'safety' goal with the least cost, but will count exposure to attacks from the player as having a substantial cost. It would prefer to stay out of reach or out of range as much as it can on the way to safety.  So we should build a 'danger map' giving the approximate level of player-danger associated with each map square, then ADD its values to the simple distances as extra square-traversal costs for a signpost to 'safety' goal squares.

And that leads to yet more tactical considerations.  In proportion to their Intelligence and cowardice, monsters should always prefer to stand on squares whose route-to-safety has a low cost (as measured in danger) when there's a choice of squares for them to stand on. 

[reaver]

Okay.  I'm perfectly willing to call signposts an implementation of Dijkstra maps. But it's an implementation I'm *satisfied* with

Don't get me wrong, I like the incremental updates and optimisation, I just had to point out previous work But I still think handling dynamic situations is far more important, and Dijkstra maps just doesn't cut it, and probably doesn't scale with many goals either.

I'm not sure about the chunks idea, as it sounds quite a bit restrictive for map generation purposes. What about cavern-like levels and towns?

And that leads to yet more tactical considerations.  In proportion to their Intelligence and cowardice, monsters should always prefer to stand on squares whose route-to-safety has a low cost (as measured in danger) when there's a choice of squares for them to stand on. 

The other thing that I've read you can do with that is to specify how long-term or short-term the strategy is: using a short term solution (e.g. what's the cumulatively safest path away from @ that is 3 tiles long),  a monster might go in the opposite direction of the player, to avoid the encounter, but the player can trap it this way in a corner. Using a longer term solution ( what's the cumulatively safest path away from @ that is 15 tiles long) the monster could attempt to walk past the player but the increased risk could yield as a reward a safer path longer term.

I'm sure I've read that somewhere in RogueBasin dammit.

[Pickledtezcat]

Using chunks for levels is definitely a design choice, it has to be in from the beginning or it's just not viable. One reason I use it is because I'm making a 3d graphical roguelike with a chunk based tileset, so it's something I've been using from the very beginning. I worked out connectivity for each possible chunk in advance so that I can do pathfinding at a lower resolution if needed. For people using a traditional 1x1 grid it's probably not going to work.

I think if your level is only 78x20 tiles you don't have to worry about the costs involved in generating influence maps or A* pathfinding.

However, something thing you could do if you're worried about the cost of generating lots of influence maps for a extra large sized level is just do a simple floodfill from the player's location. Rooms separated by a locked or closed door wouldn't need to be calculated. A floodfill could also be run once on startup and again each time a door is opened or the map changes, so you wouldn't need to do it every turn. You could also limit the number of types of influence maps generated to those required by the monsters currently in the level. If there are no stealth using monsters, you don't have to create a stealth map. As more rooms are opened, more area needs to be calculated, but by this time, there are far fewer living monsters remaining, so probably few types of map required to be generated. You could combine the flood fill with the cropped area idea to further reduce the area calculated.

For an auto explore influence map you can still do it like this, and have two different routines. One is to actively seek out and open doors (closed doors would have a high influence rating) while another would be to avoid doors. I think people might like the option of auto exploring without opening doors at first.