• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Najkrótsza droga potworka do celu.

0 głosów
198 wizyt
pytanie zadane 10 września 2016 w C i C++ przez Munvik Dyskutant (8,630 p.)

Cześć. Potrzebuje pomysłu jak zrobić algorytm na znalezienie najkrótszej drogi do celu (postaci w grze).

Mam na mapie potworki i chcę, żeby atakowały postać w grze. Napisałem już kod, który sprawia, że biegną w moją stronę i to wszystko działa. Problem powstaje, gdy na drodze jednego potworka stoi inny potworek.

Chcę żeby potworek wtedy poszedł najbardziej opcjonalną drogą nadal idąc w moją stronę.

Gra jest w SFML.

 

Może ktoś chociaż troche wie jak zacząć taki algorytm, czego się trzymać ?

4 odpowiedzi

+1 głos
odpowiedź 10 września 2016 przez obl Nałogowiec (46,240 p.)
wybrane 10 września 2016 przez Munvik
 
Najlepsza

Ja w mojej grze zaimplementowałem algorytm z mojego starego projektu tutaj.

Polega to na tym, że plansza,  po której obiekty się poruszają jest podzielona na pola. Na mapie przeszkoda oznaczona jest przez 1 (umownie), przez 2 jest oznaczony punkt startowy, następnie jest przeszukiwanie sąsiednich pól i wstawianie, jeżeli te są wolne liczby o 1 większej - ten krok powtarzany jest do  momentu "dojścia" do punktu docelowego lub, gdy wszystkie dostępne pola zostały już przeliczone co oznacza, że dojścia do celu nie ma. Jeżeli znaleziono dojście do celu, to robisz ścieżkę, skacząc od pola o największej wartości o krok w dół uzyskując serię współrzędnych pól, po których obiekt musi się przemieszczać. A i jeżeli w trakcie ruchu coś zajdzie drogę danemu stworkowi to musisz przeliczyć ścieżkę i poszukać nowego dojścia. W mojej grze wygląda to na razie tak:

https://www.youtube.com/watch?v=1fYKm7o1j7Q

komentarz 10 września 2016 przez Munvik Dyskutant (8,630 p.)
Myślisz, że mogę zrobić tak bez mapy kafelkowej ? U mnie każde pole może być pozycje

x = 0.0003 ,  y = 0.5 ze względu na to, że wszystko porusza się na vectorze predkosci i czasu :/
komentarz 10 września 2016 przez obl Nałogowiec (46,240 p.)

x = 0.0003 ,  y = 0.5 ze względu na to, że wszystko porusza się na vectorze predkosci i czasu :/

No dobra, to taka zagadka: po czym u mnie  się poruszają czołgi? Też jest wektor prędkości razy czas = wektor przemieszczenia.

Ten algorytm prawdopodobnie był wykorzystany w grze Heroes Of Might and Magic III. Musisz tylko dobrze przemyśleć jaki ma być rozmiar pul. Ale najpierw to spróbuj napisać sobie sam algorytm, bo później to będzie z górki.

komentarz 10 września 2016 przez Munvik Dyskutant (8,630 p.)
Dzięki ale jeszcze nie wszystkiego czaje z tego co napisałeś. Jeżeli mob stoi sam, biegnie bez żadnych przeszkód to oznaczmy go 2. Nie ma 1 na mapie. To wokół niego są pole o wartości 3 ?
komentarz 10 września 2016 przez obl Nałogowiec (46,240 p.)
Nie wiem jak ci to wyjaśnić, ale może moje nagranie działania tego algorytmu uświadomią ci jak to działa:

https://www.youtube.com/watch?v=9fZhoPan4Rc

Możesz też program ten ściąć (na mojej stronie jest link) i zobaczyć (potestować) jak to działa
komentarz 10 września 2016 przez Munvik Dyskutant (8,630 p.)
Teraz już czaje, dzięki kolego :)))
+1 głos
odpowiedź 10 września 2016 przez Sinnley Stary wyjadacz (12,740 p.)
Czy potworki ruszają się w tym samym czasie?

Są jakieś potworki z inną szybkością niż reszta potworków?

Napisałeś, że w grze nie da się poruszać na skos. Wobec tego proponowałbym takie rozwiązanie.

Załóżmy, że wielość potworka i gracza to 1 pole. Wtedy możesz zostać zaatakowany tylko z 4 punktów. Załóżmy, że zostałeś otoczony przez 4 potworki. Wtedy reszta powinna ustawiać się w "najblizszej kolejce" i gdy mobek w niej zginie atakować ciebie. W przypadku gdyby zginął mobek z innej kolejki może "zmienić plany" i iść właśnie w tamtą stronę.

Na pewno zapisujesz gdzieś pozycje potworków i gracza, a więc zajęte pola. W algorytmie poruszania się bierz pod uwagę tylko to nie zajęte i wszystko powinno działać.
komentarz 10 września 2016 przez Munvik Dyskutant (8,630 p.)

Wielkość postaci się różni od mobka poza tym mam wdrożyć różne rozmiary mobków i jeszcze jest kwestia, że mobki są w stanie atakować mając takie pozycje:

komentarz 10 września 2016 przez Sinnley Stary wyjadacz (12,740 p.)
Wszystko zależy od rozmiaru pola. Górny mobek z lewej strony ma bardzo małą przerwe do mobka pod nim, na dodatek jest minimalnie przesunięty w prawo.

