LibColony

LibColony is a C++ (and JavaScript) library for task sheduling, perfect for colony simulation games like Rimworld or Dwarf Fortress. LibColony reduces the need for micromanagement, increases autonomy of colonists and prevents spirals of death. As a result the player can focus on planning rather than firefighting.

LibColony to biblioteka C++ (i JavaScript) do planowania zadań w grach symulujących kolonie. Jest to odpowiedź na problem, który występuje w grach typu Dwarf Fortress albo Rimworld, a polegający na tym, że zachłanny algorytm przydzielania zadań reagując na drobne incydenty prowadzi do spiral zagłady.

LibColony ogranicza potrzebę interwencji gracza oraz zwięsza autonomiczność kolonistów. W efekcie gracz może skupić się na planowaniu kolonii, a nie na gaszeniu pożarów.

Demo ↴

Introduction

Wprowadzenie

Video: BlindiRL

Colony simulators

Symulatory kolonii

Gameplay in games like Dwarf Fortress or Rimworld usually involves planning a colony - the layout of buildings, workshops and houses. This is done with a great deal of freedom. For example, we can decide that our colony will be an isolated toy factory, an inn on a popular trade route, or a bandit camp.

Rozgrywka w grach typu Dwarf Fortress albo Rimworld zwykle polega na planowaniu kolonii - układu budynków, warsztatów i domów. Odbywa się to z dużą dozą dowolności. Możemy na przykład zdecydować, że nasza kolonia będzie odizolowaną od cywilizacji fabryką zajmującą się produkcją zabawek, karczmą na popularnym szlaku handlowym, czy też obozem bandytów.

One of the most interesting elements that distinguishes this genre of games is that the built colony can actually be left alone. Its inhabitants take care of their own needs. The player can take on the role of a passive observer - like in an ant colony - following the fate of his subjects.

Jednym z ciekawszych elementów, który odróżnia ten gatunek gier jest to, że zbudowaną kolonię można właściwie pozostawić samą sobie. Jej mieszkańcy sami dbają o swoje potrzeby. Gracz może wcielić się w pasywnego obserwatora - niczym w kolonii mrówek - śledzić losy swoich poddanych.

Death spiral

Spirala zagłady

At least that's how it looks in theory. In practice, colonies are often annihilated for trivial reasons. Most often revolts caused by unmet needs of colonists - lack of food, protection from the elements or growing frustration. Tasks essential to the operation of the colony, such as maintaining fortifications or producing food, are routinely neglected.

Tak przynajmniej wygląda to w teorii. W praktyce kolonie często ulegają zagładzie z błachych powodów. Najczęściej buntów spowodowanych niezaspokojeniem potrzeb kolonistów - brakowi jedzenia, ochrony przed żywiołami czy też narastającej frustracji. Istotne dla działania kolonii zadania, takie jak utrzymanie fortyfikacji czy produkcja jedzenia są rutynowo zaniedbywane.

Problems tend to develop in spirals - they start with a single disgruntled character who destroys something in anger, spoiling the mood of subsequent colonists. Therefore, player intervention is constantly needed, reminding colonists what to do, and putting out fires while they are still manageable.

Problemy mają tendencję do rozwoju spiralnego - zaczynają się od pojedynczej niezadowolonej postaci, która w złości coś niszczy, psując nastroje kolejnych kolonistów. Dlatego ciągle potrzebna jest interwencja gracza, przypominającego kolonistom co mają robić, oraz gaszącego pożary, kiedy te są jeszcze do opanowania.

This mechanism, known as the death spiral, follows a certain well-known pattern. It relies on the fact that minor incidents generate additional tasks - both completely unimportant and vital to the survival of the colony. The insignificant tasks immediately consume the colonists, while the few vital tasks remain unperformed. This causes problems to grow and inevitably leads to further incidents. Chaos ensues.

Mechanizm ten, zwany spralą zagłady postępuje zgodnie z pewnym dobrze znanym schematem. Polega on na tym, że drobne incydenty generują dodatkowe zadania - zarówno zupełnie nieistotne, jak i kluczowe dla przetrwania kolonii. Nieistotne zadania pochłaniają natychmiast kolonistów, natomiast te kilka kluczowych zadań pozostaje niewykonanych. Powoduje to narastanie problemów i nieuchronnie prowadzi do dalszych incydentów. Ma miejsce efekt lawinowy.

