Estado do jogo 'Stack'?

52

Eu estava pensando em como implementar estados de jogos no meu jogo. As principais coisas que eu quero são:

  • Estados principais semi-transparentes - poder ver através de um menu de pausa o jogo por trás

  • Algo OO-Eu acho isso mais fácil de usar e entender a teoria por trás, além de manter a organização e adicionar mais.



Eu estava pensando em usar uma lista vinculada e tratá-la como uma pilha. Isso significa que eu poderia acessar o estado abaixo para obter a semi-transparência.
Plano: Faça com que a pilha de estados seja uma lista vinculada de ponteiros para IGameStates. O estado superior lida com seus próprios comandos de atualização e entrada e, em seguida, possui um membro isTransparent para decidir se o estado abaixo deve ser desenhado.
Então eu poderia fazer:

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

Para representar o carregamento do player, acessar as opções e o menu principal.
É uma boa ideia ou ...? Devo olhar para outra coisa?

Obrigado.

O Pato Comunista
fonte
Deseja ver o MainMenuState atrás do OptionsMenuState? Ou apenas a tela do jogo por trás do OptionsMenuState?
Skizz
O plano era que os estados tivessem uma opacidade / isTransparent value / flag. Eu verificaria se o estado superior tinha esse valor verdadeiro e, se sim, qual o valor que ele tinha. Em seguida, torne-o com tanta opacidade sobre o outro estado. Neste caso, não, eu não faria.
The Duck comunista
Sei que é tarde, mas para futuros leitores: não use newda maneira mostrada no código de exemplo, é apenas pedir vazamentos de memória ou outros erros mais sérios.
Pharap

Respostas:

44

Eu trabalhei no mesmo mecanismo que o coderanger. Eu tenho um ponto de vista diferente. :)

Primeiro, não tínhamos uma pilha de FSMs - tínhamos uma pilha de estados. Uma pilha de estados cria um único FSM. Não sei como seria uma pilha de FSMs. Provavelmente muito complicado para fazer algo prático.

Meu maior problema com nossa Máquina de Estado Global era que era uma pilha de estados, e não um conjunto de estados. Isso significa, por exemplo, ... / MainMenu / O carregamento foi diferente de ... / Loading / MainMenu, dependendo se você abriu o menu principal antes ou depois da tela de carregamento (o jogo é assíncrono e o carregamento é principalmente orientado pelo servidor )

Como dois exemplos de coisas isso ficou feio:

  • Isso levou, por exemplo, ao estado LoadingGameplay, então você tinha Base / Loading e Base / Gameplay / LoadingGameplay para carregar no estado Gameplay, que precisou repetir grande parte do código no estado normal de carregamento (mas não todos, e adicionar um pouco mais )
  • Tínhamos várias funções como "se no criador do personagem, vá para o jogo; se no jogo, vá para o personagem selecionado; se no personagem, selecione voltar para o login", porque queríamos mostrar as mesmas janelas de interface em diferentes estados, mas fazer o botão Voltar / Avançar botões ainda funcionam.

Apesar do nome, não era muito "global". A maioria dos sistemas de jogos internos não o utilizava para rastrear seus estados internos, porque eles não queriam que seus estados estivessem mexendo com outros sistemas. Outros, por exemplo, o sistema de interface do usuário, poderiam usá-lo, mas apenas para copiar o estado em seus próprios sistemas de estado locais. (Eu recomendaria especialmente ao sistema os estados da interface do usuário. O estado da interface do usuário não é uma pilha, é realmente um DAG, e tentar forçar qualquer outra estrutura nele só tornará as interfaces de usuário frustrantes de usar.)

O que era bom era isolar tarefas para integrar código de programadores de infraestrutura que não sabiam como o fluxo do jogo era realmente estruturado, para que você pudesse dizer ao cara que escreveu o patcher "coloque seu código no Client_Patch_Update" e o cara que escreveu os gráficos loading "coloque seu código em Client_MapTransfer_OnEnter", e poderíamos trocar certos fluxos lógicos sem muito problema.

