'A*'에 해당되는 글 1건

  1. 2011.12.05 Shortest Path Algorithm (1)
2011.12.05 20:59
[Shortest Path Algorithm]

최단거리 알고리즘

부대에 있을때, 스타크래프트에 관한 유닛의 이동에 관해서 궁금증이 생겼었다.

그러니깐,,, 지형을 보고 유닛이 목표지점까지 최단거리로 이동하는것.

그래서 찾아본게 길찾기 알고리즘! 다양한 길찾기가 있었는데, 제일 많이 보이는게 A*알고리즘이었다.

A*알고리즘은 타일기반의 게임에서 적절할것 같았다. 하지만, 스타가 타일기반 게임이긴해도 타일대로 움직이면 뻣뻣(?) 해 보일것 같아, 대충 알고리즘을 이해하고 넘어가기로 했다.

그러던중, 최단거리란게, 단순히 지형의 꼭지점을 지나가면 된다(? 뭔가 말이 이상한데, 아래 그림을 보고 확인하길..) 는생각을 하게 됬다. 그래서 이걸 만들어 보기로 했다.. 

하지만 먼저 검색을 통해 이미 있는 알고리즘이란걸 확인;;;-_-;;
 

출처 : http://www.cs.uwaterloo.ca/~alubiw/shortest-path-lecture.pdf

그래! 바로 내가 생각한게 이거야! 

이미 있을줄은 예상했지만;; 조금 뭔가 아쉽다고 해야 하나;;;ㅋ

 

저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License

'Math/Pahycis/Algorithm' 카테고리의 다른 글

[알고리즘] 카프-라빈 알고리즘 구현해보기  (2) 2012.02.09
Shortest Path Algorithm  (1) 2011.12.05
Voronoi diagram  (1) 2011.12.05
Trackback 0 Comment 1
  1. Favicon of http://estellenotes.tistory.com BlogIcon 에스텔시아 2011.12.11 00:17 신고 address edit & del reply

    A알고리즘...최적화를 위해서 어떤 꼼수를 써야하는지 고민하는게 일품이지.



티스토리 툴바