How to make monster pathfinding to work realistic?

[SomeGuy]

Hi.

I'm creating some roguelike but I have a little problem with monster pathfinding.

Actually, the algorithm I'm using works perfect and everything is ok.
The only problem I got is when the player is in a situation like this:



Here we have a thin corridor where the player and a Kobold are approaching, and in the other side, an Orc.

The Kobold can go straight and reach the player, but the straight path to the player is blocked for the Orc, so the pathfinding algo searches an alternative route.
This doesn't sound bad for this example since the 0rc can reach in little amount of turns the other side of the corridor, but I see here two problems:

- when the map is large and complicated the pathfinding algorithm searches a route that may require a lot of turns, which is quite dumb, and nobody will go for a long route if he can wait a couple of turns for the Kobold to die,
- If there is no alternate route, the Orc just stuck in place until the Kobold dies and the route is free.

So I want the Orc to move towards the player and just await behind the Kobold until this one dies rather than searching an alternate route if this alternate route if this route is too long, but also, use the alternate route if the distance to run is relatively short.

Any idea on how to do this?

Actually I'm using a Jump-Point pathfinding algorithm, so I'm not sure if there is some interesting tweak that it is recommended to do specifically for Roguelikes.
Also, I'm using a blockmap for the player and another for the enemies. (blockmap = array that contains the walkable tiles)
The enemies' blockmap has all walls and floors in the normal map, but also monsters here are represented by "#" too, so they are basically like walking walls, so the pathfinding is recalculated like if monsters were walls.

Thanks a lot.

[Quendus]

You might want to try making the pathing cost of the blocked tile greater than the pathing cost of the empty floor tiles - something like 5 or 10 times. That way the pathing monster considers both the blocked path and the indirect path.

The choice between the two paths would be determined both by the number of monsters blocking the direct route (so a corridor jammed by a horde of angry windshield monsters is worse than a corridor with a sleeping dragon), and by the difference in length between the two alternative paths.

If you would prefer the corridor full of windshield monsters to be considered "less blocked" than the corridor with a sleeping dragon, then you could make the pathing cost that the monster adds to be dependent on its level and its sleeping/awake state.

The main case in which this idea doesn't work is when a powerful blocking monster is awake  and about to enter a spacious room to attack the player - in this case the pathing monster might try to choose the indirect route, then double back and follow the direct route as soon as the powerful monster exits the corridor.

[Krice]

You could test different paths or in this case simply check if there is a direct way to the player (including monsters between) and go there first, without using pathfinding at all.

[guest509]

  When choosing a path don't count monsters as blocking. Makes them less smart but more realistic.

[SomeGuy]

......

......

Thanks for both answers they gave me the idea on how to solve it.

  When choosing a path don't count monsters as blocking. Makes them less smart but more realistic.

Actually I changed the initial behavior.

I solved the thing as follows. It's not the most elegant way. but it's good for keep things working in a simple and quite realistic way:

