Ahn9807: 새 문서: 분류: 경로 탐색 가운데 == 개요 == A는 목적지까지의 경로를 찾아야만, 탐색이 종료된다. 실시간 게임에서 이러한 과정을 기다리기는 너무 오래 결릴 수도 있음으로, 경로 탐색이 끝나기 전에 납득할 만한 경로를 주는 알고리즘이 TBA (Time-Bounded A)이다. Real-time이며 Optimal하다. == 알고리즘 == 가운데 A...

2023-02-25T10:50:53Z

새 문서: 분류: 경로 탐색 프레임없음|가운데 == 개요 == A*는 목적지까지의 경로를 찾아야만, 탐색이 종료된다. 실시간 게임에서 이러한 과정을 기다리기는 너무 오래 결릴 수도 있음으로, 경로 탐색이 끝나기 전에 납득할 만한 경로를 주는 알고리즘이 TBA* (Time-Bounded A*)이다. Real-time이며 Optimal하다. == 알고리즘 == 프레임없음|가운데 A*...

새 문서

[[분류: 경로 탐색]]

[[파일:TBA*.png|프레임없음|가운데]]

== 개요 ==
A*는 목적지까지의 경로를 찾아야만, 탐색이 종료된다. 실시간 게임에서 이러한 과정을 기다리기는 너무 오래 결릴 수도 있음으로, 경로 탐색이 끝나기 전에 납득할 만한 경로를 주는 알고리즘이 TBA* (Time-Bounded A*)이다.

Real-time이며 Optimal하다.

== 알고리즘 ==
[[파일:TBA Star.png|프레임없음|가운데]]
[[A*]]알고리즘을 이용하면서 경로를 만든다. 그러나 경로를 만들던 도중에 현재 생각되는 최선의 위치라고 생각되는 Path를 탐색하고 움직임에 반영시킨다. 그러면서 한정된 자원 (NS _ 탐색할 수 있는 노드의 개수, NT - 탐색할 수 있는 경로의 깊이)를 이용하여 Path를 계속 추적하고 현재 AI가 움직이는 Path와 새로운 Path가 겹치는 지점이 있으면, 새로운 패스를 반영하고 아니면 현재 패스를 백트래킹시킨다. 그 외의 경우에는 현재 패스를 따라가게 된다. 여기서 NS와 NT는 컴퓨터 속도에 따라서 자유롭게 설정 가능하다.

결국 기본적으로는 A*와 같지만, 중간에 산출되는 결과물을 AI가 이용할 수 있도록 추가하는 과정이 있는 알고리즘이다.

==Pseudocode==
The following [[pseudocode]] describes the algorithm:

<syntaxhighlight lang="pascal" start="1">
function reconstruct_path(cameFrom, current)
total_path := {current}
while current in cameFrom.Keys:
current := cameFrom[current]
total_path.prepend(current)
return total_path

// A* finds a path from start to goal.
// h is the heuristic function. h(n) estimates the cost to reach goal from node n.
function A_Star(start, goal, h)
// The set of discovered nodes that may need to be (re-)expanded.
// Initially, only the start node is known.
// This is usually implemented as a min-heap or priority queue rather than a hash-set.
openSet := {start}

// For node n, cameFrom[n] is the node immediately preceding it on the cheapest path from start
// to n currently known.
cameFrom := an empty map

// For node n, gScore[n] is the cost of the cheapest path from start to n currently known.
gScore := map with default value of Infinity
gScore[start] := 0

// For node n, fScore[n] := gScore[n] + h(n). fScore[n] represents our current best guess as to
// how short a path from start to finish can be if it goes through n.
fScore := map with default value of Infinity
fScore[start] := h(start)

while openSet is not empty
// This operation can occur in O(1) time if openSet is a min-heap or a priority queue
current := the node in openSet having the lowest fScore[] value
if current = goal
return reconstruct_path(cameFrom, current)

openSet.Remove(current)
for each neighbor of current
// d(current,neighbor) is the weight of the edge from current to neighbor
// tentative_gScore is the distance from start to the neighbor through current
tentative_gScore := gScore[current] + d(current, neighbor)
if tentative_gScore < gScore[neighbor]
// This path to neighbor is better than any previous one. Record it!
cameFrom[neighbor] := current
gScore[neighbor] := tentative_gScore
fScore[neighbor] := gScore[neighbor] + h(neighbor)
if neighbor not in openSet
openSet.add(neighbor)

// Open set is empty but goal was never reached
return failure
</syntaxhighlight>

TBA* - 편집 역사