What becomes clear is that the problem is primarily the way tasks are assigned to colonists. It involves a character who has free time checking a list of tasks and choosing something from it for themself. In doing so, it does not take into account the tasks performed by other characters. The decision is made "locally", based on a schedule and the work rules set by the player - that's why this approach is called "greedy". The selected task is reserved (reservations prevent other characters from taking over the task). The colonist then performs it until something gets in his way, or until the task gets completed. This simple and seemingly obvious algorithm leads to a series of problems and is the basis of the death spiral.

Oczywistym staje się to, że problem stanowi przede wszystkim sposób przydzielania zadań do kolonistów. Polega on na tym, że postać, która ma wolny czas sprawdza listę zadań i wybiera z niej coś dla siebie. Nie bierze pod uwagę przy tym zadań wykonywanych przez inne postaci. Decyzja podejmowana jest "lokalnie", na podstawie jej harmonogramu oraz reguł pracy ustalonych przez gracza - dlatego podejście to nazywane jest "zachłannym". Wybrane zadanie jest rezerwowane (rezerwacje uniemożliwiają innym postaciom przejęcie zadania). Następnie wykonuje je aż coś jej nie przeszkodzi, albo doprowadzi zadanie do końca. Ten prosty i z pozoru oczywisty algorytm prowadzi do szeregu problemów i stanowi podstawę spirali zagłady.

Given the above problems, and the fact that the intervention of a player directing the colonists' movements meticulously can prevent a death spiral, we can make the following claim:

Biorąc pod uwagę powyższe problemy oraz to, że interwencja gracza kierującego drobiazgowo ruchami kolonistów może zapobiec spirali zagłady możemy wysunąć następujące twierdzenie:

An appropriate assignment algorithm can counteract death spirals on an ongoing basis by meeting the needs of colonists and repairing the effects of minor incidents.

Odpowiednii algorytm przydzielania zadań może przeciwdziałać spiralom zagłady na bieżąco zaspokajając potrzeby kolonistów oraz naprawiając skutki drobnych incydentów.

In other words - do exactly what a firefighting player does.

Innymi słowy - robić dokładnie to, czym zajmuje się gaszący pożary gracz.

A few years ago, while taking part in a programming competition (and winning 😎) I had the opportunity to write a program that flexibly assigns such tasks. Therefore, I decided to dig up the old code, develop it and release it as a library. I provide a description of its operation, and the source code (under the MIT license) below.

Kilka lat temu, biorąc udział w zawodach programistycznych (i wygrywając 😎) miałem okazję napisać program elastycznie przydzielający takie zadania. Dlatego postanowiłem odgrzebać stary kod, opracować go i wydać jako bibliotekę. Opis jej działania, oraz kod źródłowy udostępniam (na licencji MIT) poniżej.

Problems of greedy task allocation

Problemy zachłannego przydziału zadań

Greedy assignment of tasks leads to several problems. Let's list them:

Zachłanne przydzielanie zadań prowadzi do kilku problemów. Wymieńmy je:

During work, colonists do not take breaks and completely ignore their needs. Long tasks significantly increase their frustration.
A colonist reserving a task for himself prevents other, better positioned colonists from taking over. Therefore, even if a colonist is at the other end of the map and faces a long trek, he will not give the task to another colonist idling nearby.
A group of small tasks located far from the colony often results in the escapade of entire groups of colonists (each reserving one of the distant tasks for themselves). Despite the fact that it would be enough for one of them to go.
Some colonists are simply better at certain tasks than others. In order for the greedy algorithm to assign them the right jobs, the player must create appropriate work rules that prohibit the others from the given jobs. Such rules must be updated as colonists join and leave the colony, requiring constant intervention by the player.
Minor tasks, are often ignored by colonists who pass right by them and could have done them virtually immediately. Instead, they are left for later - and then require another colonist to make a long trip to the site.
A colonist with special requirements, such as needing more entertainment at the moment, has the same amount of free time as others. Such colonists require special care from the player, who adjusts their time accordingly.

