効率的に自然なNPCの動きを実現するアルゴリズムを提案する論文紹介

miya

2025年2月17日 10:42

本記事の概要

ゲーム内のNPCの動きをより自然で人間らしくする効率的な新しいアルゴリズムを提案する論文を紹介する記事となります。

論文名

Toward the Believability of Non-Player Characters (NPC) Movement in Video Games

論文の著者

Rawia Mohamed *1, Waleed Al Adrousy *2, Samir Elmougy *3

*1: Department of Computer Science, Faculty of Computers and Information, Mansoura University, Mansoura 35516, Egypt
*2: Department of Computer Science, Faculty of Computers and Information, Mansoura University, Mansoura 35516, Egypt
*3: Department of Computer Science, Faculty of Computers and Information, Mansoura University, Mansoura 35516, Egypt

論文のURL

論文の投稿日時

2023/11/11

論文の概要

本論文では、ゲームにおけるNPCの動きをよりスムーズで人間らしいものにするための新しいアルゴリズムを提案しています。
従来のA*アルゴリズムを改良し、ヒープソートアルゴリズムとチェビシェフ距離を組み合わせた「Heap_Heuristic_A*」アルゴリズムを開発しました。
実験の結果、このアルゴリズムを使用することで、NPCの経路探索がよりスムーズで自然になり、計算時間も短縮されることが示されました。

提案アルゴリズム「Heap_Heuristic_A*」

Heap_Heuristic_A*アルゴリズムの概要

提案されたHeap_Heuristic_A*アルゴリズムは、従来のA*アルゴリズムを基に、以下の2つの主要な改良を加えたものです。

ヒープソートアルゴリズムの導入
チェビシェフ距離を用いたヒューリスティック関数の変更

これにより、NPCの動きが人間らしくなり、ゲームの没入感が向上します。

従来のA*アルゴリズム

グラフ上で最短経路を見つけるための代表的な探索アルゴリズムです。
大まかな流れは以下の通りです。

1. 開始ノードをオープンリストに追加します。
2. 以下を繰り返します。
   - オープンリストから最小f(n)を持つノードを選択します。
   - 選択したノードが目標ノードなら終了します。
   - そのノードをクローズドリストに移動します。
   - そのノードの各隣接ノードを処理します。：
      * クローズドリストに存在する隣接ノードは無視します。
      * 各隣接ノードのf、g、hを計算します。
      * 隣接ノードをオープンリストに追加（既に存在する場合は更新（fコストがより小さい場合））します。
3. オープンリストが空になるか目標に到達するまで続けます。

オープンリスト

探索アルゴリズムがまだ評価を終えていないノードを保持しておくためのリストです。
オープンリストには、通常、以下の情報が格納されます。

ノード自身: 探索対象のノード
gコスト: スタート地点からそのノードまでのコスト
hコスト: そのノードからゴール地点までの推定コスト (ヒューリスティック関数によって計算)
fコスト: gコストとhコストの合計 (f = g + h)

クローズドリスト

評価済みのノードを保持するリストであり、このリスト内のノードは探索対象になりません。

ヒープソートアルゴリズム

ヒープソートアルゴリズムとは、以下のような特徴を持つ効率的なソートアルゴリズムです。

ヒープデータ構造を利用してソートを行います。
- ヒープデータ構造とは、完全二分木で、最小ヒープ、もしくは最大ヒープの条件を持つ木構造です。
  - 完全二分木とは最下層以外のノードがすべて埋まっており、最下層は左から右へ詰めて配置される木構造です。
  - 最小ヒープとは、各ノードの値がその全ての子ノードの値以下である完全二分木です。最大ヒープはその逆で、全ての子ノードの値以上であるものです。
O(n log n) の時間計算量を持ちます。
比較回数が少なく、メモリ効率が良いため、大規模なデータのソートに適しています。

従来のA*アルゴリズムのオープンリストの管理にヒープソートを利用すると、最小コストのノードを素早く取り出すことができ、アルゴリズムの効率が向上します。

チェビシェフ距離を用いたヒューリスティック関数の変更

チェビシェフ距離とは2点間の距離を計算する方法の1つで、

$$
チェビシェフ距離 = max(|x₁ - x₂|, |y₁ - y₂|)
$$

で与えられます。
8方向（上下左右および斜め）の移動を全て同じコストとして考えるのが特徴です。