Em um projeto paralelo, tive mais sorte com um conjunto de estados do que com uma pilha , sem medo de criar várias máquinas para sistemas não relacionados e me recusando a me deixar cair na armadilha de ter um "estado global", que é realmente apenas uma maneira complicada de sincronizar as coisas por meio de variáveis ​​globais - claro, você vai acabar fazendo isso perto de um prazo, mas não crie esse objetivo como seu objetivo . Fundamentalmente, o estado em um jogo não é uma pilha e os estados em um jogo não são todos relacionados.

O GSM também, como indicadores de função e comportamento não local, dificultavam as coisas de depuração, embora a depuração desse tipo de transições de estado grandes não fosse muito divertida antes de tê-lo. Conjuntos de estados em vez de pilhas de estados realmente não ajudam nisso, mas você deve estar ciente disso. Funções virtuais em vez de ponteiros de função podem aliviar um pouco isso.


fonte
Ótima resposta, obrigado! Acho que posso aproveitar muito o seu post e suas experiências passadas. : D + 1 / Tick.
O pato comunista
O bom de uma hierarquia é que você pode criar estados de utilitários que são levados ao topo e não precisam se preocupar com o que mais está sendo executado.
Coderanger
Não vejo como isso é um argumento para uma hierarquia, e não para conjuntos. Em vez disso, uma hierarquia torna toda a comunicação interestadual mais complicada, porque você não tem idéia de onde elas foram empurradas.
O ponto em que as interfaces de usuário são realmente DAGs é bem aceito, mas discordo que certamente pode ser representado em uma pilha. Qualquer gráfico acíclico direcionado conectado (e não consigo pensar em um caso em que não seria um DAG conectado) pode ser exibido como uma árvore, e uma pilha é essencialmente uma árvore.
Ed Ropple
2
Pilhas são um subconjunto de árvores, que são um subconjunto de DAGs, que são um subconjunto de todos os gráficos. Todas as pilhas são árvores, todas as árvores são DAGs, mas a maioria dos DAGs não são árvores e a maioria das árvores não são pilhas. Os DAGs têm uma ordem topológica que permitirá que você os armazene em uma pilha (para travessia, por exemplo, resolução de dependência), mas depois que você os coloca na pilha, você perde informações valiosas. Nesse caso, a capacidade de navegar entre uma tela e seu pai, se ele tiver um irmão anterior.
11

Aqui está um exemplo de implementação de uma pilha de gamestate que achei muito útil: http://creators.xna.com/en-US/samples/gamestatemanagement

Ele está escrito em C # e, para compilá-lo, você precisa da estrutura XNA; no entanto, basta verificar o código, a documentação e o vídeo para ter uma idéia.

Ele suporta transições de estado, estados transparentes (como caixas de mensagens modais) e estados de carregamento (que gerenciam o descarregamento de estados existentes e o carregamento do próximo estado).

