3D first person shooter AI

read the Halflife SDK 2.0
The sources of the AI are available in it. As well search for bot coding ... try that one for a good start.

good luck, ''cause it ain''t easy at all
What kind of project is that ? Is that like one year project for a Degree ? ''cause the level I would rate it ...

Most FPSs use a Finite State Machine (FSM) for AI, this is the basics of how they work:

Each enemy is in one of a finite number of states (as the name suggests), these states may be like this:

Guarding
Patrolling
Suspicious
Following
Attacking
Fleeing


The state of each enemy is set firstly by whoever designs the level, and from then on, the enemy will control itself.
Say it is in the guarding state and it hears a noise, it may go into a suspicious state, where it moves slowly to where it heard the noise. Then, if it sees the player, it will go into the attacking state. If it is then wounded, it will go into the fleeing state.
Still with me?
Now, you have to code how all these states will work, most of them will involve finding a path from point A to point B.
Now, the enemies won''t need to move too far anyway, so you probably won''t need very complex pathfinding, maybe even a straight line will do.
To determine the line of sight, I think most games cheat. It is probably quite CPU intensive and much easier.
hth

"I'm going to live for ever. Even if I die trying"
Benjamin Franklin (I think)

Thanks, ahw. I''ll check out that Half Life stuff and see if I can figure anything out from it. I''ll probably have plenty of questions about it, though. There''s a lot of code there, and it''s pretty sparsely commented.

The project I''m doing is a year-long senior design project. We are working in a team of four. Right now we''re just sort of doing research on the technologies in the different areas we are going to need for the game. I''m the one researching AI. We also have someone researching multi-player gaming over a network. So if the AI turns out to be way too hard, we might have only multi-player gaming against other human opponents.


I don''t understand how you could "cheat" to determine if an enemy has line of sight to the player. What does that mean? I guess I could just say that if the enemy is within a certain distance, he automatically spots the player even if he''s behind a wall or something. But I''d like something better than that. And I still think that having the enemies navigate from where they are to a given destination will be complicated. I need the enemies to be able to navigate the level properly from one point to another. Like if I want them to chase the player, the destination will be wherever the player is. Having them just go straight towards him until they hit a wall, and then turn a little bit and do it again, seems like it would result in some pretty stupid behavior by the enemies. And they''d always be sliding up against the walls.

If anyone else has any more advice, or just knows somewhere that I could find more information about this, please let me know. Thank you.

First off, I don''t understand neither how you could "cheat" while doing Line of Sight, I''d like to know your ideas about that.
The way it''s done in HL is simply to trace a line between two points and it returns a percentage under 100% if the line was interrupted. (Look for the excellent tutorial about BSP in mrgamemaker.com to understand that better, that might be useful to your team anyway).
For navigation, you have to remember the one rule of game programming : you are not doing real calculations here, you''re only creating the ILLUSION of realism. So you don''t need to have bots that actually look around there environment or something that complicated. You''re not coding the pathfinding routines for a robot sent to Mars, you''re doing a game. So, cheat.
The solution used so far is called Waypoint navigation.

Waypoints are spread all over the level, and paths are calculated from point to point using simple A* algorithms, and eventually simple straightline navigation between nodes (for instance, if an enemy is not at a node, which is the most common thing).
If you want to go where the player is, jsut check what the nearest node is from the player, what the nearest is from you, and use A* to choose which nodes you are going to take to go there. simple as that.

myself, I am doing a MAsters, I don''t know though, what Senior level is. But I''d tell you one thing, if the guys at Valve didn''t give us Bots for deathmatch, don''t worry too much about achieving that yourself. Rather, concentrate maybe on doing vey well done specific monsters that demonstrates some specific things in AI .why not do a herd of little animals ? Or some sort of fleeing monsters. That would be much better than doing a crappy AI that tries to emulate a human player unsuccessfully .

good luck, and ask your questions, I am always glad to help, especially if it helps me clarify my ideas (my MAsters is gonna be on group AI in games ...)

youpla :-P

Ok, here is my master plan for cheating =):

Give each room a unique number.
Make a list of all the rooms that shows exactly how they connect, so it would look something like this:

Room 1: Room 2, Room 4, Room 6
Room 2: Room 1, Room 3
Room 3: Room 2... and so on

Now, if the player does any actions that might cause noise (jumping, firing, running, shouting in pain), then any monsters within range of the noise who are also in the room, are considered to be within the line of sight.
Draw the floor plan of a room, and use 2d collision detection to determine other line of sights (so a player can''t just walk in front of enemies silently and not get seen).
Finally, if the player is really close to the enemy, always consider that to be a line of sight. They do this in Quake II I''ve noticed. And it is really annoying when you try and play a mission giving yourself 1 health and a blaster to play with the whole way through =)