ヒューリスティック関数とは、探索アルゴリズムにおいて、現在の状態から目標状態までの推定コストを計算する関数です。
従来のA*アルゴリズムでは、ヒューリスティック関数として、主にマンハッタン距離やユークリッド距離が利用されていましたが、提案手法であるHeap Heuristic A*アルゴリズムでは、チェビシェフ距離を採用しています。

マンハッタン距離とユークリッド距離は以下の計算式で求められます。

$$
マンハッタン距離 = |x_1 - x_2| + |y_1 - y_2|
$$

$$
ユークリッド距離 = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}
$$

Heap Heuristic A*の詳細

上図は、論文に掲載されているHeap Heuristic A*アルゴリズムの詳細な手順です。

`Ol = HeapSort (Ol)`
オープンリスト `Ol` をヒープソートしています。
`Ol` 内のノードがf値の昇順にソートされ、最も評価値の低いノードがリストの先頭に配置されます。
`Current := Ol [0]`
ヒープソートされたオープンリスト `Ol` の先頭の最も評価値の低いノードを `Current` ノードとして取り出します。

オープンリストのヒープソートは上記の部分で行なっていると思いますが、残念ながら、それ以外の一部の処理（ヒューリスティックスの計算処理など）については、本記事著者には理解できませんでした。
そのため、上記のアルゴリズムを、本記事著者でも理解しやすいように、LLM（Gemini）に修正してもらいました。
以下に修正版アルゴリズムを記載します。

Geminiによる修正版Heap Heuristic A*アルゴリズム

