Approaching "enemy sees player"

[SomeGuy]

Hi.

I am stuck with this problem
I need opinions on how would you implement the way enemies detect/see players.
Lets say, at first, enemies are inactive. They didnt see the player and they dont move.

How would you make enemies to detect the player, when he (the player) is seen/detected?

I thought about three different ways:

1) Enemies have their own LOS. When the player enters the LOS of the enemy, then the enemy awakes and starts chasing the player. This way uses a LOS algorithm for each monster, each turn. I think it is the most realistic and flexible, since the enemies can have their our "see distance", and enemies can awake from outside players LOS (i.e. the enemy has a bigger LOS than the player). But the downside is, we have to recalculate a LOS all the time.

2) Simple squared, static LOS. Enemies have a simple square/circle of sight around them that covers both floor and walls. Whenever the player enters this squared LOS, the enemy awakes. The goodness about this is that you can justify it going over walls as "the enemy can hear someone around". Also it should be faster than the true and real LOS. In this case is just checking some map cells around the enemy. The downside is, it is less realistic, and could awake enemies that are in a room/corridor completely unconnected from the player's location

3) Enemies awake when player sees them. In this case, the enemies only awake when they are seen by the player. It is quite ok for a simple roguelike, but I need to implement enemies with different LOS size, so this wont work. Anyway, the goodness about this is, only calculate LOS once per turn, and check if any enemy is within player's LOS. Downside, it wont work if you need to implement enemies with different LOS size.

4) The pathfinding way. I thought about running a pathfinding algorithm every turn for each monster, starting in moster x,y position, and finishing in player x,y position. Then, for each "step" in the path, we check whether the player is in such step or not. We repeat this "player check" for a certain amount of times, that are basically the enemy see distance. This is good and quite realistic since you can simulate not only a LOS, but also "enemy hears the player around the corner, even when there is not direct "eye contact" (because pathfinding will turn over corners and etc). The bad is, heavy on calculations, it is basically a pathfinding algorithm every turn for each monster.

Do you have any other idea or thought?

Please share with us.

Thanks

[Krice]

3) Enemies awake when player sees them. In this case, the enemies only awake when they are seen by the player. It is quite ok for a simple roguelike, but I need to implement enemies with different LOS size, so this wont work.

Could work if you also check the distance to the player and don't wake up the creature if it's too far away. I would also use "sound" based approach with simple distance check and possibly how much the player is making noise. Also, I would use pathfinding only if the creature has difficulties to approach the player directly when it knows where the player is. Even then it's often questionable, because how does some simple monster know how to pathfind the player? Maybe it could just stand there or leave.

[AgingMinotaur]

My own design philosophy involves not to overthink whatever I can avoid. Since this mainly touches on events happening outside of the player's line of sight, I think it's okay to give one self some leeway here. I think the effect we are looking for, is two-fold: We want the player to get the feeling they are moving around in a living world, but we also don't want interesting events to play out outside of the player's line of sight. It's cool to come into a room where a knight and a bear are in the middle of a fight, for instance. It's less interesting to explore a dungeon full of already vanquished enemies.

Both my games that ever saw a release has a variant of "wake up monsters when player is at a certain distance". My first game had very strict division of the map into different rooms, and I'd simply let monsters wake up whenever a tile belonging to their home room came into the player's line of sight (including outer walls/doors, so most monsters would wake up when the player was somewhere in the room adjacent to them). My current project plays in an open landscape rather than a dungeon. Here I just divided the map into big chunks (approx. 16 x 16 points), and I make sure that all beings currently in the same map chunk as the player, or one adjacent to it, is active. As the player moves around, map chunks that are too far away are conversely put to sleep again.

As always,
Minotauros

[SomeGuy]

3) Enemies awake when player sees them. In this case, the enemies only awake when they are seen by the player. It is quite ok for a simple roguelike, but I need to implement enemies with different LOS size, so this wont work.

Could work if you also check the distance to the player and don't wake up the creature if it's too far away. I would also use "sound" based approach with simple distance check and possibly how much the player is making noise. Also, I would use pathfinding only if the creature has difficulties to approach the player directly when it knows where the player is. Even then it's often questionable, because how does some simple monster know how to pathfind the player? Maybe it could just stand there or leave.

Distance checking Line of Sight is the simplest I can come up with, but the downside appears when the monster can see from a farther distance than the player.
Lets say, the enemy is only "awaken" when the player seen him. In this case, all the enemies' LOS distance = player LOS discantance.

So then, distance checking should be performed from monsters' perspective, i.e. for each monster, check if player is within that monster's LOS distance.

