Jak działają algorytmy generowania historii?

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).

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.

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.

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

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.