FIRST: I calculate a normal route for monsters, using the usual game  map, where # is blocking and · is walkable.
SECOND: monsters are not taken into account as blocking elements (as Jo suggested)
THIRD: before a monster moves to the next cell in the route, the game checks if there is another monster in such cell. If there is nothing, then just move to the new cell. But if there is a monster, then execute another algorithm that calculates an alternate route, but this time, using a different blocking map, where other monsters are basically walls. With that new route, the monster will calculate the shortest distance to the player again, but without having into account the route weight as Quendus suggested (btw I'm going simple). Actually the behaviour I found when testing this is that monsters tend to surround the player, so, for example, in open areas like rooms, they simply avoid monsters that are attacking the player.


I know it's quite simple and can make monsters to use stupid routes in certain situations. I'm not interested in Smart Kobold, but this method is quite decent for some simple initial AI.

[requerent]

I think you may get uninteresting results if you simply lighten weights on occupied tiles. What if the player ran away? If the kobold took an alternative path, he might cut off the player's escape route.

There are some cool ways to govern these sort of things- Expectimax or Minimax are very simple and might yield interesting results if you can keep your branching factor really low. Markov Models could also do well- though Monte Carlo is the way of the future. If you're sticking with simple reflex agents, then weighting the map is going to get you the result you want, but I would seek something a little more sophisticated.

[SomeGuy]

I think you may get uninteresting results if you simply lighten weights on occupied tiles. What if the player ran away? If the kobold took an alternative path, he might cut off the player's escape route.

There are some cool ways to govern these sort of things- Expectimax or Minimax are very simple and might yield interesting results if you can keep your branching factor really low. Markov Models could also do well- though Monte Carlo is the way of the future. If you're sticking with simple reflex agents, then weighting the map is going to get you the result you want, but I would seek something a little more sophisticated.

That sounds great. I didn't take a look at *max algos.
But definitely, when finish other parts of the game, I will be tweaking everyting. I want to implement some more advanced pathfinding method, and the ones you suggested are the first I'm gonna take a look.

Thnx.

[requerent]

I think you may get uninteresting results if you simply lighten weights on occupied tiles. What if the player ran away? If the kobold took an alternative path, he might cut off the player's escape route.

There are some cool ways to govern these sort of things- Expectimax or Minimax are very simple and might yield interesting results if you can keep your branching factor really low. Markov Models could also do well- though Monte Carlo is the way of the future. If you're sticking with simple reflex agents, then weighting the map is going to get you the result you want, but I would seek something a little more sophisticated.

That sounds great. I didn't take a look at *max algos.
But definitely, when finish other parts of the game, I will be tweaking everyting. I want to implement some more advanced pathfinding method, and the ones you suggested are the first I'm gonna take a look.

Thnx.

Oh- these aren't quite pathing methods (though they could be used that way). They're decision methods- you would likely use pathing methods in conjunction with these to make them more efficient/abstract.

Say for example a monster can have two aggressive states-- They can minimize their distance to the player OR they can try and path to the player perfectly. 'Distance Minimization' means that the entity will never move further away from the player, whereas 'Perfect Pathing' will always take the unblocked path.

Similarly, we might assume two behaviors that the player may exhibit- either move aggressively (attack) toward an enemy, or maximize distance between enemies (flee).

While these entities can perform a huge number of actions (move any direction, stand still, attack, throw potion, use spell, special abilities etc, etc, etc), it's too processor intensive to evaluate how every single one of them might affect the player. To simplify matters, we just need to know if the monster is in a position to deal damage to the player and, if it is not, which method of movement ('min distance' or 'perfect path') will likely result in the most overall damage. Abstracting the problem can allow us to reduce the complexity of the state space (all the possible actions and reactions among entities) in a way that is very searchable-- IE, a binary tree.

In this sense, your individual entities aren't acting on their own, but are being played by the computer like chess pieces. To keep it simple, instead of evaluating all possible moves, we evaluate behavior patterns/states that the monster might be in- since entities behave in predictable ways ('min distance' or 'perfect path'), we can get a pretty good idea of which state is LIKELY to yield the best results. Note, in either state, entities ALWAYS attack if it is possible for them to do so- in such situations that portion of the tree is simplified (the interesting thing about this paradigm is that it will work regardless of the speed or attack range of the monster).

Then you just simulate all possible decision paths on the binary tree and see which one has the most desirable results. You'll need an evaluation function to determine that, and that's the hard part about AI and heuristics. If your sole measure is the player's HP, then the simulation will assume that the player is always running. The best Delta between damage taken/dealt might work, but may not yield the most interesting results. Adversarial algorithms are pretty simple to implement so long as you can come up with a clever and concise way to describe the state space (you need some kind of data structure that can store representations of the game state so that you can look ahead at the possible outcomes).


Anyhow- just some food for thought. Most roguelikes don't use very advanced AI-- they're typically reflex agents that make predictable decisions. This isn't a bad thing- If a Goblin Conjurer or Pink Jelly from Brogue used adversarial search, it'd be very difficult to pass the early levels without luck.