Arquitetura de ordem de comando da Fortaleza dos Anões

21

Qual é a maneira mais elegante de implementar um sistema de pedidos de comandos para IA? por exemplo, na fortaleza dos anões quando você marca uma área florestal para o corte de madeira, os anões fazem a seguinte sequência:

  1. Vá para a árvore
  2. Pique a árvore
  3. Entregue madeira ao estoque
  4. Ir para outra árvore
  5. e assim por diante..

Eu já tenho um comando de pilha funcionando não. 1, que passa do estado inativo para alcançar o bloco de destino da árvore.

O que eu tenho medo é como isso ficaria confuso quando eu criar mais pedidos como este:

Construa uma casa

  1. Ir para o estoque
  2. trazer madeira para a área de construção
  3. voltar ao estoque
  4. Trazer pedra para a área de construção
  5. animar sprite de construção

Plantio

  1. Ir para o estoque
  2. trazer sementes para a fazenda

Cervejaria

  1. Ir para o estoque
  2. Trazer planta para ainda
  3. animar cerveja sprite

Portanto, minha pergunta é: como implemento um sistema de ordenação de comandos como o Dwarf Fortress e evitando o código de espaguete ao mesmo tempo? existem estruturas de dados que eu preciso estudar? Preciso colocar a sequência de comandos em um arquivo xml separado?

Jed T.
fonte
1
Dwarf Fortress, na verdade, não possui esse sistema. Os anões recebem uma tarefa de cada vez, e os anões ociosos procurarão algo para fazer. ( "Ei, há uma árvore marcada para cortar - I deve cortá-la!" / "Hey, há um pouco de madeira não em um estoque - eu deveria levá-lo a um!")
user253751
1
Os anões não recebem nada do jogador, mas tarefas "atribuídas" pelo sistema, que é exatamente a arquitetura que Jed T. descreve acima. Criar pedido e o sistema atribui tarefas de componentes individuais para atender a esse pedido.
Attackfarm
2
Observe que isso se chama Alocação e agendamento de tarefas e é amplamente estudado em vários campos da engenharia. Você encontrará muitos documentos discutindo esse problema, o que pode ser interessante.
precisa saber é o seguinte
@ Attackfarm O sistema não decide todas as tarefas antecipadamente; nem atribui várias tarefas ao mesmo anão. Uma tarefa é inicialmente designada e, quando concluída, tem a consequência de disponibilizar outra tarefa.
precisa saber é o seguinte
2
Isso soa como um caso de uso excelente para -Oriented Meta Planejamento de Ações
Problemática

Respostas:

27

A princípio, você vê que seus comandos estão na forma de uma lista ; portanto, seu primeiro instinto pode ser recriar essa estrutura, e cada anão percorrerá essa lista em sequência. O que eu sugiro é dividir a lista em etapas , com cada etapa com pré-requisito (s) e, em seguida, você executa o comando inteiro ao contrário . Deixe-me demonstrar com um exemplo:

Corte de madeira

  • Estou carregando madeira e em um estoque? Sim : deixe cair
  • Estou carregando madeira? Sim : vá a um estoque
  • Estou em uma árvore? Sim : pique
  • Não a todos acima : vá para uma árvore

As vantagens disso são:

  • Muito simples de implementar
  • Flexível - você pode decompor livremente esta lista, adicionar itens, remover itens, combinar itens
  • Sem estado - você pode executar esta lista a partir do topo para qualquer anão em qualquer estado, e o anão fará apenas a coisa certa TM

Desvantagens:

  • É fácil ficar preso em loops, já que não há estado nem consciência de estar preso

Logicamente, você pode representar esses comandos como um fluxograma, que é executado a partir do topo de cada vez, e o que você faz depende de responder sim / não a cada etapa. Se você implementa isso no código ou em um arquivo externo como XML, é com você.

