https://factorio.com/blog/post/fff-317
작년 10월경 업데이트된 신규 길 찾기 알고리즘
청크 단위로 A*를 실행하게 변경됐던데
바이터의 공격 대상인 대포는 외각 경계에 있고
아무리 생각해봐도 저 정도 영역 탐색은 불필요해 보이는데
발코딩 ㅅㅂ
이것저것 확인해보는데 신규 길 찾기 알고리즘 도입할 때 대규모 테스트는 전혀 안 해봤나 봄
디버깅 메뉴 활성화 시켰을 때 화면 외부 데이터는 안 그린다는 가장 기본적인 최적화도 안 되어있는 것 보면
대규모 상황을 고려 안 할 거면 길 찾기 최적화는 왜 한 건지 의문이다
엥? 그거 님 공해 때문아님? 공해 닿은 애들이 공격 오겟다고 경로 보는거지 안닿은 애들은 그냥 별거 없는데
지금 공해로 유발되는 활성 바이터를 줄이려고 영역을 확장시키는 중이거든. 이미 공해로 유발되는 바이터는 없는데, 스샷에는 안 나와있지만 UPS가 많이 떨어질 때 Path finder 에서 잡아먹는 시간이 60% 정도 되더라
https://gall.dcinside.com/mgallery/board/view/?id=factorio&no=20081
남쪽 애들이 공해를 먹고 있긴 한데 이 상태로 대포 안 쏠 때는 60UPS거든
지금 상황을 간단하게 설명하자면, 북동쪽 끝에 대포 1개에 도달하기 위해 바로 앞에 있는 바이터 무리가 길 찾기 연산을 짤에 나오는 초록 범위만큼 하고 있는 거야
청크단위로 A*한다는게 맵을 사각타일로 일률적으로 나누고 각타일들을 A*의 노드로 계산한다는소리야?
아 A*으로 계산하는 도착점이 너무 넓다는 소리구나 그러게 엄청넓네 바이터들이 눈이 좋은건가
팩토리오는 32 * 32 타일 단위로 청크가 구성되는데(시프트+스페이스 또는 show-tile-grid로 확인 가능) 길 찾기를 최적화 하기 위해 청크 단위로 추상 노드를 구성하고 길 찾기를 실행할 때 이걸 참고하거든. 쉽게 말해서 길 찾기에 사용되는 레이어가 타일 단위와 청크 단위 2개인 셈인데, 짤에 표시되는 녹색 범위는 청크 단위 추상 노드고 A* 시 목표 지점이 코앞이고 연결 경로가 없는 것도 아닌데 참조하는 범위가 너무 크다는 거지. 버그 같음
청크단위를 크기가 똑같은 그리드 단위로 하는게 맞구나 근데 궁금한게 R트리나 Quad Tree처럼 청크나누고 A*로 길찾기는 못함? 아니면 이미 Quad tree 처럼 하고 있는건가?
근데 초록색 범위를 다시보니 Quad트리는 아닌거 같긴한데
A* 노드 구성 자체가 일종의 트리 형식임. 청크와 타일 레이어 2개로 구성돼서 최적화되는 이유는 기본적으로는 타일 레이어로 A*를 돌리는데 청크 단위로 목표를 선택하는 형식이라 그럼(아마도)
어 난 A*가 맵을 구역별로 나눈뒤 각 구역을 점으로 보고 인접하면 선으로 이은 그래프 대상으로 길찾기하는 걸로 아는데 내가 궁금한건 어떻게 맵을 구역별로 나눌지에 대해서인데 단순히 바둑판처럼 그리드로 나눌수도 있고 R 트리이나 Quad 트리처럼 구역별 오브젝트수를 비슷하게 나눌수도 있다고 생각해서
이미 청크 나누는데 Quad트리 같은걸 적용하고 있다면 탐색영역이 커도 연산량이 적을거 같아서 물어봤음