État du jeu 'Stack'?

52

Je réfléchissais à la manière d'implémenter les états de jeu dans mon jeu. Les principales choses que je veux pour cela sont:

  • Les états supérieurs semi-transparents sont capables de voir à travers un menu de pause au jeu derrière

  • Quelque chose OO-I trouve cela plus facile à utiliser et à comprendre la théorie derrière, ainsi que de rester organisé et d'ajouter plus à.



Je comptais utiliser une liste chaînée et la traiter comme une pile. Cela signifie que je pourrais accéder à l'état ci-dessous pour la semi-transparence.
Plan: la pile d’états doit être une liste chaînée de pointeurs vers IGameStates. L'état supérieur gère ses propres commandes de mise à jour et d'entrée, puis un membre, isTransparent, lui permettant de décider si l'état situé en dessous doit être tracé.
Alors je pourrais faire:

states.push_back(new MainMenuState());
states.push_back(new OptionsMenuState());
states.pop_front();

Pour représenter le chargement du joueur, puis aller aux options, puis au menu principal.
Est-ce une bonne idée ou ...? Devrais-je regarder autre chose?

Merci.

Le canard communiste
la source
Voulez-vous voir MainMenuState derrière OptionsMenuState? Ou simplement l'écran de jeu derrière OptionsMenuState?
Skizz
Le plan était que les états aient une opacité / une valeur / un drapeau isTransparent. Je vérifierais et verrais si l'état supérieur avait ceci vrai, et si ainsi quelle valeur il avait. Puis rendez-le avec autant d'opacité sur l'autre état. Dans ce cas, non je ne le ferais pas.
Le canard communiste du
Je sais qu'il est tard, mais pour les futurs lecteurs: n'utilisez pas newcomme indiqué dans l'exemple de code, il s'agit simplement de demander des fuites de mémoire ou d'autres erreurs plus graves.
Pharap

Réponses:

44

J'ai travaillé sur le même moteur que coderanger. J'ai un point de vue différent. :)

Premièrement, nous n'avions pas de pile de FSM - nous avions une pile d'états. Une pile d'états constitue un seul FSM. Je ne sais pas à quoi ressemblerait une pile de FSM. Probablement trop compliqué pour faire quoi que ce soit de pratique.

Mon plus gros problème avec notre machine à états globale était qu'il s'agissait d'une pile d'états et non d'un ensemble d'états. Cela signifie que, par exemple, ... / MainMenu / Le chargement était différent de ... / Loading / MainMenu, selon que le menu principal était activé avant ou après l'écran de chargement (le jeu est asynchrone et le chargement est principalement piloté par le serveur. )

Comme deux exemples de choses rendues laides:

  • Cela conduisait par exemple à l'état LoadingGameplay, donc vous aviez Base / Loading, et Base / Gameplay / LoadingGameplay pour le chargement dans l'état Gameplay, qui devait répéter une grande partie du code dans l'état de chargement normal (mais pas tous, et en ajouter d'autres). )
  • Nous avions plusieurs fonctions telles que "si le créateur de personnage va dans le gameplay; si dans le gameplay allez dans la sélection de personnage; si dans la sélection de personnage revenez à la connexion", parce que nous voulions afficher les mêmes fenêtres d'interface dans des états différents mais faire le Back / Forward les boutons fonctionnent toujours.

