Box2Dベンチマーク (Python 線分交差判定)

先日、線分交差判定の方法をまとめました。こういった当たり判定を多用する物理エンジンでは、Sweep and Pruneアルゴリズムなどを用いて当たり判定の枝刈りをしたり、そもそもネイティブPythonではなく、C++で実装して高速化するなどしています。

そういった2D向け物理エンジンでPython向けのインタフェースがあるものにBox2DやChipmunkがありますが、OpenAI GymのBipedalWalkerではBox2Dが採用されています。このBox2Dがネイティブ実装と比較してどのくらいの性能が出るのか比較しました。

実行環境

python 3.8
Box2D==2.3.10
numba==0.54.1

ベンチ環境

大量の隔壁に向けてLidarを照射し、距離を測ります。ネイティブ実装では純粋に"壁の数×レーザー数"回だけの当たり判定処理を行います。アルゴリズムについては先日のエントリーをご参照ください。

結果

ノートをこちらで公開。

縦10x横1000枚の隔壁にレーザーを照射した結果がこちらで、Box2Dが圧倒的でした。Pythonインタフェースのドキュメントが充実していないので使うのがしんどいですが、今度から手組み辞めようかなと思うくらい速い…。

	方法	結果[msec]	指数
1	Box2D	0.037	1.0
2	Numba実装	202.878	5,483.0
3	Native Python実装	549.742	14,857.9

そして、試した範囲内では理論通りO(n)になっているっぽい(※ Box2Dのグラフは細かく読んでない)

Box2D実装メモ

Box2D Pythonインタフェースのドキュメントは体系的なものがないため毎度困るので実装メモを残す。

シミュレーション世界の初期化

import Box2D
from Box2D.b2 import (edgeShape, fixtureDef)

world = Box2D.b2World()
# v2.1.2でedgeShapeが導入された[1]
walls_2d = [
  fixtureDef(shape = edgeShape(
    vertices= [(w[0][0], w[0][1]), (w[1][0], w[1][1])])
  ) for w in walls
]
world.CreateStaticBody(fixtures = walls_2d)
# 上記とこれに大きな違いはない
# for f in walls_2d:
#   world.CreateStaticBody(fixtures = f)
class LidarCallback(Box2D.b2.rayCastCallback):
    # BipedalWalkerでは基底クラスに含まれている扱いだが明示的に宣言必要
    p1 = [0., 0.]
    p2 = [0., 0.]
    fraction = 1.0
    def ReportFixture(self, fixture, point, normal, fraction):
        self.p2 = point
        self.fraction = fraction
        # ReportFixtureの戻り値で振る舞いが変わる
        # [2] b2RayCastCallback Class Referenceを参照
        return fraction
lidar = [LidarCallback() for _ in range(ray_n)]

RayCast

Lidarのレーザー起点と有効圏で初期化してRayCastする。当たり判定に伴う処理はReportFixtureで定義済み。

import numpy as np
# ロボットの定義(再掲)
o = np.array([50., 150.]) # ロボット位置
ray_l = 200 # Lidar有効距離
ray_n = 9   # Lidar線数
ray_angles = [math.pi/2 * i / (ray_n - 1.) - math.pi/4 for i in range(ray_n)]
ray_ends = o + ray_l * np.array([[math.cos(theta), math.sin(theta)] for theta in ray_angles])

for l, p in zip(lidar, ray_ends):
    l.p1 = o
    l.p2 = p
    world.RayCast(l, l.p1, l.p2)

シミュレーション内のオブジェクト取得

C++/Javaのインタフェースでは定義されているworld.getBodies()はPythonでは提供されておらず、world.bodiesでアクセスする。

import matplotlib.pyplot as plt
for b in world.bodies:
    for f in b.fixtures:
        w = f.shape.vertices
        # 隔壁が2点で定義されている前提の描画処理
        plt.plot([w[0][0], w[1][0]], [w[0][1], w[1][1]], color = 'black')
for l in lidar_b2d:
    plt.plot([l.p1[0], l.p2[0]], [l.p1[1], l.p2[1]], color = 'blue')
plt.show()