Temple of The Roguelike Forums
Development => Design => Topic started by: Bear on July 26, 2014, 04:15:35 PM
-
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?
-
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.
-
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
-
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.
-
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!
-
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.
-
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 (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?
-
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).
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
I've found this: http://www.roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps (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?
-
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.
-
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.
-
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)
-
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...
-
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.
-
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.
-
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.
-
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 (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.
-
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. ;D
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.
-
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.
-
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?
-
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.
-
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?
-
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.
-
If most fights resolve at less than 15 squares, I'm just not seeing it as a terribly important choice.
That's exactly my point, if it's irrelevant, why are you adding extra complexity? Just be consistent.
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?
It's a matter of which is more important, making your system consistent, or making it look a certain way. (filtered through your understanding of your players desires perhaps)
To me, an inconsistency like that is simply unthinkable in a game intended to be tactical.