[💬] 2년간 고민했던 패스파인딩 해결..

[Anonymo..(220.86)]

옛날부터 스타크래프트2 유닛처럼 이동할때 동적장애물(유닛)에 대한 회피 알고리즘을 어떻게 할지 고민이 많았음.

스타2는 지형 길찾기는 그냥  타일기반 AStar같은데, 유닛들은 그게 아니라 Boid라는 것을 사용한다고 하더라고.

근데 Boid 튜토리얼같은 거 보면 Boid기본기능만 가지고는 스타2처럼 안되더라? 그냥 Seek랑 Separation기능만 키면 아래처럼 나옴

서로를 피할줄알았는데 장벽이 있으면 저렇게 못지나가버리는 애들이 생길수밖에 없음. 이게 만약 적들이 V자 깔때기(Convex Shape)로 서있으면 저게 더 심해짐.

저것떄문에 2년동안 끙끙 앓다가 완벽하진 않지만 그래도 90% 만족하는 방법을 찾음!

하 고놈들 잘 피한다 ㅠ 이뿌다! 힣

이게 그냥 스타1처럼 유닛도 장애물로 판단하고 AStar하면 될수도 있지만, 거긴 거기 나름대로 문제점들이 있거든.

그래서 어떻게든 Boid로 해결을 해보고 싶었음.

뭐 여기 인갤에는 이정도쯤은 몇일만에 걍 해결하겠지만, 나름 몇년동안 고민해서 해결한거라 기뿌네!

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[Anonymous(220.86)]

Boid에 Separation,Seek랑 별개로 Avoidance라는 기능을 추가한건데, Seek가 목적지(Destination)이 있을때만 동작하는것처럼, Avoidance도 목적지를 가지고 동작함. 목적지를 향하는 벡터 앞에 적이 있으면, 좌 혹은 우로 피하도록 Steer값을 주면됨. 단, 좌로 가기로 했으면 한 5초동안은 무조건 앞에 장애물이 있으면 무조건 좌로 가게 해야됨. 끗

[거붓(ggp02217)]

오 바로 이해했음, 헌데 boid는 처음부터 그 3가지 기능 다 있지 않았음?

[Anonymous(220.86)]

그 Avoidance 예제로 본거 대로 해봤는데, 막 벽처럼 가로막고있으면 안되더라고. 내가말한 Avoidance는 그 예제랑 다르게 그냥 한방향으로 일정시간동안 가는것뿐임. 이건 위에 스타2 gif을 보면, 저글링이 한방향으로만 가다가 다시 반대방향 가는거 보일거야. 왠지 애내도 그렇게한거같아서리.

[익명(175.120)]

오!! 멋있음

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[Anonymous(220.86)]

ㄴRVO를 이해하고 만들었단말야? 난 문서보고 이건 내가할수있는게 아닌거같아 포기했는데..

[익명(218.234)]

팩트: 인갤러들 이런거 할줄모른다

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[Anonymous(220.86)]

Lockstep기반이라 위치값같은 동기화는 없음. 클라이언트끼리는 입력만 주고받을거야

[Anonymous(220.86)]

예를들어 플레이어가 X,Y위치로 갓! 하고 입력을 주면, 다른 클라이언트에서는 그 입력만 받아서 '똑같이' 시뮬레이션만 하는거지. 그게 가능하게 하기 위해서 유니티에 NavMeshAgent같은 편리한건 사용못하고, 이렇게 직접 구현따로 한거고.

[Anonymous(220.86)]

실제로 내 첫 회사에서 만든게 모바일 AOS장르, Lockstep으로 만든건데. 그 스노우볼 시작점 찾는거가 정말 힘들지 ㅋ. 첨엔 5분마다 싱크가 엇나갔는데, 나중엔 안나오길래 됬다 싶었는데, 2시간뒤에 엇나가는 경우도 있더라고. 몇가지만 지켜주면 거의 엇나가는 일은 없음. 1.절대 유니티의 Update에 의존하는 것들을 사용하면 안됨.(Physics,NavMesh등) 2. Dictionary, HashSet을 foreach하는 행동(순회 순서가 플랫폼마다 다름) 3.float 절대 사용하지 말것. FixedFloat사용해야함. 당근 유니티의 Time.deltaTime같은건 사용불가지.

[익명(118.39)]

A* 문제 머가 있어?

[Anonymous(220.86)]

A*에 문제라기보다는, A*로 패스를 찾은 뒤가 문제. 동적장애물이 내가 찾은 경로를 가로막고있으면, 다시 패스파인딩을 해야되거든.

[Anonymous(220.86)]

근데 이게 목적지가 너무 먼데, 시작지점부터 동적장애물에 막히면 경로다시 계산하면 부하도 쌔고, 맵전체에 동적장애물을 장애물로 치고 경로계산을 다 하는것도 좀 이상하거든. 예를들어 옛날 스타크래프트 로템맵에서, SCV로 적진영 순찰가는데, 적이 입구막아버리면, SCV로 안보이는 적진 찍었을때 이상하게 움직이면 입구막혀서 이상한데로 움직이거든, 그럼 안가봐도 거기 적이 있다는거 바로 알수 있듯이. 이런 문제도 있고

