Architektura porządkująca polecenia Dwarf Fortress


21

Jaki jest najbardziej elegancki sposób na wdrożenie systemu porządkowania poleceń dla AI? na przykład w krasnoludzkiej fortecy, gdy zaznaczysz obszar leśny do wycinania drewna, krasnoludy wykonają następującą sekwencję:

  1. Idź do drzewa
  2. Posiekaj drzewo
  3. Dostarcz drewno do magazynu
  4. Idź do innego drzewa
  5. i tak dalej..

Mam już polecenie stosu działające nie. 1, która przechodzi ze stanu bezczynności do osiągnięcia docelowej płytki drzewa.

Obawiam się, że byłoby to bałagan, gdy utworzę więcej takich zamówień:

Zbudować dom

  1. Idź do zapasów
  2. przynieść drewno na plac budowy
  3. wróć do zapasów
  4. Przynieś kamień na plac budowy
  5. animuj duszka budowlanego

Sadzenie

  1. Idź do zapasów
  2. przynieść nasiona na działkę

Browarnictwo

  1. Idź do zapasów
  2. Doprowadzić roślinę do spokoju
  3. animuj duszka do warzenia

Więc moje pytanie brzmi: jak wdrożyć system porządkowania poleceń, taki jak forteca karłowata i jednocześnie unikając kodu spaghetti? czy są jakieś struktury danych, które muszę zbadać? Czy muszę umieścić sekwencję poleceń w osobnym pliku XML?


1
Dwarf Fortress w rzeczywistości nie ma takiego systemu. Krasnoludy są przydzielane po jednym zadaniu na raz, a bezczynne krasnoludy będą szukały czegoś do zrobienia. („Hej, jest drzewo przeznaczone do rąbania - powinienem je posiekać!” / „Hej, drewna nie ma w składzie - powinienem je zabrać!”)
user253751 30.01.2015

1
Krasnoludom nic nie przypisuje gracz, ale zadania są „przypisywane” przez system, a dokładnie taką architekturę Jed T. opisuje powyżej. Utwórz zamówienie, a system przydzieli poszczególne zadania komponentu w celu realizacji tego zamówienia.
Attackfarm

2
Należy pamiętać, że nazywa się to alokacją zadań i harmonogramem i jest szeroko badane w kilku dziedzinach inżynierii. Znajdziesz wiele artykułów omawiających ten problem, który może być interesujący.
TonioElGringo

@Attackfarm System nie decyduje wcześniej o wszystkich zadaniach; nie przypisuje też wielu zadań temu samemu karzełowi. Jedno zadanie jest początkowo przypisane, a po jego zakończeniu powoduje udostępnienie innego zadania.
użytkownik253751

2
To brzmi jak doskonały przykład użycia w planowaniu działań zorientowanych
problematyczne

Odpowiedzi:


27

Na początku widzisz, że twoje polecenia mają postać listy , więc twoim pierwszym instynktem może być odtworzenie tej struktury, a każdy karzeł będzie przeglądał tę listę po kolei. Sugeruję jednak, aby podzielić listę na etapy , przy czym każdy krok musi spełniać wymagania wstępne , a następnie uruchomić całą komendę w odwrotnej kolejności . Pokażę na przykładzie:

Cięcie drewna

  • Czy przewożę drewno i na składzie? Tak : zostaw to
  • Czy niosę drewno? Tak : idź do zapasów
  • Czy jestem na drzewie? Tak : posiekaj to
  • Nie dla wszystkich powyżej : idź do drzewa

Zaletą tego jest:

  • Bardzo prosty do wdrożenia
  • Elastyczny - możesz dowolnie rozkładać tę listę, dodawać elementy, usuwać elementy, łączyć elementy
  • Brak stanu - możesz uruchomić tę listę od góry dla każdego krasnala w dowolnym stanie, a krasnal po prostu zrobi właściwą rzecz TM

Niedogodności:

  • Utknięcie w pętli jest łatwe, ponieważ nie ma stanu ani świadomości utknięcia

Logicznie można reprezentować te polecenia jako schemat blokowy, który jest uruchamiany za każdym razem od góry, a to, co zrobisz, zależy od tego, czy na każdym kroku odpowiesz tak / nie. Niezależnie od tego, czy zaimplementujesz to w kodzie, czy w pliku zewnętrznym, takim jak XML, zależy od Ciebie.


2
Ma to również tę zaletę, że pozwala przesłonić polecenia statusu. Czy jestem głodny? jeśli tak, porzuć wszystko i ustaw zadanie „jedzenia” z jedzeniem podobnym do pracy przy wyciąganiu drewna.
maniak zapadkowy

7
@ratchetfreak "Wiem, że bezpieczeństwo mojej fortecy polega na tym, że walczę z tym potworem, aby nie zaatakował cywilów, ale, kurwa, mój żołądek tylko warknął!" Staraj się nie robić tego zbyt podobnym do DF w tym względzie: P
Pułkownik Trzydzieści Dwa