1.	Input:
2.	    G: Grid Map (グリッドマップ)
3.	    S: Start node (スタートノード)
4.	    T: Target node (ターゲットノード)
5.	
6.	Output:
7.	    Ps: The shortest path from Start to Target (スタートからターゲットまでの最短パス)
8.	    OpenList: Open List (優先度付きキュー、最小ヒープ)
9.	    ClosedList: Closed List (評価済みノード集合)
10.	
11.	Procedure:
12.	    Initialize:
13.	    OpenList := PriorityQueue()  // 最小ヒープとして実装された優先度付きキュー
14.	    ClosedList := Set()          // 空の集合として初期化
15.	    gScore := map with default value of Infinity // g値を格納するマップ、初期値は無限大
16.	    fScore := map with default value of Infinity // f値を格納するマップ、初期値は無限大
17.	    parentMap := map of nodes to nodes // 親ノードを格納するマップ
18.	
19.	    gScore[Start] := 0
20.	    fScore[Start] := Heuristic_Chebyshev(Start, Target) // f値 = g値 + h値、初期h値はチェビシェフ距離
21.	    OpenList.insert(Start, fScore[Start]) // オープンリストにスタートノードとf値を挿入
22.	
23.	    While OpenList is not empty:
24.	        Current := OpenList.extract_min() // オープンリストから最小f値のノードを取り出す (ヒープの最小値取り出し)
25.	
26.	        If Current == Target:
27.	            Return Reconstruct_Path(parentMap, Target) // パスを再構築して返す (従来のA*のパス再構築)
28.	
29.	        ClosedList.add(Current) // Currentノードをクローズドリストに追加
30.	
31.	        For each neighbor of Current:
32.	            If neighbor in ClosedList:
33.	                Continue // 評価済みノードはスキップ
34.	
35.	            If not IsTraversable(neighbor): // 移動不可能なノードはスキップ
36.	                Continue
37.	
38.	            tentative_gScore := gScore[Current] + Get_Movement_Cost(Current, neighbor) // 標準的なg値計算
39.	
40.	            If tentative_gScore < gScore[neighbor]: // より良いパスが見つかった場合
41.	                parentMap[neighbor] := Current      // 親ノードを更新
42.	                gScore[neighbor] := tentative_gScore // g値を更新
43.	                fScore[neighbor] := tentative_gScore + Heuristic_Chebyshev(neighbor, Target) // f値を再計算
44.	
45.	                If neighbor in OpenList: // オープンリストにneighborが既に含まれている場合
46.	                    OpenList.update_priority(neighbor, fScore[neighbor]) // オープンリスト内で優先度を更新 (ヒープの再調整)
47.	                Else: // オープンリストにneighborが含まれていない場合
48.	                    OpenList.insert(neighbor, fScore[neighbor]) // オープンリストに追加 (ヒープに挿入)
49.	
50.	        Return failure // オープンリストが空になった場合、パスが見つからなかった
51.	
52.	Function Heuristic_Chebyshev(nodeA, nodeB): // ヒューリスティック関数: チェビシェフ距離
53.	    dx := abs(nodeA.x - nodeB.x)
54.	    dy := abs(nodeA.y - nodeB.y)
55.	    Return max(dx, dy)
56.	
57.	Function Get_Movement_Cost(nodeA, nodeB): // 移動コスト取得関数
58.	    If IsDiagonalNeighbor(nodeA, nodeB):
59.	        Return SQRT2 // 対角線移動コスト (√2)
60.	    Else:
61.	        Return 1    // 水平/垂直移動コスト (1)
62.	
63.	Function IsDiagonalNeighbor(nodeA, nodeB): // 対角線隣接判定関数 (実装は省略)
64.	    // ... (nodeAとnodeBが対角線方向に隣接しているか判定するロジック) ...
65.	
66.	Function IsTraversable(node): // トラバース可能判定関数 (実装は省略)
67.	    // ... (nodeがグリッドマップ内で移動可能かどうか判定するロジック、例: 範囲内、障害物がないか) ...
68.	
69.	Function Reconstruct_Path(parentMap, targetNode): // パス再構築関数
70.	    path := []
71.	    currentNode := targetNode
72.	    While currentNode is in parentMap:
73.	        path.append(currentNode)
74.	        currentNode := parentMap[currentNode]
75.	    path.reverse() // パスを反転してスタートからゴール順にする
76.	    Return path
77.	
78.	Class PriorityQueue: // 優先度付きキュー (最小ヒープ) クラス (簡易的な例)
79.	    Constructor():
80.	        this.heap = [] // ヒープを配列で表現
81.	        this.node_positions = {} // ノードの位置を追跡するマップ (update_priority用)
82.	
83.	    insert(node, priority):
84.	        this.heap.push({node: node, priority: priority}) // ノードと優先度をヒープに追加
85.	        this.node_positions[node] = this.heap.length - 1 // ノードの位置を記録
86.	        this._heapify_up(this.heap.length - 1) // 挿入したノードを浮き上がらせる
87.	
88.	    extract_min():
89.	        if this.isEmpty():
90.	            return null
91.	        if this.heap.length === 1:
92.	            const min_item = this.heap.pop();
93.	            delete this.node_positions[min_item.node];
94.	            return min_item.node;
95.	
96.	        const min_item = this.heap[0];
97.	        delete this.node_positions[min_item.node];
98.	        this.heap[0] = this.heap.pop(); // 末尾要素をルートに移動
99.	        this._heapify_down(0) // ルートノードを沈下させる
100.	        return min_item.node;
101.	
102.	    update_priority(node, new_priority):
103.	        if !(node in this.node_positions):
104.	            return; // ノードがヒープに存在しない場合は何もしない
105.	
106.	        const index = this.node_positions[node];
107.	        this.heap[index].priority = new_priority; // 優先度を更新
108.	
109.	        // 優先度が下がった場合 (f値が小さくなった場合) は浮き上がらせる
110.	        if (index > 0 && this.heap[index].priority < this.heap[Math.floor((index - 1) / 2)].priority) {
111.	            this._heapify_up(index);
112.	        } else { // 優先度が上がった場合 (f値が大きくなった場合) は沈下させる (沈下は必須ではない場合もあるが、安全のため実装)
113.	            this._heapify_down(index);
114.	        }
115.	
116.	
117.	    isEmpty():
118.	        return this.heap.length === 0
119.	
120.	    _heapify_up(index): // 浮き上がらせ操作
121.	        while (index > 0) {
122.	            const parentIndex = Math.floor((index - 1) / 2);
123.	            if (this.heap[index].priority >= this.heap[parentIndex].priority) {
124.	                break; // 親ノード以上の優先度なら終了
125.	            }
126.	            this._swap(index, parentIndex);
127.	            index = parentIndex;
128.	        }
129.	
130.	    _heapify_down(index): // 沈下操作
131.	        while (true) {
132.	            let smallestChildIndex = index;
133.	            const leftChildIndex = 2 * index + 1;
134.	            const rightChildIndex = 2 * index + 2;
135.	
136.	            if (leftChildIndex < this.heap.length && this.heap[leftChildIndex].priority < this.heap[smallestChildIndex].priority) {
137.	                smallestChildIndex = leftChildIndex;
138.	            }
139.	            if (rightChildIndex < this.heap.length && this.heap[rightChildIndex].priority < this.heap[smallestChildIndex].priority) {
140.	                smallestChildIndex = rightChildIndex;
141.	            }
142.	            if (smallestChildIndex === index) {
143.	                break; // 自身が最小の子ノードなら終了
144.	            }
145.	            this._swap(index, smallestChildIndex);
146.	            index = smallestChildIndex;
147.	        }
148.	
149.	    _swap(index1, index2):
150.	        [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]]; // 要素を交換
151.	        this.node_positions[this.heap[index1].node] = index1; // 位置情報を更新
152.	        this.node_positions[this.heap[index2].node] = index2;.