Malgré le nom, ce n'était pas très "global". La plupart des systèmes de jeu internes ne l'utilisaient pas pour suivre leurs états internes, car ils ne voulaient pas que leurs états fouillent avec d'autres systèmes. D'autres, par exemple le système d'interface utilisateur, pourraient l'utiliser, mais uniquement pour copier l'état dans leurs propres systèmes d'état locaux. (Je voudrais tout particulièrement mettre en garde contre le système pour les états d'interface utilisateur. L'état d'interface utilisateur n'est pas une pile, mais bien un groupe de disponibilité de base, et essayer de forcer toute autre structure dessus ne fera que créer des interfaces utilisateur dont l'utilisation est frustrante.)

Ce qui était bien, c’était de séparer les tâches d’intégration de code des programmeurs d’infrastructure qui ne savaient pas comment le flux de jeu était structuré, de sorte que vous puissiez dire au gars qui écrit le correctif "placez votre code dans Client_Patch_Update" et au gars qui écrit les graphiques. chargement "mettez votre code dans Client_MapTransfer_OnEnter", et nous pourrions échanger certains flux logiques sans trop de problèmes.

Sur un projet parallèle, j’ai eu plus de chance avec un ensemble d’ états que avec une pile . juste un moyen compliqué de synchroniser les choses avec des variables globales - Bien sûr, vous allez finir par le faire dans un délai raisonnable, mais ne concevez pas cela comme votre objectif . Fondamentalement, l'état dans un jeu n'est pas une pile et les états dans un jeu ne sont pas tous liés.

Le GSM aussi, comme le font souvent les indicateurs de fonction et les comportements non locaux, a rendu le débogage plus difficile, bien que le débogage de ce type de grandes transitions d'état ne soit pas très amusant avant que nous l'ayons. Les ensembles d'états au lieu de piles d'état n'aident pas vraiment cela, mais vous devriez en être conscient. Les fonctions virtuelles plutôt que les pointeurs de fonctions peuvent atténuer quelque peu cet inconvénient.


la source
Super réponse, merci! Je pense que je peux tirer beaucoup de votre post et de vos expériences passées. : J + 1 / Tick.
Le canard communiste
La bonne chose à propos d'une hiérarchie est que vous pouvez créer des états d'utilitaires qui sont simplement poussés vers le haut sans avoir à vous soucier de ce qui se passe ailleurs.
coderanger
Je ne vois pas en quoi c'est un argument pour une hiérarchie plutôt que des ensembles. Au contraire, une hiérarchie complique toutes les communications entre États, car vous ne savez pas où elles ont été poussées.
Le point que les UI sont en fait des DAG est bien compris, mais je ne suis pas d’accord sur le fait qu’il peut certainement être représenté dans une pile. Tout graphe acyclique dirigé connecté (et je ne peux pas penser à un cas où il ne s'agirait pas d'un DAG connecté) peut être affiché sous la forme d'un arbre et une pile est essentiellement un arbre.
Ed Ropple
2
Les piles sont un sous-ensemble d'arbres, qui sont un sous-ensemble de DAG, qui sont un sous-ensemble de tous les graphiques. Toutes les piles sont des arbres, tous les arbres sont des groupes de disponibilité de base, mais la plupart ne sont pas des arbres et la plupart des arbres ne sont pas des piles. Les groupes de disponibilité de base de données ont un ordre topologique qui vous permettra de les stocker dans une pile (pour la traversée, par exemple, la résolution des dépendances), mais une fois que vous les avez mis dans la pile, vous avez perdu des informations précieuses. Dans ce cas, possibilité de naviguer entre un écran et son parent s’il a un frère antérieur.
11

Voici un exemple d'implémentation d'une pile de jeu qui m'a semblé très utile: http://creators.xna.com/en-US/samples/gamestatemanagement

Il est écrit en C # et pour le compiler, vous avez besoin du framework XNA. Cependant, vous pouvez simplement consulter le code, la documentation et la vidéo pour vous faire une idée.

Il peut prendre en charge les transitions d'état, les états transparents (tels que les boîtes de message modales) et les états de chargement (qui gèrent le déchargement des états existants et le chargement de l'état suivant).

J'utilise maintenant les mêmes concepts dans mes projets de passe-temps (non-C #) (d'accord, cela pourrait ne pas convenir pour des projets plus importants) et pour les projets de petite taille / hobby, je peux définitivement recommander l'approche.

Janis Kirsteins
la source
5

Ceci est similaire à ce que nous utilisons, une pile de FSM. Fondamentalement, il suffit de donner à chaque état une fonction entrée, sortie et coche et de les appeler dans l’ordre. Fonctionne très bien pour gérer des choses comme le chargement aussi.

coderanger
la source
3

L'un des volumes "Game Programming Gems" contenait une implémentation de machine à états destinée aux états de jeu; http://emergent.net/Global/Documents/textbook/Chapter1_GameAppFramework.pdf donne un exemple d'utilisation de ce jeu pour un petit jeu et ne devrait pas être trop spécifique à Gamebryo pour être lisible.

