Spore mapki w światach izometrycznych dla gier rts

Cześć,

Na początku zaznaczę że nie interesuje mnie żadne rozwiązanie w "silniku" ot szukam wskazówek by poruszać szarymi komórkami.

1. Ma ktoś pomysł jak stare gry przechowywały w pamięci mapki izometryczne jak np Twierdza? Zauważyłem że składa się ona z wielu kwadracików ale jakoś standardowa mapa 2d (zwykła tablica 1 wymiarowa albo 2 wymiarowa) w pamięci mi nie pasuje.

Domyślam się że jest kilka warstw takiej mapy gdzie znajdują się różne elementy (zasoby, jednostki, budynki, navmesh), a wysokość generowana jest na podstawie bitmapy w odcieniach szarości jednak jakoś mi się to nie spina bo zakładając że zwykła piekarnia zajmuje 5 bloczków, a tych piekarni można nastawiać od zatrzęsienia to zwykła mapa była by np 1024 x 1024 = 1.048.576 * 4 => 4.194.304 bajtów (4MB) pamięci zakładając że struktura na którą wskazuje referencja nic nie waży.

Dzielenie takiej mapki też raczej wiele nie daje bo przecież rozgrywka odbywa się na całej mapie jednocześnie. Wielkość przeze mnie przytoczona też jest chyba mocno zaniżona jak grałem w tą grę to wydawało mi się że mapka jest sporo większa.

2. Jak realizowany może być "strzał"? Zauważcie że na poniższym zdjęciu niektóre jednostki stoją na takich wysokich wieżach więc ich zasięg rośnie, a inne jednostki muszą strzelić "wyżej" bo inaczej nie mają zasięgu.

To co zauważyłem:

• Na pewno jest wiele warstw mapy (inna na path finding, inna na budynki, a jeszcze inna na zasoby)
• Wysokość każdego z bloczków można edytować oddzielnie co wskazuje na posiadanie bitmapy opisującej wysokość
• Każda jednostka zabiera 1 SQM
• Strzały lecą po jakieś paraboli bo "obijają się" od murów.

Tak jak już napisałem w komentarzu, zawyżyłeś rozmiar mapki, dla Stronghold to będzie 400x400, w związku z czym taka dwuwymiarowa tablica kafli będzie mniej obciążająca dla pamięci niż by się zdawało. Ażeby to zobaczyć w praktyce, zajrzałem do kodu gry Warzone2100, strategii RTS wydanej w 1999, której kod wypuszczono w całości w 2004. Od tego czasu ludki pracują sobie z tym kodem, repo można znaleźć w https://github.com/Warzone2100/warzone2100. Przepisali to w całości z C do C++. Żeby więc olać te nowsze zmiany, zajrzyjmy do innego repo, ze starym legacy kodem w C, pod linkiem https://github.com/Subsentient/wz2100legacy. Być może gdzieś się poniewiera jeszcze starszy kod, jak ktoś chce to niech się bawi w archeologa i szuka ;)

Limit rozmiaru to 256*256 kafli (tutaj).

Tutaj mamy definicję kafla: https://github.com/Subsentient/wz2100legacy/blob/microwave/src/map.h#L84-L102

/* Information stored with each tile */
typedef struct _maptile
{
	uint8_t			tileInfoBits;
	uint8_t			tileVisBits;	// COMPRESSED - bit per player
	uint8_t			height;			// The height at the top left of the tile
	uint8_t			illumination;	// How bright is this tile?
	uint8_t			radarIllumination; // Tile Illumination inverted to show proper heights on minimap.
	uint16_t			texture;		// Which graphics texture is on this tile
	uint8_t			watchers[MAX_PLAYERS];		// player sees through fog of war here with this many objects
	float			level;
	BASE_OBJECT		*psObject;		// Any object sitting on the location (e.g. building)
	PIELIGHT		colour;
	short			limitedContinent;	/** For land or sea limited propulsion types */
	short			hoverContinent;		/** For hover type propulsions */
	uint16_t firecount; // how many fire effects are on this tile?

//	TYPE_OF_TERRAIN	type;			// The terrain type for the tile
} MAPTILE;

Jak widać leżą na nim takie dane jak wysokość, informacje na temat fog of war, jak i wskaźnik na obiekt (jak budynek), jeżeli takowy tak jest. Tutaj natomiast jest kod tworzący mapę, który alokuje całą tablicę. Jaki rozmiar ma ów kafel...?

#include <stdio.h>

#include "wz2100legacy/src/map.h"

int main() {
    printf("%ld\n", sizeof(MAPTILE));
}

$ gcc test.cpp -o test -I/tmp/wz2100legacy/ -I/usr/include/SDL/
48

Czyli wychodzi, że dla maksymalnego rozmiaru mapy zajmuje ona 3MB. W tamtych czasach RAM w typowym kompie miał około 32MB, więc nie brzmi to szczególnie strasznie.

Resztę wątpliwości pewnie też można rozwiązać studiując ten kod.

A tutaj inny przykład, Seven Kingdoms: Ancient Adversaries, wydany w 1998, udostępniony jako Open Source w 2009. Tutaj jakieś modyfikowane repo https://github.com/the3dfxdude/7kaa. Kod, po pobieżnym przeglądnięciu daleko mniej przejrzysty od tego z Warzone2100.

Limit mapy to jak się zdaje 200x200 (link). Kafle to chyba klasa Location, w ramach oszczędności miejsca dane są upakowane po bitach, cała masa metod pomocniczych pozwala zwracać informacje na temat szczegółów, w rodzaju:

	int	has_hill()			{ return (loc_flag & LOCATE_BLOCK_MASK) == LOCATE_IS_HILL; }

