Tactical AI Kit: Leaving the Player with Nowhere to Hide
by Bryce · 01/02/2009 (10:17 pm) · 12 comments
Hello GarageGames!
A lot has changed (for the better) recently regarding my progress on the Tactical AI Kit. First off: I got a new (not refurbished, like my last three dead laptops) computer for Christmas! It's a very fast, nice little laptop, great for my work. Specs for anyone interested:
Dell Vostro 1510
Windows Vista Basic
Intel Core 2 Duo Processor, 1.8 GHz
250G Hard Drive
4.0G RAM (!!!!!)
So, this should help a summer or fall release to be more possible. Now I don't have to work on the AI code every other week when I'm at the right parent's house.
Second, I have reworked the TAI Player's method of navigation. I was previously using Dan Keller's Flexible A* Pathfinding resource, but I was having some problems with NPCs getting stuck. So, I installed Gabriel Notman's resource instead. It was a little difficult to get it going the way I wanted it, node placement is time consuming, and there are several bugs in the system, but I think it's much more flexible for me and efficient.
Letting each waypoint be an existing, selectable object in the game world allows TAI Players to have access to various node information (such as position) in script, making it much easier to tweak on-the-fly.
I have been constantly adding onto and refining the way TAI Players deal with threats. Whenever I add a feature to the reaction system, I am always satisfied with the result, but I keep thinking of some other feature that would make it even better. I guess that's a good way for an AI programmer to think.
Anyway, let's get on with it...
When a TAI Player is sitting around, minding his own business, and suddenly hears suspicious movement lurking in his area, he will go out to investigate. My first (and very basic) system told the NPC to walk over to the location where he heard something, stop, and then walk back to where he was before. The problem with that is that most stealthy players would attempt to hide upon hearing the NPC say "is someone there?" This can make AI Players look dumb. For example, if the NPC hears movement in a large field with barrels, crates, and other various opaque objects to hide behind, the NPC shouldn't just walk over there and stop. He should think, "Okay, what if I did really hear an enemy? What if he is just hiding from me?" and then figure out where a threat may want to hide.
Hunting behavior for Tactical AI Players was then what I set out to implement. After sitting down and sketching out some simple maps and ideas, I finally got an idea as to how to use waypoints to figure out logical hiding spots. I decided that a waypoint is only a hiding spot if within a certain radius from the spot where movement was heard, if that waypoint does not have line-of-sight to that location, and if that waypoint also does not have line-of-sight to the hunting AI Player. Hiding spot waypoints should also not have line-of-sight to other hiding spot waypoints.
Here are some diagrams I worked up to help demonstrate:
1) The playing area. The hunting NPC is the green circle, the location of suspicious movement is the red question mark. Note the black lines are walls inside of buildings that you can't see.
2) The waypoint map, with the red nodes and blue lines to show adjacency.
3) Excluding waypoints outside a certain radius (this radius depends on the distance from the NPC to the possible enemy location).
4) Excluding nodes that the NPC can see.
5) Excluding nodes that the enemy movement position can see.
6) The hiding spot waypoints, marked in green. Note that no hiding spot can see another--this is to make sure that the NPC would go into a room, look around, and move on, rather than move to each and every node in the room.
After we have a list of possible hiding spots, the NPC moves to the enemy movement position, then navigates to each hiding spot before moving back to where he started.
Once again, I have managed to add a very advanced feature to the Tactical AI Kit that doesn't resort to annoying cheating!
Please rate and comment this. Feedback is vital; I want all questions and suggestions--I mean it! Thank You!
A lot has changed (for the better) recently regarding my progress on the Tactical AI Kit. First off: I got a new (not refurbished, like my last three dead laptops) computer for Christmas! It's a very fast, nice little laptop, great for my work. Specs for anyone interested:
Dell Vostro 1510
Windows Vista Basic
Intel Core 2 Duo Processor, 1.8 GHz
250G Hard Drive
4.0G RAM (!!!!!)
So, this should help a summer or fall release to be more possible. Now I don't have to work on the AI code every other week when I'm at the right parent's house.
Second, I have reworked the TAI Player's method of navigation. I was previously using Dan Keller's Flexible A* Pathfinding resource, but I was having some problems with NPCs getting stuck. So, I installed Gabriel Notman's resource instead. It was a little difficult to get it going the way I wanted it, node placement is time consuming, and there are several bugs in the system, but I think it's much more flexible for me and efficient.
Letting each waypoint be an existing, selectable object in the game world allows TAI Players to have access to various node information (such as position) in script, making it much easier to tweak on-the-fly.
I have been constantly adding onto and refining the way TAI Players deal with threats. Whenever I add a feature to the reaction system, I am always satisfied with the result, but I keep thinking of some other feature that would make it even better. I guess that's a good way for an AI programmer to think.
Anyway, let's get on with it...
When a TAI Player is sitting around, minding his own business, and suddenly hears suspicious movement lurking in his area, he will go out to investigate. My first (and very basic) system told the NPC to walk over to the location where he heard something, stop, and then walk back to where he was before. The problem with that is that most stealthy players would attempt to hide upon hearing the NPC say "is someone there?" This can make AI Players look dumb. For example, if the NPC hears movement in a large field with barrels, crates, and other various opaque objects to hide behind, the NPC shouldn't just walk over there and stop. He should think, "Okay, what if I did really hear an enemy? What if he is just hiding from me?" and then figure out where a threat may want to hide.
Hunting behavior for Tactical AI Players was then what I set out to implement. After sitting down and sketching out some simple maps and ideas, I finally got an idea as to how to use waypoints to figure out logical hiding spots. I decided that a waypoint is only a hiding spot if within a certain radius from the spot where movement was heard, if that waypoint does not have line-of-sight to that location, and if that waypoint also does not have line-of-sight to the hunting AI Player. Hiding spot waypoints should also not have line-of-sight to other hiding spot waypoints.
Here are some diagrams I worked up to help demonstrate:
1) The playing area. The hunting NPC is the green circle, the location of suspicious movement is the red question mark. Note the black lines are walls inside of buildings that you can't see.
2) The waypoint map, with the red nodes and blue lines to show adjacency.3) Excluding waypoints outside a certain radius (this radius depends on the distance from the NPC to the possible enemy location).4) Excluding nodes that the NPC can see.5) Excluding nodes that the enemy movement position can see.6) The hiding spot waypoints, marked in green. Note that no hiding spot can see another--this is to make sure that the NPC would go into a room, look around, and move on, rather than move to each and every node in the room.After we have a list of possible hiding spots, the NPC moves to the enemy movement position, then navigates to each hiding spot before moving back to where he started.
Once again, I have managed to add a very advanced feature to the Tactical AI Kit that doesn't resort to annoying cheating!
Please rate and comment this. Feedback is vital; I want all questions and suggestions--I mean it! Thank You!
#2
Question....(since you asked for them...)
If a player is on a rooftop. The npc is on the ground. Can the npc find the stairs? or does he just run into the wall and try to walk thru it? Same goes with doors.
If an npc hears a player, possibly in that building, will the npc attempt to look thru a window before finding the door?
If the npc hears a sound from directly in front of him, will he still check the hiding spots to the side? or will he look straight ahead for a hiding spot there first?
01/03/2009 (11:42 am)
This just keeps getting better and better. I still have the demo. My son, grandson and I like playing it.Question....(since you asked for them...)
If a player is on a rooftop. The npc is on the ground. Can the npc find the stairs? or does he just run into the wall and try to walk thru it? Same goes with doors.
If an npc hears a player, possibly in that building, will the npc attempt to look thru a window before finding the door?
If the npc hears a sound from directly in front of him, will he still check the hiding spots to the side? or will he look straight ahead for a hiding spot there first?
#3
Very common tactical error I see in games is they send NPCs rushing into a building one by one instead of waiting for support and sending a tactical team in to do a sweep. All depends on your NPC and storyline. If the NPCs are common thugs, then they would probably be hot heads and trace through. Properly trained military would probably wait for backup and orders to clear the room.
Probably more than you are looking for, but if the NPC goes charging into the room without stoping at the door and clearing, then hes toast every time and the game becomes very predictable.
01/03/2009 (11:51 am)
Will the NPV try and flank? Or call for support?Very common tactical error I see in games is they send NPCs rushing into a building one by one instead of waiting for support and sending a tactical team in to do a sweep. All depends on your NPC and storyline. If the NPCs are common thugs, then they would probably be hot heads and trace through. Properly trained military would probably wait for backup and orders to clear the room.
Probably more than you are looking for, but if the NPC goes charging into the room without stoping at the door and clearing, then hes toast every time and the game becomes very predictable.
#4
@Randy Hearn: I did have flanking working, but there was a bug in the system and I need to re-implement it. With the new navigation resource in, more advanced flanking behavior should be a little easier to pull off.
I have found it difficult to define to the NPC what a room actually is. I read an article about using "pinch-points" to tell an NPC to wait outside a door for an enemy to run out, and that may be useful, but the pinch-point system requires a very specific and picky node layout to define doorways, hallways, etc. So room clearing would be a little tedious, especially the waiting for backup part. All NPCs who suspect an enemy assume they are in danger and will prefer to take out the threat immediately.
The NPCs will have a sense of self-preservation when searching and will move slowly and cautiously when hunting an enemy. In a some time before release, I will have the NPCs rotate to face the next node they plan to move to before they get there, so they strafe around corners like intelligent players.
edit: They don't look through windows on their own
01/03/2009 (12:17 pm)
@Mike Rowley: The Tactical AI Kit has an A* Pathfinding System included, so it will automatically generate the most direct route around obstacles (and up stairs). They don't look through windows on their own, as that behavior is a bit too advanced and difficult to define. As for hearing an enemy directly in front of them, the NPC first moves to where he heard the movement, then to the closest hiding spot, to the closest hiding spot from there, etc. I'm not sure exactly what you are asking, but the move-to-closest behavior usually causes nodes to be searched in groups, creating the illusion of individual room/building clearing.@Randy Hearn: I did have flanking working, but there was a bug in the system and I need to re-implement it. With the new navigation resource in, more advanced flanking behavior should be a little easier to pull off.
I have found it difficult to define to the NPC what a room actually is. I read an article about using "pinch-points" to tell an NPC to wait outside a door for an enemy to run out, and that may be useful, but the pinch-point system requires a very specific and picky node layout to define doorways, hallways, etc. So room clearing would be a little tedious, especially the waiting for backup part. All NPCs who suspect an enemy assume they are in danger and will prefer to take out the threat immediately.
The NPCs will have a sense of self-preservation when searching and will move slowly and cautiously when hunting an enemy. In a some time before release, I will have the NPCs rotate to face the next node they plan to move to before they get there, so they strafe around corners like intelligent players.
edit: They don't look through windows on their own
#5
Remember, when the NPC gets close to the player, you can always have it pick up and follow the breadcrumbs left by the player. I am not sure I like that method as it keeps you from hiding from the NPC. But I was playing FarCry 2 the other day, hid in a rail car and I had an NPC walk in, look at me then proceed to walk over and lay down and go to sleep! Really annoying, but I am sure they designed that on purpose as I could not move without walking the guy up, so ended up having to kill him and alert my position anyway:)
01/03/2009 (12:25 pm)
Good deal...Remember, when the NPC gets close to the player, you can always have it pick up and follow the breadcrumbs left by the player. I am not sure I like that method as it keeps you from hiding from the NPC. But I was playing FarCry 2 the other day, hid in a rail car and I had an NPC walk in, look at me then proceed to walk over and lay down and go to sleep! Really annoying, but I am sure they designed that on purpose as I could not move without walking the guy up, so ended up having to kill him and alert my position anyway:)
#6
01/03/2009 (12:41 pm)
@Randy: By "picking up and following the bread crumbs left by the player," do you mean that the NPC would automatically know where the player's position is, regardless of whether the player was seen or not? If that is what you mean, that's making the AI cheat, and few things make me angrier than cheating AI :-)
#7
It is part of Baisc Pathfinding and a valid way to program AI. By combining it with other AI features it can be a very effective way of making the game "different" each time it is played. How is that any different than programing the AI too follow a path directly to the sound?
By making it so that a certain percentage of the time the player will be found by the AI keeps the "player" from cheating.
After you get your AI done above, play it a while and see if the NPC becomes predictable. What I am saying is sometimes you have to throw something unexpected at the player to make a more realistic AI. Or, at least that is what I am striving for, something totally unpredictable.
You have to admit. Having an AI playing come lay down and sleep at your feet, is not something you would expect:) Wonder how they found me?
01/03/2009 (1:11 pm)
Well,It is part of Baisc Pathfinding and a valid way to program AI. By combining it with other AI features it can be a very effective way of making the game "different" each time it is played. How is that any different than programing the AI too follow a path directly to the sound?
By making it so that a certain percentage of the time the player will be found by the AI keeps the "player" from cheating.
After you get your AI done above, play it a while and see if the NPC becomes predictable. What I am saying is sometimes you have to throw something unexpected at the player to make a more realistic AI. Or, at least that is what I am striving for, something totally unpredictable.
You have to admit. Having an AI playing come lay down and sleep at your feet, is not something you would expect:) Wonder how they found me?
#8
@Randy, "How is that any different than programing the AI too follow a path directly to the sound? "
Well the difference is why people call it AI cheating, because the input of a sound caused by the enemy is an actual stimulus in the game world. "Breadcrumbs" left by the player do not really exist, and are something the player (or any other live players) are completely unaware of. It's is a technique which makes sense, but it depends on the type of game. The way I see it, bryce's AI appears to be more for tactical or multiplayer style combat, where each player gets a fair chance, and AI are intellectually equal to players.
01/03/2009 (1:35 pm)
You're on the ball, bryce. It looks like every month you've got a new .plan and a new feature to show us.@Randy, "How is that any different than programing the AI too follow a path directly to the sound? "
Well the difference is why people call it AI cheating, because the input of a sound caused by the enemy is an actual stimulus in the game world. "Breadcrumbs" left by the player do not really exist, and are something the player (or any other live players) are completely unaware of. It's is a technique which makes sense, but it depends on the type of game. The way I see it, bryce's AI appears to be more for tactical or multiplayer style combat, where each player gets a fair chance, and AI are intellectually equal to players.
#9
You could make the radius tweakable and whatnot, and if the node only pings one side it's not a door, but flag it to make the AI more cautious when walking past/around it, etc.
01/03/2009 (10:30 pm)
In regards to the 'pinch-point' wouldn't it be possible to have nodes(when generating the grid layout) check around itself to see if it comes into contact with something on 2 opposite sides of the node?(like a node sitting in a doorway would ping the door frame on each side) and flag that as a pinch-point node automatically? You could make the radius tweakable and whatnot, and if the node only pings one side it's not a door, but flag it to make the AI more cautious when walking past/around it, etc.
#10
I suppose I could have a special type of node that can be manually dropped at doorways with some kind of isDoorWay = true flag, and have the AI Players cautiosly approach those points...I just want to make the set-up process for the developer as simple as possible.
01/03/2009 (11:01 pm)
@Jeff: Good idea, but then some narrow hallways would be classified as doorways. The article I read suggested that every node with only two neighbors, with one outside and one inside, is a doorway, but how do you really define inside and outside with waypoint maps? What if the doorway is inside a large interior map, and both sides are still in the building?I suppose I could have a special type of node that can be manually dropped at doorways with some kind of isDoorWay = true flag, and have the AI Players cautiosly approach those points...I just want to make the set-up process for the developer as simple as possible.
#11
As for the doorway stuff, you could have it run a check on it's neighbor(toggleable feature for maps that are known to be mostly open, perhaps?) nodes and see if it's getting the same result. If it is, you can tell it to ignore it, as you're likely getting a hallway or something as you mentioned. for a doorway, you'd really only be getting one node that's pinging 2 sides to signify a door.
If you're getting erroneous effects with multiple nodes, you could tweak the radius of the check to help filter it out too.
01/04/2009 (2:10 am)
I agree that requiring the mappers to have to place markers isn't a very good solution. As for the doorway stuff, you could have it run a check on it's neighbor(toggleable feature for maps that are known to be mostly open, perhaps?) nodes and see if it's getting the same result. If it is, you can tell it to ignore it, as you're likely getting a hallway or something as you mentioned. for a doorway, you'd really only be getting one node that's pinging 2 sides to signify a door.
If you're getting erroneous effects with multiple nodes, you could tweak the radius of the check to help filter it out too.
#12
About looking through windows... Are you defining the connections between nodes by hand, or automatically? If it's by hand, this method may be easier, but whatever. You could add a special sort of 'LOS only' connection between nodes, which would be the case if two nodes are on opposite sides of, for example, a window, or a low wall. You can't move between the nodes, but from one node, you can see the other node. Then if the AI was searching hiding spots, it could potentially move to a spot from which it could see a hiding spot node. So if one hiding place possibility was in a house with a window, the AI might decide just to walk over to the window and look around.
If you're placing connections automatically, then you could make two checks for each node pair - one at ground-level to define walkability, and one at head-height to define line of sight.
I can imagine some great moments hiding below the window-sill as an enemy peers around the room... decides nobody's there, and moves on ;)
EDIT. Also, about the breadcrumbs thing. Yes, it is cheating. It might be a good way to simulate the AI chasing a player - if youre running through corridors, it's likely that in real life, an enemy close enough behind you would be able to determine pretty much where you've gone by the nose you're making. However, maybe breadcrumbs aren't a good way to do that. It could be simulated just as easily by giving the AI a hearing sense that basicaly detects the player automatically at certain noise levels. I don't know if you've got that already; I did read your old .plans, but haven't committed them to memory yet ;)
01/06/2009 (10:48 am)
The AI looks to be coming along brilliantly... it makes me jealous, being still stuck in the player movement model myself ;P. That description of your AI thought process was very helpful to those who are implementing similar stuff. If not for the specific features, then to see how you approach a problem.About looking through windows... Are you defining the connections between nodes by hand, or automatically? If it's by hand, this method may be easier, but whatever. You could add a special sort of 'LOS only' connection between nodes, which would be the case if two nodes are on opposite sides of, for example, a window, or a low wall. You can't move between the nodes, but from one node, you can see the other node. Then if the AI was searching hiding spots, it could potentially move to a spot from which it could see a hiding spot node. So if one hiding place possibility was in a house with a window, the AI might decide just to walk over to the window and look around.
If you're placing connections automatically, then you could make two checks for each node pair - one at ground-level to define walkability, and one at head-height to define line of sight.
I can imagine some great moments hiding below the window-sill as an enemy peers around the room... decides nobody's there, and moves on ;)
EDIT. Also, about the breadcrumbs thing. Yes, it is cheating. It might be a good way to simulate the AI chasing a player - if youre running through corridors, it's likely that in real life, an enemy close enough behind you would be able to determine pretty much where you've gone by the nose you're making. However, maybe breadcrumbs aren't a good way to do that. It could be simulated just as easily by giving the AI a hearing sense that basicaly detects the player automatically at certain noise levels. I don't know if you've got that already; I did read your old .plans, but haven't committed them to memory yet ;)
Torque 3D Owner 'Sidikian'