Quadtree（四分木）を p5.js で扱ってみたいと思い、そのために役立つ情報源を探してみたという話です。
情報源
動画
ざっくり調べたところ、有名どころの The Coding Train を見るのが、自分には一番良さそうな選択肢でした。
●Coding Challenge #98.1: Quadtree - Part 1 - YouTube
https://www.youtube.com/watch?v=OJxEcs0w_kE
動画は、上記と他に以下の 2つがあるようです。
●Coding Challenge #98.2: Quadtree - Part 2 - YouTube
https://www.youtube.com/watch?v=QQx_NmCIuCY
●Coding Challenge #98.3: Quadtree Collisions - Part 3 - YouTube
https://www.youtube.com/watch?v=z0YFFg_nBjw
このあたりの情報は、動画のコメント欄に書かれています。
動画の英語字幕を機械翻訳で日本語にしたものをつけて、動画を見ていくか、またはサンプルコードを見ていくか、どちらにしようかと思ったのですが、サンプルコードを見てみることにしました。
コード
動画に関係するコードのサンプルは、p5.js Web Editor上に用意されています。具体的には、以下の 2つがありました。
●p5.js Web Editor | Quadtree - Part 1
https://editor.p5js.org/codingtrain/sketches/g7LnWQ42x
●p5.js Web Editor | Quadtree Collisions - Part 3
https://editor.p5js.org/codingtrain/sketches/CDMjU0GIK
これらを軽く見ていきます。
Quadtree - Part 1
サンプルの 1つは、自分がマウスを操作して利用する形のものです。
具体的な動作は、以下の通りです。
- 画面内に白い区切り線と、白い点が描画されている
- マウスカーソルを動かすと、それに追従する緑の矩形が動く
- 緑の矩形の中に白い点が入ったら、点の色が緑になる
矩形と点の衝突判定の処理という感じのようです。
これを実現する JavaScript のプログラムは、以下のように 2つに分かれているようです。
それぞれの規模感は、30行ほどのものと、130行ほどのものという感じでした。
Quadtree Collisions - Part 3
もう 1つの残りのサンプルは、以下の動作になるようです。
- 黒い背景のキャンバスに、たくさんのグレーの円が動いている
- グレーの円同士が衝突した時は、円の色が白くなる
これを実現する JavaScript のプログラムは、以下のように 3つに分かれているようです。
それら全体は、230行くらいの規模のようでした。
おわりに
p5.js で Quadtree（四分木）を試すのに、まずは上記のサンプルを見てみるのが自分には良さそうでした。
これから、コードを見ていきながら、動画も見て内容を把握していければと思います。
その他
今回、メインの内容として The Coding Train の動画・サンプルコードを掲載しましたが、他に調査をしていた中で気になった情報をメモしておきます。
気になった JavaScript ライブラリ
Quadtree について検索していた時、JavaScriptライブラリの情報が出てきたのですが、その中で自分が気になったものを以下に掲載してみます。
ライブラリのリポジトリ
●timohausmann/quadtree-js: A lightweight quadtree implementation for javascript
https://github.com/timohausmann/quadtree-js?tab=readme-ov-file
●timohausmann/quadtree-ts: Quadtree Typescript Implementation
https://github.com/timohausmann/quadtree-ts/
ライブラリの公式デモ
●quadtree-js Simple Demo
https://timohausmann.github.io/quadtree-js/simple.html
【2025/2/11追記】
しばらく放置してしまっていたこちらのネタ、まずは下準備から着手。