Pathfinding and Navigation.

[Zireael]

I've found this: http://www.roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps

As I believe Djikstra and A* are comparable in performance, and I have a djikstra for Lua somewhere on my disk, how would the many maps presented in the article work?

[Bear]

I don't think he's calling them Dijkstra maps for anything having to do with using Dijkstra's algorithm to find them.  It sounds like he's iterating over the whole map multiple times to find them.  That said, you certainly can use Dijkstra's algorithm (breadth first search) and it'll be faster/better than the method he advises.   I haven't used them much yet, but by all accounts they work great for all kinds of purposes. 

I've just finished hacking an auxiliary cost map into my signposts, and now my signposts calculate minimum path costs to the goal taking into account the extra non-movement costs of traversing a square.  *And* takes the extra costs into account when prioritizing the frontier, so the 'radius' or 'breadth first' mode expands to the set of squares you can reach via equal costs rather than by equal travel distances. 

The auxiliary costs also affect AStar, meaning that it searches wherever the path cost plus heuristic estimate of remaining path cost is equal, taking the auxiliary costs of mapped squares (but not squares yet to be traversed) into account.  Mostly this makes AStar explore high-danger (high auxiliary cost) areas looking for a short way out of them even if that way doesn't lead immediately toward the pathfinding goal.  The "optimal path" can start with several steps directly away from the goal followed by normal movement around the room in hallways out of danger, rather than going straight across a high-danger room to a doorway that leads directly toward the goal. 

This makes me happy.  Critters are getting smarter.

[Pickledtezcat]

Are these sign posts like waypoints? That would be a fast alternative to chunk/grid based pathfinding/influence maps. Like how in 3d games grid based pathfinding is rearely used these days, instead using either polygon based walkmeshes or waypoint based navigation. I don't see any problem with using waypoint navigation in a grid based game.

You could write an algorithm to generate signposts for a map when it is created. The result would have monsters following each other around, rather than finding their own way, but it'd be a good way of reducing the resolution of influence maps or A*pathfinding.

Sounds good. Waypoints would also work well in auto explore.

[reaver]

It's not waypoints, but rather areas with precalculated best path information towards given goals (center of signposts), if I understand that correctly.

For actual waypoints, I've been thinking about something that works unfortunately only in typical roguelike dungeons (rooms/corridors):
If you representing the dungeon as a connectivity graph, door-to-door, then you can precalculate the minimum cost of going from a door to any other connected door, as well as the paths. Then, your critters, in order to travel far in the dungeon they can consult this reduced connectivity graph to figure out the best route, and when they reach the door that leads to the room of interest, they can run A* locally, limiting the search space to the room's tiles.

