Quadtree（四分木）を p5.js で扱うための情報源を探してみる

Quadtree（四分木）を p5.js で扱ってみたいと思い、そのために役立つ情報源を探してみたという話です。

## 情報源
### 動画
ざっくり調べたところ、有名どころの [The Coding Train](https://www.youtube.com/@TheCodingTrain) を見るのが、自分には一番良さそうな選択肢でした。

●Coding Challenge #98.1: Quadtree - Part 1 - YouTube
https://www.youtube.com/watch?v=OJxEcs0w_kE

<iframe width="560" height="315" src="https://www.youtube.com/embed/OJxEcs0w_kE?si=AYUPD_kPTjOJo5tq" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe>

動画は、上記と他に以下の 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

このあたりの情報は、動画のコメント欄に書かれています。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/50868/9faf0628-e0df-cd9b-f814-4fcada949372.png)

動画の英語字幕を機械翻訳で日本語にしたものをつけて、動画を見ていくか、またはサンプルコードを見ていくか、どちらにしようかと思ったのですが、サンプルコードを見てみることにしました。

### コード
動画に関係するコードのサンプルは、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つは、自分がマウスを操作して利用する形のものです。

具体的な動作は、以下の通りです。

1. 画面内に白い区切り線と、白い点が描画されている
1. マウスカーソルを動かすと、それに追従する緑の矩形が動く
1. 緑の矩形の中に白い点が入ったら、点の色が緑になる

矩形と点の衝突判定の処理という感じのようです。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/50868/d952641c-f423-b927-1c80-c2a3c16ff380.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/50868/82aed711-1858-900f-966a-2b824b62aab5.png)

これを実現する JavaScript のプログラムは、以下のように 2つに分かれているようです。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/50868/eb2b3aa5-4997-1f5a-5012-7c8b770e2894.png)

それぞれの規模感は、30行ほどのものと、130行ほどのものという感じでした。

#### Quadtree Collisions - Part 3
もう 1つの残りのサンプルは、以下の動作になるようです。

1. 黒い背景のキャンバスに、たくさんのグレーの円が動いている
1. グレーの円同士が衝突した時は、円の色が白くなる

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/50868/a805e677-6e9d-647e-0529-a379dd2520ef.png)

これを実現する JavaScript のプログラムは、以下のように 3つに分かれているようです。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/50868/ce30f2b7-61b6-92f6-41b7-58cbc0165f28.png)

それら全体は、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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/50868/d4359670-ece0-a7a1-3b44-40b8447a1d04.png)

## 【2025/2/11追記】
しばらく放置してしまっていたこちらのネタ、まずは下準備から着手。

https://x.com/youtoy/status/1889207478585323784