[Anonymous(220.86)]

예전에 했던 기억으로는 그놈에 동적장애물때문에 예외처리하느라 코드 줜나더러워졌었음...

[익명(118.39)]

어 그러네 동적장애물 처리하는게 무조건 장점인줄 알았는데 아닌경우도 있네

[연어(smosal)]

NavMeshAgent같은거 안쓰는이유가있나? 동적개체 패스파인딩 지원되던거같은데 무거워서?

[Anonymous(220.86)]

네트워크 동기화로 Lockstep기반으로 할거라. 유니티의 FrameUpdate로 이루어지는 NavMeshAgent를 사용할수가업서서 그랬어

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[Anonymous(220.86)]

반갑다 친구야 ㅋㅋ 다 서버클라위치동기화 방식 쓰는데, 난 옛날 Lockstep방식이 좋더라고. ㅋㅋ

[거붓(ggp02217)]

그리드 보면 나눠지던데 HPA* 만든거임?

[Anonymous(220.86)]

저거 그냥 Boid끼리 근처에있는 애들 찾을때 최적화를 위해서 쓴 QuadTree 디버그로 보여주는 거임. 특정 구역에 Boid가 많이 모이면 그부분의 트리 뎁스가 하나 더 늘어나는게 보이는거.

[거붓(ggp02217)]

그렇구나 답글 ㄱㅅㄱㅅ

[익명(118.241)]

https://arongranberg.com/astar/docs_rvo_fix/local-avoidance.php
이걸로
해결가능하던데

[Anonymous(220.86)]

ㅇㅇ 맞아. 저것도 보긴했는데. Lockstep때문에 저런 라이브러리를 사용할수가 없었어. float연산은 쓰면 안되거든. FixedFloat를 사용하는 LocalAvoidance 프레임웤을 찾을수가 없더라고.

[익명(118.241)]

오... 그런것도 있구나 공부가 된다

[익명(119.194)]

118.241 local avoidance알려줘서 검색삽질 해결 ㄳㄳ

[익명(122.45)]

에이스타로 경로를 찾고 보이드로 그 경로로 steering하는거임? 오

[익명(122.45)]

다음 목적지를 향해 스티어링하고 어보이던스 하면 되는거였음? 오...

[익명(122.45)]

동적으로 길막히면 에이스타 다시해야하는거아님? 어렵누..

[Anonymous(220.86)]

맞음. 지형지물 피하는건 A스타로, 그 지형을 돌아다니는 애들은 Boid로 Steering해서 피하는거. 이게 그나마 게임만들때 심플한거같더라고

[익명(39.112)]

인갤 프로그래머 상위 0.01퍼센트

[감자마법(gamjamage)]

[익명(218.234)]

캬 ㅆㅅㅌㅊ

[익명(7hvc5bphs4sv)]

A*를 직접짜노...

[익명(119.194)]

A*갖고 4개월 고민한 인붕이한테는 꿈같은 이야기!! 개추 ㅋㅋㅋㅋㅋ

[익명(49.164)]

[익명(61.34)]

선생님 fixed float이 뭔가요

[Anonymous(39.7)]

1+4=5라는 계산은 amd든 intel,arm(모바일) 동일하죠? 근데 1.1+1.98=3.08이라는 계산은 amd랑 cpu,arm 다 다를 수 있어요. 시피유별로 출력해보면 3.080000001,같이 각자 시피유별로 정확하게 떨어지지 안을수있어요. 이건 float변수가 floating point(부동소수점)이기 때문에 그런데요.

[Anonymous(39.7)]

정확하게아는건아니지만 저 부동소수점이 시피유별로 계산이 다르다고 해요. 근데 fixed point(고정소수점)이라고 제가 위에서 언급한 fixedfloat라고말햇는데, 이건 내부적으로 int처럼 계산을해서 어긋나는게 없다고해요. 이 fixedPoint는 프로그램언어차원에서 지원하는 타입은 아니라서, int정수를 래핑한 타입으로 만드셔도되용

[Anonymous(39.7)]

Lockstep기반 네트워킹은 시뮬레이션 결과가 컴터마다 다 동일해야해서 다른시피유끼리 계산결과가 다르지 않게 해야되거든요. 그래서 fixedpoint를 써요. 옛날 게임에 lockstep동기화가 쉬웟던 이유는 기기들이 거진 다 비슷해서 시뮬결과가 비슷햇다는 얘기도 있고, 그당시 시피유들이 소수점 계산방식이 전부 인트여서 그랫다는 야기도 있어용

[EE(endolfinpump)]

[123(122.38)]

재밌어보이네

[익명(180.230)]

RTS가 잘 없는 이유는 장르자체가 사장세기도 하지만 만들기도 보기보다 겁나 빡세서인게 아닌가 싶다