Godotを使ってBITMAP衝突判定(Scratch3風)

始めに

以前の記事 Godotを使ってScratch3風にコードを書きたい(悲) にて、GodotでもScratch3っぽく試行したと書きましたが、Bitmap衝突判定について、もう少し踏み込んでみます。

Bitmap衝突判定とは

２つのスプライトの画像のうち、見えている（不透明な部分）ピクセルのうち、どこかで重なる部分があるときに「衝突」と判定する方法です。これはScratch3にて採用している衝突判定です。

【図-01: 衝突していない例】

【図-02: 衝突している例】

メリット

見た目どおりに衝突判定が行われるので、「わかりやすい」です。

デメリット

見えているピクセルが相手スプライトの見えているピクセルと同じ位置にあるか否かを調べる必要があり、スプライトの画像ピクセルの走査をする必要があります。そのため他の衝突判定の手法に比べて処理速度が遅くなる傾向にあります。

今回の記事の狙い

• Godot4にてBitmap衝突判定が可能であることを示すこと
• Bitmap衝突判定の処理速度を速くするための手法を紹介すること

Bitmap衝突判定( Godot4 )の事例

Bitmap衝突判定を実装した事例（動画）を紹介します。

• Sprite2Dである２つのスプライトを使った例です
• Node2Dの下にSprite2Dが２つ存在するだけの簡単なものです
• なんとかCollisionのノードは使いません

カニ(Glob)【ドラッグ可】をニワトリ（Niwatori)の方へ近づけていき、画像が重なったときに カニの色をかえるようにしています。

【GIF-01: 近づくがぎりぎり衝突しない例】

【GIF-02: 画像が重なり衝突する例】
画像が重なり衝突した。赤い丸は、衝突したピクセルの位置です

Bitmap衝突判定の処理効率改善策

Bitmap衝突判定は、画像ピクセル走査が欠かせません。
フレームごとの短時間で全てのピクセルを走査するのは、Godotの処理速度ではかなり無理っぽいかな(悪口じゃないです)。

効率的なピクセル走査の手法が必要です。

走査数を減らす方法（その１）

外周だけで衝突判定

画像のすべてのピクセルを走査すると大変なので、不透明な部分の外周のみをチェック対象としてみました。かなりの効率化が図れるはず。

【図-03: 連続した外周の例】

外周の数を減らす

外周の点を飛び飛びにして点の数を減らせば、より効率化が図れるはず。

【図-04: 飛び飛びの外周の例】

Pixel Spacingは、独自に用意したExport変数です。この値はデフォ=ゼロですが、5とすれば 5個飛ばしの外周点を作り出すようにしています。

外周の数を減らすときの注意点

対象とする点を減らしすぎると、衝突判定のミスが発生しがちです。対象数の減らしすぎには注意が必要です。画像のサイズが大きいときは 外周の点の数も増えますので衝突判定に要する時間が長くなり、全体の動きが緩慢になってきます。そのような場合はPixel Spacingの量を増やし、外周の点の数を減らす調整をするとよいでしょう。

外周だけで衝突判定できないケース

「外周点が相手に重なっているか？」の方法だけでは、相手の大きさが小さくて自身の外周の内部に相手の全画像が収まってしまう場合に「すべての外周点が相手にふれていない」状態になりますので、衝突と判定してくれません。

【図-05: カニの外周がニワトリに触れていない例】

「外周点が相手に触れていない」場合には、相手側からの衝突判定を行わせる「ひと手間」を用意します。

相手側の外周点が自分自身に衝突している場合、２つのスプライトは衝突しているとみなすことができるというわけです。

衝突判定ロジック

• 【ステップ１】自分自身の外周が相手に触れている
• 【ステップ２】以外の場合、相手の外周が自分自身に触れている

としています。

近傍判定