W czasie pracy koloniści nie robią przerw i całkowicie ignorują swoje potrzeby. Długie zadania istotnie zwiększają ich frustrację.
Kolonista rezerwując sobie zadanie uniemożliwia innym, lepiej usytuowanym kolonistom przejęcie go. Dlatego nawet jeśli kolonista jest na drugim końcu mapy i czeka go długa wędrówka, nie odda zadania bezczynnemu koloniście stojącemu na miejscu.
Grupa drobnych zadań zlokalizowanych daleko od kolonii często powoduje eskapadę całych grup kolonistów (każdy rezerwuje sobie po jednym z odległych zadań). Pomimo, że wystarczyłoby, żeby wybrał się jeden z nich.
Niektórzy koloniści są zwyczajnie lepsi w pewnych zadaniach od innych. Aby zachłanny algorytm przydzielił im odpowiednie prace gracz musi stworzyć odpowiednie reguły pracy, które zabronią pozostałym danych prac. Reguły takie muszą być aktualizowane w miarę jak koloniści dołączają i opuszczają kolonię, wymagając ciągłych interwencji gracza.
Drobne zadania, są często ignorowane przez kolonistów którzy przechodzą tuż obok nich i mogliby wykonać je właściwie natychmiast. Zamiast tego są pozostawiane na później - a później wymagają od innego kolonisty długiej podróży na miejsce.
Kolonista mający szczególne wymagania, na przykład potrzebujący w danej chwili więcej rozrywki, posiada taką samą ilość wolnego czasu jak inni. Koloniści tacy wymagają specjalnej opieki gracza, który odpowiednio dostosowuje ich czas pracy.

LibColony algorithm

Algorytm LibColony

Performance

Wydajność

One of the most important factors for gamedev libraries is their speed. If they are not fast enough, game developers will rewrite them for their own use in a more efficient way. That's why LibColony is written in high-performance C++, with the ability to call from other languages. For the demonstration at mrogalski.eu, I wrote the corresponding interface in JavaScript. This way it can be used both in games written in C++ and in games written in JavaScript.

Jednym z najistotniejszych czynników dla bibliotek gamedev-owych jest ich szybkość. Jeśli nie są dość szybkie, to autorzy gier będą je przepisywać na własne potrzeby w sposób bardziej wydajny. Dlatego też LibColony jest napisana w wysoko wydajnym języku C++, z możliwością wywołania z innych języków. Na potrzeby demonstracji na mrogalski.eu napisałem odpowiedni interfejs w JavaScript. W ten sposób można ją używać zarówno w grach napisanych w C++ jak i w grach napisanych w JavaScript.

The algorithm itself avoids any allocations, operating only on the stack, as well as any system calls. In this way, it avoids both of the biggest sources of slowdown, and makes efficient use of the processor's cache.

Sam algorytm unika jakichkolwiek alokacji, działając wyłącznie na stosie, a także jakichkolwiek wywołań systemowych. W ten sposób unika obu największych źródeł spowolnienia oraz skutecznie wykorzystuje pamięć podręczną procesora.

Recalculation every frame

Przeliczanie co klatkę

Thanks to its high performance, LibColony is able to recalculate task assignments multiple times (yes!) per frame of animation, even when the number of colonists and tasks reaches hundreds. This allows colonists to react immediately to changes in the game world, as well as for (described later) long-term planning.

Dzięki wysokiej wydajności LibColony jest w stanie przeliczać przydział zadań wielokrotnie (tak!) w ciągu jednej klatki animacji, nawet jeśli liczba kolonistów oraz zadań sięga setek. Pozwala to na natychmiastową reakcję kolonistów na zmiany w świecie gry, a także na (opisane dalej) planowanie długoterminowe.

Uniform treatment of needs and tasks

Jednorodne traktowanie potrzeb i zadań

LibColony satisfies colonists' needs by treating them analogously to tasks. As a character's need grows in importance, its priority gradually increases. As a result, colonists are able to interrupt work to meet their needs. The distance from where the need is met is also taken into account. By this, for example, colonists who work near the kitchen will eat more often than colonists working in remote corners of the colony.

