Witam.
Poszukuję prostego w implementacji algorytmu znajdowania drogi z punktu a do punktu b, który uwzglednia kolizję z kolistymi obiektami o parametrach x, y, radius. Jak się za to zabrać ?
Jeżeli chcesz podać kod to prosiłbym o pseudo-kod lub c++ w starej wersji.
0
6
Najprostszy chyba będzie A*: https://theory.stanford.edu/~amitp/GameProgramming/
Tutaj masz nawet wideo tutorial:
Kuliste obiekty najlepiej sobie uprość do kwadratów.
Kiedyś na podstawie tego implementowałem pathfinding: https://csis.pace.edu/~benjamin/teaching/cs627/webfiles/Astar.pdf
Funkcja zwracała listę współrzędnych, na gridzie od punktu A do B.
Dodam jeszcze, że w Unity mógłbyś użyć gotowca, NavMesh 
2
Najlepsze chyba źródło o A* https://www.redblobgames.com/pathfinding/a-star/introduction.html
A przynajmniej najbardziej wizualne.
No i jak szukasz czegoś prostego, to nawet A* nie musisz, tylko Breadth First Search, wtedy nie robisz heurystyk, tylko sobie jedziesz po wszystkich polach (ale ważne, żeby trzymać gdzieś informacje, czy dane pole było odwiedzone, czy nie. I żeby nie iterować po już odwiedzonych): https://en.wikipedia.org/wiki/Breadth-first_search
który uwzglednia kolizję z kolistymi obiektami o parametrach x, y, radius. Jak się za to zabrać ?
Te algorytmy zwykle robi się na prostokątnej siatce, więc wtedy taki kolisty obiekt mógłbyś umieścić w siatce (być może na kilku różnych polach) i miałbyś niedoskonałe przybliżenie.
Natomiast te algorytmy nie wymagają wcale prostokątnej siatki. Od strony algorytmu przechodzisz po prostu przez jakiś graf. Więc jeśli potrzebna byłaby dokładność, że to akurat ma być kolista przeszkoda, mógłbyś np. jakoś zakrzywić przestrzeń wokół przeszkody.
Albo zrobić na kilka etapów - najpierw odszukać ścieżkę na duże prostokąty, a potem w miejscach, gdzie jest przeszkoda, dodatkowo podzielić to na mniejsze prostokąty.
Przy czym zakładam cały czas, że przeszkoda byłaby statyczna.
0
Dijkstra albo zalewowy chyba.
3
W przypadku, gdy wiele źródeł dąży do jednego lub kilku celów, polecam
https://leifnode.com/2013/12/flow-field-pathfinding/
wtedy bez znaczenia, może być i 100 agentów w różnych miejscach a liczymy tylko raz
1
tBane napisał(a):
Poszukuję prostego w implementacji algorytmu znajdowania drogi z punktu a do punktu b, który uwzglednia kolizję z kolistymi obiektami o parametrach x, y, radius.
Trochę mało danych. Po współrzędnych widać, że chodzi o 2D, ale przydałoby się jeszcze wiedzieć tak pi razy drzwi ile tych kolistych obiektów może być po drodze, czy ścieżka może przebiegać pomiędzy dwoma obiektami i jeśli tak, to jaki musi być pomiędzy nimi minimalny prześwit. No i też przydałoby się wiedzieć czy ścieżka ma być absolutnie najkrótsza, czy ma być w konkretnej minimalnej odległości od obiektów oraz czy ma być zgodna z kafelkami, czy w formie linii łamanej.
Porób trochę rysunków poglądowych, tak aby łatwiej było zrozumieć czego potrzebujesz.