Godot3 で作る 2D グリッドベース経路探索

extends TileMap

# Player の移動するパスの点を格納する配列
var path: Array = []
# Board(TileMap)でタイルが配置されているセルの配列
var cells = get_used_cells()

# Obstacles ノードの参照
onready var obstacles = $Obstacles
# AStar2D クラスのインスタンス
onready var astar = AStar2D.new()
# Board(TileMap) のセルの半分のサイズ
onready var half_cell_size = cell_size / 2


func _ready():
    # AStar の点を追加するメソッドを呼び出す
	add_points()
    # AStar の点をつなぐメソッドを呼び出す
	connect_points()
    # AStar の点を無効化するメソッドを呼び出す
    # 引数は Obstaclesノードの子ノードの位置を配列で返すメソッド
	disable_points(get_obstacles())


# AStar の点を追加するメソッド
func add_points():
    # タイルマップ上のタイルが配置されたセルでループ処理
	for cell in cells:
        # セルのIDを生成して AStar の点として追加する
		astar.add_point(id(cell), cell)


# AStar の点をつなぐメソッド
func connect_points():
    # タイルマップ上のタイルが配置されたセルでループ処理
	for cell in cells:
        # そのセルが AStar の点に含まれていたら
		if astar.has_point(id(cell)):
            # 隣り合う四方向の方向ベクトルを配列にする
			var neighbors = [
				Vector2.RIGHT,
				Vector2.LEFT,
				Vector2.DOWN,
				Vector2.UP
			]
            # それぞれの方向ベクトルに対してループ処理
			for neighbor in neighbors:
                # 隣接するセルを定義
				var next_cell = cell + neighbor
                # 隣接するセルにタイルが配置されている場合
				if cells.has(next_cell):
                    # AStar のもとのセル上の点と隣接するセル上の点をつなぐ
					astar.connect_points(id(cell), id(next_cell), false)


# Obstaclesノードの子ノードの位置を配列で返すメソッド
func get_obstacles() -> Array:
    # 障害物が配置されているセルのグリッド座標を入れる配列
	var obstacle_cells = []
    # Obstacles の全ての子ノード（Obstacle インスタンス）でループ処理
	for child in obstacles.get_children():
        # 用意した配列に障害物のグリッド座標を追加する
		obstacle_cells.append(world_to_map(child.global_position))
    # 戻り値として配列を返す
	return obstacle_cells


# AStar の点を無効化するメソッド
# 引数にはセルのグリッド座標を要素にもつ配列を渡す
func disable_points(target_cells):
    # 引数の配列の要素（セルのグリッド座標）でループ処理
	for cell in target_cells:
        # 該当のセルに相当する AStar の点を無効化する
		astar.set_point_disabled(id(cell))


# Player が移動する最短経路（通過する点の配列）を更新するメソッド
func update_path(start, end):
    # AStar で引数の出発地点から目的地点までの最短経路を探索する
	path = astar.get_point_path(id(start), id(end))


# グリッド座標からIDを生成するメソッド
func id(point):
	var a = point.x
	var b = point.y
	return (a + b) * (a + b + 1) / 2 + b

extends Control


onready var board: TileMap = get_parent().get_node("Board")
onready var astar: AStar2D = board.astar
onready var offset: Vector2 = board.half_cell_size


# シーンツリーにノードが読み込まれたら _draw() 関数を呼び出す
func _ready():
	_draw()

# スクリーンにAStar の点と線を描画するよう組み込み関数 _draw()を上書き
func _draw():
    # AStar の全ての点（ID）でループ処理
	for point in astar.get_points():
        # 点が無効化されていたらこの後の処理をスキップ
		if astar.is_point_disabled(point):
			print("astar point is disabled")
			continue
		
        # AStar の点（ID）からグリッド座標に変換
		var cell = astar.get_point_position(point)
        # グリッド座標からワールド座標に変換
		var pos = board.map_to_world(cell)
        # AStar の点のワールド座標をセルの左上角から中央にズラして描画する
		draw_circle(pos + offset, 4, Color.white)
		
        # 取得した AStar の点につながっている上下左右の点(ID)を全て取得
		var point_connections = astar.get_point_connections(point)
        # つながっている全ての点をワールド座標として格納するための配列
		var connected_positions = []
		
        # つながっている点でループ処理
		for connected_point in point_connections:
            # もしつながっている点が無効化されている場合はこの後の処理をスキップ
			if astar.is_point_disabled(connected_point):
				print("connected point is disabled")
				continue
            # つながっている点のIDをグリッド座標に変換
			var connected_cell = astar.get_point_position(connected_point)
			# グリッド座標からワールド座標に変換
            var connected_pos = board.map_to_world(connected_cell)
            # ワールド座標を配列に追加
			connected_positions.append(connected_pos)
		
        # つながっている点のワールド座標の配列の要素でループ処理
		for connected_pos in connected_positions:
            # 元の点とそれに接続している点をつなぐ線を描画する
			draw_line(pos + offset, connected_pos + offset, Color.white, 2)

extends Node2D

# Board ノードの参照
onready var board = $Board
# Line ノードの参照
onready var line = $Line
# Player ノードの参照
onready var player = $Player


func _input(event):
    # マウスの左ボタンがクリックされたら
	if event.is_action_pressed("move_to"):
        # マウスカーソルのグローバルな x, y 座標からタイルマップ上のセルの座標を目的地として取得
		var target_cell = board.world_to_map(get_global_mouse_position())
        # 目的地のセルの座標から AStar 用の ID を生成
		var target_cell_id = board.id(target_cell)
        # ID が AStar の有効な点に含まれている場合
		if board.astar.has_point(target_cell_id):
            # Player のゲーム画面上の x, y 座標からタイルマップ上のセルの座標を取得
			var player_cell = board.world_to_map(player.global_position)
            # Player のセルから目的地のセルの経路を更新する
			board.update_path(player_cell, target_cell)
            # Player ノードを移動させるメソッドを呼び出す
			move()


# プレイヤーの駒を移動させるメソッド
func move():
    # 移動中はクリック操作ができないようにインプットプロセスを無効にする
	set_process_input(false)
    # 経路を構成する点のセル座標でループ処理して Line ノードのパスを描画
	for point in board.path:
        # 点のゲーム画面上の x, y 座標を Line ノードのパスに追加
		line.add_point(board.map_to_world(point) + board.half_cell_size)
	# 経路を構成する点のセル座標でループ処理して Player ノードを移動
	for point in board.path:
        # 点のゲーム画面上の x, y 座標を Player ノードの位置として上書きする
		player.global_position = board.map_to_world(point)
        # 0.1秒待機
		yield(get_tree().create_timer(0.1), "timeout")
	# 移動が完了したら Line ノードのパスの点を消去
	line.clear_points()
    # インプットプロセスを有効にする
	set_process_input(true)