LibColony zaspokaja potrzeby kolonistów traktując je analogicznie do zadań. W miarę jak potrzeba postaci rośnie na znaczeniu, stopniowo wzrasta jej priorytet. Dzięki temu koloniści są w stanie przerwać pracę by zaspokoić swoje potrzeby. Brana pod uwagę jest też odległość od miejsca, w którym spełniona jest dana potrzeba. Przez to na przykład koloniści, którzy pracują w pobliżu kuchni będą jeść częściej niż koloniści pracujący w odległych zakątkach kolonii.

In general, the following are taken into account:

Ogólnie rzecz biorąc uwzględniane są:

travel time to the task location
time to complete the task
risk of failure, after which a repeat of the task will be required
relative priority/importance of the task

czas podróży do miejsca wykonania zadania
czas wykonania zadania
ryzyko porażki, po której wymagane będzie ponowienie zadania
względny prioritytet/istotność zadania

The last element is particularly important because it allows game developers to distinguish key tasks from unimportant ones. This can include, for example:

Ostatni element jest szczególnie istotny gdyż pozwala autorom gier odróżnić zadania kluczowe od tych nieistotnych. Można tu uwzględnić na przykład:

whether a given cleaning task is located in a place where colonists frequent, or is far away from them (and thus less important).
whether adequate food supplies are available, or whether food is running out (and thus cooking tasks are more relevant)
the value / rarity of war spoils to be collected from the battlefield
etc. etc.

czy dane zadanie sprzątania znajduje się w miejscu gdzie często bywają koloniści, czy też jest daleko od nich (i przez to jest mniej istotne)
czy dostępne są odpowiednie zapasy żywności, czy też jedzenie się kończy (i przez to zadania gotowania są bardziej istotne)
wartość / rzadkość łupów wojennych do zebrania z pola bitwy
itd. itp.

Each of these elements can take on different values for each colonist and change over time.

Każdy z tych elementów może przyjmować różne wartości dla każdego kolonisty oraz ulegać zmianom w czasie.

Hungarian algorithm

Algorytm węgierski

The heart of the algorithm is the Hungarian algorithm, which guarantees optimal assignment of tasks to characters. Its complexity is O(n^3), although LibColony offers an optional (and rarely required) optimization that limits the number of assignments considered, so that the complexity drops to O(n^2).

Sercem algorytmu jest algorytm węgierski, który gwarantuje optymalne przypisanie zadań do postaci. Jego złożoność wynosi O(n^3), choć LibColony oferuje opcjonalną (i rzadko wymaganą) optymalizację ograniczającą liczbę rozważanych zadań, dzięki czemu złożoność spada do O(n^2).

Delivery scheduling

Planowanie dostaw

To schedule delivery tasks, the algorithm can be run twice. In the first run, it assigns items to locations where they are to be delivered. This allows it to determine the delivery cost for each item (while minimizing the total time for all deliveries). Then the algorithm is run again, this time assigning delivery tasks to the colonists who are to deliver them.

Aby zaplanować zadania dostawy, algorytm może zostać uruchomiony dwukrotnie. W pierwszym przebiegu przypisuje on przedmioty do lokalizacji, gdzie mają zostać dostarczone. Pozwala to na ustalenie kosztu dostawy dla każdego przedmiotu (jednocześnie minimalizując łączny czas wszystkich dostaw). Następnie algorytm jest uruchamiany ponownie, tym razem przypisując zadania dostaw do kolonistów, którzy mają je dostarczyć.

Long-term planning

Planowanie długoterminowe

Sometimes a single colonist can independently complete many tasks faster than many (slower) colonists. For example, when several small tasks occur in a remote location, a nearby colonist can complete them all faster than a group of colonists running from the other end of the map.

Czasami pojedynczy kolonista może samodzielnie wykonać wiele zadań szybciej niż wiele (wolniejszych) kolonistów. Na przykład, gdy kilka małych zadań pojawia się w odległym miejscu, pobliski kolonista może wykonać je wszystkie szybciej niż grupa kolonistów biegnących z drugiego końca mapy.

This requires planning many tasks ahead, and LibColony can also help with this.

Wymaga to zaplanowania wielu zadań w przyszłość i LibColony również może w tym pomóc.