Tom Hudson
la source
La première section de "Programmation de jeux de rôle avec DirectX" implémente également un système d'état (et un système de processus - distinction très intéressante).
Ricket
C'est un excellent document qui explique à peu près exactement comment je l'ai implémenté dans le passé, à l'exception de la hiérarchie inutile des objets qu'ils utilisent dans les exemples.
dash-tom-bang
3

Juste pour ajouter un peu de standardisation à la discussion, le terme CS typique pour ce type de structures de données est un automate à pile .

munificent
la source
Je ne suis pas sûr qu'une implémentation réelle de piles d'états dans le monde réel équivaut presque à un automate à pile. Comme mentionné dans d'autres réponses, les implémentations pratiques se terminent invariablement par des commandes telles que "pop deux états", "permuter ces états" ou "passer ces données à l'état suivant en dehors de la pile". Et un automate est un automate - un ordinateur - pas une structure de données. Les piles d'état et les automates à pile utilisent une pile comme structure de données.
1
"Je ne suis pas sûr qu'une implémentation réelle de piles d'état soit presque équivalente à un automate à pile." Quelle est la différence? Les deux ont un ensemble fini d'états, une histoire d'états et des opérations primitives pour pousser et faire apparaître des états. Aucune des autres opérations que vous mentionnez ne diffère fondamentalement de celle-là. "Pop two states" est juste deux fois. "swap" est un pop et un push. Transmettre des données est en dehors de l’idée de base, mais chaque jeu utilisant un «FSM» exploite également des données supplémentaires sans avoir l’impression que le nom ne s’applique plus.
magnifique
Dans un automate à pile, le seul état pouvant affecter votre transition est l'état du dessus. L'échange de deux états au milieu n'est pas autorisé; Même en regardant les états au milieu n'est pas autorisé. Je pense que l’expansion sémantique du terme "FSM" est raisonnable et présente des avantages (et nous avons toujours les termes "DFA" et "NFA" pour le sens le plus restreint), mais "pushdown automon" est strictement un terme informatique et il y a seulement une confusion à attendre si nous l'appliquons à tous les systèmes basés sur des piles.
Je préfère les implémentations où le seul état qui peut affecter quelque chose est l'état qui domine, bien que dans certains cas, il soit pratique de pouvoir filtrer l'entrée d'état et de passer le traitement à un état "inférieur". (Par exemple, le traitement des entrées du contrôleur correspond à cette méthode, l'état supérieur prend les bits dont il se préoccupe et éventuellement les efface, puis passe le contrôle à l'état suivant de la pile.)
dash-tom-bang
1
Bon point, corrigé!
magnifique
1

Je ne suis pas sûr qu'une pile soit entièrement nécessaire et limite les fonctionnalités du système d'état. En utilisant une pile, vous ne pouvez pas "sortir" d'un état vers l'une des nombreuses possibilités. Supposons que vous commenciez dans «Menu principal», puis dans «Charger la partie». Vous souhaiterez peut-être passer à un état «Pause» après avoir chargé avec succès la partie sauvegardée et revenir à «Menu principal» si l'utilisateur annule la charge.

Je voudrais juste que l'état spécifie l'état à suivre lors de sa sortie.

Pour les cas où vous souhaitez revenir à l'état précédant l'état actuel, par exemple "Menu principal-> Options-> Menu principal" et "Pause-> Options-> Pause", laissez simplement comme paramètre de démarrage l'état Etat à retourner.

Skizz
la source
J'ai peut-être mal compris la question?
Skizz
Non tu ne l'as pas fait. Je pense que l'électeur a fait.
Le canard communiste
L'utilisation d'une pile n'empêche pas l'utilisation de transitions d'état explicites.
dash-tom-bang
1

Une autre solution aux transitions et autres opérations similaires consiste à fournir l’état de destination et de source, ainsi que la machine à états, qui pourraient être liés au "moteur", quel qu’il soit. La vérité est que la plupart des machines d'état devront probablement être adaptées au projet en cours. Une solution pourrait être bénéfique à tel ou tel jeu, d’autres pourraient l’entraver.

