I'm firmly of the belief that there is no such thing as a perfect pathfinding algorithm. I've mentioned this during the article series on Unangband AI, but I'm working on improving traps in Unangband at the moment (a corrollory to getting druidic ongoing spell effects working), and it's very clear that in order to handle the complexity I want traps to have will overly complicate any attempt to build a 'correct' pathfinding algorithm.
I've just added the ability to avoid traps, as well as disarm them. Avoiding traps will become a more important requirement when I added ranged traps to the game (using a different implementation to NPPAngband ranged traps), but for the moment, think of it as particular trap types will not trigger if the player is in a particular state. If you are flying, you won't trigger pits or trap doors. If you are invisible, you won't trigger silent watchers. If you are in darkness, you won't trigger shafts of light. And so on.
My favourite is surreal paintings: you won't trigger these traps if you can see the painting. Which is just the kind of mess with your head weirdness that a magical scene that comes to life when you aren't looking should convey.
An important part of this concept is ensuring that the player can learn the various ways of avoiding traps. To do this, I try to make many of the trap types result in the game condition that then allows you to avoid the trap. This allows you to learn the associated way of avoiding the trap. For instance, one effect shafts of light can do is darken the room - which brings on the condition of darkness that prevents them from working. Similarly, magical symbols don't affect you if you have run out (or nearly run out) of mana. And an early magical symbol effect will be to drain you of mana.
Here's where the complication comes in: I want to make monsters avoid traps under the same scenarios as the player - to help the player learn these associations further. But this means that correct pathfinding will not only require knowing about the monster's permanent abilities, but their temporary ones. Which complicates pathfinding, because I need to model future effects. In particular, magical symbols will mean I'll need to model the monster's regeneration of mana, to determine whether they can safely cross an area filled with magical symbols (or more importantly, a single magical symbol with an area effect).
I've always had this problem, of course, because of dynamic terrain. Consider the following scenario and tell me how to design a pathfinding algorithm to handle it:
A monster runs into the room to attack the player standing in the doorway. Half way across, the player pulls a lever that floods the floor of the room with oil, then pulls out a match. Should the monster: a) keep advancing, b) retreat or c) stand still waiting for the player's next move? What other factors need to be considered?
Sunday, 14 December 2008
The Trap of Perfect Pathfinding
Subscribe to:
Post Comments (Atom)
Posts
13 comments:
I'm always intrigued by the progress in Unangband - and often watch the changes in SVN with interest. Then I roll up a new character and play for a bit - and then remember/notice that shops are all empty - and give up. I've never really enjoyed playing shopless-ironman. Once this gets fixed (hopefully soon!), I'll happily go back to playing Un again.
I'm assuming you're using A* or similar.
---
For multiple terrain types that are blocking based on creature abilities, that does not seem difficult. When pushing nodes onto the open list, compare the creature's abilities with each tile, and make the immediate cost of moving into the node dependent in part on the difficulty of the terrain (or discard the tile outright if it is impassible). This is only a fractional increase in the processing time.
If you aren't using variable difficulty, all terrain is passible or impassible based on the creature's abilities, and the creature's abilities are fixed over time, you can even just binary AND a couple bit fields, one for the ability of the terrain to block, one for which terrain types actually block this creature -- if they annihilate each other, then the tile is passible, if they don't, it's impassible.
---
For the mana trap, I would just have creatures that use magic avoid them, and creatures without mana ignore them. If you want to have magic users path through mana traps based on whether they have mana left, then yeah, you'd have to build in a model for mana gain over time.
This needs not be a permanent fixture in the algorithm; it can be calculated on the fly when needed, given the creature's speed and the distance travelled to get to the node in question, you know how much time it will take to get to any given point, and using that and the creature's mana regeneration rate, you can estimate how much mana will have regenerated by that point.
---
For the monster who is in the middle of the room when the player floods the room with oil and pulls out a match, I don't think this is a pathfinding issue at all. This is a monster logic issue. When the environment changes in any way you want to affect monster decision making, the monsters should be interrupted from their current tasks and forced to reason about what their next goal is.
If the monster again decides to attack the player, you call pathfinding to get to the player again (now using the modified terrain). If the monster reasons "I am standing in oil and my enemy has a flaming weapon" and just wants to get out of the oil, you can generate a fresh pathfinding request to the nearest non-oily tile. If the monster decides to stand still, no pathfinding is necessary.
Either way, pathfinding doesn't need to be modified at all -- it's just a matter of interrupting the monster to tell it to re-evaluate the situation whenever certain events occur. To avoid flip-flopping in a rapidly changing environment, you might give the creature a strong bias toward continuing its previous action.
Big Al: You're right. Just spent some time debugging this and it looks like I'm to blame - the side effect of messing with the terrain.txt. Working on a fix now.
Jonathan: I'm not using A* at this stage. The oil example is an extreme case of the fact that much of Unangband terrain is capable of dynamically changes from turn to turn. To solve this perfectly, I need to predict what the entire map would look like from turn to turn as a part of any pathfinding algorithm. Consider a map with moving platforms which part of the time form a faster path, but other times are slower than a fixed path, depending on the current platform positions.
Big Al: Fixed, just for you. You'll need to start a new char though...
Hey thanks, that was quick. I should have asked for that months ago! Can't wait to try the new stuff.
You mentioned you're not using A*; what are you using for pathfinding?
If the moving platforms are moving in a predetermined pattern, then that *can* be predicted, but presumably a lot of the dynamic changes are due to unpredictable events, so I'm not sure that definition of perfect pathfinding is even a worthwhile goal. It's impossible for a pathfinding algorithm to foresee the future if the dynamic terrain changes are dependent on player actions or decisions made by other agents -- if the changes are predictable, that's one thing, but if there's player involvement or random factors, that's entirely different.
I don't think it's a strike against your pathfinding if the AI can't predict when a player will throw a lever or cast a terrain modification spell, and thus has their path messed up before they reach their destination. Predicting these issues requires much higher level reasoning, and even very intelligent humans may be completely incapable of negotiating a platform puzzle if there is another player at the other end of it throwing levers that move platforms around in ways that frustrate the player's efforts.
Reacting to dynamic changes when they occur might be a pathfinding issue... it depends what you want your response to be. If it's just the player throwing up a wall of stone or growing a tree that obstructs the existing path, and you want the creature to path around the obstacle, there are algorithms that can handle that gracefully. If it's as dramatic a change as the player flooding the room with oil and pulling out a match, then it's so extreme that it's no longer within the domain of pathfinding -- you really need to reconsider what to do next, and pathfinding is all about how to do something.
Even an idealized perfect pathfinding algorithm would merely determine what the new fastest (or most preferred) way to get to the player through the oil is; you will still have to interrupt the monster and have it do some higher level goal picking if you want to get a more intelligent response from it.
I'm sorry if I come across as critical or argumentative, that's not really my intended tone here -- I'm just interested in pathfinding and artificial intelligence, and I like problem solving.
I fully agree with Jonathan. The match problem is a matter of AI, if a monster is supposed to deal with that situation you need to implement it at the state-machine / event handling level.
About predicting the state of a tile in the future, as long as you obey some sensible constraints, it can be *extremely* easy. The state of the tile must be dependent *only* on:
b) The state at the time of planning.
a) The time interval between the time of planning (t0) and the time for which you want to calculate something (t).
For example, a (supposedly) immutable state:
health(t) = health(t0)
If there's a bad buff sucking the monster's health, you have:
health(t) = health(t0) - rate * (t - t0)
For mana, you can take into account mana regen:
mana(t) = mana(t0) + rate * (t - t0)
A tile's fire can be put out after a while:
fire(t) = fire(t0) - rate * (t - t0)
You need to know the quantity (t - t0) for any given state. So, the pathfinding algorithm must carry forward the passing of time, just like you carry forward the distance traveled, as you explore the possibility-space. As an analogue to traveled distance, you can call it traveled time :)
In A* and Dijkstra this is trivial. The lists and such deal with the distance traveled, just augment it to include also the passed time. When you calculate the cost of a possible next step, use the passed time to figure out current stats, using appropriate formulas like above. Don't forget to cap the results at appropriate quantities (like 0 and max_health).
And voilà - you can predict states in the future and figure out if a tile will be passable or impassable.
This is extendable to other problems such as "will this door be locked in the future?" or "will the player cast an AOE spell?", but then you'd need to carry forward more state than just that time interval, and update it continually as the algorithm goes. Like a mini-game-simulation of the future, with different realities in possibility-space. But that would probably be too complicated for your purposes :)
This is all WAY out of my league, but completely fascinating to read. As far as my limited understanding goes, though, I agree with Jonathan that the problem at hand lies at the intersection of pathfinding and decision logic.
While an AI goal remains constant, pathing changes should probably incur a penalty X, so that the new path must be an improvement of X over the old path in order to be viable; moreover, the penalty can be cumulative in many (most?) situations to forestall flip-flopping / paralysis by analysis. The real doozy is figuring out when a path change is so expensive, or a path so risky / low-gain, that the best decision is to change goals entirely. For example: two drawbridges span a chasm between you and an opponent, and a switch on your side toggles which drawbridge is down. As long as your opponent's goal is to reach you, you can repeatedly toggle the switch to make that impossible, even though there is always a physically possible path. The best AI behavior, I'd think, would be to have the opponent's cumulative penalty for path change get so high that a new goal must be formed -- sound the alarm, wait somewhere out-of-sight, etc.
Your monster-in-oil scenario doesn't really involve pathfinding. Consider a variation that places the monster 1/3 of the way towards the player. At this point, you're weighing distance to player D1, distance to safe retreat D2, a set of goals with numerical ranks (some being equally ranked), and time to ignition T. Can the monster travel D1 before T elapses? If yes, continue current goal of attacking; otherwise, the current goal is nonpreferred, so examine other goals like retreat. Can the monster travel D2 before T elapses? If yes, then add that goal to the list of preferred goals, and ultimately evaluate which goal in that list has the best rank ("best" being up to you -- could be greatest reward, could be lowest risk). If the list of preferred goals ends up empty, there is no incentive to change goals, so press the attack and hope for the player to make a mistake. However, if the room's risk is fluctuating -- e.g. if the oil covers different areas of the floor at different times, unpredictably -- that's when the pathfinding penalty starts to accrue, which could also result in goal change (i.e. "It's not worthwhile to navigate this shifting terrain, I'm gonna scram!").
Of course, that's just one amateur's thoughts. You've got BrainWorks on your blogroll; I'm sure that site's author would have an opinion...
(Not that I mean to nag, but just letting you know that stores aren't fully fixed yet. They exist now, but seem to be randomly shuffled around. There's two of Elrond's House in Bree and all kinds of craziness. Not a big deal, but just making sure that you're aware of it. Thanks.)
Jonathan: Not at all. I'm actually not sure what I'm using, pathfinding wise: I've just inherited whatever is in the 4GAI model. It's has a cost based, short range route planner of some kind. However, more importantly, it uses 'smell' and 'noise' to attempt to approximate a sense based path finding system, which is not perfect, but perfectly good for the vast majority of situations.
"It's impossible for a pathfinding algorithm to foresee the future if the dynamic terrain changes are dependent on player actions or decisions made by other agents -- if the changes are predictable, that's one thing, but if there's player involvement or random factors, that's entirely different."
Exactly. I couldn't have summarised it better...
Well, someone has to post the classic game dev solution.
Cheat.
Don't change the pathfinding at all.
For 2 reasons: One, because it's simple and less eo prone, and Two, because it rewards the player for being smart.
If you really want the monsters to seem smarter then this, try conditions that change the AI independent of pathfinding. For example, the monsters retreat not because they see the match, but because they get "afraid" once they are covered in oil. This way you haven't predicted anything, except the obvious. And you've handled other awkward cases (what if the player has fire spells instead?)
Moving platforms is trickier, but I'd try something similar to how you solved pushing for formations, with one square ahead future hints. Depending on you path distances, would be fine. If the distances are large, you could have the platforms do simple velocity checks, the same way your monsters would do player intercept now.
It seems like all the scenarios that have been discussed here work the same:
1) A monster finds a path to its destination
2) Something happens that changes the terrain
3) How should the monster react dynamically to the change?
It doesn't matter what changes the terrain, whether it's a trap being created, tunnels being dug, or whatever. Is it really too hard to re-path all traveling monsters every time the terrain changes in an area their path travels through?
As far as the magic symbols go, there must be a tipping point where below a certain point, the monster shouldn't care that its mana is being drained. When the monster regains mana past that point, set whatever flag makes the monster care about mana traps, and re-path! It's not such a big deal if the monster runs up to the symbol, gains that last point of mana that makes it not want to get zapped, and decide to backtrack. In fact, isn't that the exact kind of behavior you want to use to teach players about trap avoidance?
I assume the oil example is an example of an area-effect trap being created, and not an example of the monster AI having to know about every possible cause-and-effect action in the game. When the trap is created, the terrain changes, which should force a re-path. Since the monster is halfway into the room, it has nothing to lose by continuing on its path toward the player, and nothing to gain by retreating through the back half of the room which is also trapped. If the trap was created completely in front of the monster, it should re-path around it is vulnerable to fire.
It may even be desirable to divide monsters up into smart/cautious monsters who treat traps like obstacles, and dumb/brave monsters who don't. Zombies and bloodthirsty orcs, for example, might charge even if they can detect a trap, while I (as a player) would like to see an intelligent foe stop when he detects a trap and perhaps switch to ranged combat.
Obviously Halo isn't exactly the bible for AI, but this this article makes an interesting point: keep the AI focused on the player's experience. If the player goes to all the trouble to set an elaborate trap for the enemy, he or she wants the satisfaction of seeing that trap work. If it doesn't, he or she should be made to understand why it didn't and how to make it work in the future. Building an AI that is so smart that it always avoids the player's traps is not only next to impossible for you, it's also no fun for the player.
I'm surprised that no-one has mentioned D* or other similar dynamic pathfinding algorithms. These algorithms are capable of optimally (and fairly efficiently) finding paths in an unknown and/or changing environment. The algorithms obviously can't be smart about predicting the future, but I suspect that in many cases where you want such behaviour, it will be possible to special-case the logic (e.g. 'there is no way for me to get from here to my goal, but there is a moving platform that stops both here and at a place from which I can reach my goal. Wait for the platform to arrive.')
Beyond that, I don't think prediction adds anything to the game. The monsters aren't supposed to be plotters and schemers. They're supposed to be mildly entertaining decorations for your dungeon generation algorithms :)
Post a Comment