Agora, uso os mesmos conceitos em meus projetos de hobby (não C #) (concedido, pode não ser adequado para projetos maiores) e, para projetos pequenos / de hobby, posso definitivamente recomendar a abordagem.

Janis Kirsteins
fonte
5

Isso é semelhante ao que usamos, uma pilha de FSMs. Basicamente, basta atribuir a cada estado uma função de entrada, saída e marcação e chame-os em ordem. Funciona muito bem para lidar com coisas como carregar também.

coderanger
fonte
3

Um dos volumes "Game Programming Gems" tinha uma implementação de máquina de estado destinada a estados de jogo; http://emergent.net/Global/Documents/textbook/Chapter1_GameAppFramework.pdf tem um exemplo de como usá-lo em um pequeno jogo e não deve ser muito específico para Gamebryo para ser legível.

Tom Hudson
fonte
A primeira seção de "Programação de jogos de papéis com DirectX" também implementa um sistema de estados (e um sistema de processos - distinção muito interessante).
Ricket
Esse é um ótimo documento e explica quase exatamente como eu o implementei no passado, além da hierarquia desnecessária de objetos que eles usam nos exemplos.
dash-tom-bang
3

Apenas para adicionar um pouco de padronização à discussão, o termo clássico de CS para esse tipo de estrutura de dados é um autômato de empilhamento .

maravilhoso
fonte
Não sei se qualquer implementação no mundo real de pilhas de estados é quase equivalente a um autômato de empilhamento. Como mencionado em outras respostas, implementações práticas invariavelmente acabam com comandos como "pop two states", "swap esses estados" ou "passam esses dados para o próximo estado fora da pilha". E um autômato é um autômato - um computador - não uma estrutura de dados. Pilhas de estado e autômatos de empilhamento usam uma pilha como uma estrutura de dados.
11
"Não tenho certeza de que qualquer implementação no mundo real de pilhas de estados seja quase equivalente a um autômato de empilhamento". Qual é a diferença? Ambos têm um conjunto finito de estados, uma história de estados e operações primitivas para empurrar e estourar estados. Nenhuma das outras operações mencionadas é diferente em termos financeiros. "Pop two states" está apenas aparecendo duas vezes. "swap" é um pop e um empurrão. A transmissão de dados está fora da idéia principal, mas todo jogo que usa um "FSM" também adere a dados adicionais sem parecer que o nome não se aplica mais.
munificent
Em um autômato de empilhamento, o único estado que pode afetar sua transição é o estado no topo. Não é permitido trocar dois estados no meio; mesmo olhando para os estados do meio não é permitido. Sinto que a expansão semântica do termo "FSM" é razoável e traz benefícios (e ainda temos os termos "DFA" e "NFA" para o significado mais restrito), mas "autômato de empilhamento" é estritamente um termo de ciência da computação e existe apenas confusão esperando se a aplicarmos a todos os sistemas baseados em pilha existentes no mercado.
Eu prefiro as implementações em que o único estado que pode afetar qualquer coisa é o estado que está no topo, embora em alguns casos seja útil poder filtrar a entrada de estado e passar o processamento para um estado "inferior". (Eg entrada do controlador de processamento de mapas com este método, o estado de topo leva os bits que se preocupa e possivelmente limpa-las em seguida, passa o controlo para o estado seguinte na pilha.)
traço-TOM-bang
11
Bom ponto, fixo!
11786 munificent
1

Não tenho certeza se uma pilha é totalmente necessária, além de limitar a funcionalidade do sistema de estados. Usando uma pilha, você não pode 'sair' de um estado para uma das várias possibilidades. Digamos que você comece no "Menu principal" e vá para "Carregar jogo". Você pode ir para o estado "Pausar" depois de carregar com sucesso o jogo salvo e retornar ao "Menu principal" se o usuário cancelar a carga.

Gostaria apenas que o estado especificasse o estado a seguir quando sair.

Para aquelas instâncias em que você deseja retornar ao estado anterior ao estado atual, por exemplo "Menu principal-> Opções-> Menu principal" e "Pausa-> Opções-> Pausa", basta passar como um parâmetro de inicialização para o estado que estado para voltar.

Skizz
fonte
Talvez eu tenha entendido mal a pergunta?
Skizz
Não, você não fez. Eu acho que o eleitor de baixa renda fez.
The Duck comunista
O uso de uma pilha não exclui o uso de transições de estado explícitas.
dash-tom-bang
1

Outra solução para transições e outras coisas desse tipo é fornecer o destino e o estado de origem, juntamente com a máquina de estado, que pode ser vinculada ao "mecanismo", qualquer que seja. A verdade é que a maioria das máquinas de estado provavelmente precisará ser adaptada ao projeto em questão. Uma solução pode beneficiar esse ou aquele jogo, outras soluções podem atrapalhá-lo.

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

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

Os estados são enviados com o estado atual e a máquina como parâmetros.

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

Os estados são lançados da mesma maneira. Se você chama Enter()a parte inferior Stateé uma questão de implementação.

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;
}

Ao entrar, atualizar ou sair, o Stateaplicativo obtém todas as informações necessárias.

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
fonte
0

Eu usei um sistema muito semelhante em vários jogos e descobri que, com algumas exceções, ele serve como um excelente modelo de interface do usuário.