class StateMachine
{
public:
    StateMachine(Engine *);
    void Push(State *);
    State *Pop();
    void Update();
    Engine *GetEngine();

private:
    std::stack<State *> _states;
    Engine *_engine;
};

Les états sont poussés avec l'état actuel et la machine en tant que paramètres.

void StateMachine::Push(State *state)
{
    State *from = 0;
    if (!_states.empty()) from = _states.top();
    _states.push(state);
    state->Enter(this, from);
}

Les états sont sautés de la même manière. Que vous appeliez Enter()le bas Stateest une question de mise en œuvre.

State *StateMachine::Pop()
{
    _ASSERT(!_states.empty());
    State *state = _states.top();
    State *to = 0;
    _states.pop();
    if (!_states.empty()) to = _states.top();
    state->Exit(this, to);
    return state;
}

Lors de la saisie, de la mise à jour ou de la sortie, le Stateobtient toutes les informations dont il a besoin.

void SomeGameState::Enter(StateMachine *sm, State *from)
{
    Engine *eng = sm->GetEngine();
    eng->GetKeyboard()->KeyDown.Bind(this, &SomeGameState::KeyDown);
    LoadLevelState *state = new LoadLevelState();
    state->SetLevel(eng->GetSaveGame()->GetLevelName());
    state->Load.Bind(this, &SomeGameState::OnLevelLoaded);
    sm->Push(state);
}

void SomeGameState::Update(StateMachine *sm)
{
    Engine *eng = sm->GetEngine();
    float time = eng->GetFrameTime();
    if (shouldExit)
        sm->Pop();
}

void SomeGameState::Exit(StateMachine *sm, State *from)
{
    Engine *eng = sm->GetEngine();
    eng->GetKeyboard()->KeyDown.UnsubscribeAll(this);
}
Nick Bedford
la source
0

J'ai utilisé un système très similaire sur plusieurs jeux et j'ai constaté qu'à quelques exceptions près, il constituait un excellent modèle d'interface utilisateur.

Les seuls problèmes que nous avons rencontrés concernaient des cas dans lesquels, dans certains cas, il était souhaitable de revenir dans plusieurs états avant de passer à un nouvel état (nous avons redistribué l'interface utilisateur pour supprimer l'exigence, car il s'agissait généralement d'un signe de mauvaise interface utilisateur) et de la création de style assistant. flux linéaires (résolus facilement en passant les données le long de l'état suivant).

L'implémentation que nous avons utilisée encapsulait la pile et gérait la logique de mise à jour et de rendu, ainsi que les opérations sur la pile. Chaque opération sur la pile a déclenché des événements sur les états pour les avertir de l'opération en cours.

Quelques fonctions d'assistance ont également été ajoutées pour simplifier les tâches courantes, telles que Swap (Pop & Push, pour les flux linéaires) et Reset (pour revenir au menu principal ou mettre fin à un flux).

Jason Kozak
la source
En tant que modèle d'interface utilisateur, cela a du sens. J'hésiterais à les appeler des États, car dans ma tête, je l'associerais aux éléments internes du moteur de jeu principal, tandis que "Menu principal", "Menu Options", "Écran de jeu" et "Écran de pause" sont de niveau supérieur. et n’ont souvent aucune interaction avec l’état interne du jeu principal, et envoient simplement des commandes au moteur principal de la forme "Pause", "Unpause", "Niveau de charge 1", "Niveau de démarrage", "Niveau de redémarrage", "Enregistrer" et "Restaurer", "définir le niveau de volume 57", etc. Bien que cela puisse varier considérablement selon les jeux.
Kevin Cathcart le
0

C’est la démarche que j’adopte pour presque tous mes projets, car cela fonctionne incroyablement bien et est extrêmement simple.

Sharplike , mon projet le plus récent , gère le flux de contrôle de cette manière. Nos états sont tous câblés avec un ensemble de fonctions d'événement appelées lorsque les états changent, et il comporte un concept de "pile nommée" dans lequel vous pouvez avoir plusieurs piles d'états dans la même machine à états et se ramifier parmi eux - un concept outil, et pas nécessaire, mais pratique pour avoir.

Je mettrais en garde contre le paradigme "Dites au contrôleur quel état doit suivre celui-ci quand il se termine" suggéré par Skizz: ce n'est pas structurellement solide, et cela crée des éléments comme des boîtes de dialogue (qui, dans le paradigme standard de l'état de pile, consistent simplement à créer une nouvelle sous-classe d’état avec nouveaux membres, puis lecture de celle-ci lorsque vous revenez à l’état invoquant) beaucoup plus difficile qu’il ne l’est.

