Path Finding

드론 경로 탐색 알고리즘

GitHub - supercontact/PathFindingEnhancedGitHub

아래의 3가지 알고리즘을 사용하였습니다.

Algorithm 1 A*

 procedure Main()
 open := closed := φ;
 g(sstart) := 0;
 parent(sstart) := sstart;
 open.Insert(sstart, g(sstart) + h(sstart));
 while open 6= φ do
 s := open.P op();
 if s = sgoal then return ”path found”;
 closed := closed ∪ {s};
 for each s' ∈ nghbr(s) do
 if s' ∈/ closed then
 if s' ∈/ open then
 g(s') := ∞;
 parent(s') := NULL;
 UpdateV ertex(s, s');
 return ”no path found”;

 procedure UpdateVertex(s,s’)
 gold := g(s');
 ComputeCost(s, s');
 if g(s') < gold then
 if s' ∈ open then
 open.Remove(s');
 open.Insert(s', g(s') + h(s'));

 procedure ComputeCost(s,s’)
 / ∗ P ath 1 ∗ /
 if g(s) + c(s, s' < g(s') then
 parent(s') := s;
 g(s') := g(s) + c(s, s');

Algorithm 2 Theta*

Algorithm 3 Lazy Theta*