As for pathfinding, it''s probably best to use the waypoint system, or you can cheat completely, and if the player is > 4 rooms away then just teleport from one room, to the next, as long as the player doesn''t see it, you can do anything =)

"I'm going to live for ever. Even if I die trying"
Benjamin Franklin (I think)

Ok, here is my master plan for cheating =):

Give each room a unique number.
Make a list of all the rooms that shows exactly how they connect, so it would look something like this:

Room 1: Room 2, Room 4, Room 6
Room 2: Room 1, Room 3
Room 3: Room 2... and so on

Now, if the player does any actions that might cause noise (jumping, firing, running, shouting in pain), then any monsters within range of the noise who are also in the room, are considered to be within the line of sight.
Draw the floor plan of a room, and use 2d collision detection to determine other line of sights (so a player can't just walk in front of enemies silently and not get seen).
Finally, if the player is really close to the enemy, always consider that to be a line of sight. They do this in Quake II I've noticed. And it is really annoying when you try and play a mission giving yourself 1 health and a blaster to play with the whole way through =)

As for pathfinding, it's probably best to use the waypoint system, or you can cheat completely, and if the player is > 4 rooms away then just teleport from one room, to the next, as long as the player doesn't see it, you can do anything =)

The other thing I forgot is the actual need for high tech pathfinding. There are two main areas which you need path finding: Patrolling and chasing after the player.
The level editor can decide where the enemies will patrol, so couldn't they determine the path so that there is a clear straight line between all points?
And when will the enemy be chasing after the player? When they have line of sight (or close to it), so would it be possible to assume that since there is line of sight, you can simply head in a stright line (there are potential problems with this, but that's the cost of cheating =)
I think most people in the biz cheat a _lot_ for their monsters and use very simple pathfinding. Not that they are heros or anything, but they obviously have a few clues =)
hth

"I'm going to live for ever. Even if I die trying"
Benjamin Franklin (I think)

Edited by - ragonastick on September 20, 2000 2:47:09 AM

Actually I don''t remember if they use A* in Halflife, you got to check that out. As for cheating for the movement by teleporting ... I mean, are you doing a project on AI or what ???
OTOH, your idea of having rooms is nice, but necessary. You could, if you really want to have rooms, use the technique used in LMCTF (a MOD for quekae 2), where the designers simply put a volume entity (a massive box) and assign it a room number name. Not necessary at all for pathfinding routines. You could as well have better waypoints, and assign them more values (a waypoint would be more than just a point in space, it would have memeber variables).

You know, you should really check that Botman site I gave you at the beginning of that thread. This guy is doing bots and only bots, it could be a very good source of information for you.

As for my love of cheating:
Looking at the experience of Albino Squirrel, this being the very first AI project, I think things should be simple. That''s just the way I see things. And as long as the player A) Has fun and B) doesn''t realise, then who cares if we are to cheat a bit?

But the AI in most FPSs is really dodgy, it does the job, and that is about it. And I think it is really simple. Writing bots is a completely different topic, they must be able to match a human and they only have a few advantages.

I say, for a first project, mimick the basic grunt, it will do one of a few orders like guard and patrol and if it sees someone, it will shoot at them and run after. Then if their health drops below 25%, they flee. Actually, remember how everyone was really impressed (well, at least reviewers were) when monsters started doing that? It isn''t very hard to do, but it impressed the press, which I found amazing. Do I have a point? Not really. What I''m _trying_ to communicate is that simple is often best, especially for a first project.

yeah. me shut up now

"I'm going to live for ever. Even if I die trying"
Benjamin Franklin (I think)