BITMAP衝突判定は 簡素化したとしても時間を要する処理には変わりありません。相手と遠く離れていて衝突するはずがない！場合には、BITMAP衝突判定(=ピクセル走査をしない）という作戦を採用したいところです。

矩形による「近傍」判定

ここでは説明の都合上、ニワトリ側が衝突判定を行う主体だとし、相手側をカニだとします。

【図-06: カニの画像の矩形(青い線)】

スプライトは 回転することがありますので、もし矩形も回転できるなら、こんな風になるはずです。

【図-07: グローバル座標な見え方(青い線)】

矩形どおしの重なり判定のためには、それぞれの矩形の上辺下辺が水平である必要あり。

【図-08: 赤い矩形と青い矩形の重なり判定はちょっと難しい】

そこで、傾いている矩形を強引に「上辺下辺が水平」としましょう。

【図-08: 青矩形を囲む赤矩形を作り出す】

次の図のように「赤い矩形」が重なるときに「近傍」であると判定します。

【図-09: 赤矩形どうしの重なり判定】

Bitmap衝突判定の処理効率改善策(その２)

「画像が衝突」するとしたら、２つの赤い矩形が重なった範囲内のみ！だとお分かりになるかと思います。この「矩形が重なった範囲」以外の場所では「画像が衝突」することはありえません。

【図-10: 画像が衝突する場所】

この「重なった範囲」に存在する「外周の点」だけを使い BITMAP衝突判定を行うことで、ピクセルごとの衝突判定回数を大幅に減らすことができる！というわけです。

外周の点を抜き出すロジック

# ここの説明ではテキスチャーからImageを取り出すが、GITHUBの試行作では
# もうすこし込み入ったことをしている。ここでは深くは立ち入らない
var _image = self.texture.get_image() 
# 不透明部分の外周ピクセルを抽出する
var _surrounding_arr = surrounding_points( _image )
# 

# 不透明の点より、外周部の点を抽出する
func surrounding_points(_image: Image, skip_count: int = 0) -> Array:
	var size:Vector2i = _image.get_size()	
	var _opaque_arr = []
	for _x:int in range(size.x):
		var x = _x
		var pixel = _image.get_pixel(x, 0)
		if pixel.a > 0:
			_opaque_arr.append(Vector2(_x, 0))
		for _y:int in range(size.y -2):
			var y = _y + 1
            # 縦に走査しているので隣の不透明の存在がキモになる。
            # そのため隣のピクセルも調べる
			var pixel00 = _image.get_pixel(x, y-1)
			var pixel01 = _image.get_pixel(x, y)
			var pixel02 = _image.get_pixel(x, y+1)
			if pixel01.a > 0:			
				if pixel00.a > 0 and pixel02.a > 0:
					if x == 0 or x == size.x -1 :
						_opaque_arr.append(Vector2(x, y))
					else:
						var pixel_x_00 = _image.get_pixel(x-1, y)
						var pixel_x_02 = _image.get_pixel(x+1, y)
						if pixel_x_00.a > 0 and pixel_x_02.a > 0 :
							continue
						else:
							_opaque_arr.append(Vector2(x, y))
				else:
					_opaque_arr.append(Vector2(x, y))
		pixel = _image.get_pixel(x, size.y-1)
		if pixel.a > 0:
			_opaque_arr.append(Vector2(x, size.y -1))
		
	var _surroundings = []
	var _opaque_size = _opaque_arr.size()
	for idx in range(_opaque_size):
		if skip_count == 0 or idx % skip_count == 0:
			_surroundings.append(_opaque_arr.get(idx))
		
	return _surroundings

衝突判定ロジック

class_name Hit

# 衝突を検出したピクセルの位置
var position :Vector2 = Vector2(INF, INF)
# 衝突しているとき true
var hit: bool = false

本記事の意図のから離れたコードは割愛しています（Githubにある試作品と一部異なるところがあります）

Bitmap判定の効率的な実装は、少しややこしいのでコードが長いです。

is_touched()

enum CALLER  {OWN, RECALL}

# 衝突している判定
# ownは自分自身、targetは判定したい相手 です。
# Sprite2DExtはSprite2Dを継承したクラスです、仔細は割愛します
func is_touched( own: Sprite2DExt, target:Sprite2DExt, caller:CALLER = CALLER.OWN)->Hit:
    # 衝突情報インスタンス
    var hitter:Hit = Hit.new()
    # テキスチャーのSvgObjを格納する辞書(Map),そのキー配列を取り出しておく
	var own_svg_img_map = own.get_svg_img_map()
	var own_svg_img_keys = own.get_svg_img_keys()
	var target_svg_img_map = target.get_svg_img_map()	
	var target_svg_img_keys = target.get_svg_img_keys()

    # 自スプライトの画像矩形を取り出す
	var rect:Rect2 = own.get_rect()

    # ターゲットの矩形(Rect2)の四角形４点を自スプライトのローカル座標に変換し
    # 四角形４点を囲む矩形(Rect2)を作る
	var target_rect_in_own:Rect2 = get_rect2_from_target(own, target)

    # 両者の矩形が重なるか否かを調べる
	var _intersect:Rect2 = rect.intersection(target_rect_in_own)
	if !_intersect.has_area(): # 大きさをもたないとき重なっていないとする
		# 近傍にないときは「衝突しない」として戻る
		hitter.hit = false
		return hitter

	# 以降は、近傍にあるときの衝突判定処理	

    # 現在表示中のテキスチャーのキー値(自スプライト用)
	var svg_obj_key = own_svg_img_keys[own.costumes._texture_idx]
    # 現在表示中のテキスチャーSvgObj(自スプライト用)
	var svg_obj:SvgObj = own_svg_img_map.get(svg_obj_key)
	
    # 現在表示中のテキスチャーのキー値(相手スプライト用)
	var target_svg_obj_key = target_svg_img_keys[target.costumes._texture_idx]
    # 現在表示中のテキスチャーSvgObj(相手スプライト用)
	var target_svg_obj: SvgObj = target_svg_img_map.get(target_svg_obj_key)

    # svg_obj.surrounding_point_arrは、自スプライトの外周点座標配列
	# 相互の矩形が重なるところの外周座標のみを抽出する
	var _surrounding_point_arr = []
	for pos in svg_obj.surrounding_point_arr:
		var _pos = Vector2(pos.x-rect.size.x/2, pos.y-rect.size.y/2)
		if _intersect.has_point(_pos):
			_surrounding_point_arr.append(_pos)

	# 絞り込んだ不透明の境界の点を使い、衝突判定をする
	for pos in _surrounding_point_arr:
		var _pos_2:Vector2 = pos + Vector2(rect.size.x/2, rect.size.y/2)
        # グローバル座標にして相手のローカル座標にする
		var _pos_g:Vector2 = own.to_global(pos)
		var _pos_t_l:Vector2 = target.to_local(_pos_g)
        # 相手の画像が不透明かを調べる
		if target.is_pixel_opaque(_pos_t_l):
			hitter.position = pos
			hitter.hit = true
			return hitter

	# 周囲の線だけによる衝突判定であるため、相手が自身の画像のなかに
	# 完全に入ってしまっているときには「衝突」とみなされない
	# その場合、相手側から衝突判定を再度行う。
	if( caller == CALLER.OWN):
		# 自身を起点とした衝突判定の場合
		# 相手の周囲の線から自身への衝突判定
		var hitter2 = is_touched(target, own, CALLER.RECALL)
		if hitter2.hit == true:
			return hitter2
		
	hitter.position = Vector2(-INF, -INF)
	return hitter

get_rect2_from_target()

# 衝突判定相手のスプライトの画像矩形(Rect2)を取得し
# その矩形の頂点４点を 自スプライトのローカル座標に変換
# ローカル座標の４点をもとに 新たな矩形(Rect2)を作る
func get_rect2_from_target(_own:Sprite2DExt, _target: Sprite2DExt) ->Rect2 :
	# 相手スプライトの画像矩形(Rect2)を取り出す
	var _rect:Rect2 = _target.get_rect()
    # 画像矩形の頂点を配列化する
	var _posArr = []
	_posArr.append( _rect.position ) # 左上
	_posArr.append( _rect.position + Vector2( _rect.size.x, 0 ) ) # 右上
	_posArr.append( _rect.end ) # 右下
	_posArr.append( _rect.position + Vector2(0, _rect.size.y) ) # 左下	
    # 自スプライトのローカル座標にする（配列）
    var _posArr_own = []
	for _pos in _posArr:
		_posArr_own.append( _own.to_local( _target.to_global( _pos ) ) )
    # ４点を囲む矩形(Rect2)を作る
	var _rect_out = _enveloped_rect(_posArr_own)
    
	return _rect_out

_enveloped_rect()

# ４点を囲む矩形(Rect2)を作る
func _enveloped_rect( _posArr: Array ) -> Rect2:
	var own_rect_most_left = INF
	var own_rect_most_right = -INF
	var own_rect_most_top = INF
	var own_rect_most_bottom = -INF
    # 上下左右を求める
	for _pos:Vector2 in _posArr:
        # 一番左にある点
		if _pos.x < own_rect_most_left:
			own_rect_most_left = _pos.x
        # 一番右にある点
		if _pos.x > own_rect_most_right:
			own_rect_most_right = _pos.x
        # 一番上にある点
		if _pos.y < own_rect_most_top:
			own_rect_most_top = _pos.y
        # 一番下にある点
		if _pos.y > own_rect_most_bottom:
			own_rect_most_bottom = _pos.y
    # 上下左右の位置を元に Sizeを計算
    var _size = Vector2(
		own_rect_most_right - own_rect_most_left,
		own_rect_most_bottom - own_rect_most_top	
	)
    # 上下左右の位置を元に 開始座標を計算
	var _end = Vector2(
		own_rect_most_right,
		own_rect_most_bottom
	)
	var _start = _end - _size
    # 開始位置とサイズをもとに矩形(Rect2)化する
	var _rect = Rect2(_start, _size)
	return _rect

SvgCostumes について

Spriteの _ready() のタイミングで SVG画像を読み込み、Costumesの中にため込みます。複数のコスチュームをためこみ、コスチュームを切り替えることができるようにします。

Sprite2Dのコード例

extends Sprite2D
var costumes = SvgCostumes.new(self) # 自分自身を与えてインスタンス化
func _ready()->void:
    # パスを与えて画像を読み込み、画像ごとに次を行う
    # (1) SVG文字列を保持する
    # (2) イメージを生成、ImageTexture化して保持する
    # (3) 不透明部の外周を走査し、座標配列として保持する
    # 上の(1)～(3)はCostumesインスタンス内でSvgObj配列として保持
    costumes.svg_file_path_setting([
        "res://assets/glob-a.svg",
        "res://assets/glob-b.svg",
    ])
    # 先頭の画像をスプライトテキスチャーとして表示する
    costumes.current_svg_tex()

SvgObj クラス

# Svgテキスチャー情報
class_name SvgObj

var name : String
var rect: Rect2
var svg_text: String
var svg_scale: float = 1.0
var svg_scale_created : float = 1.0
#var image: Image = Image.new()
var texture: ImageTexture = ImageTexture.new()
var surrounding_point_arr = [] # 不透明部分の外周ピクセル配列
var distance:float = -INF
enum Axis { X, Y }

func get_image()->Image:
	if self.svg_scale != self.svg_scale_created:
		self.create_svg_from_text()
	return self.texture.get_image()

func get_texture()->ImageTexture:
	return self.texture

func create_svg_from_text( ) ->void:
	var image = Image.new()
	image.load_svg_from_string(self.svg_text, self.svg_scale)
	self.texture.set_image(image)
	self.svg_scale_created = self.svg_scale

SvgCostumes クラス

class_name SvgCostumes

var sprite: Sprite2DExt
var neighborhood_value: int = 10
# SVG 関連
var _svg_img_map = Dictionary()
var _svg_img_keys = Array()
# テキスチャの位置
var _texture_idx = 0
#var image: Image
	
func _init(sprite: Sprite2DExt):
	self.sprite = sprite

func svg_file_path_setting(svg_path_arr: Array) -> void:
	if self.sprite._cloned == true :
		# クローンされたときは何もしない
		return
		
	var _regex := RegEx.new()
	var _error = _regex.compile("^.+/(.+)\\.svg$")
	# スプライトテキスチャーの型をImageTextureにする
	self.sprite.texture = ImageTexture.new()
	if _error != OK:
		return
	for path in svg_path_arr:
		if path != null and path is String and _regex.is_valid():
			var file = FileAccess.open(path, FileAccess.READ)
			if file != null:
				var result = _regex.search(path)
				var name = result.get_string(1)		# 拡張子を除いたファイル名
				var _txt = file.get_as_text(true)	# skip_cr = true
				_svg_img_keys.append(name)
				var svg_obj:SvgObj = SvgObj.new()
				svg_obj.name = name
				svg_obj.svg_text = _txt
				svg_obj.svg_scale = self.sprite.svg_scale
				svg_obj.create_svg_from_text()
				_svg_img_map.set(name, svg_obj)
				# 不透明なピクセル座標（Local)を配列化
				var _img = svg_obj.get_image()
				svg_obj.surrounding_point_arr = BitmapUtils.surrounding_points(_img, self.sprite.pixel_spacing)
				#print("svg_obj.surrounding_point_arr size=", svg_obj.surrounding_point_arr.size())
		else:
			print("ivalid path = ", path)

# 画像矩形をグローバル座標に変換し、矩形の中に描かれるイメージ外周点のうちから
# 中心より最も遠い点を求める
func calculate_distance(svg_obj: SvgObj) -> float :
	var _rect = svg_obj.rect
	var _global_center:Vector2 = self.sprite.to_global( Vector2( _rect.size.x/2, _rect.size.y/2 ))
	var _pixels = BitmapUtils.pixel_to_global(self.sprite, svg_obj.surrounding_point_arr)
	var _fartherst = BitmapUtils.point_fartherst_from_center(_global_center, _pixels)
	return _fartherst
	
func current_svg_tex() -> void:
	#print(self.sprite._original_sprite)
	self._draw_svg()

func next_svg_tex() -> void:
	if self.sprite._original_sprite == null:
		return
	if self.sprite._original_sprite.costumes._svg_img_keys.size() == 1:
		return
	_texture_idx += 1
	self._draw_svg()

func prev_svg_tex() -> void:
	_texture_idx -= 1
	if _texture_idx < 0:
		_texture_idx = self.sprite._original_sprite.costumes._svg_img_keys.size() -1
	self._draw_svg()
	
func _draw_svg() -> void:
	if self.sprite._original_sprite == null:
		return
	var svg_img_keys = self.sprite._original_sprite.costumes._svg_img_keys
	var svg_img_map = self.sprite._original_sprite.costumes._svg_img_map
	if _texture_idx < 0:
		return
	if svg_img_keys.size() > 0:
		var tex_size = svg_img_keys.size()
		_texture_idx = _texture_idx % tex_size
		var key = svg_img_keys.get(_texture_idx)
		var svg_obj:SvgObj = svg_img_map.get(key)
		svg_obj.svg_scale = self.sprite.svg_scale
		var image:Image = svg_obj.get_image()
		# ImageTextureへのset_image は事前に済ませておく。
		var _texture = svg_obj.get_texture()
		self.sprite.texture = _texture
		svg_obj.rect = self.sprite.get_rect()

# 画像ピクセルで判定する衝突判定
func _is_pixel_touched(_target:Sprite2DExt) -> Hit :
	#var circle :Sprite2D = $"/root/Node2D/Circle"
	var hit = SpriteUtils.is_touched(self.sprite, _target)
	return hit

BITMAP効率化のまとめ

使用する画像

画像	横(pixel)	縦(pixel)
カニ	134	90
ニワトリ	237	208

手法別の比較

Time.get_ticks_msec()を使って計測をしました

手法	計測値(ms)
全ピクセルを走査	1ms-20ms
全外周点を利用	1ms-10ms
相互の矩形が重なる部分の外周点だけ	1ms-3ms
全外周点を利用(5個飛ばし)	1ms - 5ms
相互の矩形が重なる部分の外周点だけ(5個飛ばし)	1ms - 2ms

評価

全ピクセル走査は当たる場所により判定時間のばらつきが大きいです

外周点を使った判定は短縮効果を確実に得ることができます。

相互矩形が重なる部分の外周点による判定は時間が一番短いです。

5個飛ばしですが、常に最適な衝突判定とは言えないのですが、時間短縮効果を得ることができますので飛ばし数による試行錯誤はやる価値がありそうです。

おすすめするBITMAP衝突判定手法

• 相互矩形が重なる部分の外周点による判定

上記をおすすめします。

追記：傾いた矩形のままの衝突判定

傾いている青の矩形のままで衝突判定(近傍判定)をさせたいと考え、後日に改良案を試しています。より狭い範囲の矩形のままで衝突判定(近傍判定)を行えますので、衝突判定時間を節約することができます。

傾いた矩形を使った衝突判定の記事(Qiita)

傾いた矩形で衝突判定（近傍判定)の実装をGithubにあげています。
GITHUB