Ed Ropple
la source
0

J'ai utilisé fondamentalement ce système exact dans plusieurs systèmes orthogonalement; par exemple, les états des menus front-office et in-game (aka "pause") avaient leurs propres piles d’états. L’interface utilisateur du jeu a également utilisé quelque chose comme ceci bien qu’elle ait des aspects «globaux» (comme la barre de santé et la carte / radar) que le changement d’état pourrait colorer mais qui se mettait à jour de manière commune d’un état à l’autre.

Le menu du jeu peut être "mieux" représenté par un DAG, mais avec une machine à états implicite (chaque option de menu qui passe sur un autre écran sait comment s'y rendre, et en appuyant sur le bouton Retour toujours affiché en haut de l'état), l'effet était exactement le même.

Certains de ces autres systèmes avaient également la fonctionnalité "remplacer l'état supérieur", mais celle-ci était généralement implémentée comme StatePop()suit StatePush(x);.

La manipulation de la carte mémoire était similaire, car j’ai inséré une tonne d’opérations dans la file d’opérations (qui fonctionnait de la même manière que la pile, tout comme la FIFO plutôt que la LIFO); une fois que vous commencez à utiliser ce type de structure ("il se passe une chose maintenant, et une fois terminé, il apparaît tout seul"), il commence à infecter tous les domaines du code. Même l'IA a commencé à utiliser quelque chose comme ça; l'IA était "désemparée" puis est devenue "méfiante" lorsque le joueur a émis des bruits mais n'a pas été vue, puis a été élevée à "active" lorsqu'elle a vu le joueur (et contrairement aux parties moins importantes de l'époque, vous ne pouviez pas vous cacher dans une boîte en carton et faites que l'ennemi vous oublie! Ce n'est pas que je sois amer ...).

GameState.h:

enum GameState
{
   k_frontend,
   k_gameplay,
   k_inGameMenu,
   k_moviePlayback,
   k_numStates
};

void GameStatePush(GameState);
void GameStatePop();
void GameStateUpdate();

GameState.cpp:

// k_maxNumStates could be bigger, but we don't need more than
// one of each state on the stack.
static const int k_maxNumStates = k_numStates;
static GameState s_states[k_maxNumStates] = { k_frontEnd };
static int s_numStates = 1;

static void (*s_startupFunctions)()[] =
   { FrontEndStart, GameplayStart, InGameMenuStart, MovieStart };
static void (*s_shutdownFunctions)()[] =
   { FrontEndStop, GameplayStop, InGameMenuStop, MovieStop };
static void (*s_updateFunctions)()[] =
   { FrontEndUpdate, GameplayUpdate, InGameMenuUpdate, MovieUpdate };

static void GameStateStart(GameState);
static void GameStateStop(GameState);

void GameStatePush(GameState gs)
{
   Assert(s_numStates < k_maxNumStates);
   GameStateStop(s_states[s_numStates - 1])
   s_states[s_numStates] = gs;
   s_numStates++;
   GameStateStart(gs);
}

void GameStatePop()
{
   Assert(s_numStates > 1);  // can't pop last state
   s_numStates--;
   GameStateStop(s_states[s_numStates]);
   GameStateStart(s_states[s_numStates - 1]);
}

void GameStateUpdate()
{
   GameState current = s_states[s_numStates - 1];
   s_updateFunctions[current]();
}

void GameStateStart(GameState gs)
{
   s_startupFunctions[gs]();
}

void GameStateStop(GameState gs)
{
   s_shutdownFunctions[gs]();
}
dash-tom-bang
la source