Przejdź do gry [1], Dokumentacja [2]
Na wszelkie pytania odpowiadam na forum [3]. Można też pisać do mnie PW [4].
Jest to gra strategiczna gra on-line przeznaczona dla wielu graczy (MMO). Rzeczą która wyróżnia ją od wszystkich innych gier, jest możliwość oprogramowania jednostek własnymi programami.
Gra toczy się w czasie rzeczywistym 24h na dobę. Zadaniem stawianym przez grę jest utworzenie systemu sztucznej inteligencji sterującej jednostkami, tak by pokonać innych graczy i zdominować świat.
Celem gry jest pokonanie innych graczy i wyprodukowanie jak największej liczby jednostek. Gra toczy się w niezależnych rundach, w każdej następuje reset mapy i gra rozpoczynana jest od początku, by nowi gracze mieli szansę osiągnąć dobry wynik. Przyłączyć do gry można się w dowolnym momencie, ale koniec rundy następuje dla wszystkich w tym samym czasie. Wtedy aktualizowany jest ranking i rozpoczynana jest nowa runda na nowej mapie.
Gra toczy się na mapie podzielonej na pola. Mamy do dyspozycji jednostki: Bazę, Zbieracze i Czołgi. W Bazie możemy produkować jednostki, potrzebne są do tego minerały, przynoszone do bazy przez Zbieracze. Droższe zaś Czołgi są podstawowym argumentem militarnym.
Na mapie może znajdować się wielu graczy, jest tam także stale obecny zawodowy gracz komputerowy.
Rozpoczęcie gry następuje w momencie wciśnięcia przycisku "Wejdź do gry" w zakładce "Ogólne". Otrzymujemy wówczas pierwsze jednostki w losowym miejscu, ale w pobliżu zasobów.
Opuścić grę można w podobny sposób. Wówczas utracimy kontrolę nad jednostkami, które przestaną wykonywać polecenia, ale będziemy mogli dołączyć do gry ponownie zaczynając od początku. Dołączyć do gry w jednej rundzie można maksymalnie 3 razy.
Jednostki znajdujące na mapie wykonują w każdej turze polecenia. Przykładowo polecenie MOVE x y przemieszcza jednostkę w stronę wybranego pola [x,y]. Polecenia można wydawać na 3 sposoby:
1 2 3 4 5 | #include <cstdio> int main(void) { printf("MOVE 10 22"); return 0; } |
Aby rozpocząć własny rozwój należy zacząć od zbierania zasobów. W pobliżu Bazy znajdują się minerały, które można eksploatować.
Zbierać zasoby mogą Zbieracze - jeżdzące wagoniki. W tym celu należy wydać im polecenie GATHER {x} {y}, gdzie {x} {y} są to współrzędne pola z minerałami. Zbieracz wówczas podjedzie do złoża, zbierze jedną porcję zasobów, po czym wróci do bazy i ją odda. Proces ten będzie powtarzać cyklicznie.
Złoża mają ograniczoną ilość minerałów, jednak odtwarzają się powoli w czasie.
Im więcej pracujących Zbieraczy tym więcej zasobów może być dostarczanych do Bazy, jednak należy uważać - zbyt duża ich ilość, bez żadnej dodatkowej kontroli ruchu może powodować zakorkowanie.
Produkcja jednostek odbywa się w Bazie. Służy do tego polecenie BUILD {typ}, gdzie {typ} jest liczbą oznaczającą typ (w dokumentacji). Zbieracz ma typ 5, zatem aby go wyprodukować wystarczy wydać polecenie BUILD 5. Wyprodukowana jednostka pojawi się na sąsiednim wolnym polu obok Bazy.
Domyślnie jednostki mają ustawiane polecenie STOP, jednak bezpośrednio przy produkcji można ustawić im inne, dowolne polecenie lub cały program. Przykład:
Gdy już uporamy się ze zbieraniem zasobów, nadchodzi czas by wykorzystać je w celach militarnych. Podstawową jednostką służącą do walki jest Czołg. Aby go zbudować wystarczy wydać polecenie BUILD 6.
Czołg może strzelać na odległość 3-ech pól (w sensie metryki miejskiej). Polecenie ATTACK {x} {y} powoduje, że Czołg podąża do pola [x,y] strzelając po drodze do napotkanych wrogich jednostek.
Trzeba pamiętać, że Czołg nie atakuje z poleceniami STOP i MOVE - działają one tak samo jak dla Zbieraczy. Polecenie FIRE {x} {y} każe Czołgowi strzelać do wybranego pola (tylko jeśli jest w zasięgu), można go użyć także np. do karczowania lasów.
Na następnych stronach opiszemy strategie programowania, zwiększające sukces w grze.
Aby napisać sensowny program dla jednostki, należy najpierw wczytać z wejścia opis sytuacji. Są tam podawane różne parametry takie jak pozycja na mapie i opis widzianego przez jednostkę otoczenia, szczegóły w dokumentacji [2]. Każda jednostka, jak i każdy gracz, posiada unikalny identyfikator po którym rozpoznajemy ich. Ponadto przyjazne jednostki mogą się ze sobą komunikować poprzez system komunikatów (o którym później).
A oto przykładowy program w C++, który radzi sobie z wejściem:
Read Input [5]1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | /** * Read Input * * Przykladowy program wczytujacy wejscie. */ #include <cstdio> #include <cstdlib> #include <ctime> using namespace std; int unitType;// Typ jednostki int unitId;// Identyfikator jednostki int playerId;// Identyfikator gracza int numMessages;// Liczba wiadomosci int posX,posY;// Pozycja na mapie int range;// Srednica widzenia #define MAX_RANGE 33 int areaType[MAX_RANGE][MAX_RANGE];// Typ obiektu/jednostki int areaParam[MAX_RANGE][MAX_RANGE];// Parametr obiektu/id jednostki int areaOwner[MAX_RANGE][MAX_RANGE];// Wlasciciel jednostki (id gracza) #define TYPE_EMPTY 0 #define TYPE_UNAVAILABLE 1 #define TYPE_MINERALS 2 #define TYPE_TREES 3 #define TYPE_BASE 4 #define TYPE_MINER 5 #define TYPE_TANK 6 void readInput() { scanf("%i%i%i%i%i%i%i\n",&unitType,&unitId,&playerId,&numMessages,&posX,&posY,&range); scanf("%*[^\n]"); for (int y=0;y<range;y++) for (int x=0;x<range;x++) scanf("%i%i%i",&areaType[x][y],&areaParam[x][y],&areaOwner[x][y]); } int main(void) { readInput(); printf("STOP"); return 0; } |
Program wydaje ponadto polecenie STOP, w dalszych przykładach skupimy się na procedurze main, pozostawiając wczytywanie wejścia bez zmian.
Program wczytuje kolejno liczbę oznaczającą swój typ jednostki (unitType), unikalny identifikator (unitId), unikalny identyfikator gracza - właściela (playerId), ilość komunikatów, swoją pozycję na mapie (posX,posY) i średnicę widzenia (range).
Drugi wiersz, opisujący parametry specyficzne dla typu jednostki jest pomijany, w zależności od zastosowań można wczytać z niego np. posiadane już minerały.
Kolejne wiersze to opis otoczenia, który odpowiada kwadratowi pól ze środkiem w polu, w którym znajduje się jednostka. A więc areaType[x][y] oznacza typ obiektu w polu (posX+x-r/2,posY+y-r/2) na mapie, podobnie areaParam[x][y] to parametr opisujący bardziej szczegółowo obiekt (jest to np. ilość minerałów dla pola minerałów) a areaOwner[x][y] identyfikator właściciela gdy obiektem jest jednostka.
Po tej operacji do wczytania pozostają jeszcze opcjonalne komunikaty, których ilość mamy w zmiennej numMessages. Ich wykorzystaniem później się zajmiemy.
Jednym z mankamentów bezpośredniego zbierania jest fakt, iż po skończeniu się zasobów Zbieracz czeka przy złożu aż pojawią się nowe minerały do zebrania. Lepszym rozwiązaniem byłoby poszukanie w takiej sytuacji najbliższego złoża z dostępnymi minerałami.
Oto przykład (początek kodu jak w Read Input bez funkcji main, będzie taki sam dla wszystkich przykładów):
Miner Simple Gathering [6]1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | int main(void) { readInput(); // Szukamy najblizszych mineralow int minX=0,minY=0; bool found=false; for (int y=0;y<range;y++) for (int x=0;x<range;x++) // Jesli mineraly i sa blizej niz dotychczas znalezione if (areaType[x][y] == TYPE_MINERALS && areaParam[x][y] > 0 && (!found || abs(x-range/2)+abs(y-range/2)<abs(minX-range/2)+abs(minY-range/2) )) { found = true; minX = x; minY = y; } if (found) { // Jesli sa mineraly to wydajemy polecenie zbierania printf("GATHER %i %i",minX+posX-range/2,minY+posY-range/2); } else { // Jesli nie ma to wydajemy polecenie zbierania w miejscu // w celu ewentualnego powrotu do bazy z mineralami printf("GATHER %i %i",posX,posY); } return 0; } |
Zamiast ręcznie przydzielać każdemu nowemu Zbieraczowi jakieś złoże, można wyposażyć Bazę w program, który będzie kierował go do jakiegoś złoża. W tym celu wystarczy przejrzeć otoczenie w celu znalezienia złóż i wybrać jakieś, po czym produkować Zbieracze od razu z odpowiednim poleceniem GATHER.
Oto program produkujący zbieracze i wysłający je do losowo wybranych minerałów:
Base Simple Production [7]1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | int main(void) { readInput(); // Liczymy ilosc pelnych zloz mineralow oraz Zbieracze int numMiners = 0; int numMinerals = 0; for (int y=0;y<range;y++) for (int x=0;x<range;x++) { if (areaType[x][y] == TYPE_MINER) numMiners++; else if (areaType[x][y] == TYPE_MINERALS && areaParam[x][y] >= 10) numMinerals++; } if (numMinerals > 0 && numMiners < 20) { // Losujemy zloze srand(time(NULL)); int selectedMinerals = rand()%numMinerals; // Znajdujemy je int mineralX=0,mineralY=0; for (int y=0;y<range;y++) { if (selectedMinerals < 0) break; for (int x=0;x<range;x++) { if (areaType[x][y] == TYPE_MINERALS) { selectedMinerals--; if (selectedMinerals < 0) { mineralX = x; mineralY = y; break; } } } } // Produkujemy Zbieracza printf("BUILD 5\n\nGATHER %i %i",mineralX+posX-range/2,mineralY+posY-range/2); } else { printf("STOP"); } return 0; } |
Minerały wybierane są losowo, co daje w miarę równy rozkład bez zbędnych komplikacji. Program produkuje Zbieracze tylko do pewnego momentu, aby nie było ich za dużo w celu uniknięcia korków.Łatwo zmodyfikować go tak, by potem zamiast STOP np. zaczął produkował Czołgi.
Powyższe 2 programy można także połączyć, wypisując pierwszy program zamiast standardowego GATHER w drugim programie. W celu konwersji kodu programu na string w C++ można użyć Converter [8]. A tutaj już gotowy taki program: Gather Simple Production With Simple Gathering [9].
Program ten zamiast losowego przydziału minerałów ustawia im program, dzięki któremu same znajdą sobie właściwe złoże. Zbieracze również produkowane są aż osiągnięta zostanie pewna ich ilość.
Dalej przejdziemy do bardziej zaawansowanych możliwości, związanych z systemem komunikatów.
Komunikaty umożliwiają porozumiewanie się między własnymi jednostkami. Ale nie tylko: poprzez komunikaty programy mogą również zapamiętywać dane, wydawać polecenia innym jednostkom oraz uzyskiwać dodatkowe informacje o sytuacji (np. uzyskać listę wszystkich jednostek).
Korzystając z możliwości nadawania poleceń zdalnie (polecenie *), możemy centralnie sterować Zbieraczami. Mając pełny obraz sytuacji, możemy sprawniej unikać konfliktów między nimi.
Poniżej program, który przydziela każdemu Zbieraczowi najbliższe minerały, rezerwując przy okazji porcję zasobów. Wykorzystywany jest w tym celu BFS rozpoczynany równolegle ze wszystkich pól ze Zbieraczami.
Base Controller [10]1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 | // Dopasowuje zachlannie najblizsze mineraly kazdemu Zbieraczowi void assignMineralsToMiners() { queue<Position> q; // Pola niedostepne lub juz odwiedzone dla kazdego Zbieracza static bool visited[MAX_RANGE][MAX_RANGE][MAX_RANGE][MAX_RANGE]; // Dla kazdego Zbieracza rozpoczynamy szukanie trasy for (int my=0;my<range;my++) for (int mx=0;mx<range;mx++) if (areaType[mx][my] == TYPE_MINER) { Position p = {mx,my,mx,my}; q.push(p); for (int y=0;y<range;y++) for (int x=0;x<range;x++) visited[mx][my][x][y] = !(areaType[x][y] == TYPE_EMPTY || (areaType[x][y] == TYPE_MINERALS && areaParam[x][y] > 0)); } while (!q.empty()) { Position pc = q.front(); q.pop(); // Jesli Zbieracz juz dostal polecenie ignorujemy go if (areaType[pc.mx][pc.my] != TYPE_MINER) continue; // Jesli mineraly to przydzielamy je dla tego Zbieracza if (areaType[pc.x][pc.y] == TYPE_MINERALS && areaParam[pc.x][pc.y] > 0) { printf("%i GATHER %i %i\n",areaParam[pc.mx][pc.my],pc.x+posX-range/2,pc.y+posY-range/2); areaParam[pc.x][pc.y]--; areaType[pc.mx][pc.my] = TYPE_UNAVAILABLE; continue; } // Idziemy w kazdym z 4-ech kierunkow if (pc.x > 0 && !visited[pc.mx][pc.my][pc.x-1][pc.y]) { Position p = {pc.mx,pc.my,pc.x-1,pc.y}; q.push(p); visited[pc.mx][pc.my][pc.x-1][pc.y] = true; } if (pc.x < range-1 && !visited[pc.mx][pc.my][pc.x+1][pc.y]) { Position p = {pc.mx,pc.my,pc.x+1,pc.y}; q.push(p); visited[pc.mx][pc.my][pc.x+1][pc.y] = true; } if (pc.y > 0 && !visited[pc.mx][pc.my][pc.x][pc.y-1]) { Position p = {pc.mx,pc.my,pc.x,pc.y-1}; q.push(p); visited[pc.mx][pc.my][pc.x][pc.y-1] = true; } if (pc.y < range-1 && !visited[pc.mx][pc.my][pc.x][pc.y+1]) { Position p = {pc.mx,pc.my,pc.x,pc.y+1}; q.push(p); visited[pc.mx][pc.my][pc.x][pc.y+1] = true; } } } int main(void) { readInput(); // Liczymy Zbieracze int numMiners = 0; for (int y=0;y<range;y++) for (int x=0;x<range;x++) if (areaType[x][y] == TYPE_MINER) numMiners++; // Liczymy ilosc Zbieraczy w nablizszym otoczeniu int numNearMiners = 0; for (int y=range/2-4;y<=range/2+4;y++) for (int x=range/2-2;x<=range/2+4;x++) if (areaType[x][y] == TYPE_MINER) numNearMiners++; // Wydajemy polecenia Zbieraczom assignMineralsToMiners(); // Jesli jest malo Zbieraczy to produkujemy if (numNearMiners < 8 && numMiners < 20) { printf("BUILD 5\n\n*"); } else { printf("STOP"); } return 0; } |
Program oprócz kontroli Zbieraczy produkuje nowe, jeśli jest ich mało w okolicy - nie ma ryzyka korków. Można go jeszcze ulepszyć na wiele sposobów: wydawanie rozkazu przesuwania się o 1 pole (mamy pewność co do kierunku Zbieracza), unikanie kolizji lub pozyskanie informacji o Zbieraczach z ładunkiem w celu uwzględnienia ich trasy do Bazy. To ostatnie np. jest możliwe dzięki komunikatom systemowym.
Komunikaty systemowe - za pomocą komunikatów można także otrzymywać bardziej szczegółowe informacje, niedostępne z opisu otoczenia. Wysyła się w tym celu komunikat do identyfikatora 0, od którego otrzymuje się później odpowiedź. Można w ten sposób pobrać listę wszystkich jednostek lub uzyskać szczegóły danej jednostki. W dokumentacji opisany jest format zapytań systemowych.
Klasyczna sytuacja - zmasowany atak daje większą szansę na wygraną niż wypady jeden po jednym.
W trakcie walki Czołgi gdy są dostatecznie blisko atakują się, a kolejność wykonywanych akcji jest losowa, więc szansa dla każdego, że pierwszy strzeli wynosi 1/2. Jednak gdyby atakować większą ilością Czołgów naraz, wówczas prawdopodobieństwo, że atakowany Czołg odda strzał przed wszystkimi atakującymi maleje. I tak gdy atakujemy 2-ma Czołgami pbb. wynosi tylko 1/3, gdy 3-ma pbb. wynosi 1/4. Łatwo policzyć, że teoretycznie pbb. to wynosi 1/(n+1) gdzie n jest liczbą atakujących.
Aby skutecznie wykorzystywać przewagę ilościową, należy nie tylko wysyłać wiele jednostek naraz (aczkolwiek samo to też pomaga). Istotne jest także opracowanie i utrzymywanie odpowiedniego szyku bojowego.
Umiejąc przewidzieć ruchy przeciwnika, można wcześniej otworzyć do niego ogień. Ostrzeliwujemy wówczas pole na które wróg dopiero wchodzi. W ten sposób mamy szansę zniszczyć go zanim będzie stanowić dla nas zagrożenie - jeśli w danej turze wejdzie na pole przed oddaniem strzału. Prawdopobieństwo zwycięstwa w takiej sytuacji wynosi 1/2 i podobnie jak poprzednio, im większą mamy siłę ognia tym większą mamy szansę zlikwidować go w tym momencie.
Oczywiście ta technika wymaga wiedzy, na które pole wejdzie przeciwnik. Inną możliwością jest postawienie całej ściany ognia na wielu polach, utrudniającej zbliżenie się wrogom. Rozpraszamy jednak w ten sposób siłę ognia.
To tyle jeśli chodzi o wstęp. Każdy pomysł sterowania jednostkami jest dobry, na tyle na ile będzie skuteczny.
Życzymy powodzenia i dobrej zabawy!
Odnośniki:
[1] http://informatyka.wroc.pl/node/623
[2] http://informatyka.wroc.pl/node/714
[3] http://informatyka.wroc.pl/forum/viewforum.php?f=67
[4] http://informatyka.wroc.pl/forum/ucp.php?i=pm&mode=compose&u=63
[5] http://informatyka.wroc.pl/mszykula/sc/doc/read_input.cpp
[6] http://informatyka.wroc.pl/mszykula/sc/doc/miner_simple_gathering.cpp
[7] http://informatyka.wroc.pl/mszykula/sc/doc/base_simple_production.cpp
[8] http://informatyka.wroc.pl/mszykula/sc/doc/converter.cpp
[9] http://informatyka.wroc.pl/mszykula/sc/doc/base_simple_production_with_simple_gathering.cpp
[10] http://informatyka.wroc.pl/mszykula/sc/doc/base_controller