[AI] : advice on FSM structure and transitions

Posted By: demiGod

[AI] : advice on FSM structure and transitions - 03/09/07 22:09

Hi,

I need some advice here in a basic finite state machine architecture that i plan to execute and expand later. Now a little picture:



Well, i want to implement a hierarchical FSM where the teams have the ability to perform commands to their respective players defining the goals to be anchieved, considering the game circunstances like defending or attacking.

Also, the players have their own states and i pretend to centralize the logic of the transitions between states embedded in the states themselves.

If you see the picture, the animation states and steering behaviors are calculated / checked in the players states and not in the players action.

In the other hand i need to implement two game modes: a player mode when the player controls the selected entity by the input (keyboard, gamepad, joystick), and a computer mode, when there is the AI that controls the movement and behavior of the entities.

Well, i have some doubts about the good way / modular way to implement and join all this parts i mentioned in one functional architecture, so i am waitting some answers from people more experient in this matter, about these questions:

1) Is this a good way to anchieve what i want, or there is another better approach?

2) Should i handle the animation states in the player states logic or in the global players action, or it is the same?

3) If the transition logic its embedded in the states themselves, how can i prevent to duplicate constant if checking transitions in all states, i mean, there is another way to do that unless using if statements to define what transition should occour?
This way i need to check every frame a "transition table" in all states, or not?

4) Where should be included the player and computer modes in the overall structure i am presenting, in an effective way?

Ok, resuming i need some hints / guidelines from people who have done this already and know the problems of a FSM when handle many states, and its integration with animation, input, steering behaviors, etc.

Thanks in advance and sorry for the long post.
Posted By: Gordon_Shumway

Re: [AI] : advice on FSM structure and transitions - 03/10/07 00:10

Hi DemiGod !!!

First of all, what kind of game your planing to do ?

In my opinion FSM is very powerfull and a good way to create AI for most of the games. A very, very important point, which is maybe missing in your picture, is the communication between the different machines.

Just a simple example ....mmmh let me think .... ok:
Jon can do a few things: working, go home, eat, sleep
His wife can do: do housework(yesterday was the worlds-woman-day ), cook, sleep
After work before he gets a little bit sleep, he wants to eat a nice lunch.

So, If they are not communicate with each other, the following will happen:
Jon is working the whole day and when he finished he gets home and is very hungry, but his wife is doing housework until she gets to bed. Jon has to go to bed without eat anything. She will never cook for him.

But if Jon is sending a message everything is fine and the situation is the following:
Jon has finishing work and is sending the message "Honey, I'' be at home in 1 hour and I'm very hungry, please cook me a nice litte lunch". His wife receives the messages stopps what she was doing and starts to cook lunch.
The he wents home, eats and then goes to bed.

I hope, you understand that communication is very important in FSMs.

Bye, G.S.
Posted By: demiGod

Re: [AI] : advice on FSM structure and transitions - 03/10/07 11:51

Hi Gordon, thanks for your answer.

You are right, communication between FSMs its very important indeed and the examples you gave are very explanatory. However i already had planned introducing a message system but i didnt included in the picture because of the complexity of the links and probably will difficult to transmit my idea / doubts:

You see, i am planning to do an AI architecture for sport games, especially game with players and ball or other object(s) and i want it in such a way that can be modular and reusable to handle a wide range of situations.

The message system actually will be the bridge between the FSMs but also the entities themselves can send messages between them, and each team will communicate with their respective players with the messaging system (ex: AI_goHome (sender, receiver, message);)

The problem is, with all those independent systems and modules i need to know for sure which will be the better (or one better) way to join all this together and i dont have yet in my mind the right solution.

So, still need some hints / advices / guidelines.
Posted By: Gordon_Shumway

Re: [AI] : advice on FSM structure and transitions - 03/10/07 13:27

HI again,

ok a sports game. There is one book which could be very intresting for you "Programming Game AI by Example" by Mat Buckland. It's all in C++ but it's not that hard to translate it into C-script.
He creates a simple soccer game (two computers play soccer against each other) based on FSM.

