OpenSiv3Dでセグメント木を可視化する

OpenSiv3D

Last updated at 2022-12-07Posted at 2022-12-06

はじめに

この記事はSiv3D Advent Calendar 2022 6日目の記事です。

アドベントカレンダーのネタ探しのためにSiv3D のウェブページを見たところ、幅優先探索の可視化という項目を見つけました。そこで、今回はセグメント木の可視化に挑戦してみました。
可視化したときの画面は↓のようになります。

方針

セグメント木を実装して、値が変化した場所などに色を付けることでアルゴリズムの挙動を可視化します。ただし、何の工夫もせずに実装して動作させると実行速度が速すぎて目で追うことができなくなってしまいます。

そこで、幅優先探索の可視化を参考にして、前フレームからの経過時間を測定することができるScene::DeltaTime()を使って、1秒ごとに1ステップだけ動作が進むように実装しました。具体的には、アルゴリズムの中でfor文を使う部分をif文に直して、OpenSiv3Dのメインループ中に置くようにしています。

while (System::Update())
{
    // 状態更新フラグ
	bool updateFlag = false;	

	// 前フレームからの経過時間を加算
	accumulatedTime += Scene::DeltaTime();

	// 更新間隔を超えていたら
	if (UpdateTime <= accumulatedTime)
	{
		accumulatedTime -= UpdateTime;

		updateFlag = true;
	}
    if (updateFlag)
    {
        // ここにアルゴリズムのfor文の中身を書く
    }       
}

全体のソースコード

セグメント木ではモノイドであるという条件さえ満たせばある区間内の最小値、最大値、和を求めるなど色々な操作を行うことが可能です。今回は、セグメント木の5番目の要素に5を代入し、次に1番目の要素から5番目の要素までの和を求めるという動作を可視化しました。

# include <Siv3D.hpp>

void Main()
{
	// 背景色を水色に
	Scene::SetBackground(ColorF{ 0.8, 0.9, 1.0 });

	// 距離の表示用フォント
	const Font font{ 18, Typeface::Bold };

	// 可視化するときのマスのサイズ（ピクセル）
	constexpr int32 CellSize = 40;

	// 配列: 木
	Array<int32> tree =
	{ 36, 10, 26, 3, 7, 11, 15, 1, 2, 3, 4, 5, 6, 7, 8 };

	// 更新の間隔（秒）
	constexpr double UpdateTime = 1.0;

	// 蓄積時間（秒）
	double accumulatedTime = 0.0;

	// 更新された場所を記録
	Array<int32> updated(16, 0);

	// 値を読んだ場所を記録
	Array<int32> got(16, 0);

	int32 com = 1;
	int32 updateIndex = 4, updateValue = 5;
	int32 getL = 0 + 7, getR = 5 + 7, res = 0;
	while (System::Update())
	{
		// 状態更新フラグ
		bool updateFlag = false;
		

		// 前フレームからの経過時間を加算
		accumulatedTime += Scene::DeltaTime();

		// 更新間隔を超えていたら
		if (UpdateTime <= accumulatedTime)
		{
			accumulatedTime -= UpdateTime;

			updateFlag = true;
		}

		// 更新箇所をリセット
		if(updateFlag)
		{
			for(int32 i = 0; i < 16; i++)
			{
				updated[i] = 0;
			}
			for(int32 i = 0; i < 16; i++)
			{
				got[i] = 0;
			}
		}

		// 更新を周期的に実行(get)
		if (updateFlag && updateIndex == 0 && getL <= getR && getR > 0)
		{
			if((getL + 1) & 1)
			{
				got[getL] = 1;
				res += tree[getL++];
			}
			if((getR + 1) & 1)
			{
				getR--;
				res += tree[getR];
				got[getR] = 1;
			}
			// getL >>= 1, getR >>= 1;
			getL = (getL - 1) / 2, getR = (getR - 1) / 2;
		}

		if(com)
		{
			updateIndex += 7;
			tree[updateIndex] = updateValue;
			updated[updateIndex] = 1;
			com = 0;
		}
		// 更新を周期的に実行(set)
		if (updateFlag && updateIndex > 0)
		{
			updateIndex = (updateIndex - 1) / 2;
			tree[updateIndex] = tree[updateIndex * 2 + 1] + tree[updateIndex * 2 + 2];
			updated[updateIndex] = 1;
		}

		

		// 状態を可視化
		ClearPrint();
		Print << res;
		Print << getL << U" " << getR;
		Print << tree;
		for (int32 i = 0; i < tree.size(); ++i)
		{
			// マスの正方形
			int32 y = log2(i + 1), x = i - Pow(2, y) + 1;
			// Print << i << U" " << x << U" " << y;
			// const Rect rect = Rect{ (x * CellSize + (8 - (int32)Pow(2, y - 1)) * CellSize), (y * CellSize), CellSize }.stretched(-1);
			const Rect rect = Rect{ (x * CellSize * (int32)Pow(2, 4 - y)), (y * CellSize), CellSize * (int32)Pow(2, 4 - y), CellSize }.stretched(-1);
			{
				// 白で表示
				rect.draw();
				font(tree[i]).drawAt(rect.center(), ColorF{ 0.25 });
			}

			// 更新された部分の可視化
			if(updated[i])
			{
				// 赤い半透明の正方形を重ねる
				rect.draw(ColorF{ 1.0, 0.0, 0.0, 0.5 });
			}
			if(got[i])
			{
				// 赤い半透明の正方形を重ねる
				rect.draw(ColorF{ 1.0, 0.5, 0.0, 0.5 });
			}
		}
	}
}

おわりに

セグメント木の動作の可視化に挑戦してみました。値を代入したときの動作は思った通りだったのですが、合計を求めるときの動作が予想外に感じました。また、実際に動作を見ながら書くことで、アルゴリズムの理解も深まったように感じました。

アルゴリズムの中のfor文をif文に直してからメインループの中に入れることで良い感じに動作を可視化できることが分かったので、他のアルゴリズムの可視化にも挑戦してみたいです。¹

参考資料

この方法では再帰を使うアルゴリズムを可視化することができません。セグメント木は再帰でもfor文でも書くことができたのでどうにかできましたが、再帰でないと書くのが難しいアルゴリズムを可視化するのは今後の課題になりそうです。もし良い方法をご存知の方がいましたら、教えていただけると助かります。 ↩

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up