Wyszukiwanie drogi

Question

Juz chyba od ponad 2 miesiecy zastanawiam sie jak zrobic algorytm wyszukiwania drogi. Na necie czytalem przyklady z mapami kafelkowymi,  gdzie petla musieliśmy przeleciec po calej mapie. A co gdy mamy mape 5000+ x 5000+, ktora nie jest mapa kafelkowa?

Jak dziala takie wyszukiwanie drogi w np. Gta v gdzie mapa jest ogromna?

Answer 1

Kafelki mapy to jest efekt renderingu informacji geoprzestrzennej i jeśli mowa o jakiś obliczeniach (routing) to w oparciu o takie dane to się przeprowadza. Nie jestem w tym zakresie specjalistą, tylko taką ogólną informację mogę Ci podsunąć.

M.

Comments

Em srednio rozumiem. Mozna powiedzieć ze moja mapa to kafelki 1x1 px.

---

Kafelek jest grafiką i ciężko mówić o obliczeniach w oparciu o taki materiał. Kafelki powstają na bazie informacji wektorowej (punkty, linie, współrzędne). Mając takie dane można pokusić się o wyznaczanie drogi. W grze pewnie jest to podobnie realizowane. Chyba, że czegoś nie rozumiem :-)

M.

Answer 2

A jakbyś zmodyfikował algorytm dijkstra, żeby zamiast wartości najkrótszej drogi zwracał tą drogę? I tylko jakbyś zboczyl z trasy dopiero wtedy generowal nowa drogę?

Edit: mógłby być problem taki, że trzeba mieć listę punktów. I o tyle byłoby lepiej, że mógłbyś sobie ograniczyć je, zakładając że np długość drogi nie będzie większa od powiedzmy 5x odległość.

Edit2: nie wiem czy o tym mówiłeś, bo nie znalazłem czegoś takiego jak mapy kafelkowe.

Answer 3

Dość dawno temu napisałem taki programik, który pokazuje proces znajdowania drogi tutaj możesz zobaczyć jak działa https://www.youtube.com/watch?v=9fZhoPan4Rc

W GTA mapa jest raczej podzielona na sektory i jak się przemieszczasz to kolejny sektor jest wczytywany. Dzięki temu dużo mniej obliczeń trzeba robić żeby znaleźć trasę. Mapy o rozmiarach 5000 x 5000 raczej muszą być również dzielone na mniejsze sektory bo przy tak dużej mapie powstają spore problemy z znajdowaniem drogi.