Jak działają algorytmy generowania historii?


19

Słyszałem o grze Dwarf Fortress, ale dopiero teraz jedna z osób, które obserwuję na Youtube, skomentowała ją ... Byłem bardziej niż zaskoczony, gdy zauważyłem, jak Dwarf Fortress generuje historię dla świata!

Jak działają te algorytmy? Co zwykle przyjmują jako dane wejściowe, z wyjątkiem długości symulacji? Jak szczegółowe mogą być?

A co ważniejsze; czy można je tworzyć w Javascript, czy też Javascript jest zbyt wolny? (Myślę, że to zależy od głębokości symulacji, ale weźmy jako przykład Dwarf Fortress).


3
„Czy można je tworzyć w JavaScript?” Odpowiedź brzmi oczywiście tak, ale zależy to od tego, jak szybko chcesz uzyskać wyniki i jak skomplikowane mają być. Dwarf Fortress też zajmuje trochę czasu - i zwalnia z wiekiem! Tak długo, jak chcesz mieć płytką historię, tak, możesz to zrobić w Javascripcie, więc zależy to od stopnia złożoności historii.
doppelgreener

2
Ma na myśli „na poziomie Dwarf Fortress”, jak w skali.
MichaelHouse

2
@Bane Tak, mam na myśli, że możesz zmienić, ile historii będzie w DF. Kiedy zaczynasz świat, najpierw losowo generuje teren, a następnie zaczyna starzeć się na twoich oczach i generować historię w miarę upływu czasu. Patrzysz, jak imperia się powiększają i kurczą, zmiany terenu, lasy rosną i maleją, obszary nawiedzają się (lub przestają być nawiedzane) i tak dalej. Postępuje z roku na rok (a nawet kilka lat na raz) na twoich oczach. To trwa, dopóki nie każesz mu przestać. Im dalej, tym wolniej generuje się (ze względu na użycie procesora, a nie mechanikę gry).
doppelgreener

1
Mówiąc wprost: im starszy jest świat, tym wolniej każdego roku oblicza się. W młodym świecie pędzi przez pierwsze kilka lat, w świecie liczącym setki lat, kolejny rok może zająć sekundę lub kilka sekund.
doppelgreener

1
Och, to wiem. Przez „głębokość” nie miałem na myśli liczby lat, miałem na myśli liczbę zdarzeń, które się zdarzają, i precyzję symulacji. Możesz po prostu zachować liczbę osób, które ma imperium, lub możesz mieć tak zwaną klasę Person, która wykonuje obowiązki, idzie do wojska itp. Płytkie pozwoliłoby, aby wielkość imperium decydowała o wynikach bitew, ale każdy z żołnierzy walczyłby o swoje.
jcora

Odpowiedzi:


27

Po pierwsze, istnieją pewne wskazówki dotyczące generowania historii na temat Dwarf Fortress. Ktoś zapytał na forach Bay12 jakiś czas temu, a transkrypcja została udostępniona i można znaleźć początek dyskusji, szukając: „naszym dzisiejszym tematem jest generowanie świata i generowanie historii”.


Nie wiem dokładnie, jak to robi Forteca Krasnoludów, ale wyjaśnię, w jaki sposób planuję wdrożyć bardzo podstawowy pierwszy projekt w mojej grze. Użyję prostego automatu komórkowego . Jeśli przejrzysz te prototypy zarodników , takie jak hodowla komórkowa i biom.

wprowadź opis zdjęcia tutaj

Są to przykłady automatyzacji komórkowych i tego, co mogą wytworzyć. Zasadniczo stworzę reguły dla różnych ras. Oto niektóre przykłady reguł:

  • Ich wrogość wobec innych ras
  • Ich preferencje klimatyczne
  • Ich wymagania dotyczące zasobów
  • Ich wskaźnik urodzeń i długość życia
  • Ich pragnienia (badania technologiczne, handel, pokojowa egzystencja, dominacja nad światem)
  • Ich możliwości (budowanie struktury, gromadzenie zasobów, tworzenie wojen itp.)
  • I tak dalej...

Zatem najważniejszym wkładem do tego wszystkiego jest świat, w który można wpuścić te rasy. Teren określi ich preferencje i ekspansję. Kiedy już stworzysz świat, wybierz losowe miejsca na świecie, w których rasy te będą żyły i pozwól im się uwolnić. Teraz zaczynają się dziać ciekawe rzeczy. Teraz, gdy masz ziemię i rasy z pragnieniami i możliwościami, możesz zacząć budować historię. Rasy te gromadzą zasoby, a następnie budowane są struktury:

  • Miasta w obszarach o wysokich zasobach i wysokiej jakości życia.
  • Drogi łączą większe miasta.
  • Mosty przez rzeki.
  • Tunele przez góry.
  • Twierdze w pobliżu linii frontu ekspansji w odpowiedzi na bitwy.

