Struktura danych do reprezentowania połączeń między krajami na mapie

9

W grze, którą opracowuję dla klienta, kluczowa koncepcja gry polega na poruszaniu się po mapie. W tym przypadku rozmiary i kształty różnych krajów są nieistotne: przejście z jednego kraju do sąsiedniego kraju liczy się jako jeden krok.

Próbuję znaleźć najlepszą strukturę danych do wewnętrznego reprezentowania połączeń między krajami. W danym kraju gra musi wiedzieć, które kraje sąsiadują ze sobą, zarówno aby wiedzieć, w jaki sposób gracze mogą się poruszać, jak i umożliwić sztucznej inteligencji gry zaplanowanie tras, określając możliwe ścieżki z jednego kraju do drugiego. AI musi również ocenić, jak dobrze jest powiązany kraj, nie tylko z sąsiadującymi bezpośrednio sąsiadami, ale także z sąsiadami tych krajów itp.

Wymyśliłem kilka możliwości, ale wydają się one niewygodne i nieefektywne. Ponieważ sztuczna inteligencja będzie musiała obliczyć kilka możliwych tras, aby podejmować dobre decyzje dotyczące ruchu, „nieefektywne” jest bardzo problematyczne.

Podejrzewam, że jest to dość powszechna łamigłówka CS i że istnieje wspólne rozwiązanie, ale nie mogłem wiele znaleźć, szukając. Wszelkie sugestie są mile widziane.

maps efficiency Matthew Frederick
źródło
Jeśli mam o to zapytać na GameDev.StackExchange, daj mi znać. Pytam tutaj, ponieważ jestem pewien, że tego rodzaju rzeczy są potrzebne do wszelkiego rodzaju problemów programistycznych i nie potrzebuję pomocy z „grą”, jako taką, tylko częścią planowania trasy.
Matthew Frederick
Potrzebujesz wykresu lub macierzy połączeń (co jest przydatne, ponieważ zamknięcie jest łatwe do obliczenia). Być może potrzebujesz obu. Sprawdź je.
2
Spójrz na struktury i algorytmy danych wykresu: en.wikipedia.org/wiki/Graph_%28data_structure%29
1
To nie wygląda mi na temat. Powinien to być GameDev lub Stack Overflow, ponieważ jest to zbyt obiektywny temat na ten temat.

Odpowiedzi:

6

Zdecydowanie wykres. Sprawdź to tutaj. Teoria grafów , w zasadzie masz węzły i krawędzie. Węzeł może zawierać 0 lub więcej krawędzi do innych węzłów.

Istnieje wiele algorytmów do obliczania najkrótszej ścieżki (przeskok lub odległość), sprawdzania liczby cykli (więcej niż jeden sposób na dotarcie do siebie) itp.

Teraz, aby móc wdrożyć wydajne rozwiązania, jest to trochę bardziej złożone, ale jak zwykle istnieją sposoby.


źródło
Wspaniale, dziękuję. Czy masz jakieś sugestie, gdzie znaleźć takie algorytmy? Nie potrzebuję tak najkrótszej ścieżki, ale takie rzeczy jak sprawdzanie kręgów itp. Byłyby bardzo przydatne.
Matthew Frederick
2

Jak już wspomniano, potrzebny byłby wykres przedstawiający wszystkie możliwe połączenia między krajami. Każde połączenie utrzyma również odległość między dwoma krajami.

Następnie można użyć algorytmu znajdowania ścieżki, takiego jak A *, w celu ustalenia najkrótszej ścieżki między dwoma krajami.

Istnieje również kilka dobrych książek na temat gry ai: Game AI na przykład Mat Buckland http://www.ai-junkie.com/books/toc_pgaibe.html

lub seria AI Game Programming Wisdom. http://www.aiwisdom.com/ Pierwsza książka zawiera kilka rozdziałów na temat wyszukiwania ścieżek.

Stephen
źródło
Doskonale, dziękuję za wskazówki do książek. Wydaje się, że istnieje mnóstwo książek na temat sztucznej inteligencji, a osobiste rekomendacje są znacznie lepsze niż ogólne wyniki wyszukiwania.
Matthew Frederick