• Advertisement
Sign in to follow this  

Hidden Markov Models instead of FSM in an FPS

This topic is 2690 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have been working on a course project in which we implemented an FPS using FSMs, by showing a top 2d view of the game, and using the bots and players and circles. The behaviour of bots was deterministic. For example, if the bot's health drops to below a threshhold, and the player is visible, the bot flees, else it looks for health packs.

However, I felt that in this case the bot isn't showing much of intelligence, as most of the decisions it takes are based on rules already decided by us.

What other techniques could I use, which would help me implement some real intelligence in the bot? I've been looking at HMMs, and I feel that they might help in bringing more uncertainty in the bot, and the bot might start being more autonomous in taking decisions than depending on pre defined rules.

What do you guys think? Any advice would be appreciated.

Share this post


Link to post
Share on other sites
Advertisement
The problem is not that your rules are hand-crafted, but that you don't have enough of them and likely that each one of them only takes into account a small number of inputs (e.g. Health < x && Player visible). The more relevant information you take into account in more subtle ways, the more complex and potentially realistic your behaviors will look.

To be honest, it all depends on the information you have available to your agent. If you don't have a lot of info in your world model, HMMs, NNs, or anything else for that matter, won't do you a lot of good.

That being said, what other information is available to your agent?

Share this post


Link to post
Share on other sites
Well, the agent(bot) can

1. See anything in it's field of view, which is a square of finite size around the bot. It constantly quiries its field of view for health packs and the player, and knows their coordinates if they are in the field of view.
This is used when the player is deciding between searching for the player or attacking the player.

2. Knows its own health and ammunition count, which are used in deciding whether to flee or attack

3. Has a memory, which is an array which contains the locations of health packs that it encounters. So, even when it is not taking health packs, if one happens to fall in its Field of view, it stores its location in its memory. This can be used when it needs to replenish its health.

4. It can find out if the player is in its Line of sight (this is used in deciding whether to fire or not). It can also tell if an obstacle is in the way.

5 It knows its own state information

Should I be giving more information to my agent?

Share this post


Link to post
Share on other sites
Can it assess another position regarding line of sight and such?

I don't know your world allows, but for example, if you had complex terrain that you can use for cover, and the bot can assess line of sight and hypothetical vulnerability in a given location, you could factor that into your pathfinding algorithm; it would be smart enough, for example, to run through a canyon for cover towards a target, or something.

This is somewhat integrated with your game design.

Does position matter, or is combat maneuvering superfluous?

If it matters, can your bot really assess different positions? Can it see an advantaged position, and plot a safe route to that position?

If it's injured, can it plot a safe route to a known health point giver widget? A safe route back to its team?

At this point it would still be very reactionary, insect-like, unimaginative, but possibly able to give a good impression.

Share this post


Link to post
Share on other sites
What about team work?

If an agent detects the player can it call for help? Direct other agents to surround the player and attack on all sides? Lure the player into a trap?

Share this post


Link to post
Share on other sites
I see why you might generalize from FSMs to Markov models for your bots. But what's "hidden;" why are you considering HMMs?

Typically, you use an HMM to model an unknown process. Do you want to use HMMs to model (and predict) the player's actions? That would make sense, though I'm not sure I'd suggest it as the first thing to do.

Share this post


Link to post
Share on other sites
Quote:
Original post by Emergent
I see why you might generalize from FSMs to Markov models for your bots. But what's "hidden;" why are you considering HMMs?

Typically, you use an HMM to model an unknown process. Do you want to use HMMs to model (and predict) the player's actions? That would make sense, though I'm not sure I'd suggest it as the first thing to do.


I'm sorry, I meant Markov Systems. I just want to maybe include a level of uncertainity. I agree it won't give any more intelligence to the bot, but a player who's playing would not be able to predict the behaviour of the bot.

Share this post


Link to post
Share on other sites
Quote:
Original post by JoeCooper
Can it assess another position regarding line of sight and such?

