BLOG main image
분류 전체보기 (92)
Cocoa Touch (11)
Cocoa (10)
Objective-C (13)
Swift (6)
Development (11)
Tools (11)
Books (7)
etc (21)
Application release (1)
Document Project (1)
106,090 Visitors up to today!
Today 0 hit, Yesterday 7 hit
daisy rss
tistory 티스토리 가입하기!
'Jump Point Search'에 해당되는 글 2건
2013. 11. 1. 12:30

예전에 JPS를 Objective-C로 구현했다고 포스팅한 글이 있는데 github에 소스를 공개해놓고 블로깅을 하지 않았군요.


그래서 다시 관련 글을 포스팅합니다. 아래 링크에서 OS X에서 구현한 JPS 소스를 받아보실 수 있습니다.

제대로 사용하지 않아서 버그가 있을 수 있으니 알아서 보시기를...


https://github.com/bearkode/PathFinder


PS. 라이센스를 명시하지 않았는데... 뭐 그리 큰 소스도 아니고... 대충 사용하세요 라이센스쯤 되려나요?

Name
Password
Homepage
Secret
2013. 5. 26. 12:34

게임을 제작하다보면 간혹 길찾기 알고리즘을 사용해야 할 때가 있다.

학교에서는 Dijkstra를 많이 가르치는 것 같은데 실제 많이 사용되는것은 A*알고리즘인것 같다.

그런데 문제는 별다른 확인 없이 그냥 맹목적으로 그것을 사용하는 경우가 많은것 같다.

어느 날 갑자기(사실은 갑자기라기 보다는 더 빠른 알고리즘을 찾아봐야 할 필요가 생겼다.) 길찾기 알고리즘에 다른 것이 또 뭐있나 궁금해졌고 JPS(Jump Point Search)를 찾게 되었다.

여기저기 뒤적 뒤적하면서 확인해본 결과 JPS는 A*보다 꽤 많이 빠르다. 다만, 이동의 코스트가 각 grid 마다 다를때 처리가 좀 문제가 될것 같고 최단거리를 찾아주지는 못하는것 같다. 하지만 빠른 속도로 얼핏 봤을때 가까운 길을 찾아주는것 같다. 게임용으로는 최적이라는 판단이 들었다.


그런데 여기서 가장 중요한 문제에 부딪쳤다. Objective-C는 거녕, C/C++로 구현된 코드를 찾기 힘들었다. (C++코드를 하나 찾기는 했지만 수정없이 편하게 쓰기는 거의 불가능했다.)

그래도 비교적 깔끔하게 다른 길찾기 알고리즘과 비교해 볼 수도 있고 코드도 공개된 곳이 있었다.

그런데, 이것도 문제인 것이 코드가 JavaScript다. 정말 산너머 산이라고...


결국... Objective-C로 직접 구현하기로 마음 먹었다. (왜 C로 구현해야지 하는 생각을 안했는지...)

그리고... 얼핏 돌아가는 것 처럼 보이는 코드가 완성되었고 테스트 중이다. (언제 공개할 수 있을려나?)




Name
Password
Homepage
Secret
prev"" #1 next