Wydaje mi się, że przypomina to wykorzystanie (lub przynajmniej użycie), które pozwoliło na wadliwy artefakt spakowania samolotu (było to spowodowane zakazanym przedmiotem, który spowodował wspomniane zapętlenie)
Destrictor 30.01.2015

3
@ColonelThirtyTwo Gdzie jest funto? ;)
Lasse

Zdecydowanie odradzam stosowanie do tego celu deklaratywnego symbolicznego planowania działań. Debugowanie jest w zasadzie niemożliwe, a niepożądane zachowanie może łatwo powstać. Znacznie łatwiej jest zakodować sekwencje czynności dla każdego zadania w sposób proceduralny.
mklingen

10

Jeśli potrafisz sprawić, by sekwencje były dość ogólne, kodu spaghetti jest niewiele.

W przypadku dostaw, np .: WorkTask działa z WorkPlan. Workplan mówi, jaki rodzaj jednostki zasobów musi wybrać, z jakiego domu, przy użyciu animacji spaceru, przy użyciu animacji pracy, czasu do pracy i wszystkich takich szczegółów. Na koniec WorkTask może wyglądać następująco:

  1. Znajdź% resource1% na mapie
  2. Idź do tej lokalizacji, używając% animacji_1%
  3. Pracuj w miejscu, używając% animacji_2% przez% time%
  4. Weź% req_resource1% w% req_count1% liczby
  5. Idź do% home% przy użyciu% animacji%
  6. Uruchom% animację_6% w środku na% time_2%
  7. itp..

Z powodzeniem stosujemy opisane podejście. W naszej grze mamy ~ 15 zadań. Niektóre najważniejsze:

  • Zadania dają akcje jednostek (idź tam, wejdź, wyjdź, idź tutaj, zostań, pracuj, idź)
  • Akcja kończy się stanem Gotowe lub Przerwane i przekazuje ją do Zadania
  • Wszystko jest zakodowane na stałe (nie trzeba pisać analizatora składni, metod interfejsu, kompatybilności wstecznej)
  • Każde zadanie implementuje abstrakcyjną klasę zadań za pomocą kilku typowych metod (tworzenie, wykonywanie, zapisywanie, ładowanie)
  • Zasadniczo jedno zadanie na moduł, ale podobne zadania znajdują się w jednym module
  • Bardzo podobne zadania są w obrębie jednej klasy i są zarządzane przez kilka IF (dostarczyć do domu lub dostarczyć do jednostki)
  • Każde zadanie wymaga odpowiedniego zablokowania i odblokowania zasobów (np. Jeśli jednostka umiera na DOWOLNYM kroku, zablokowany zasób musi zostać uwolniony)

2
Tego systemu używamy w naszej grze przypominającej fortecę karła. Zadania są realizowane przez drzewa zachowań. Zasoby są blokowane przez zachowania i odblokowywane przez awarię. Jest o wiele bardziej solidny i łatwy do debugowania niż podejście do planowania działań opisane w pierwszej odpowiedzi
mklingen

5

Jest to w zasadzie problem z sortowaniem topograficznym.

Masz wykres, każdy węzeł jest zadaniem, które należy wykonać, a niektóre węzły zależą od niektórych innych węzłów (jest to reprezentowane przez krawędź na wykresie od węzła zależnego do węzła, od którego zależy). Chcesz wykonać wszystkie zadania, więc musisz wykonać NIEKTÓRE uporządkowanie węzłów, które jest topograficzne OK (zależne węzły są za węzłami, od których zależą).

Obecnie zwykle istnieje wiele takich porządków (ponieważ niektóre węzły nie mają zależności i można je umieścić gdziekolwiek, a niektóre węzły mają te same zależności i nie są od siebie zależne, więc mogą być w dowolnej kolejności między sobą, a dowolny węzeł może umieść w dowolnym miejscu po zakończeniu zależności i zanim zakończone zostaną węzły zależne).

Możliwe jest również, że nie ma sposobu na posortowanie topografii wykresu - dzieje się tak, gdy na wykresie występują cykle (nie masz drewna, aby uzyskać drewno, musisz posiekać drzewo, aby posiekać drzewo, potrzebujesz siekiery, aby zrobić siekierę potrzebuje drewna). W takim przypadku algorytm powinien prawdopodobnie wskazać graczowi, że tych zadań nie można wykonać.

Możesz także dodawać priorytety do węzłów, a zadaniem może być znalezienie takiego uporządkowania spośród wszystkich porządków, które wypełniają zależności, które mają pierwszeństwo dla węzłów o wyższym priorytecie.

Możesz także dodawać zadania odzyskiwania - najłatwiejszym sposobem będzie po prostu dodanie zadania z limitem czasu do wykresu za każdym razem, gdy zostanie wykonane.

Teraz, jak to rozwiązać - http://en.wikipedia.org/wiki/Topological_sorting

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.