Tworząc tą mapę i algorytm ruchu musiałeś przyjąć jakieś jednostki. Jeśli mob jest w stanie atakować mając choć minimalną "część siebie" stykającą się z twoją postacią, to zwyczajnie na tej zasadzie powinien działać twój algorytm, czyli szukać najbliższego wolnego miejsca, w które ze swoimi rozmiarami jest w stanie wcisnąć się chociaż w kawałku i takie szukanie powtarzać wraz z każdym odświeżeniem funkcji, co powinno następować conajmniej tak często, jak ruch któregoś z mobków lub jego śmierć.
komentarz 10 września 2016 przez Munvik Dyskutant (8,630 p.)
Zgadzam się, nawet bym potrafił napisać coś takiego, ale najbardziej mi zależy na napisanie najkrótszej drogi, w zasadzie to funkcji która wskaże dla moba vector (kierunek) w którym ma się poruszać, żeby iść w stronę celu.
komentarz 10 września 2016 przez Sinnley Stary wyjadacz (12,740 p.)
edycja 10 września 2016 przez Sinnley

No to jaki problem? Masz przecież współrzędne najbliższego wolnego punktu. Kierunek będzie zależał od dwóch rzeczy:

1. Typowo drogi w dobra strone, zwyczajnie ruch musi sprawiac ze odleglosc miedzy punktami ma się zmiejszać, sprawdzasz to na zasadzie

x0 - polozenie w poziomie gracza/najblizszego wolnego punktu
y0 - polozenie w pionie gracz/najblizszego wolnego punktu

x1 - polozenie startowe mobka w poziomie
x2 - polozenie po zrobieniu ruchu mobka w poziomie

y1 - polozenie startowe mobka w pionie
y2 - polozenie po zrobieniu ruchu mobka w pionie

if((mod(x1,x0)>mod(x2,x0))||(mod(y1,x0)>mod(y2,y0))
     zblizyles sie do celu.

2. Musisz wziac pod uwage zajete pola.

Nie ma tutaj jakiegos super optymalnego rozwiazania, bo nie możesz się ruszać na skos. Wobec tego za kazdym razem gdy zachodzi to co napisalem w ifku powyżej twój potworek zrobił ruch w dobrą stronę.

komentarz 10 września 2016 przez Munvik Dyskutant (8,630 p.)

To teraz zobacz:

Mob 1 będzie się ruszał w góre i w dół.

Przejdzie kilka razy do dołu i stwierdzi, że najbliższa najlepsza opcja to góra ruszy się w górę, potem stwiedzi, że najlepsza opcja to dół i tak w kółko.

 

komentarz 10 września 2016 przez Sinnley Stary wyjadacz (12,740 p.)
Niby dlaczego ma tak stwierdzić? Rozumiem, że nie zmieści się w tej przerwie u góry, skoro tak to ma stwierdzić, że najlepsza opcja to dół i tak stwierdzi, po prostu zrób warunek zmieszczenia się w tej przerwie. Znasz jej wymiary oraz znasz wymiary moba :)
komentarz 10 września 2016 przez Munvik Dyskutant (8,630 p.)
Dzięki za pomoc, ale algorytm który mi podał obi jest bardziej trafny / zrozumiały już dla mnie.
0 głosów
odpowiedź 10 września 2016 przez CzikaCarry Szeryf (75,440 p.)
Po prostu mówisz dla mobka, aby odsunął się od drugiego na jakas odległość w randomowym kierunku i wtedy odpalasz ten twój algorytm z tym podazaniem mobka w twoja stronę.
komentarz 10 września 2016 przez Munvik Dyskutant (8,630 p.)

Gorzej gdy zajdzie taka sytuacja:

I jeszcze mobków sie namnoży :/

0 głosów
odpowiedź 10 września 2016 przez Patrycjerz Mędrzec (187,390 p.)
Sądzę, że najlepiej zaimplementować przenikanie się potworów nawzajem.

Można także stworzyć kolizję między nimi, gdzie obiekty "sunęłyby" po sobie, gdyby nie miały miejsca do poruszania (udział w ruchu brałaby jedynie wtedy jedna ze składowych wektora prędkości).
komentarz 10 września 2016 przez Munvik Dyskutant (8,630 p.)

A co gdy zajdzie coś takiego ?

Poza tym ruch odbywa się tylko poziom albo pion (bez skosu).

komentarz 10 września 2016 przez Munvik Dyskutant (8,630 p.)
Poza tym coraz bardziej jestem przechylny do przenikania potworków, bo AI to już nie dla mnie

Podobne pytania

0 głosów
2 odpowiedzi 214 wizyt
pytanie zadane 16 stycznia w Nasze projekty przez Mavannkas Obywatel (1,070 p.)
0 głosów
0 odpowiedzi 188 wizyt
Porady nie od parady
Zadając pytanie postaraj się o szczegółowe opisanie problemu oraz udostępnienie wszystkich istotnych informacji (kody źródłowe, zrzuty ekranu itp.).Opisanie problemu

67,127 zapytań

114,075 odpowiedzi

241,784 komentarzy

47,030 pasjonatów

Przeglądających: 219
Pasjonatów: 18 Gości: 201

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...