このチュートリアルでは 2D ゲームにおける経路探索 (Path Finding) について紹介する。経路探索というのは、例えばあるオブジェクトをある目的地へ移動させる際に、オブジェクトから目的地までの移動可能な最短経路を割り出す機能だ。なお、AStar というアルゴリズムを利用したグリッドベースの経路探索については「Godot で作る 2D グリッドベース経路探索 」の記事で紹介している。
Godot 3.4 までは経路探索の実装に Navigation ノードを利用していた。特に不便ということもなかったが、これを使ったゲーム開発の方法論が限定的で、応用が効かない部分があったようだ。今回紹介するのは Godot 3.5 から追加された Navigation Server を使用した実装方法だ。これは現在開発が盛んに進められている Godot 4 からのバックポート（新しいバージョンから古いバージョンへの移植）だ。本記事は 3.5 以降を使用されている方を対象としている。もし Godot のバージョンが 3.4 以前の環境では非対応の内容を含むためご注意いただきたい。
このチュートリアルで最後にできあがるプロジェクトのファイルはGitHubリポジトリ に置いている。.zipファイルをダウンロードしていただき、「End」フォルダ内の「project.godot」ファイルを Godot Engine でインポートしていただければ、直接プロジェクトを確認していただくことも可能だ。
Environment
Godot のバージョン: 3.5
コンピュータのOS: macOS 11.6.5
Basic Articles
以下の記事もお役立てください。
Godot をダウンロードする
Godot のプロジェクトマネージャー
Godot の言語設定
準備
新規プロジェクトを作成する
それでは Godot Engine を立ち上げて、新規プロジェクトを作成しよう。プロジェクトの名前はあなたのお好みで決めていただいてOKだ。もし思いつかなければ「2D Path Finding Start」としておこう。
プロジェクト設定を更新する
エディタが表示されたら、プロジェクト全体に関わる設定を更新しておく。
まずはゲームのディスプレイサイズを設定する。
- 「プロジェクト」メニュー＞「プロジェクト設定」を開く。
- 「一般」タブのサイドバーから「Display」＞「Window」を選択する。
- 「Size」セクションで以下の項目の値を変更する。
- Width: 512
- Height: 320
- Test Width: 768
- Test Height: 480
- 「Stretch」セクションで以下の項目の値を変更する。
- Mode: 2d
- Aspect: keep
- 「インプットマップ」タブに切り替え、アクションに「move_to」を追加する。
- 「move_to」の操作に「マウス左ボタン」を割り当てる。
アセットをダウンロードしてインポートする
次に、KENNEYのサイトからアセットをダウンロードして利用させてもらおう。今回利用するのは 1-Bit Pack というアセットパックだ。この素晴らしすぎる無料の素材に感謝せずにはいられない。
ダウンロードしたら「Tilesheet」フォルダ内の「colored-transparent_packed.png」ファイルをエディタのファイルシステムドックへドラッグ&ドロップしてプロジェクトにインポートする。
ファイルをインポートした直後は画像がぼやけた感じになっているので、これを以下の手順で修正しておく。
- ファイルシステムドックでインポートしたアセットファイルを選択した状態にする。
- インポートドックで「プリセット」＞「2D Pixel」を選択する。
- 一番下にある「再インポート」ボタンをクリックする。
これでピクセルアート特有のエッジの効いた画像になったはずだ。インポートしたタイルセットは、後ほどタイルマップやプレイヤーキャラクターのテクスチャに利用する。
World シーンを作る
World シーンを新規作成する
まず最初にゲームの世界を用意するために「World」シーンを作成する。
- 「シーン」メニュー＞「新規シーン」を選択する。
- 「ルートノードを生成」にて「その他のノード」を選択する。
- 「Node2D」クラスのルートノードが生成されたら、その名前を「World」に変更する。
- シーンを保存する。フォルダを作成して、ファイルパスを「res://Scene/World.tscn」としてシーンを保存する。
World シーンに TileMap ノードを追加して編集する
「World」ルートノードに「TileMap」ノードを追加する。
インスペクターにて、「TileMap」ノードの「TileSet」プロパティに「新規 TileSet」リソースを適用する。
適用した「TileSet」リソースをクリックして、エディタ下部のタイルセットパネルを開く。
タイルセットパネルの左サイドバーに、先にインポートしておいた KENNEYの「res://colored-transparent_packed.png」リソースファイルをドラッグして追加する。
追加したテクスチャシートを選択し、以下の３つのシングルタイルを用意する。
- キャラクターが通る通路用のタイル
*このナビゲーション領域が設定されているタイルが経路探索の対象となる。- 砂利のタイルを使用
- コリジョンポリゴン: 不要
- ナビゲーションポリゴン: 必要
- キャラクターは通らないが衝突もしないタイル
*経路探索してキャラクターが移動する際、コリジョン形状を持つ木のタイルに引っかからないようにマージンとして使用する。- 草のテクスチャを使用
- コリジョンポリゴン: 不要
- ナビゲーションポリゴン: 不要
- キャラクターは通らないし衝突判定ありのタイル
*経路探索時に通過不可の障害物として使用する。- 木のテクスチャを使用
- コリジョンポリゴン: 必要
- ナビゲーションポリゴン: 不要
- キャラクターが通る通路用のタイル
シーンドックで「TileMap」を選択し、2D ワークスペース上でタイルマップを作成する。以下はサンプルだ。砂利のタイルで通り道（ナビゲーション領域）がある程度確保できていればOKだ。
ただし、ここで注意すべきなのは、障害物用の木のタイルを置いたら、その周りに必ずマージン用の草のタイルを配置することだ。そうしないと、キャラクターが経路探索して移動するときに木のタイルギリギリをを通ろうとしてしまい、引っかかって移動できなくなってしまうのだ。これは今後改善してほしいポイントでもある。まだキャラクターの実装をしていないが、先にどういう挙動になるかをお見せしておく。
World シーンに Line2D ノードを追加して編集する
「Line2D」ノードは探索して確定した経路を視覚的にわかりやすくするために使用する。
- 「World」ルートノードに「Line2D」ノードを追加する。
- インスペクターで「Line2D」ノードの「Width」プロパティを 1 にする。
Player シーンを作る
ここからは探索した経路上を移動させるプレイヤーキャラクターのシーンを作成する。
Player シーンを新規作成する
- 「シーン」メニュー＞「新規シーン」を選択する。
- 「ルートノードを生成」にて「その他のノード」を選択する。
- 「KinematicBody2D」クラスのルートノードが生成されたら、その名前を「Player」に変更する。
- シーンを保存する。フォルダを作成して、ファイルパスを「res://Scenes/Player.tscn」としてシーンを保存する。
Player シーンにノードを追加して編集する
「Player」ルートノードにノードを追加して、シーンツリーを以下のようにする。
- Player(KinematicBody2D)
- Sprite
- CollisionShape2D
- NavigationAgent2D
続いて各ノードを編集していく。
Sprite ノード
このノードで「Player」シーンにテクスチャ（見た目）を施す。
- インスペクターにて「Texture」プロパティに KENNEY のサイトからダウンロードした「res://colored-transparent_packed.png」リソースを適用する。
- 「Region」＞「Enabled」プロパティにチェックを入れて有効にする。
- エディタ下部のテクスチャ領域パネルを開き、好みのプレイヤーキャラクターのテクスチャの領域を選択する。このチュートリアルでは保安官っぽいテクスチャを採用した。
CollisionShape2D ノード
このノードで KinematicBody2D クラスである「Player」ルートノードのコリジョン形状を設定する。
- インスペクターにて「Shape」プロパティに「新規 RectangleShape2D」リソースを適用する。
- さらに適用した「RectanbleShape2D」リソースの「Extents」プロパティの値を (x: 6, y: 6) にする。
- 2Dワークスペース上では以下のようになる。
NavigationAgent2D ノード
このノードは Godot 4 からバックポートされる形で Godot 3.5 で導入されたノードだ。このノードを子に追加している親ノード（今回の場合は「Player」ノード）は、自動的に障害物との衝突を回避し、経路探索による移動が可能になる。デフォルトの World2D の navigation map に登録されて制御される仕組みのようだ。
Godot Docs:
NavigationAgent2D
- 「Avoidance」＞「Avoidance Enabled」プロパティにチェックを入れて有効にする。これにより、障害物との衝突回避が制御され、経路探索が可能になる。
- 「Avoidance」＞「Radius」プロパティを 8 にする。このプロパティはこのエージェントのサイズだ。「Sprite」ノードのテクスチャのサイズに合わせて、半径 8 px とした。
- 「Avoidance」＞「Neighbor Dist」プロパティも 8 にする。このプロパティは、他のエージェントを検知する距離を設定する。あとでこの「Player」を自動的に追跡する他のオブジェクトシーンを作成し、それらにも NavigationAgent2D ノードを追加することになるが、それらのエージェントが「Player」のすぐ隣に来るまでは検知する必要はないので、エージェントのサイズと同様に 8 とした。
- 「Avoidance」＞「Max Speed」プロパティを 40 にする。これはエージェントの最大移動速度だ。
World シーンに Player シーンのインスタンスを追加する
ここで作成した「Player.tscn」シーンのインスタンスノードを「World」シーンに追加する。「World」シーンのシーンドックが以下のようになればOKだ。
Player ノードにスクリプトをアタッチして編集する
「Player」シーンに戻ったら、「Player」ルートノードにスクリプトをアタッチしてコードを記述していく。ファイルパスを「res://Scripts/Player.gd」としてスクリプトを作成しよう。スクリプトエディタが開いたら以下のコードを記述する。
###Player.gd###
extends KinematicBody2D
# Player のスピード
export (float) var speed = 40
# WorldシーンのLine2Dノードを参照
onready var line: Line2D = get_node("../Line2D")
# NavigationAgent2Dノードを参照
onready var nav_agent = $NavigationAgent2D
# ノードがシーンツリーに読み込まれたら呼ばれる組み込み関数
func _ready():
# NavigationAgent2Dにより現在の位置を暫定の目的地としてセット
nav_agent.set_target_location(global_position)
# 毎フレーム呼ばれる組み込みの物理プロセス関数
func _physics_process(delta):
# もし探索した経路の最後の位置に到達していなければ
if not nav_agent.is_navigation_finished():
# 次の障害物のない移動可能な位置を取得
var next_loc = nav_agent.get_next_location()
# 現在のPlayerの位置を取得
var current_pos = global_position
# 次の移動可能な位置に対する方向とスピードから速度を計算
var velocity = current_pos.direction_to(next_loc) * speed
# NavigationAgent2Dの衝突回避アルゴリズムに速度を渡す
# 速度調整が完了次第velocity_computedシグナルを発信する
nav_agent.set_velocity(velocity)
# インプットマップアクションmove_to（マウス左ボタン）を押したら
if Input.is_action_pressed("move_to"):
# 経路探索を開始するメソッドを呼ぶ
find_path() # このあと定義
# 経路探索を開始するメソッド
func find_path():
# NavigationAgent2Dにより現在のマウスの位置を次の目的地としてセット
nav_agent.set_target_location(get_global_mouse_position())
# 次の障害物のない移動可能な位置を取得
nav_agent.get_next_location()
# WorldシーンのLine2DのパスにNavigationAgent2Dが生成した経路の情報を渡す
# どちらもデータ型がPoolVector2Arrayなのでそのまま渡すことができる
line.points = nav_agent.get_nav_path()
ここで「NavigationAgent2D」ノードのシグナルを3種類、このスクリプトに接続する。
上のスクリーンショットだと順番が下からになるが、まず一つ目は「velocity_computed」シグナルだ。このシグナルは「NavigationAgent2D」が周りのオブジェクトとの衝突回避のための速度調整を完了したタイミングで発信される。
二つ目は「target_reached」シグナルだ。このシグナルは最終目的地への経路上で次に移動可能な位置へ到達できたタイミングで発信される。
三つ目のシグナルは「navigation_finished」だ。これは経路上の最終目的地に到達したタイミングで発信される。
それぞれのシグナルをスクリプトに接続したら、生成されたメソッド内に必要なコードを記述していく。コードは以下のようになる。
###Player.gd###
# NavigationAgent2Dが速度調整を終えたら発信するシグナルで呼ばれる
func _on_NavigationAgent2D_velocity_computed(safe_velocity):
# 調整された速度をPlayerの移動に適用する
move_and_slide(safe_velocity)
# NavigationAgent2Dが次の移動可能な位置に到達した時に発信するシグナルで呼ばれる
func _on_NavigationAgent2D_target_reached():
# WorldシーンのLine2Dノードのパスに...
# NavigationAgent2Dの更新された経路を反映する
line.points = nav_agent.get_nav_path()
# NavigationAgent2Dが経路の最後の目的地に到達した時に発信するシグナルで呼ばれる
func _on_NavigationAgent2D_navigation_finished():
# WorldシーンのLine2Dノードのパスのポイントを0にリセットする
line.points.resize(0)
以上で「Player.gd」スクリプトの編集は完了だ。このタイミングで一度プロジェクトを実行してみる。初めてプロジェクトを実行する場合は、メインシーンに「res://Scenes/World.tscn」を選択する。
タイルマップ上を適当にクリックして、「Player」が問題なく経路探索して移動するかどうか確認してみよう。
Animal シーンを作る
「Player」シーンではマウスの位置を目的地とした経路探索を実装したが、ここからは、その移動する「Player」を目的地として移動する別オブジェクトの経路探索を実装する。とはいえ、ほとんどやることは同じなので心配は無用だ。
さきほど作成した「Player」のインスタンスオブジェクトに複数の動物のオブジェクトが集まってくるようにしてみよう。その動物のオブジェクトのために「Animal」シーンをこれから作成していく。
Animal シーンを新規作成する
- 「シーン」メニュー＞「新規シーン」を選択する。
- 「ルートノードを生成」にて「その他のノード」を選択する。
- 「KinematicBody2D」クラスのルートノードが生成されたら、その名前を「Animal」に変更する。
- シーンを保存する。フォルダを作成して、ファイルパスを「res://Scenes/Animal.tscn」としてシーンを保存する。
Animal シーンにノードを追加して編集する
「Animal」ルートノードにノードを追加して、シーンツリーを以下のようにする。
- Animal(KinematicBody2D)
- Sprite
- CollisionShape2D
- NavigationAgent2D
- PathTimer(Timer)
続いて各ノードを編集していく。
Sprite ノード
このノードで「Animal」シーンにテクスチャ（見た目）を施す。
- インスペクターにて「Texture」プロパティに KENNEY のサイトからダウンロードした「res://colored-transparent_packed.png」リソースを適用する。
- 「Region」＞「Enabled」プロパティにチェックを入れて有効にする。
- エディタ下部のテクスチャ領域パネルを開き、動物のテクスチャ6つ分の領域を選択する。
- 「Animation」＞「Hframes」プロパティの値を 6 にする。先に選択したテクスチャ領域が動物 6 種類分を含むので、1種類につき 1frameとなるように設定している。「Frame」プロパティでデフォルトのフレームを 0（1番目）としている。
CollisionShape2D ノード
このノードで KinematicBody2D クラスである「Animal」ルートノードのコリジョン形状を設定する。
- インスペクターにて「Shape」プロパティに「新規 RectangleShape2D」リソースを適用する。
- さらに適用した「RectanbleShape2D」リソースの「Extents」プロパティの値を (x: 8, y: 8) にする。
- 2Dワークスペース上では以下のようになる。
NavigationAgent2D ノード
「Animal」シーンでも「Player」シーンと同様に、このノードを使って、障害物との衝突を回避し、経路探索による移動を可能にする。
- 「Avoidance」＞「Avoidance Enabled」プロパティにチェックを入れて有効にする。
- 「Avoidance」＞「Radius」プロパティをはデフォルトの 10 のままとする。「Sprite」ノードのテクスチャのサイズより少し大きめにして、動物たちの間隔を少しだけ取るようにした。
- 「Avoidance」＞「Neighbor Dist」プロパティもデフォルトの 500 のままとする。ディスプレイサイズの横幅を 512 px にしているので、500 にしておけば、だいたいディスプレイの端から端まで他のエージェントを検知して衝突を回避できる。「Animal」シーンの複数のインスタンスが「Player」インスタンスの周りに群がることになるので、身動きが取れなくなるのを少しでも緩和するのが狙いだ。
PathTimer(Timer) ノード
このノードは移動する目的地（「Player」のインスタンスノード）の位置を定期的に更新するために使用する。
- 「Wait Time」プロパティはデフォルトの 1 のままにしておく。
- 「One Shot」プロパティもデフォルトのまま無効にしておく。これで 1 秒おきに繰り返しタイムアウトする。
- 「Autostart」プロパティのチェックを入れて有効にする。これでこのノードがシーンツリーに読み込まれた時点で自動的にタイマーがスタートする。
Animal ノードにスクリプトをアタッチして編集する
ここからは「Animal」ルートノードにスクリプトをアタッチして、コードを記述して「Animal」シーンを制御していく。ファイルパスを「res://Scripts/Animal.gd」としてスクリプトを作成する。スクリプトエディタが開いたら以下のようにコーディングする。
###Animal.gd###
extends KinematicBody2D
# Animalのスピード
var speed = 30
# 経路の目的地となるオブジェクトを代入するための変数
var target
# Spriteノードの参照
onready var sprite = $Sprite
# NavigationAgent2Dの参照
onready var nav_agent = $NavigationAgent2D
# 以下、Player.gdとほぼ同様
func _ready():
nav_agent.set_target_location(global_position)
func _physics_process(_delta):
if not nav_agent.is_navigation_finished():
var current_pos = global_position
var next_loc = nav_agent.get_next_location()
var velocity = current_pos.direction_to(next_loc) * speed
nav_agent.set_velocity(velocity)
# 目的地のオブジェクトのx座標の方がanimalノードのx座標より小さい場合は
# SpriteノードのTextureイメージを反転
sprite.flip_h = target.global_position.x < global_position.x
続いてシグナルを2つスクリプトに接続する必要がある。
まず一つ目は「Player」シーンの時と同様に、「NavigationAgent2D」ノードの「velocity_computed」シグナルを接続する。
接続したら、生成された_on_NavigationAgent2D_velocity_computedメソッド内にmove_and_slideメソッドを記述して「Animal」ノードの移動を制御する。
###Animal.gd###
# NavigationAgent2Dが速度調整を終えたら発信するシグナルで呼ばれる
func _on_NavigationAgent2D_velocity_computed(safe_velocity):
# 調整された速度をPlayerの移動に適用する
move_and_slide(safe_velocity)
次は「PathTimer」ノードの「timeout」シグナルをスクリプトに接続する。
接続したら、生成されたメソッド_on_PathTimer_timeout内で、目的地となるオブジェクト（ここでは「Player」）の位置を経路探索時の目的地にセットするよう「NavigationAgent2D」ノードのset_target_locationメソッドを記述する。これで、1秒ごとのタイムアウト時に、最新の「Player」インスタンスノードの位置を取得して、そこを目的地とした経路探索が行われる。
###Animal.gd###
func _on_PathTimer_timeout():
nav_agent.set_target_location(target.global_position)
以上で「Animal.gd」スクリプトは完成だ。
World シーンに Animals ノードを追加する
- 「World」シーンに「Animal」シーンのインスタンスを複数格納するための入れ物として Node2D クラスのノードを追加し、名前を「Animals」に変更する。「Animal」のインスタンスの追加はこのあとスクリプトで行うようにしていく。
World ノードにスクリプトをアタッチして編集する
「World」ルートノードにスクリプトをアタッチし、それを編集して、「Animal」のインスタンスを複数追加する。ファイルパスを「res://Scripts/World.gd」としてスクリプトを保存し、スクリプトエディタが開いたら、以下のようにコードを記述する。
###World.gd###
extends Node2D
# プリロードしたAnimalシーンファイルの参照
const animal_scn = preload("res://Scenes/Animal.tscn")
# Animalインスタンスの数
export (int) var head_count = 12
# TileMapノードの参照
onready var tile_map = $TileMap
# Playerノードの参照
onready var player = $Player
# Animals(Node2D)ノードの参照
onready var animals = $Animals
func _ready():
# 乱数生成関数のためにランダマイズ
randomize()
# TileMap上のID9のタイルを配列で取得
var cells = tile_map.get_used_cells_by_id(9)
# Animalのインスタンスの数だけループ
for i in head_count :
# ID9のタイルの数の範囲内でランダム値を生成
var random_index = randi() % cells.size()
# ID9のタイルからランダム値に当てはまるタイルを取得
var spawn_tile = cells.pop_at(random_index)
# もしそのタイルが配列からすでに取り出し済みかつまだ配列が空でなければ
while spawn_tile == null and not cells.empty():
# 再度ID9のライルの数の範囲内でランダム値を生成
random_index = randi() % cells.size()
# 再度ID9のタイルからランダム値に当てはまるタイルを取得
spawn_tile = cells.pop_at(random_index)
# Animalインスタンスを生成するメソッドを呼び出し...
# 取得したタイル上にAnimalインスタンスを置く
spawn_animal(spawn_tile)
# Animalインスタンスを生成するメソッド
func spawn_animal(spawn_tile):
# 引数で渡されたタイルのx,y座標に(8, 8)ずらした位置を取得
var spawn_pos = tile_map.map_to_world(spawn_tile, true) + Vector2(8, 8)
# Animalシーンのインスタンスを生成
var animal = animal_scn.instance()
# Animalインスタンスの位置を引数で渡されたタイル上に配置
animal.position = spawn_pos
# Animalインスタンスの目的地用プロパティにPlayerノードを代入して参照
animal.target = player.global_position
# AnimalインスタンスのSpriteノードのテクスチャをランダムに決定
animal.get_node("Sprite").frame = randi() % animal.get_node("Sprite").hframes
# AnimalインスタンスをAnimalsノードの子にする
animals.add_child(animal)
これで「World.gd」スクリプトは完成だ。プロジェクトを実行して、複数の「Animal」インスタンスが「Player」に近寄ってくる様を見てみよう。
スクリプト内で定義したhead_countプロパティの数は、exportキーワード付きなのでインスペクターで簡単に編集できる。試しに「Animal」を100匹に増やしてみたが、最後は身動きが取れなくなった。「Animal」がゾンビだったらまさに地獄だ。
サンプルゲーム
今回のチュートリアルで作成したプロジェクトをさらにブラッシュアップしたサンプルゲームを用意した。
サンプルゲームのプロジェクトファイルは、GitHubリポジトリ
に置いているので、そこから .zip ファイルをダウンロードしていただき、「Sample」フォルダ内の「project.godot」ファイルを Godot Engine でインポートすれば確認していただけるはずだ。
ゲームのルール
- マウス左クリックで、マウスカーソルの位置に移動
- スペースキーでマウスカーソルの方向へ銃を撃つ
- 弾丸は最大12発。尽きるとリロードモーションの後また12発充填される。
- 敵（虫）に一定距離まで近づくと攻撃してくる
- 敵に当たるとハートが一つ減る
- ハートがなくなるとゲームオーバー
- 敵は色が濃いほどライフが多くスピードは遅い、色が薄いほどライフが少なくスピードが早い
- 敵を倒すと落ちるジュエルを拾った数がプレイヤーのスコア
おわりに
今回のチュートリアルでは Godot 3.5 で追加された新しい Navigation Server による経路探索を実装した。2Dの場合、痒いところに手が届かない印象は若干あるが、まだまだこれから改善されていくことを期待したい。今回のプロジェクトにおけるポイントを最後にまとめておこう。
- TileMap を使用する場合は移動可能なタイルに必ずナビゲーションを設定する。
- TileMap を使用する場合は、角に引っかからないように領域のみ設定したタイルでマージンを作る。
- 今回は使用しなかったが NavigationPolygonInstance ノードを使ってナビゲーション領域を定義しても良い。
- 移動したいオブジェクトの子に「NavigationAgent2D」ノードを追加する
- スクリプトで経路探索を制御する際、最終目的地のセット、次に移動可能な位置の取得、衝突回避のために速度を調整、調整した速度で移動、の順番を意識してコードを記述する。
参考
- Official Article - Navigation Server for Godot 4.0
- Official Article - Godot 3.5: Can't stop won't stop
- Godot Doc - NavigationAgent2D
- YouTube - Godot 3.5 | NavigationAgent2D
- YouTube - Godot 3.5 is Out, and it's SICK! Real-time pathfinding, new tween animations, and more
- GitHub - godotengine/godot - issue #60546
UPDATE
2022/09/19 2D グリッドベース経路探索の記事へのリンクを追加