So maybe have a look at that.

I can give you the advice, first script all FSMs, that every entity can do anything it should do.
Than create a master mind and use communications.

If you have a special question pleas ask me.

Bye G.S.
Posted By: Damocles

Re: [AI] : advice on FSM structure and transitions - 03/10/07 14:09

I could imagine for a message system, that every
Entity has a message-que where messages and requests are stored
by importance and expieration time.

Whenever the State Machine comes to deciding to switch
to another state, it looks into the message-que and
commits the most important orders stores there. (with some random variation)

This message-que can be accessed by other entities (nearby), a common controll AI,
or simply be the entity itself (like the request to restore health or react to an attack)

So every time the statemachine checks for a statechange
(either every frame, or whenever it finished its last action)
it will switch to the corresponding state to fulfill the most important order.

Putting some random variation into the choise is important, to
make the AI behave less predictable.

The message-que should expire old requests that are over time, and
remove requests that where fulfilled.

---

Animation is not linked to the AIs decisionmaking, but a nice addon to its grafical
apperance. So the animation should be seperated from the AI logic, as it does not belong there.
The current state should just set the entities "animation-state" to the corresponding
animationtype. The animation itself is run in a paralel function that reads out the animation-state.
Posted By: demiGod

Re: [AI] : advice on FSM structure and transitions - 03/10/07 16:07

@ Gordon: thanks for the advice, actually i already bought that book and read it and some concepts i mentioned its based on that, but translating c++ to c-script isnt so easy for me, so i will accept your offer and if i have specific questions i will ask you, if you dont mind..

About the master mind you are referring after scripting all FSMs.. its some kind of central CPU? i dont understood, you see, i am scripting all the transitions logic embedded in the transitions themselves, why should i need a central master mind with ifs and thens, thats what i want to avoid..


@ Damocles:

a) i understand the concept of message quering, but you see, i will
implement a separate function for each message (msg_passToMe,
msg_returnHomeRegion, etc.), and when an entity sends a message to
another team mate, where should be made that quering? If i am centralizing
the state transition logic in the states themselves, should be there or
in a separate global / CPU function?

b) about the random variation i intend to implement also some kind of fuzzy
logic in the states transition, but later;

c) about the animation, yes the animation handle its done with separate
states / functions saved in a simple skill like my.animation_state. So you
are saying that the animation states transition should be checked inside
the players states transition logic, isnt it?

I have another problem, i dont very well how to integrate the computer and player modes, because the input its making some mess with concorrent states transitions..
Posted By: Damocles

Re: [AI] : advice on FSM structure and transitions - 03/10/07 17:54

There are so many ways to program the messaging or state-transotion logic,
I can only tell you how I would approach it.

You could make all states for example as a seperate, looping function.

For example, a statefunction could look like this:


//the state is just an everlooping funtion, that will do the
//current states tasks, and switch to another function if required

function state_a (this_state)
{
var new_state;

new_state=this_state;
while(1)
{

new_state=get_new_state(this_state); //get the required state from the logic

//either switch to a new state, or keep in this one
if(new_state!=this_state)
{
//switch to new state
if(new_state==statetype_b){state_b(new_state);}
if(new_state==statetype_c){state_c(new_state);}
if(new_state==statetype_d){state_d(new_state);}
return; //terminate this state-loop
}


//do the thinks to do for this state
...


wait(1);
}
}



function get_new_state(current_state)
{
//here is the logic that determines what state to take
//this is the complicated logic to program

var priority; //the priority tells you, how important the current state is the bot is in

if(current_state==statetype_a){priority=10;} //low priority state, like patroling on a path
if(current_state==statetype_b){priority=50;} //high priority state, like attacking an enemy
if(current_state==statetype_c){priority=90;} //very high priority state, almost dead and looking for healthpickup
if(current_state==statetype_d){priority=0;} //no priority state, waiting for example

//get a new state from the "normal" statechange
if(need_statechange()){current_state=get_new_best_state();}

//overwrite the current state, if there is a hight priority state in the message stack
if(message_stack_priority()>priority) //is the most important state in the list more important than what I do now?
{
current_state=get_state_from_messagestack(); //get the required new state from the messages
}

return (current_state); //no changes required, just keep the old state
}