(The above has possibly been done before as it's a navigation mesh variant, if anybody has heard of it or/and knows extension to more "open" levels, I would love that)

[Pickledtezcat]

I guess it's getting a bit off topic, the original question was how to handle Autoexplore, though there was the question of "and pathfinding".

Personally I'd never use autoplay, if you're moving automatically, picking up items automatically, and fighting automatically, are you still really playing a game, or just watching a rather dull movie? It could be an interesting programming exercise, writing your own bot program, but if you're just running the built in autoplay feature I can't see the point. Or rather I'd be asking myself "What's so boring that I have to automate it?" If some part of the game is too boring that someone can't bear to play through it manually, shouldn't it be cut from the game, or replaced with something more interesting?

However, I'm in favor of fast movement in certain situations, like if you've got designated resting/healing areas that you have to backtrack to, or dungeons are part of an overworld map and you have to go out of the dungeon to go to town and sell your items/heal/learn new skills or whatever. In that case you should be able to move almost instantly to any tile you've already discovered if there are no monsters near by and there is an unblocked path to that point. When there are large levels, I hate having to backtrack in real time to pick up some loot that I though was worthless but now need, or to look again for a key I missed or a hidden door I didn't discover.

Waypoints or signposts would be good for that, with a waypoint being inactive if an active monster is too close, or it hasn't been seen yet.

On the other hand, if you're going to use autoplay, why not make a feature of it? Instead of having a main character controlled directly by the player, how about a small number of minions with custom autoplay options. Maybe you could even enter script directly in to the game from the UI to teach your minions how to play on the fly. Maybe that'd be a good 7DRL...

[Bear]

They aren't waypoints by themselves, but they are sure a useful component if you're building waypoints.

In simplest terms, a signpost is defined by a set of goal locations, and has the ability, given any location in the map, to tell the cost of the lowest-cost path from the given location to any of the set of goals. 

All the implementation, storage, map, efficient calculation algorithms, cached values, etc, is "detail" at some high level of algorithmic abstraction, which is why 'signposts' and 'dijkstra maps' are sort-of the same thing.  The absolute requirement is that they can tell you the cost of the lowest-cost path from any starting point on the map to a goal. 

You can use this in pathfinding your way from anywhere to the goal, simply by choosing your next available step based on whether its location has a lower path cost than the one you're on.  The most efficient path is the one that chooses the lowest available path cost at every step.   You can also use this the other direction pathfinding from the goal to any particular location, just by calculating a path from that location to the signpost and then reversing it.

If you want to implement waypoints in terms of them, that's fairly easy; you just set a signpost at each waypoint, make sure it has cached path-costs for all the steps on optimum paths to the nearest other connected waypoints, and then you can do your waypoint navigation using graph theory at a high level - where you say 'Mob 37 needs to get from region A to region K, and that involves going via waypoints W3, W8, W9, and W4...."  Then you'd use the signpost at W3 to tell the mob how to get from wherever it is in region A to waypoint W3, the signpost at W8 to tell it how to get from W3 to W8, the signpost at W4 to tell it how to get from W8 to W4, and then use W4 again with the reversal trick to calculate a path from W4 to its final destination in region K. 

So your long-range pathfinding can be done on a very simplified graph; the waypoints where paths can diverge are the only vertexes you need to consider, and of course they know the path costs to the locations of the vertexes they're connected to. So while doing long-range route planning you don't need to consider each square along the way.

[Bear]

Yeah, auto-play makes for a boring movie.  Or maybe a fascinating screensaver, I don't know which. 

With sufficient carefully-added randomness and logging though, it'll make a great fuzz-testing suite for finding bugs to stomp :-)

Auto-pathfind is not auto-play.  It's a way for the player to specify a play strategy at a higher level than one step at a time.  I want the player to be able to pick up a key in a room on level 6, and when she decides she wants to go back to a chest she left on level 3 to see if the key fits it, she should not have to mash a button for every square the character traverses.  That should be 'autopath - upstair' three times, then 'autopath - objects - chest'  once.  Or, depending on interface preferences, it could be a series of four mouse clicks.

If you're implementing a borg or a bot, then yes you need autopath in a way you don't for a human player.  But if the autopath is just doing strategy that the human decided on, I consider it to be the human who is the one playing the game.  Autopath doesn't (shouldn't, IMO) make decisions that matter.  If there's a single reason (ie, it matters) why a player would legitimately want to decide on one path over another, then either that decision needs to be something she can instruct the autopath system to make in her place, or she needs to not be using the autopath system.

Likewise, if on the way autopath is  interrupted six times by seeing a rat, then the player needs to decide to break off and chase them, or ignore them and keep going, or route around them as necessary, or just thwack them when they get in the way - either individually or as a pathfinding choice. If the automation serves to implement the players decisions, it's still the player's decisions that win or lose the game.  If the automation makes decisions for the player, that becomes the kind of problem you're concerned about.

[Eben]

I've used Djikstra maps that get recomputed each turn and they're not too computationally expensive. In my implementation (and my FOV and LOS) I used a strategy pattern to get the distance function. This allowed me to have creatures use 1 movement in all 8 directions but projectiles use actual radius distance with the same algorithm.

The projectiles do that because that's what people expect, even though it's not consistent with move distance. If the projectile max distance is far enough, the inconsistency rarely actually matters in a roguelike.

[Pickledtezcat]

Yeah, auto-play makes for a boring movie.  Or maybe a fascinating screensaver, I don't know which. 

With sufficient carefully-added randomness and logging though, it'll make a great fuzz-testing suite for finding bugs to stomp :-)

Auto-pathfind is not auto-play.  It's a way for the player to specify a play strategy at a higher level than one step at a time.  I want the player to be able to pick up a key in a room on level 6, and when she decides she wants to go back to a chest she left on level 3 to see if the key fits it, she should not have to mash a button for every square the character traverses.  That should be 'autopath - upstair' three times, then 'autopath - objects - chest'  once.  Or, depending on interface preferences, it could be a series of four mouse clicks.

If you're implementing a borg or a bot, then yes you need autopath in a way you don't for a human player.  But if the autopath is just doing strategy that the human decided on, I consider it to be the human who is the one playing the game.  Autopath doesn't (shouldn't, IMO) make decisions that matter.  If there's a single reason (ie, it matters) why a player would legitimately want to decide on one path over another, then either that decision needs to be something she can instruct the autopath system to make in her place, or she needs to not be using the autopath system.

Likewise, if on the way autopath is  interrupted six times by seeing a rat, then the player needs to decide to break off and chase them, or ignore them and keep going, or route around them as necessary, or just thwack them when they get in the way - either individually or as a pathfinding choice. If the automation serves to implement the players decisions, it's still the player's decisions that win or lose the game.  If the automation makes decisions for the player, that becomes the kind of problem you're concerned about.