I don't know your world allows, but for example, if you had complex terrain that you can use for cover, and the bot can assess line of sight and hypothetical vulnerability in a given location, you could factor that into your pathfinding algorithm; it would be smart enough, for example, to run through a canyon for cover towards a target, or something.

This is somewhat integrated with your game design.

Does position matter, or is combat maneuvering superfluous?

If it matters, can your bot really assess different positions? Can it see an advantaged position, and plot a safe route to that position?

If it's injured, can it plot a safe route to a known health point giver widget? A safe route back to its team?

At this point it would still be very reactionary, insect-like, unimaginative, but possibly able to give a good impression.



Yeah, I see what you mean. The bot probably does not have enough information.

Nevertheless, will moving from FSMs to Markov systems/ Fuzzy systems help in making the game more uncertain, so that the player is not able to predict the behaviour of the bot?

Share this post


Link to post
Share on other sites
If all you want to do is make the actions of the bot less predictable, all you really need to do is put some fuzzyness in the FSM transitions. Keep in mind, a state in a FSM is only what the bot is doing at any one time. Regardless of the underlying decision process, you are still going to end up in something analagous to a state. A behavior tree, for example, sifts through the tree to find the most appropriate state for the agent to be in at that time. The only different between a FSM and a behavior tree is that the reasoning code is held in a separate place (the tree) rather than putting the transition logic in each state as in a classic FSM.

That being said, you have a number of choices -- even in a classic FSM structure. By simply making your transitions non-deterministic, you are going to achieve a lot of what you are looking for. For example, rather than StateA having transition logic that says "if ConditionB -> StateB" and "if ConditionC -> StateC" you could do something as simple as "if rand() % 3 == 1 then StateB else StateC". As you can see, StateA will transition to StateB 1 out of 3 times and State C 2 out of 3. Obviously, this is a simple example but the point is, not all transition logic needs to be based on deterministic criteria.

A more complicated, but very effective and reasonable-looking, method is what I describe in my book. By analyzing the various available choices, scoring them somehow based on their attractiveness at the time, and then using those scores -- not to always pick the winner -- but to seed weighted randoms (where the weights are based on the scores), you can have dozens, or even hundreds of potential actions in play. The good ones will be chosen more often than the bad ones because their weights will be greater. The bot will not be entirely predictable, but it will look reasonable at any given time. Rather than being able to say "he will now do this" before the fact, you will be able to say "that made sense" after the fact.

Share this post


Link to post
Share on other sites
Quote:
Original post by InnocuousFox
If all you want to do is make the actions of the bot less predictable, all you really need to do is put some fuzzyness in the FSM transitions. Keep in mind, a state in a FSM is only what the bot is doing at any one time. Regardless of the underlying decision process, you are still going to end up in something analagous to a state. A behavior tree, for example, sifts through the tree to find the most appropriate state for the agent to be in at that time. The only different between a FSM and a behavior tree is that the reasoning code is held in a separate place (the tree) rather than putting the transition logic in each state as in a classic FSM.

That being said, you have a number of choices -- even in a classic FSM structure. By simply making your transitions non-deterministic, you are going to achieve a lot of what you are looking for. For example, rather than StateA having transition logic that says "if ConditionB -> StateB" and "if ConditionC -> StateC" you could do something as simple as "if rand() % 3 == 1 then StateB else StateC". As you can see, StateA will transition to StateB 1 out of 3 times and State C 2 out of 3. Obviously, this is a simple example but the point is, not all transition logic needs to be based on deterministic criteria.

A more complicated, but very effective and reasonable-looking, method is what I describe in my book. By analyzing the various available choices, scoring them somehow based on their attractiveness at the time, and then using those scores -- not to always pick the winner -- but to seed weighted randoms (where the weights are based on the scores), you can have dozens, or even hundreds of potential actions in play. The good ones will be chosen more often than the bad ones because their weights will be greater. The bot will not be entirely predictable, but it will look reasonable at any given time. Rather than being able to say "he will now do this" before the fact, you will be able to say "that made sense" after the fact.


Thanks a lot! That's exactly what I needed!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement