[💬] 야매 알고리즘) 길찾기 연구중 스압

[Otoflak(badlow)]

길을 찾으려면 당연히 시작 지점과 목표 지점이 필요하다. 여기서 빨간점은 시작 지점이고 파란 점은 목표 지점이다.

어떤 방법을 통해 도달 했는지 모르겠지만 아마 아래와 유사한 길을 통해 목적지에 도달할 것이다.

길찾기 알고리즘을 통해 얻고자 하는게 뭔지 모르겠다만 수많은 방법론이 존재하고 다양한 변형이 존재함.

목적이 최단거리 구하는 것이라면 문제가 있는데 게임에서는 최단거리 루트를 구하는게

지나친 컴퓨터 자원 낭비가 될 수 있다는 점임. 따라서 적당히 빠른 길을 찾는게 연산을 덜 함.

일반적으로 A*니 뭐니 하는것들도 있는데 복습, 학습하기 귀찮으니 넘어가고

길을 찾는데 목적을 어디 두느냐에 따라서 방식이 갈리고, 자원은 2가지가 있음. 도달시간, 연산.

1. 가장 짧은 길을 탐색(도달시간 우선)

2. 목적지에 도달만 하면 됨(연산 우선)

3. 탐색 정확도 조절.

4. 필요한 자료만 남김.

복잡한건 됬고 탐색 정확도를 조금 낮추고 무식한 방법으로 해봄.

그림에서 빨간색 선이 서로 수직으로 교차하는 곳은 기준이 되는 좌표임임

일단 빨간 선이 교차하는 포인트와 벽이 겹치는지 확인해봐야 함.

이제 녹색 지점은 못감으로 정의하고 빨간선이 수직으로 교차하는 곳은 갈 수 있는 곳이 됨.

다음과 같은 알고리즘을 거침

1. 제일 목적지와 가까운 곳이 어디인가?

2. 해당 위치로 이동

3. 1~2을 반복한다.

뭔가 이상하지만 대충 넘어가고 나중에 문제가 터지면 교정해보자. 일단

출발지와 가장 가까운 곳은 M이고 목적지와 제일 가까운 곳은 D다

하지만 M은 목적지에서 멀어지는 길이고 제일 가까운 길은 J임.

J에서 탐색해보자 F, G는 전부 막히고 J에서 갈 수 있는 곳 중에 목적지와 제일 가까운 곳은 K임

??? 근데 J와 K의 벽을 뚫고 감. 알고리즘에 헛점이 생김 그래서 정밀도를 높히기 위한

다음과 같이 수정함.

1. 제일 목적지와 가까운 곳이 어디인가?

2. 목적지에 도달 할 때까지 해당 위치로 한칸씩 이동.

3. 벽을 만났다면 정밀도를 높힘.(범위를 좁힘 1/2 정도)

4. 1~3을 반복한다.

어... 그림이 이상하지만 넘어가자 e에 해당 하는 위치에 벽이 있다.가면 안대!

하지만 b, c에는 없다. 그러면 c로 가야하는데 이번에는 한칸 이동할때마다 벽이 있는지 확인하고 있음

정밀도를 올림

점점 그림이 지저분해지고 뒤틀린다.

e로 가는 라인은 막혔으니 s로 갈라 했다. 근데 s도 막혔으니 r로 가면 됨.

근데 우리는 최단거리에 대한 근사치만 구하면 되기에 정밀도를 다시 낮춰줘야 함

알고리즘 수정

1. 제일 목적지와 가까운 곳을 탐색한 후 그곳을 저장

2. 목적지에 도달 할 때까지 해당 위치로 한칸씩 이동.

3. 벽을 만났다면 정밀도를 높힘.

4. 목적지에 도달했다면, 이전에 저장한 위치를 다음에 이동할 위치로 덮어씌움.

5. 1~4을 반복한다.

어.... 최단거리는 아니지만 일단 길은 찾았다. 사실 맵핵을 원하는게 아니면 이게 전부임

최단거리도 찾고 싶으면 저기서 막혀있는 방향만 걸러서 정밀도 올려가다가

누적된 이동거리를 비교해서 이동시키면 된다.

여러 방법 중 하나를 그냥 생각나는대로 씨부린거고 매우 오류가 많고 정확하지 못함.

결정적으로 내가 너무 게을러서 티끌만한 의문도 그냥 씹고 대충 연구해서 씀

문제점 지적이나 더 나은 방법, 의문점 모두 환영함

말해줘야 내가 정식판을 빨리 내놓지

개힘들어 씨벌...

[익명(121.168)]

오호 그렇구만...

[ㄴㄷㅎ(143.248)]

스타크래프트 드라군 알고리즘 찾아보셈

[Otoflak(badlow)]

ㄴㄷㅎ// 그게 머야 A*?

[ㄴㄷㅎ(143.248)]

A* 맞는거같은데 그거 리프레쉬 주기를 빠르게 하면 똑똑해지고 느리게 하면 드라군처럼 멍청해진다던데

[Otoflak(badlow)]

ㄴㄷㅎ// 연산량 많다고 최적해는 못구해도 개조해서 쓰는 사람들이 종종 있다 들었음