Os únicos problemas que encontramos foram os casos em que, em certos casos, é desejado retornar vários estados antes de enviar um novo estado (reintroduzimos a interface do usuário para remover o requisito, pois geralmente era um sinal de má interface do usuário) e criar um estilo de assistente fluxos lineares (resolvidos facilmente passando os dados para o próximo estado).

A implementação que usamos na verdade envolveu a pilha e lidou com a lógica de atualização e renderização, bem como as operações na pilha. Cada operação na pilha acionava eventos nos estados para notificá-los da operação que estava ocorrendo.

Também foram adicionadas algumas funções auxiliares para simplificar tarefas comuns, como Trocar (Pop & Push, para fluxos lineares) e Redefinir (para retornar ao menu principal ou encerrar um fluxo).

Jason Kozak
fonte
Como um modelo de interface do usuário, isso faz algum sentido. Eu hesitaria em chamá-los de estados, já que, na minha cabeça, associaria isso aos componentes internos do mecanismo principal do jogo, enquanto "Menu principal", "Menu opções", "Tela do jogo" e "Tela de pausa" são de nível superior, e geralmente não têm interação com o estado interno do jogo principal, e simplesmente envia comandos para o mecanismo principal no formato "Pausa", "Não pausado", "Nível de carga 1", "Nível inicial", "Reiniciar nível", "Salvar" e "Restaurar", "definir o nível 57 do volume", etc. Obviamente, isso pode variar significativamente de acordo com o jogo.
21911 Kevin Kevin Cathcart
0

Essa é a abordagem adotada para quase todos os meus projetos, porque funciona incrivelmente bem e é extremamente simples.

Meu projeto mais recente, Sharplike , lida com o fluxo de controle exatamente dessa maneira. Todos os nossos estados estão conectados com um conjunto de funções de eventos que são chamadas quando os estados mudam e apresenta um conceito de "pilha nomeada" no qual você pode ter várias pilhas de estados na mesma máquina de estado e ramificar entre elas - um conceito ferramenta, e não é necessário, mas útil para ter.

Eu alertaria contra o paradigma "diga ao controlador que estado deve seguir este quando terminar" sugerido pela Skizz: não é estruturalmente sólido e cria coisas como caixas de diálogo (que no paradigma padrão de estado de pilha envolve apenas a criação de um novo subclasse de estado com novos membros e, em seguida, lê-la quando você retornar ao estado de chamada) muito mais difícil do que deve ser.

Ed Ropple
fonte
0

Eu usei basicamente esse sistema exato em vários sistemas ortogonais; os estados de menu de interface e de jogo (também conhecido como "pausa"), por exemplo, tinham suas próprias pilhas de estados. A interface do usuário no jogo também usava algo assim, embora tivesse aspectos "globais" (como a barra de saúde e o mapa / radar) que a troca de estado pode ter, mas que é atualizada de maneira comum entre os estados.

O menu do jogo pode ser "melhor" representado por um DAG, mas com uma máquina de estado implícita (cada opção de menu que vai para outra tela sabe como ir para lá, e pressionar o botão voltar sempre exibia o estado superior) o efeito era exatamente o mesmo.

Alguns desses outros sistemas também tinham a funcionalidade "substituir estado superior", mas isso geralmente era implementado conforme StatePop()seguido StatePush(x);.

O manuseio do cartão de memória foi semelhante, pois eu realmente coloquei uma tonelada de "operações" na fila de operações (que funcionava da mesma maneira que a pilha, exatamente como FIFO, em vez de LIFO); quando você começa a usar esse tipo de estrutura ("há uma coisa acontecendo agora e, quando termina, ela aparece automaticamente"), ela começa a infectar todas as áreas do código. Até a IA começou a usar algo assim; a IA ficou "sem noção" e depois mudou para "cautelosa" quando o jogador fez barulhos, mas não foi vista, e finalmente elevada para "ativa" quando viu o jogador (e, diferentemente dos jogos menores da época, você não podia esconder em uma caixa de papelão e fazer o inimigo te esquecer! Não que eu seja amargo ...).

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]();
}
traço-tom-bang
fonte