ビットボードと戯れていたらふと思いついたので記事を書いてみました。
内容に誤りがあったらコメントで教えて貰えると助かります。
最初に
高速化なのになんでPythonなの？→Pythonしか使えないからです。
ビットボードって何？→ビットボードはすごいやつです。
わかりやすい記事→ビットボードの凄さをざっくりと解説してみる
A*探索アルゴリズムでよくない？→よいです。ロマンです。
記事わかりづらいんだけど→申し訳ないです。
変数名の付け方癖強くない？→真心を込めて名付けています。
ビットボードによる経路探索のメリット
- 複数の経路を同時進行で計算できる
- 容量に優しいかもしれない
- 速い！
- スタート地点やゴール地点を複数設置できる
デメリット
- コードの可読性が下がる
実装
入力
main.py
example_map = '''
########
#..#.#.#
#S.#...#
##...#.#
#..##..#
#.#G..##
#..#...#
########
'''.strip()
#：壁
S：スタート地点
G：ゴール地点
.：無
ルール
スタート地点から上下左右に一マスずつ移動できます。
壁は通り抜けられません。
ビットボード化
このマップをビットボードとして扱うために、二進数で表します。
壁がある場所を0、壁がない場所を1としたbit_map、
スタート地点を1としたbit_S_points、
ゴール地点を1としたbit_G_points、
の三つのビットボードを用意します。
main.py
def print_bbd(bbd, w, h, one_text='1', zero_text='0', **args):
bit_text = bin(bbd & (2**(w*h) - 1) | (1 << w*h))[3:]
bbd_text = '\n'.join([bit_text[row*w:(row+1)*w] for row in range(h)])
print(bbd_text.replace('1', one_text).replace('0', zero_text), **args)
w, h = 8, 8
example_map_rows = example_map.split('\n')
bit_map = 0
bit_S_points = 0
bit_G_points = 0
for y in range(h):
for x in range(w):
s = (h-1-y) * w + (w-1-x)
point = example_map_rows[y][x]
bit_map |= int(point in ['.', 'S', 'G']) << s
bit_S_points |= int(point == 'S') << s
bit_G_points |= int(point == 'G') << s
print_bbd(bit_map, w, h)
>>>00000000
01101010
01101110
00111010
01100110
01011100
01101110
00000000
print_bbd(bit_S_points, w, h)
>>>00000000
00000000
01000000
00000000
00000000
00000000
00000000
00000000
print_bbd(bit_G_points, w, h)
>>>00000000
00000000
00000000
00000000
00000000
00010000
00000000
00000000
探索
移動可能な場所を表すビットボードpointsを使って探索を行っていきます。
探索は、ゴールにたどり着くか、これ以上探索できなくなった時点で終了します。
main.py
points = bit_S_points
histories = [0,points]
while points != histories[-1] or ((bit_G_points & points) == 0):
points |= ((points << 1) | (points >> 1) | (points << w) | (points >> w)) & bit_map
histories.append(points)
これだけだと分かりづらいと思うのでリストhistoriesのビットボードを表示してみます。1と0ばっかりだと分かりづらいので、移動可能な場所を#、移動不可能又は未探索の場所を.で表します。
main.py
for history in histories:
print_bbd(history, w, h, '#', '.')
print()
output.txt
........
........
........
........
........
........
........
........
........
........
.#......
........
........
........
........
........
........
.#......
.##.....
........
........
........
........
........
........
.##.....
.##.....
..#.....
........
........
........
........
........
.##.....
.##.....
..##....
..#.....
........
........
........
........
.##.....
.##.....
..###...
.##.....
........
........
........
........
.##.....
.##.#...
..###...
.##.....
.#......
........
........
........
.##.#...
.##.##..
..###...
.##.....
.#......
.#......
........
........
.##.#...
.##.###.
..###...
.##.....
.#......
.##.....
........
........
.##.#.#.
.##.###.
..###.#.
.##.....
.#......
.##.....
........
........
.##.#.#.
.##.###.
..###.#.
.##...#.
.#......
.##.....
........
........
.##.#.#.
.##.###.
..###.#.
.##..##.
.#......
.##.....
........
........
.##.#.#.
.##.###.
..###.#.
.##..##.
.#...#..
.##.....
........
........
.##.#.#.
.##.###.
..###.#.
.##..##.
.#..##..
.##..#..
........
........
.##.#.#.
.##.###.
..###.#.
.##..##.
.#.###..
.##.###.
........
ちゃんと探索できていることが分かります。
逆算
経路を求めるために、ゴール地点からリストhistoryをつかってスタート地点まで逆算します。
main.py
path = [bit_G_points]
for history in histories[:-1][::-1]:
if (x := path[-1] << 1) & history:
pass
elif (x := path[-1] >> 1) & history:
pass
elif (x := path[-1] << w) & history:
pass
elif (x := path[-1] >> w) & history:
pass
else:
break
path.append(x)
path = path[::-1]
表示してみるとこんな感じになります。
path.txt
........
........
.#......
........
........
........
........
........
........
........
..#.....
........
........
........
........
........
........
........
........
..#.....
........
........
........
........
........
........
........
...#....
........
........
........
........
........
........
........
....#...
........
........
........
........
........
........
....#...
........
........
........
........
........
........
........
.....#..
........
........
........
........
........
........
........
......#.
........
........
........
........
........
........
........
........
......#.
........
........
........
........
........
........
........
........
......#.
........
........
........
........
........
........
........
.....#..
........
........
........
........
........
........
........
........
.....#..
........
........
........
........
........
........
........
....#...
........
........
........
........
........
........
........
...#....
........
........
まとめるとこんな感じです。
result.txt
........
........
.##.###.
..###.#.
.....##.
...###..
........
........
最後に
ビットボードを使って最短経路を探索することができました。
完全に自己満足の記事ですが何かの役に立つと嬉しいです。
Pythonの場合、シフトを4つ使うより掛け算を使ったりするなど、まだまだ高速化できる余地があると思います。
忙しい時期なのに書きたい衝動が抑えられず書いた記事なのでクオリティが低いのは申し訳ないです…
訂正や質問があれば是非コメントください！