【農家はReplace()されました】迷路を再帰関数を用いた深さ優先探索で解いてみる

はじめに

迷路を解く方法として、公式では壁伝いに移動する方法が紹介されていて記事もそれに倣ったものが多いので、今回は別の方法として再帰関数を用いた深さ優先探索で攻略してみる。
※再配置による連続の探索は考慮していません。

ソースコード

#
# 深さ優先探索で迷路を攻略する関数
#	direction: 移動方向
#
def depth_first_search(direction=None):
	if direction:
		move(direction)
	
	# 今いる場所が宝箱の真上なら収穫してTrueを返す
	if get_entity_type() == Entities.Treasure:
		harvest()
		return True

	# 指定した方角に移動可能かつ元の場所に戻らない場合次のステップへ
	if can_move(North) and direction != South:
		if depth_first_search(North):
			return True
		move(South)
	
	if can_move(South) and direction != North:
		if depth_first_search(South):
			return True
		move(North)
	
	if can_move(East) and direction != West:
		if depth_first_search(East):
			return True
		move(West)
	
	if can_move(West) and direction != East:
		if depth_first_search(West):
			return True
		move(East)
	
	# 行き止まりもしくはその先に宝箱がない場合Falseを返す
	return False


# 迷路の生成
clear()
plant(Entities.Bush)
substance = get_world_size() * 2**(num_unlocked(Unlocks.Mazes) - 1)
use_item(Items.Weird_Substance, substance)

# 迷路探索開始
depth_first_search()

解説

depth_first_search()の動作イメージを解説していく。

1. スタートマス

def depth_first_search(direction=None):
	if direction:
		move(direction)
	
	# 今いる場所が宝箱の真上なら収穫してTrueを返す
	if get_entity_type() == Entities.Treasure:
		harvest()
		return True

	# 指定した方角に移動可能かつ元に戻る方角でない場合次のステップへ
	if can_move(North) and direction != South:
		if depth_first_search(North): # <- 再帰的に関数を呼び出す
			return True
		move(South)

引数はNoneのためどこにも移動せず、宝箱マスでもないためスルー。
北方向へ移動するため関数を再帰呼び出しする。

2. スタートマスから(1, 0)マスへ

def depth_first_search(direction=None):

	# 指定した方角に移動可能かつ元に戻る方角でない場合次のステップへ
	if can_move(North) and direction != South:
		if depth_first_search(North): # <- 再帰的に関数を呼び出す
			return True
		move(South)

スタートマスから北に移動する。
宝箱マスではないためスルー。
まだ北方向へ移動できるため関数を再帰呼び出しする。

3. (1, 0)マスから(2, 0)マスへ

def depth_first_search(direction=None):

	# 指定した方角に移動可能かつ元に戻る方角でない場合次のステップへ
	if can_move(North) and direction != South:
		if depth_first_search(North): # <- 再帰的に関数を呼び出す
			return True
		move(South)

上記と同様。

4. (2, 0)マスへから(3, 0)マスへ

def depth_first_search(direction=None):
    
	# 行き止まりなのでFalseを返す
	return False

(3, 0)マスではどの方向へも移動できないためFalseを返す。

5. (3, 0)マスへから(2, 0)マスへ

def depth_first_search(direction=None):

	# 指定した方角に移動可能かつ元に戻る方角でない場合次のステップへ
	if can_move(North) and direction != South:
		if depth_first_search(North): # <- Falseが返ってくる
			return True
		move(South)


	if can_move(East) and direction != West:
		if depth_first_search(East): # <- 再帰的に関数を呼び出す
			return True
		move(West)

3. の再帰呼び出しでFalseが返ってくるためif文はスキップし南【(3, 0)から(2, 0)】へ移動する。
次に東へ移動できるので関数を再帰呼び出しする。

7. 繰り返し

以降、上記の手順を宝箱が見つかるまで繰り返す。

おわりに

壁伝いに移動する方法と比べて、視点がぐるぐる動かないぶん理解しやすいかなという印象。