Jestem absolutnie początkującym w tworzeniu gier i wszystko, co wiem o unikaniu kolizji / rozwiązywaniu problemów, nauczyłem się tego na tej stronie lub za jej pośrednictwem w ubiegłym tygodniu ... więc nie wahaj się mnie poprawić, jeśli o to pytam na podstawie błędnych założeń / nieporozumień. Starałem się, aby wszystko było jasne, ale powiedziano mi, że temat jest dla mnie wciąż nowy.
Pojazdy
W mojej grze mam pojazdy, które poruszają się autonomicznie. Są one umieszczone w przestrzeni 3D, a ich ruchem rządzi wiele zmiennych, które są różne dla każdego pojazdu. Interesujące tutaj są przede wszystkim:
- Tylko ruch do przodu .
- Prędkości , które mogą różnić się pomiędzy minimum i maksimum, ale której minimum jest nie (nawet w pobliże) zera.
- Promień kierownicy , która jest zależna od prędkości obrotowej (prędkości większej, tym większy promień)
- Dwa maksymalne przyspieszenia (dla zmniejszania i zwiększania prędkości)
Cel
Moim celem jest zaimplementowanie sztucznej inteligencji, która w 100% pozwoli uniknąć kolizji (tzn. Będę mieć pewność, że pojazdy nigdy nie zderzą się).
Projekt
- Chociaż wolałbym bardziej pomysł posiadania AI na pokładzie (tj. Każdy pojazd ma własną „AI unikania kolizji”, ewentualnie wysyłanie zapytań i / lub wysyłanie wiadomości do innych pojazdów), jest również możliwe, aby zaimplementować AI AI na poziom centralny (wysyłanie poleceń do pojazdów).
- W większości przypadków pojazd będzie musiał po prostu omijać się w dowolnym kierunku, ale w pewnych okolicznościach będą musieli unikać kolizji i zbliżać się do tego samego celu
Co znalazłem do tej pory i gdzie utknąłem
Wśród wielu linków, które znalazłem w innych pytaniach na tej samej stronie, znalazłem szczególne zastosowanie tych:
Chociaż te trzy linki „otworzyły mi oczy” na wiele sposobów, nie jest od razu jasne, jak wykorzystać te informacje w moim przypadku. W szczególności artykuł nr 2 „tylko” próbuje zapobiec kolizji (ale kolizje zdarzają się od czasu do czasu). Podczas gdy artykuł nr 3 musi czasami zatrzymywać pojazdy, aby uniknąć kolizji.
Zauważyłem również, że powyższe algorytmy unikania kolizji używają „natychmiastowej projekcji” prędkości liniowej, aby sprawdzić, czy coś nie jest w drodze z pojazdem. Zastanawiałem się, czy to wystarcza w moim przypadku, czy też musiałem rzucić swoją pozycję w bardziej realistyczny sposób (np .: Jeśli jestem 60 ° w kierunku skrętu o 90 ° w prawo, powinienem obliczyć swoją pozycję dla reszty 30 ° krzywej, a następnie przy założeniu ruchu liniowego).
Wreszcie szczególnie obawiam się impasu . Innymi słowy: chociaż gęstość pojazdów na świecie będzie dość niska, martwię się, że biorąc pod uwagę pewną liczbę pojazdów zbliżających się do tego samego punktu, kiedy zdadzą sobie sprawę, że są na kursie kolizyjnym, wszelkie manewry omijania będą niemożliwe ponieważ spowodowałoby to, że pojazd znalazłby się na drodze kolizji z innymi pojazdami.
Pytanie
Jak mogę osiągnąć swój „cel”? Dogłębne wyjaśnienie jest oczywiście bardzo mile widziane, ale linki do zasobów zewnętrznych również byłyby bardzo pomocne (jestem pewien, że nie jestem pierwszy z tym problemem, ale prawdopodobnie użyłem niewłaściwych słów kluczowych do wyszukiwania w Internecie? )
Z góry dziękuję za Twoją pomoc!
źródło
Odpowiedzi:
Czy zastanawiałeś się nad algorytmami flokowania ? Kiedy patrzę na twój opis, przychodzi mi na myśl. Jest wiele artykułów na ten temat, oto jeden lubię . Prawdopodobnie nie wykorzystasz wszystkich aspektów uciekania, takich jak spójność. Większość aspektów byłaby przydatna do tego, co próbujesz zrobić, na przykład wyrównanie i separacja, które pomogłyby uniknąć kolizji. Skończyłbyś się czymś innym niż uciekanie, ale powinno ci to pomóc zacząć.
Powodzenia!
źródło
Oto podejście: każdy pojazd ma krótką rzutowaną ścieżkę, w której pojazd na końcu zwalnia i wchodzi w pętlę, ścieżki te nie mogą się pokrywać. Za każdym razem, gdy pojazd zbliża się do punktu, w którym jest spowolniony, próbujesz wygenerować nową ścieżkę, która nie zachodzi na żadną z istniejących. Jeśli nie okaże się to możliwe, pojazd kontynuuje podążanie wyznaczoną ścieżką i okresowo próbuje wykonać nową ścieżkę.
Metodę można ulepszyć, aby umożliwić ściślejszy ruch, pozwalając, aby ścieżki prowadzące do pętli nachodziły na siebie i pętle, w których można ustalić, że nie spowoduje to kolizji.
źródło
Zastosuj metodę w każdym pojeździe, w której wykonuje ono po sobie wyszukiwanie promieniowe, jeśli w promieniu znajdują się inne pojazdy, odsuń się w sposób odpowiedni dla twoich upodobań: 1) Poruszaj się w przeciwnym kierunku, 2) zwolnij, 3) przyspieszyć itp.
Możesz nawet wykonywać kombinacje: jeśli wektor drugiego pojazdu nie jest na wprost ani bezpośrednio za: odsuń się; inaczej, jeśli jest prosto: zwolnij; inaczej: przyspieszyć.
źródło
Gdyby to było możliwe, zostałby do tej pory umieszczony na wszystkich samolotach świata.
Sugeruję złagodzenie aspektu „autonomicznego” i posiadanie funkcji, która rozwiązuje przewidywane kolizje między 2 (lub więcej) pojazdami. Może być tak naiwny, jak wybieranie losowych nowych kierunków podróży i sprawdzanie, czy to rozwiązuje problem, ale ważne jest to, że funkcja powraca tylko wtedy, gdy osiągnie porozumienie, które pasuje do obu pojazdów.
Sugeruję również, że każdy pojazd, który ma zderzyć się w najbliższej przyszłości, zmniejsza prędkość przy zachowaniu tej samej odległości do przodu - da to twoim pojazdom więcej możliwości uniknięcia kolizji, tak jak w prawdziwym życiu.
źródło
Brzmi mi to tak symulacja tłumu może być tematem najbardziej odpowiednim do tego, co próbujesz osiągnąć. Grupa GAMMA w UNC ma wiele pracy na ten temat, który może być wart uwagi. Ich opis:
http://gamma.cs.unc.edu/research/crowds/
źródło
Nie sądzę, aby istniała metoda 100% unikania, ale jeśli masz pełne informacje o świecie, możesz zamknąć każdy pojazd w polu, którego długość zależy od jego prędkości, i wykonać kontrolę kolizji na tych polach. Jeśli rzeczywiście dochodzi do kolizji, kieruj się z siłą zależną od bezpośredniego uderzenia (lub obszaru kolizji między dwoma skrzynkami) i spowalniaj (ale utrzymuj skrzynkę na tej samej długości podczas operacji unikania).
Oczywiście to nie zadziała, jeśli pojazdy nie będą miały pełnych informacji, ale w tym przypadku nic nie gwarantuje 100% unikania (z wyjątkiem, jak już powiedziano, ruchu równoległego)
niektóre opisane tutaj metody byłyby prawdopodobnie przydatne, w szczególności ta: zachowanie kierowania w przypadku niezrównanego unikania kolizji
pozdrowienia
źródło