But the downside is, monsters would be able to see through walls, doors and any other LOS blocking map feature: (continue after Minotauro's quote):

My own design philosophy involves not to overthink whatever I can avoid. Since this mainly touches on events happening outside of the player's line of sight, I think it's okay to give one self some leeway here. I think the effect we are looking for, is two-fold: We want the player to get the feeling they are moving around in a living world, but we also don't want interesting events to play out outside of the player's line of sight. It's cool to come into a room where a knight and a bear are in the middle of a fight, for instance. It's less interesting to explore a dungeon full of already vanquished enemies.

That is a good point you have there. Afterall, with a simple "distance LOS" system we could justify it as if the enemy hears the player. And even we can implement a stealth check:

Code: [Select]

if enemy.viewDistance >= enemy.distanceToPlayer AND player.stealth < enemy.detectHidden then
     enemy.seesPlayer()
else
    enemy.doesNotSee()
end
We could even increase stealth based on distance.

Both my games that ever saw a release has a variant of "wake up monsters when player is at a certain distance". My first game had very strict division of the map into different rooms, and I'd simply let monsters wake up whenever a tile belonging to their home room came into the player's line of sight (including outer walls/doors, so most monsters would wake up when the player was somewhere in the room adjacent to them). My current project plays in an open landscape rather than a dungeon. Here I just divided the map into big chunks (approx. 16 x 16 points), and I make sure that all beings currently in the same map chunk as the player, or one adjacent to it, is active. As the player moves around, map chunks that are too far away are conversely put to sleep again.

As always,
Minotauros

Basically, your 1st game was based on Rogue wake system.
Whereas your 2nd game, since it is a openworld system, there are not meaningful obstacles that totally block monsters LOS.
But the problem I want to avoid as much as possible is this, directly related with dungeon-style Roguelikes:

Code: [Select]

   # # # # # # # # # #
   # . . . # . . . . #
 # # . . . # . . . . # #
   . . E . # . . @ . .
 # # . . . # . . . . # #
   # . . . # . . . . #
   # # # # # # # # # #


In that case, lets say enemy 'E' has a LOS distance of 10. Both, the player and E are in totally unconnected rooms, but the distance from E to @ in less than 10, so E can see @ even through walls.

So, in the end I might go all the way to simple distance checking, as you suggest, it is better to do things simple. But just wondering, for dungeon roguelikes how should be the best approach that balances realism with computational speed.

Btw, I tried pathfinding system, and it is terribly slow, even for a mere 10 enemies in the map.
Then I tried a LOS calculation (LOS from each monster towards the player position), and even when it is slightly faster, it is far from comfortable for the player.
And finally, simple squared distance check, the fastest, but could lead to "monsters can see through walls" effect.

I dont know if there are other methods to approach this, that is the question I really wanted to ask.


Thanks for your answer, both of you.

[sokol815]

I'm a fan of the pathfinding method.

You don't have to run pathfinding for every monster. You can just use Dijkstra's algorithm (http://forums.roguetemple.com/index.php?topic=3652.0) once with the player as the goal... then check the spot the monster is located at to see if they can reach the player... (you'll know this because when you instantiate dijkstra's, you give all cells a default very high value... any cell retaining the default value is unable to path to the goal) you only need to re-calculate whenever paths in the dungeon change (paths blocked, explosions open new paths) or the PC moves.

Dijkstra's maps can also be used for more complex AI interaction, as mentioned here: http://www.roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps (Note: this article is the subject of the above roguetemple link I posted)

Good luck!

[SomeGuy]

I'm a fan of the pathfinding method.

You don't have to run pathfinding for every monster. You can just use Dijkstra's algorithm (http://forums.roguetemple.com/index.php?topic=3652.0) once with the player as the goal... then check the spot the monster is located at to see if they can reach the player... (you'll know this because when you instantiate dijkstra's, you give all cells a default very high value... any cell retaining the default value is unable to path to the goal) you only need to re-calculate whenever paths in the dungeon change (paths blocked, explosions open new paths) or the PC moves.

Dijkstra's maps can also be used for more complex AI interaction, as mentioned here: http://www.roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps (Note: this article is the subject of the above roguetemple link I posted)

Good luck!

Good idea. I dont know why I didnt thought about Dijkstra maps!

But I think we can make this a bit more efficient: instead of calculating the whole Dijkstra, we can do simple distance check between the monster and the player.
If the player is within the monster's viewing distance, we do the pathfinding, otherwise, we dont.
So, instead of calculating the distance for lots of cells around the player (the Dijkstra map), we do the calculation only once.

What do you think?

[sokol815]

Good idea. I dont know why I didnt thought about Dijkstra maps!

But I think we can make this a bit more efficient: instead of calculating the whole Dijkstra, we can do simple distance check between the monster and the player.
If the player is within the monster's viewing distance, we do the pathfinding, otherwise, we dont.
So, instead of calculating the distance for lots of cells around the player (the Dijkstra map), we do the calculation only once.

What do you think?

Hey! Sorry about that... I forgot this forum does not auto-activate notify when you respond to a thread.

Yeah, you could totally do this... just decide upon a threshold at which Dijkstra's will stop spreading from the source... I've been playing around with a max Dijkstra distance of 24 (E.G. it stops pathing after more than 24 tiles away from the goal) for a PC with a sight range of 12 and it's still very interesting... you want monsters to be active if they are still close and out-of-sight of the player, otherwise the player might realize they can deactivate a monster just by getting them out-of-sight.

As far as optimization goes... My Dijkstra implementation (Breadth-first Priority Queue) can run through my entire 80x100 map in less than 1ms. You probably don't need to worry a lot about optimization until it becomes a problem.

What I refer to as "Dijkstra's algorithm":
1. Initialize all cells to default high value (I use 9999) & mark them all as not in the queue.
2. Create an array containing positions of our current goals(usually just 1 element with the PC's location).. this will be called the queue.
3. Mark all goals on the map as having a dijkstra value of 0 (or lower/higher if you want to make some goals more important than others, lower numbers being more important)
4. While the priority Queue is not empty, remove the first element from the queue and process it:
   a. Mark it as not in the queue
   b. Grab the list of it's path-able neighbors (e.g. open spots, not walls) and check if their dijkstra values are more than 1 + this cell's value... if so, set the neighbor's value to 1 + the current cell's value. If you changed the value, check to see if they are already in the queue, if not... add the neighbor to the queue and mark the cell as in the queue.

To use the above generated map, just employ an algorithm starting at the position of your monster and "roll down the hill" through it's neighbors to your goal.

When I first learned about Dijkstra's, I implemented the algorithm in a horrible fashion of using a while loop and inside of that, doing double for loops to iterate over every cell looking for neighbors that needed to be updated... if I updated anything in the for loops, I'd have to continue the while loop. That method could easily take 30ms to run in a 80x100 map.

I hope you've already made a choice as to how you're going to implement it, but if not... I hope this helped.