24. Current := OpenList.extract_min() // オープンリストから最小f値のノードを取り出す (ヒープの最小値取り出し)
最小ヒープのOpenListから最小のf値のノードを取り出します。
取り出し後、OpenListはヒープ条件を満たすように再構築されます。

20. fScore[Start] := Heuristic_Chebyshev(Start, Target) // f値 = g値 + h値、初期h値はチェビシェフ距離
43. fScore[neighbor] := tentative_gScore + Heuristic_Chebyshev(neighbor, Target) // f値を再計算
Chebyshev距離を利用したh値を計算し、g値に加えることでスタートもしくは隣接ノードのf値を計算します。

46. OpenList.update_priority(neighbor, fScore[neighbor]) // オープンリスト内で優先度を更新 (ヒープの再調整)
オープンリスト内の既存の隣接ノード（neighbor）のf値（優先度）をより小さい値に更新します。
更新後、OpenListはヒープ条件を満たすように再構築されます。

21. OpenList.insert(Start, fScore[Start]) // オープンリストにスタートノードとf値を挿入
48. OpenList.insert(neighbor, fScore[neighbor]) // オープンリストに追加 (ヒープに挿入)
この部分で、スタートもしくは隣接ノードをOpenListに挿入します。
挿入後、OpenListはヒープ条件を満たすように再構築されます。

実験結果

パスの形状の比較

図8〜11は、異なるグリッドサイズにおいて、4種類のアルゴリズムが生成したパスを比較したものです。
4種類のアルゴリズムとは、Native A*, A* with Heapsort, AMOD, Heap Heuristic A*アルゴリズムとなります。

Native A*は、従来の基本的なA*アルゴリズムです。
ヒューリスティック関数としてマンハッタン距離を使用し、OPENリストのソートにはヒープソートが使用されていません。

A* with Heapsortは、Native A*アルゴリズムのOPENリストのソートにヒープソートを使用したアルゴリズムだと思います。

A*MODは、Native A*アルゴリズムのヒューリスティック関数としてチェビシェフ距離を使用したアルゴリズムです。
詳細は関連URLの論文「A* pathfinding algorithm modification for a 3D engine」をご参照ください。

Heap Heuristic A*は提案アルゴリズムとなります。

Heap Heuristic A*アルゴリズムは、他のアルゴリズムと比較して、グリッドサイズが大きくなるにつれて、より曲線的で自然なパスを生成していることがわかります。
まるで、人間が迷いながら道を探しているような動きといえます。

訪問ノード数と計算時間の比較

表1, 図12は、異なるグリッドサイズにおける4つのアルゴリズムのパスの計算時間を表しています。
Heap Heuristic A*アルゴリズムは、ほぼすべてのグリッドサイズにおいて、最も短い計算時間を達成しました。

表2, 図13は、異なるグリッドサイズにおける4つのアルゴリズムの訪問ノード数を表しています。
Heap Heuristic A*アルゴリズムは、他のアルゴリズムと比較して、訪問ノード数が多くなる傾向がありました。
訪問ノード数が増加しても、計算時間は短縮されていることから、必ずしも訪問ノード数の増加は計算時間の増加に繋がらない、もしくは本アルゴリズムの効率化の効果が大きいため訪問ノード数が増加しても結果として計算時間の短縮に繋がったと言えるかもしれません。

所感

ヒープソートとチェビシェフ距離を導入することで、計算効率が向上し、グリッドサイズが増えるほどより自然なパスが生成できるようになるというのは素晴らしい研究結果だと思います。
余力があれば、Heap Heuristic A*アルゴリズムをゲーム内で試してみたいと思います。

使用AI技術

Claude 3.5 Sonnet

本記事の文章生成に使用しました。

gemini-2.0-flash-thinking-exp-01-21

本記事の文章生成に使用しました。
「Geminiによる修正版Heap Heuristic A*アルゴリズム」の作成に使用しました。

使用画像

全て本論文に掲載されている画像となります。