To do this, first assign tasks in the usual way. This initial assignment will assign tasks to all available colonists - both nearby and distant. The trick is that the task that is completed first in this assignment is marked as completed; the colonist who completed it is moved (virtually) to the place where the task was completed, and the cost of all the tasks they can perform is increased by the cost of completing this just-completed task.

Aby to zrobić, najpierw zadania przypisywane zą w zwykły sposób. To początkowe przypisanie przydzieli zadania wszystkim dostępnym kolonistom - zarówno tym pobliskim jak i odległym. Sztuczka polega na tym, że zadanie, które w tym przypisaniu jest ukończone jako pierwsze oznacza się jako ukończone; kolonistę, który je wykonał przemieszcza się (wirtualnie) na miejsce wykonania zadania, a koszty wszystkich wykonywanych przez niego zadań powiększane są o koszt wykonania tego właśnie ukończonego zadania.

The tasks are then assigned again and the whole process is repeated. The task completed first is marked as completed and the position and times of the other tasks of the colonist who completed it are corrected. This process can be repeated as many times as desired (within a certain time budget or until all tasks are completed).

Następnie zadania przypisywane są ponownie i cały proces jest powtarzany. Zadanie wykonane jako pierwsze oznacza się jako ukończone oraz koryguje się pozycję oraz czasy pozostałych zadań kolonisty, który je wykonał. Proces ten może zostać powtórzony dowolną ilość razy (w ramach określonego budżetu czasowego lub do zakończenia wszystkich zadań).

The final long-term plan consists of the tasks that were completed during this process (assigned to colonists who completed them), followed by the tasks that were assigned to colonists in the last run of the algorithm.

Ostateczny plan długoterminowy składa się z zadań, które zostały zakończone podczas tego procesu (przypisane do kolonistów, którzy je ukończyli), a następnie z zadań, które zostały przypisane do kolonistów w ostatnim przebiegu algorytmu.

Demo

Below is a demo that shows how the library works. You can select different scenarios and see how LibColony handles them.

Poniżej znajduje się demo, które pokazuje jak działa biblioteka. Możesz wybrać różne scenariusze i zobaczyć jak radzi sobie z nimi LibColony.

The C++ version is approx. 3 times faster than the WebAssembly version (embedded below).

Wersja C++ jest ok. 3 razy szybsza od wersji WebAssembly (zagnieżdżonej poniżej).

GrafikaSprites: penzilla.itch.io

ScenariuszScenario

Random Small corresponds to the typical colony in the Rimworld game and the initial colony in Dwarf Fortress. In this scenario, you can see how 10 characters dynamically exchange tasks to complete them as quickly as possible.
Random Medium corresponds to a typical colony in a Dwarf Fortress game after a few hours of play. This is more characters than are encountered in typical Rimworld games. As the number of characters and quests increases, LibColony continues to deftly swap between characters.
Random Large corresponds to the advanced colony in the Dwarf Fortress game. In the Dwarf Fortress game, colonies of this size are associated with considerable lag. LibColony copes with this problem.
Random Huge corresponds to the largest colonies possible in Dwarf Fortress (~250 characters). Gameplay in such colonies in Dwarf Fortress runs at a few frames per second. LibColony at this stage already requires more time than the typical animation frame budget (16.6ms). To use LibColony in games of this size, task scheduling is best done in a separate thread.
Random Insane demonstrates LibColony's performance in huge colonies (500 characters, 2000 tasks).
Row a simple test case where the optimal solution coincides with the greedy one. Each character runs to the nearest task.
Skewed row a tricky scenario where the optimal solution requires characters to coordinate task allocation among themselves. In this case, the greedy algorithm is unable to find the optimal solution.
That guy case demonstrating the usefulness of long-term planning and the problems of the greedy approach. A group of characters runs towards a group of tasks at the other end of the map, despite the fact that the character there can handle the tasks by himself anyway. A greedy planning algorithm would prevent the character located at the end of the map from taking away the other characters' reserved tasks. Long-term planning, on the other hand, would allow a group of characters to realize that there is no need to run anywhere because the tasks will be completed before they get there anyway.
Circle, Square, Inversed Square a set of simple test cases.