congusbongus
fonte
2
Isso também tem a vantagem de permitir que o status substitua os comandos. Estou com fome? se sim, largue tudo e defina a tarefa para "comer", sendo que o comer é semelhante ao trabalho de transporte de madeira.
catraca aberração
7
@ratchetfreak "Eu sei que a segurança da minha fortaleza depende de eu lutar contra esse monstro para não atacar os civis, mas, caramba, meu estômago apenas ronca!" Tente não parecer muito com DF a esse respeito: P
Coronel Trinta e Dois
Eu acho que isso se assemelha ao que usa (ou pelo menos usado) que permitiu o artefato com bug do planepacked (isso ocorreu devido a um item proibido, que causou o loop)
Destritor
3
@ColonelThirtyTwo Onde está funisso? ;)
Lasse
Eu recomendo fortemente não usar um planejamento de ação simbólico declarativo para isso. É basicamente impossível depurar, e comportamentos indesejáveis ​​podem surgir facilmente. Muito mais fácil codificar as seqüências de ação para cada tarefa de maneira processual.
precisa saber é
10

Se você pode criar seqüências bastante gerais, não há muito código de espaguete.

No caso de entregas, por exemplo: WorkTask opera com um WorkPlan. O plano de trabalho diz que tipo de unidade de recursos deve ser escolhida, de que tipo de casa, usando qual animação a pé, qual animação, hora de trabalhar e todos esses detalhes. Portanto, no final, a WorkTask pode se parecer com:

  1. Encontre% resource1% no mapa
  2. Vá para esse local usando% animation_1%
  3. Trabalhe no local usando% animation_2% por% time%
  4. Aceite% req_resource1% na contagem de% req_count1%
  5. Vá para% home% usando% animation%
  6. Inicie% animation_6% dentro por% time_2%
  7. etc ..

Utilizamos com sucesso a abordagem descrita. Temos ~ 15 tarefas em nosso jogo. Alguns destaques:

  • As tarefas dão ações unitárias (vá lá, entre, saia, vá aqui, fique, trabalhe, vá)
  • A ação termina com o estado Concluído ou Abortado e passa para a Tarefa
  • Tudo é codificado (sem necessidade de escrever analisador, métodos de interface, compatibilidade com versões anteriores)
  • Cada tarefa implementa a classe Task abstrata com apenas alguns métodos comuns (criar, executar, salvar, carregar)
  • Geralmente uma tarefa por módulo, mas tarefas semelhantes estão em um módulo
  • Tarefas muito semelhantes estão dentro de uma classe e são regidas por poucos FIs (entrega em casa ou entrega em unidade)
  • Cada tarefa precisa de um bloqueio e desbloqueio adequados de recursos (por exemplo, se a unidade morrer em QUALQUER etapa, o recurso que ele bloqueou deve ser liberado)
Kromster diz apoio Monica
fonte
2
Este é o sistema que usamos em nosso jogo de fortaleza anã. As tarefas são realizadas por árvores de comportamento. Os recursos são bloqueados por comportamentos e desbloqueados por falha. É muito mais robusto e fácil de depurar do que a abordagem de planejamento de ação descrita pela resposta principal
mklingen
5

Portanto, esse é um problema de classificação basicamente topográfica.

Você tem um gráfico, cada nó é uma tarefa que precisa ser executada e alguns nós dependem de outros nós (isso é representado por uma aresta no gráfico do nó dependente para o nó do qual depende). Você deseja executar todas as tarefas, portanto, é necessário produzir ALGUM pedido dos nós que esteja topograficamente OK (os nós dependentes estão após os nós dos quais dependem).

Agora, existem muitas ordenações desse tipo (porque alguns nós não têm dependências e podem ser colocadas em qualquer lugar, e alguns nós têm as mesmas dependências e não são dependentes um do outro, portanto, podem estar em qualquer ordem entre si, e qualquer nó pode seja colocado em qualquer lugar depois que as dependências forem concluídas e antes que os nós dependentes sejam concluídos).

Também é possível que não haja como classificar um gráfico topograficamente - isso acontece quando há ciclos no gráfico (você não tem madeira, para obter madeira é necessário cortar uma árvore, para cortar uma árvore é necessário machado, para fazer machado você precisa de madeira). Nesse caso, o algoritmo provavelmente deve indicar ao jogador que essas tarefas não podem ser realizadas.

Você também pode adicionar prioridades aos nós, e a tarefa pode ser encontrar essa ordem, entre todas as ordens que atendem às dependências, que têm os nós de prioridade maiores executados primeiro.

Você também pode adicionar tarefas recorrentes - a maneira mais fácil provavelmente será adicionar a tarefa com tempo limite novamente ao gráfico sempre que isso for feito.

Agora, como resolvê-lo - http://en.wikipedia.org/wiki/Topological_sorting

Sebastian Pidek
fonte