....
And so on. The message list could be mode of arrays, that store requests by other bots,
or the controller AI to change the bots state to something.
-> like following the player or attacking a certain enemy.
these requests get a priority (fixed value + a random value)
and a time (so that like 20 seconds after the request, it is unimportant and gets erased)

This way the bot will react to important requests from the messagebox
if they are more important than what the bot is doing now.
Posted By: Damocles

Re: [AI] : advice on FSM structure and transitions - 03/10/07 18:20

You should first experiment with simple statemachines
with few states, and not too complex interactions like a team AI.

From the experience with this it is easier to plan a more complex AI later.

Better have a simple, but robust working AI, than
a too complex AI that is hard to debug.

Most of the AI can be done by thinking and writing it on paper actually,
implementing this is mostly just pure work, debugging and tunig values.
Posted By: demiGod

Re: [AI] : advice on FSM structure and transitions - 03/10/07 19:20

Yes, you are right. But i really had start simple and now i am handling with five or six states and their transition isnt so difficult to code, the states are changing considering the conditions i put in the state logic inside them.

Later i will try to expand it and implement other things, but like i said i am in trouble with the input system, i´ll give you an example:

Each entity has some important skills like:

my.team - which team this entity belongs considering the formation chosen
my.type - type of player defining its role / task
my.selection - if the entity its selected or not to perform a task
etc..
and my.gameMode, which can be playerGameMode (controlled by the player input) or computerGameMode (controlled by the AI - ex: return to its home region vector). But this way i need to check in every state transition logic which team and gameMode it belongs, its a bit annoying, i was looking for another way to handle this input question...

Thanks Damocles, i really appreciate your help.
Posted By: Damocles

Re: [AI] : advice on FSM structure and transitions - 03/10/07 19:36

Quote:

But this way i need to check in every state transition logic which team and gameMode it belongs




Ok, this is a typical example of redundant code.
Try to write a function that includes the part of code that
is repeating, so you only have to write it at one place.
Posted By: Gordon_Shumway

Re: [AI] : advice on FSM structure and transitions - 03/10/07 19:56

Hey again !!!

Why do you need a mastermind? It's a good question.
First of all there are lot of possibilöities to script such an AI.
I would use in most of the cases a mastermind, because all actions are relative easy to handle, but it depends on your game.

If you're scripting a soccer game, for example, all of your teammembers could:
run
pass the ball
shoot
defend
support defender
support attacker.....

So, if you're using a mastermind, it's in my opinion easier to switch between different situations. For example:
One entity got the ball, than he could send a message to the mastermind "Hey I've got he ball". The mastermind switches the status from defence to attack.
All the other entity except the one who has the ball could now support the attacker. And so on....A supporter is near the goal and free and if you're using a weighting something like if a value for passing is 1, the player will allways pass the ball to him, and if it's ZERO passing wouldn't be a good idea and in between ? The player with ball sees an denfender in front of him, so he has to decide shoot to the goal or pass the ball. A simple question to the mastermind "what's best?" And the masterminds says there another player free near the goal the weighting is very high - it's a good idea to pass the ball.....
If you're not using a mastermind this would be like, "Hey player1 what's your weighting?"-"My weighting is 0.35"-"Hey player2, whats your weighting"-"My is 0.8"-"Hey player3 what's your weighting?"-"My weighting is 0.15....-"Hey player11, whats your weighting"-"My is 0.55"

I hope you understand what I mean, you could scipt all without a mastermind, but I would use on because it's easier to use a mastermind.

Bye G.S.
Posted By: demiGod

Re: [AI] : advice on FSM structure and transitions - 03/10/07 20:25

Hello again Gordon,

Another very good explanation you gave, thanks.

Maybe i am making some confusion, but this mastermind couldnt be the team AI state machine? You see, depending on the state the team is, it will send messages to the respective players that belongs to that team, but ..ahh, so if the players dont send messages to team there will be a problem, so thats because we need a mastermind, or not?

