격자형 턴제게임에서는 Vector2Int 좌표계를 사용하면 이를 기반으로 논리를 연산한다
이때 시야에 있는 적이나 타일을 확인하기 위해서 탐색을 하였는데
첫번째로 DFS 깊이우선 탐색을 진행하였다 그러나 canSeethrough의 뒤편까지 탐색을 진행하여 시야를 가리는지 체크하지 못하였다
두번째로 raycast를 통해 ray가 canSeethrough false인 tile을 지나는지 확인하여 시야를 체크하려했으나 보는 바와같이 과도하게 많은 타일 즉 사이에 있는 모든 타일을 체크하기에 오히려 부정확한 결과를 갖게 되었다.
마지막으로 Bresenham 알고리즘을 사용하여 Vector2Int좌표계에 직선에 가까운 좌표 집합을 생성하고 이를 기반으로 시야체크를 진행하게 되었다.
브레젠험은 레스터방식에서 직선이나 원을 그리는 알고리즘을 만든 인물이다.
흔히 직선 방정식은 y = mx + b 이며 기울기는 m일때 x값의 정수 변화에 따라 dy = m * dx로 간단하게 구성된다.
따라서 vector2 int에서의변화도 dy - yInt > 1 일때 yInt ++ 를 해주면 완성이다.
그러나 정수연산을 하면 계산도 정확해지면 처리속도도 더 빨라진다 더군다나 격자 방식의 현재의 게임과는 더 잘맞는 방식이다.
https://playground10.tistory.com/62
[알고리즘] 브레젠험 알고리즘
선분그리기 알고리즘 중 대표적이고 정수계산이라 많이 쓰이는 브레젠헴, 브레젠험 알고리즘(Bresenham's algorithm) 오늘은 브레젠험 알고리즘의 원리와 구현방법을 포스팅하려합니다. - 브레젠험
playground10.tistory.com
이는 y(k+1) = yk , yk +1 이 될지를 선택하는 문제이다. 중간 지점이 직선의 방정식보다 위에 있을경우 yk를 아닐경우 yk+1을 넣어주어진행을 하는것이다.
이를 판별식을 통해 수정한 결과 브레젠험 직선 알고리즘이 나오게 된다.