Każda struktura może zostać najechana / podbita przez inne rasy. Im dłużej budowla (jak miasto lub forteca) istnieje w historii, tym bardziej jest obronna, tym trudniej jest ją przejąć. A tym bardziej pożądane jest dla ras, które chcą kontroli. Bitwy toczy się tam, gdzie spotykają się rasy (przynajmniej jedna jest wroga). Bitwy są nazwane na podstawie punktów orientacyjnych lub pobliskich budowli, a jeśli bitwa jest znacząca lub punkty orientacyjne nie są nazwane, punkty orientacyjne są nazywane po bitwie.

Drogi, mosty i tunele są rozbudowywane poprzez handel i transport zasobów. Każda z nich ma maksymalną przepustowość, która może wzrosnąć wraz z wydatkami na zasoby. Budujesz kamienną fortecę pośrodku muraw? Drogi te będą bardzo obciążone transportem wymaganego kamienia. Staną się większe i otrzymają imię.

Występują klęski żywiołowe, które dotykają populacje i bieg historii. Trzęsienia ziemi mogą sprowadzić miasto do ruiny lub zawalić tunel. Powódź może zmyć drogę lub most.


Nie jest tak dogłębny jak Dwarf Fortress, ale to początek. Teraz, jak możesz sobie wyobrazić (i jak wspomniał Johnathan Hobbs), im bardziej te rasy się rozwijają, tym więcej komórek jest symulowanych. Nie tylko symuluje się więcej komórek, ale symulacje są bardziej złożone, ponieważ istnieją teraz struktury do budowy / utrzymania, bitwy o pensje, handel do ... handlu i tak dalej. To staje się ciężkie dla każdego języka. JavaScript może wcześniej zwolnić. Jednak zawsze możesz poświęcić złożoność dla zwiększenia prędkości.

To wszystko symulacja (choć złożona), po prostu rejestrujesz ważne wydarzenia po drodze i nazywasz to historią.

Właśnie znalazłem post na forum Bay12, w którym ludzie przeprowadzają burzę mózgów, jak przyspieszyć generację światową Dwarf Fortress. Nie przeczytałem go, ale może dostarczyć wskazówek, jeśli kiedykolwiek napotkasz problemy ze zbyt wolnym wdrażaniem.


Świetny i pouczający jak zawsze, @ Byte56. :)
jcora,

1
Dzięki Bane. Może nie zawsze zdarza się, że ludzie zadają pytania, o których chyba coś wiem. Dziękuję, że dałeś mi okazję, aby przemyśleć to jeszcze raz i uzyskać coś spisanego :)
MichaelHouse

4

Z drugiej strony JavaScript nie jest tak wolny, jak mogłoby się wydawać .

Twórcy przeglądarek poświęcili wiele czasu i energii na optymalizację swoich silników JavaScript . Benchmark, do którego podłączyłem, pokazuje, że spośród zadań testowych w medianie JavaScript był tylko 5 razy wolniejszy niż C , czego nie można powiedzieć o niektórych innych interpretowanych językach. A dolna granica jest jeszcze bardziej imponujące: na równi z C .

Oczywiście benchmarki językowe tak naprawdę niewiele znaczą - prawdopodobnie możesz znaleźć kontrprzykłady przy użyciu innego testu porównawczego. Ale chodzi o to, że JavaScript jest dość szybki . Nie, to nie jest C ani C ++ i nie próbuje być. Ale dobrze jest nie utknąć w sposobie myślenia „interpretowany język == powolny”, ponieważ w przypadku każdego zadania o nietypowej złożoności wydajność będzie miała większe znaczenie dla projektowania algorytmów, a mniej dla wyboru języka.

Chciałem to wszystko napisać w komentarzu, ale zabrakło mi miejsca.


1

Tak, można go zbudować na javascript, sprawdź proyects, takie jak ASM.js, które osiągają prawie 2x wolniejszą prędkość niż C. Jeśli zadbasz o wiele rdzeni (używając webworkerów), może być nawet szybszy niż DF (pod względem zasobów) , który jest teraz monocore.

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.