Server
대표적으로 Login, Zone, Update, Lobby, DB 5개의 Server를 따로 두고 필요하다면 NPC Server같이 추가로 둘 수도 있음
Login Server
Zone이나 Lobby Server들 중 부하가 적은 Server를 선택해서 넘겨줌
NPC Server
NPC의 속성, 길찾기 등을 전담하는 Server
AI
Nav Mesh Server
Object의 Vertex 정보를 기반으로 CP(Check Point)를 설정하는 방법
DFS, BFS
두 방식 모두 graph를 순회하는 방법이지만 길찾기에 필요한 최단거리를 계산하는 방법과는 거리가 멈
Spanning Tree
모든 Node를 순회하는 비용이 최소가 되는 구조
Prim
연결된 Node set에서 cycle을 만들지 않는 최소비용의 edge를 선택하는 방식
Kruskal
전체 Edge들 중에서 cycle을 만들지 않는 최소 비용의 edge를 선택하는 방식
최단거리 알고리즘
Dijkstra
연결된 Node set에서 cycle을 만들지 않는 최소 비용의 edge를 선택 후 전체 node의 비용 재계산
Floyd
2개의 Node를 선택 후 중간 경로 중 가장 가까운 비용이 싼 경로를 선택하는 방식
Weight[A][B] = min(Weight[A][B], Weight[A][K] + Weight[K][B])
A Star
정적인 연산인 Dijkstra와 Floyd와는 다르게 동적으로 연산 수행
F = G + H
G : 현재까지 이동하는데 소요된 비용
H : 목적지까지 이동하는데 예상되는 비용
열린 목록에서는 가장 F가 싼 Node 선택
충돌 시 G가 가장 싼 Node로 변경
목적지에 도달하면 부모 노드를 역순으로 검색
Reference : https://itmining.tistory.com/66
개인적으로 BFS의 변형같은 느낌
H 연산을 위한 거리측정법
체비셰프, 유클리드, 맨하탄 순서로 대각선 비용이 쌈
체비셰프 : 체스의 king의 움직임
상태 전환 시스템
상태를 미리 결정 후 Event 발생에 의해 상태 변환
FSM
State마다 Process를 수행
state와 event, transition state를 미리 정의
Behavior Tree
state를 Tree 형태로 구현
수정이 편리함
Sequence
여러 조건들이 부합할 때 상태 전환
Select
여러 조건들 중 부합하는 조건에 대해서 상태 전환
Group Behavior
Flocking Algorithm
군집의 cohension(결집), separation(분리), Alignment(정렬)에 대한 알고리즘
Alignment
철새들이 하늘을 날 때 대형을 갖추는 모습
Agent를 따라가는 구조
Agent가 길을 찾고 나머지는 따라가는 방식
Neural Network
Neural Network, Machine Learning, Deep Learning 등이 존재
Server의 동기화
ping test를 수행한 후, 가장 느린 client를 기준으로 시간 설정 방식
모든 Client는 Network에서 Delay가 발생할 수 밖에 없기 때문에 Client에서의 실제 정보와는 차이가 있을 수 있음
모든 Network Game은 Client에서 과거를 보여준다
위치 차이
Time마다 위치 packet을 보내는 방식
과거 위치를 기준으로 현재 온 packet에 지정된 위치로 보간하여 이동시킴
Action
Client에서 action을 요청하면 Server에 전송 후, response를 받으면 action 수행
Client의 action을 Server time 기준으로 지정해서 수행 예약하는 방식
Trick
Server에서 응답이 돌아오는 시간 차이에 대한 user의 불편함을 줄이기 위해 Effect나 Sound같은건 input과 함께 미리 수행하고 실제 action은 response를 받았을 때 계산하는 방식