Let me know if you think this is a reasonable approach. I worked out some preliminary ideas for what states the enemies could be in, and what actions would be available in each state. Each action will chosen according to certain criteria or at random. When each action is completed, another is chosen. Each enemy will also need to keep track of what direction it is traveling in, what is the next node it is going to, and what its final destination is.
1.Guarding – when in the guarding state, the enemy stays were it is, guarding a particular location. It will look around, trying to spot the player. If he sees the player, he will go into the Attacking state. If the Guarding enemy gets severely wounded, it will go into the Fleeing state.
a. Rotate45Clockwise – the enemy rotates on the spot 45° clockwise.
b. Rotate45CounterClockwise – the enemy rotates on the spot 45° counter-clockwise.
c. Rotate180 – the enemy rotates on the spot 180°.
d. Stay – the enemy stays facing in the same direction. There can be a flag that is set if the enemy should never rotate at all for situations when the player can only approach in one direction.
2.Patrolling – the enemy is patrolling around the level, searching for the player or for his comrades. If a Patrolling enemy sees the player, he will go into the Attacking state. If the player fires a weapon within a certain distance of the Patrolling enemy, it will go into the Attacking state. If a Patrolling enemy gets wounded, it will go into the Attacking state.
a. ShortPatrol – the enemy goes to a nearby node and then back again
b. LongPatrol – the enemy goes to a random node anywhere in the level
c. GroupUp – if the enemy gets within a certain distance of another Patrolling enemy, it will now follow that enemy (go to the same nodes)
3.Attacking – the enemy has seen the player and now wants to kill him. If an Attacking enemy loses line of sight of the player for a certain length of time, the enemy will go into the Patrolling state. If the Attacking enemy is severely wounded, it will go into the Retreating state. (unless the enemy is frenzied)
a. LongRangeAttack – if the enemy has a long ranged attack and he has line-of-sight to the player, he will used the long ranged attack.
b. ShortRangeAttack – if the enemy is close enough to attack the player at short range, and is facing the player, he will use his short ranged attack.
c. CloseIn – if the enemy has no long ranged attack and is too far away to use his short ranged attack, he will move directly towards the player
d. Chase – if the enemy loses line-of-sight to the player, he will move towards where the player is until he re-establishes line-of-sight
e. Reposition – if an enemy has just completed an attack, it will move to a nearby node to position itself for another attack
f. Turn – if the enemy is not facing the player, it will turn to face him
4.Retreating – the enemy has had enough of the fighting. He has been wounded badly and decides that the fight is hopeless. A Retreating enemy will perform one of the available functions, after which it will go into either a Patrolling state (if he is far from the player) or a Guarding state (if he is fairly close to the player).
a. RunAway – the enemy chooses a random node in the level that is at least a certain distance from the player and runs to this node
b. Hide – the enemy chooses a node that is not within line of sight to the player and runs to this node
c. Surrender – the enemy stops where it is and surrenders, not moving until the player is no longer within line-of-sight

The criteria that will be used to determine which state the enemy should be in includes the following: if the enemy has line-of-sight to the player, the enemy’s health, distance to the player, if the player fired a weapon, if the enemy was hit, and the amount of time since the enemy last saw the player. Data that also need to be kept track of includes: distance from enemy to nearest other enemy, direction the enemy is facing, location of each enemy, next node the enemy is going to, destination node, and the final destination of the enemy.

Sounds good, you learn fast =)

One thing you may want to consider is changing the patrolling state so the path they take is determined by the level designers rather than going to random/semi-random nodes. That way, you have more control over them and path finding will be heaps easier. And they will also probably seem smarter because the paths will be thought up by real people =)

Good luck

And what is the purpose of the surrendering state? I suppose it will make it more realistic, but what is the setting and what type of creatures are they. I know Rainbow 6 has a surrendering state, and it worked quite well. I think I''ll stop rambling now.

"I'm going to live for ever. Even if I die trying"
Benjamin Franklin (I think)

I just decided to have the enemies patrol random places for simplicity, so that the level designer would have less to do. Plus this way it won''t be so predictable. Someone could play the level 100 times and still not know where the enemies are going to be, since they''d be searching random places. I supposed it''s true that they may not seem as intelligent because they might patrol some unimportant places, but at least they''ll be unpredictable. I''m not sure if this is a good trade off, but if not, it won''t be that hard to fix.

The reason for the surrendering option in the "Retreating" state is just because I think it would be cool. I just really like when the enemies surrender in Perfect Dark and then you just get to kill them anyway. It''s fun. So in our game, if the enemy goes into the "Retreating" state, it will choose between one of the three options (run away, hide, or surrender). I''ll just make surrender be the most unlikely thing to happen, so that it only happens very rarely.

Okay, now I have another question. When I want to move an enemy through the level to a specific point, first I move him to a nearby node. Once there, I have to calculate a path from that node to the node that is closest to his destination. To do this, I want to check all the nodes adjacent to his current node and for each one calculate (distance from current node + distance to destination node). The one that comes out the lowest is the one I want to go to. My problem is, how do I quickly figure out which nodes are adjacent to the node the enemy is currently on?

And one more question: what should happen if for some reason the enemy collides with a wall or another enemy when it is going somewhere? It shouldn''t ever hit a wall, unless it gets knocked back by getting hit by a weapon or something. Otherwise, if the nodes are places well, that shouldn''t be a problem. But enemies could run into each other pretty easily. I guess I could include enemies in the collision detection when it is decided which node to go to next. Then the enemy would just go around. But it might be better to just wait until the other enemy moves out of the way. There could also be a problem with colliding with the player when the enemy is trying to retreat or reposition or something.