Klasa Matrix trzyma tablicę kafli. Wskaźnik leży tutaj. Pamięć jest zaalokowana liniowo, więc tutaj jest metoda, która zwraca Location dla danej pozycji

   Location* get_loc(int xLoc,int yLoc)
        { return loc_matrix+yLoc * max_x_loc + xLoc; }

@Spearhead
Dzięki wielkie za odpowiedź i to bardzo wyczerpującą źródła jak będę mieć chwile na pewno przejrzę. A jeszcze dopytam tylko o realizacje strzału. Myślisz że to będzie realizowane za pomocą https://pl.wikipedia.org/wiki/Krzywa_balistyczna ?

Obliczenia te wydają się dość skomplikowane jeśli weźmiemy pod uwagę że w podstawce limit jednostek wynosił 1.000 / ilość graczy, a w "dodatku" podnieśli go znacząco do 10.000 / ilość graczy. Zakładając że gracze atakują 100 jednostkami, a inni się bronią 100 jednostkami strzelającymi to wyznaczenie celów dla każdej jednostki, obliczenie strzału oraz utworzenie odpowiednich pocisków (pewnie z jakiś pooli są brane) trochę czasu zajmuje. Może jest jakiś limit na klatkę jednostek dla których wykonywane są obliczenia?

Myślałem nawet nad dzieleniem mapy na strefy i sprawdzanie jedynie jednostek znajdujących się w strefie / przylegających do strefy żeby odciążyć ilość sprawdzeń czy jakaś jednostka nie weszła w zasięg strzału.

W ogóle obsługa takiej ilości jednostek wydaje się skomplikowana nawet jeśli zaczniemy je grupować w oddziały (chyba starcraft tak robi / robił że wyznaczał lidera i tylko jemu liczył dystans, a reszta trzymała się lidera) ale to materiał na inny temat który mam w planach.

Popatrzmy znów jak to jest w Warzone2100, będę tu używał nowego repo, bo jest czystsze.

Tutaj mamy klasę pocisku. Trzymane tą tam m.in. współrzędne celu, gdzie pocisk leciał. Pociski trzymane są w statycznym wektorze tutaj (ach ten gamedev i jego antywzorce, singletony i zmienne globalne :D). Dzięki temu po wystrzeleniu pocisk nie jest w żaden sposób związany z obiektem, który go wystrzelił - ot, takie "wystrzel i zapomnij". Tutaj widzimy dość długą funkcję odpowiedzialną za wystrzał pocisku. Interesujący fragment jest tutaj, wywoływana funkcję, która oblicza początkowe prędkości według jakiegoś tam wzoru. Potem w każdym kroku aktualizowane są wszystkie pociski z wektora (funkcja). Jeżeli stwierdzimy, że pocisk ciągle leci to wołamy kolejną funkcję. Funkcja ta obsługuje różne rodzaje pocisków w zależności od jego typu, jak bezpośredni (zgaduję, że po prostu leci jak po sznurku), jest i balistyczny, który aktualizuję pozycję według jakichś tam wzorów, które można by próbować poanalizować.

Teraz Stronghold. Jest on dużo prostszy, bo w nie jest 3D, jak Warzone, a wszystko operuje na sprite'ach, dzięki czemu można spokojnie obsłużyć więcej strzelców naraz. Według tego linku limit na strzały w powietrzu to 1500. Późniejsze łatki pewnie to powiększyły, ale że w tym czasie parokrotnie zwiększyły się też i moce obliczeniowe komputerów, nie jest to problemem. Zapewne więc istnieje jakaś tablica pocisków, przy każdej klatce przelatujemy po niej i aktualizujemy pozycję sprite'a. Każdy element tej tablicy trzyma pewnie końcową pozycję wprowadzoną w momencie wystrzelenia pocisku i jak dochodzimy do końca lotu sprawdzamy, czy pod danym kaflem coś jeszcze jest - jak tak, to możemy uznać, że zaszło trafienie. Jako że wszystko i tak jest izometryczne bez możliwości pochylenia kamery, prawdopodobnie potrzebujemy przy strzale wyznaczyć jedną parabolę. Na filmiku widać, że dla ustalonej pozycji celu i strzelca każda strzała leci dokładnie tą samą trasą. W momencie strzału, przy dodaniu elementu do listy pocisków, wyznaczane są parametry, być może są one też cache'owane w obiekcie samego łucznika, dzięki czemu, jeśli strzela on w to samo miejsce bez ruchu (co pewnie jest powszechne w trakcie gameplayu) to nie musimy wyznaczać dla niego parametrów dla każdej strzały z osobna.

Najprostszy, ale pamięciowo kosztowny sposób, to byte[][] gdzie wartość komórki przechowuje to co ma zostać narysowane na mapie. Rysowanie jest proste - zaczynasz od góry wrzucać sprite'y wypełniając kolejne kafelki, i nadpisując na canvas to co jest wyżej. Do tego robisz sobie mapę typ kafelka - wysokość i na tej podstawie jesteś w stanie określić jak daleko poleci pocisk.

Możliwe optymalizacje podejścia wyżej, to zastosowanie algorytmów do przechowywania macierzy rzadkich (większość mapy to takie same kafelki, którym przyporządkowujesz wartość 0). Można też używać pojedynczych bitów (czyli przykładowo, zakładasz, ze na mapie terenu wystąpią 4 typy trawki, to każdy z bajtów tniesz sobie na 4 części po 2 bity. Reszta rzadszych obiektów jest zgrupowana, więc można utworzyć dużo mniejsze mapki. Umiejscawiając je na mapie jednym intem.
Można też całą tą mapę z roślinkami, kamieniami itd. zastąpić ciągiem pseudolosowym i pozostanie do zapisanie jedynie jego seed.