That's what I meant by "fast movement", choose a destination and "warp" there but stop if you're interrupted by a monster or something else.
With a mouse controlled game it'd be easy enough, just use pathfinding to a target location.  (kind of like this: http://youtu.be/EngRPH4gs2I) You can have the movement take time, or be instantaneous. You can use visualization of the route as I did in my video or you can just give a message feedback saying that the route is valid or not. It's nice to have a route visualized before your proceed, it allows you to decide if the route that's being suggested is safe or not, and it also allows you to see if there is in fact a valid route or not.

If you're using keys only it's harder to select a route, though you could have a waypoint/signposts system where say pressing "g" for "go" will toggle waypoint movement and then you could use arrow keys to toggle through the rooms you've already visited (with a route visualization for each choice) and then press "g" again to be transported there rapidly, stopping if your route is interrupted. In that case you'd want to create and add the waypoints during level creation and make them active if certain prerequisites were met, such as all the tiles of a room being revealed, or a room being cleared of all enemies. If you've got maps which are not standard rectangular rooms you'd have to figure out a different system of way point placement, such as place a waypoint every 10 tiles in the x and y direction making a grid, if that position would place them inside a wall, find the nearest non wall square.

[Bear]

Actually showing the planned route and letting the player make a choice is good interface design.  I oughta do that.  But  for now I'll just scribble a note in my to-do file.   

I think automove needs to take some time - not a lot, but enough so the player can actually see the movements as opposed to having both character and all other creatures disappearing at one place and appearing at different places.  Maybe a quarter-second per square?  Maybe a half?  I've got 2 seconds per square now, and that's clearly too slow.  But the monsters will all be rearranged when the character arrives at destination, and if major monsters just "appear" or "disappear" I think it's important that the player should be able to see where they came from or went.  This is especially the case when some monsters are noticeably faster than the player character.

[Kevin Granade]

I used a strategy pattern to get the distance function. This allowed me to have creatures use 1 movement in all 8 directions but projectiles use actual radius distance with the same algorithm.

The projectiles do that because that's what people expect, even though it's not consistent with move distance. If the projectile max distance is far enough, the inconsistency rarely actually matters in a roguelike.

We did something similar in CDDA, but everything (FOV, move cost, projectile range) is toggle able between Manhattan and trig distance with an option. Our projectile and view range is up to 60 squares, so the inconsistency would be significant.

[Bear]

The main decision for me is between

euclidean           sqrt(x^2 + Y^2)  or
stepwise:           (sqrt(2) - 1) * min(x,y)  +  max(x,y);

Euclidean is more consistent with real-world physics, but stepwise-euclidean is more consistent with game time and step distances.  With diagonal movement costed at sqrt(2), it takes the same number of turns to walk to any square on a stepwise-euclidean radius. 

If bowshot-distance is supposed to be the same as walking-distance, that's reasonable.  OTOH, if both are just considered approximations to euclidean distance, then even if stepwise considerations limit the accuracy of walking distance, why shouldn't bowshot distance be correct?

[Kevin Granade]

Because if you use different approximations you end up with inconsistencies like melee only monsters being less dangerous if approached from a certain direction because the projectile distance is shorter relative to the walking distance the monster has to cover to reach you.
Put more concretely, a monster will have to survive more ranged shots if it approaches from one direction compared to another.
If you wat to make a game where this sort of thing is a feature* that's one thing, but if your goal is implementing ecludian distance, you want to always use the same approximation to avoid inconsistencies like this.  As Eben points out, over short distances it won't matter, but then why are you implementing separate distance models with the same outcomes?

*I have a concept for a feng sui like chi flow through a dungeon that would introduce directionality to various actions, all characters would be influenced by it, but those that study feng sui can percieve and manipulate it.

[Bear]

The greatest possible difference is less than 8% and occurs when something approaches from 22.5deg from any axis or diagonal.  With bow fire taking twice as long as an orthogonal step, that means the distance would need to be at least 15 squares before it makes the difference of one extra bowshot. 

Also, if sight and bowshot are euclidean while movement is stepwise-euclidean, the creature (or player character) approaching from exactly one of those eight angles and sufficiently far away would be subject to an *extra* shot (relative to approaching from the same euclidean distance along an orthogonal or diagonal), not one shot fewer, because they'd be on a time-inefficient approach vector and take 8% longer to get there from that angle.

If most fights resolve at less than 15 squares, I'm just not seeing it as a terribly important choice.  That said, I have nothing against making the field of view an octagon with points on the diagonals and orthogonals.  But if I do, will players be annoyed that the field of view is the accurate w/r/t movement  octagon rather than the accurate w/r/t expectation circle?

[Eben]

The greatest possible difference is less than 8% and occurs when something approaches from 22.5deg from any axis or diagonal.  With bow fire taking twice as long as an orthogonal step, that means the distance would need to be at least 15 squares before it makes the difference of one extra bowshot. 

Thanks for doing the math to find where it makes a difference. Can't believe I never thought of it.