Random Small odpowiada typowej kolonii w grze Rimworld oraz początkowej w Dwarf Fortress. W scenariuszu tym widać jak 10 postaci dynamicznie wymienia się zadaniami by jak najszybciej je zakończyć.
Random Medium odpowiada typowej kolonii w grze Dwarf Fortress po kilku godzinach gry. Jest to więcej postaci niż spotyka się w typowych rozgrywkach Rimworld. W miarę wzrostu liczby postaci oraz zadań, LibColony dalej zręcznie wymienia je między postaciami.
Random Large odpowiada zaawansowanej kolonii w grze Dwarf Fortress. W grze Dwarf Fortress kolonie o takim rozmiarze wiążą się ze sporymi lagami. LibColony radzi sobie z tym problemem.
Random Huge odpowiada największym koloniom możliwym do uzyskania w Dwarf Fortress (~250 postaci). Rozgrywka w takich koloniach w Dwarf Fortress toczy się w tempie kilku klatek na sekundę. LibColony na tym etapie wymaga już więcej czasu niż typowy budżet klatki animacji (16.6ms). Aby korzystać z LibColony w grach o takim rozmiarze, planowanie zadań najlepiej wykonywać w osobnym wątku.
Random Insane demonstruje działanie LibColony w olbrzymich koloniach (500 postaci, 2000 zadań).
Row prosty przypadek testowy, gdzie optymalne rozwiązanie pokrywa się z zachłannym. Każda postać biegnie do najbliższego zadania.
Skewed row podstępny scenariusz, gdzie optymalne rozwiązanie wymaga by postaci skoordynowały między sobą przydział zadań. W tym przypadku zachłanny algorytm nie jest w stanie znaleźć optymalnego rozwiązania.
That guy przypadek demonstrujący przydatność planowania długoterminowego oraz problemy podejścia zachłannego. Grupa postaci biegnie w kierunku grupy zadań na drugim końcu mapy, pomimo, że znajdująca się tam postać i tak poradzi sobie z zadaniami sama. Zachłanny algorytm planowania uniemożliwiłby postaci znajdującej się miescu odebranie pozostałym postaciom zarezerwowanych przez nich zadań. Planowanie długoterminowe pozwoliłoby natomiast grupie postaci zorientować się, że nie ma potrzeby nigdzie biec bo i tak zadania zostaną zakończone zanim tam dobiegną.
Circle, Square, Inversed Square zestaw prostych przypadków testowych.

Download

Pobieranie

LibColony is available under the MIT license. The latest version can be downloaded from github.com/mafik/libcolony.

LibColony dostępne jest na licencji MIT. Najnowsza wersja może zostać pobrana z github.com/mafik/libcolony.

The C++ library is a single header that should be linked in (preferably) one translation unit. All functions are available in the `colony` namespace. Version 1.0 can be downloaded from here.

Biblioteka C++ jest pojedynczym nagłówkiem, który powinien zostać zlinkowany w (najlepiej) jednej jednostce tłumaczenia. Wszystkie funkcje są dostępne w przestrzeni nazw `colony`. Wersja 1.0 może zostać pobrana stąd.

The JavaScript library wraps C++ code compiled as WebAssembly. Version 1.0, built for browsers, can be downloaded from here. All provided functions are described in the colony_js_post.js. To use the library, you can use the following sample code:

Biblioteka JavaScript opakowuje kod C++ skompilowany jako WebAssembly. Wersja 1.0, przeznaczona do przeglądarek może zostać pobrana stąd. Wszystkie udostępnione funkcje opisane są w pliku colony_js_post.js. Aby skorzystać z biblioteki możesz użyć następującego przykładowego kodu:

<script>
  var Module = {
    onRuntimeInitialized: function() {
      window.requestAnimationFrame(tick);
    }
  };

  function tick() {
    let assignments = [{ character: "John", task: "clean blood", cost: 10 },
                       { character: "Fred", task: "clean blood", cost: 15 },
                       { character: "John", task: "construct wall", cost: 20 },
                       { character: "Fred", task: "construct wall", cost: 10 }];
    let optimized = Module.optimize(assignments);
    console.log(optimized); // [{ character: "John", task: "clean blood", cost: 10 },
                            //  { character: "Fred", task: "construct wall", cost: 10 }]
    window.requestAnimationFrame(tick);
  }
</script>
<script src="colony.js"></script>