Sorry, but i didnt understood very well the concept of the mastermind yet..

The book you mentioned above refer to a global player state that works like a message router, is that you are calling the mastermind?

Thanks.
Posted By: Gordon_Shumway

Re: [AI] : advice on FSM structure and transitions - 03/10/07 21:14

A mastermind is something like a communication interface, which also could decide what to do.

All important informations will be send to the mastermind by any teammember. Every teammember could also ask the mastermind for special informations (like who is the best player for passing? Or is shooting to the goal the best solution ?)
If you don't use a mastermind, every teammember has to ask all the other teammembers for a certain information. Just a simple example think about who has the ball ?(ok, it's not a very good example, because you could easily script it with a handle, but it show the difficulty of you're not using a mastermind)
Player1 ask Player2 - D'you have the ball? - NO
Player2 ask Player3 - D'you have the ball? - No...
...Player2 ask Player11 - D'you have the ball? - Yes - Ah good, I will support you.

Then Player11 passes the ball to player5.
So player11 has to send to all other player the message I'dont have the ball anymore.

Then all starts again
Player1 ask Player2 - D'you have the ball? - NO
Player2 ask Player3 - D'you have the ball? - No...
.....
...
And you have to do this for all Players !!!!!!

If you're using a mastermind:
Player11 send message to mastermind - "I've got the ball"
Player1 ask mastermind - "Who has the ball" - "Player11 has the ball" - "Ok I will support him" or
Mastermind send messages to all players - "Player11 has the ball"
Player11 passes the ball to Player5
Player5 send message to mastermind - "I've got the ball"
Mastermind send messages to all players - "Player5 has the ball"

I hope you see it's much easier to handle.

Bye G.S.
Posted By: demiGod

Re: [AI] : advice on FSM structure and transitions - 03/10/07 21:30

Ok, i understand what you mean, that it seems to be easy to handle that information, thougth in that example of "who has the ball" i simple created an entity pointer TheControllingPlayer, which is updated with the Id skill of the entity which have less than a given distance to the ball, so TheControllingPlayer its updated every frame and i simple can support it - supportPlayer(my, TheControllingPlayer, speed, &targetPosition).

Well, thanks for your explanations i understand the concept now and if you dont mind if i fall in serious troubles i will ask you..thanks
Posted By: Gordon_Shumway

Re: [AI] : advice on FSM structure and transitions - 03/10/07 22:09

If you've any problems, just ask or send me an PM.

One last question, what kind of sports game you're doing ?

Bye G.S.
Posted By: demiGod

Re: [AI] : advice on FSM structure and transitions - 03/10/07 22:22

Thanks.
Its a soccer type game but with robots / droids, however the goal is to implement a reusable AI that can be used in other projects too. Its not been a trivial task at all.
Posted By: Damocles

Re: [AI] : advice on FSM structure and transitions - 03/11/07 12:22

To reuse the AI, you should have a very clean and well structured
approach. I think it is very demanding to abstract the AI
enought to make it multi-purpose usable. How about you start by using UML
as a Designtool to create a dependency diagram for it.
You dont have classes in 3dgs, but with some abtraction you can create
"classlike" structures.

You should also have a look into Lite-C, as this will become some kind of standart,
an is offers more structured elements for AI programming (like the structs for example)
Posted By: demiGod

Re: [AI] : advice on FSM structure and transitions - 03/11/07 13:53

Yeah, make it reusable like a sports "template AI" it seems to me very difficult too, probably i will try developing the system just for the project i mentioned.

Actually i use for some time flowcharts to handle the systems, so i divided it into modules like teamAI, playerAI, messaging system, steering behaviors, math calculations, animation, movement / gravity, etc., the problem is, like you said, there is no classes / objects, so handling and integrating those modules could be a pain..

C++ and SDK its not solution for me right now (learning curve too high) and even lite C and structurs dont know if it will make such a difference anyway..

I think i will continue this way, too bad there is no base examples on this matter, not the code but the abstract implementation.
© 2023 lite-C Forums