関連スライド
Meta XR SDK(V66-74)でQuestアプリを開発
あうぜん
1.1M
各ページのテキスト
グラフを平面にする Webゲームを作った kuradai
“グラフ”とは？ ● グラフ ○ 頂点とそれをつなぐ辺からなる構造体 ○ 物事の関係や構造を表すことができる ○ 詳しく学びたい人は、 ２年対象の後期科目「グラフ理論」 ● 平面グラフ ○ 辺の交差なく描画できているグラフ ChatGPTが 生成したグラフの例
作ったゲーム ● 頂点の位置をマウスで操作して、 辺の交差があるグラフを平面グラフに変える ● Vanillaで作成
処理の流れ 1. ゲーム画面を表すキャンバスを作る 2. 辺の交差なく描画可能なグラフを作る 3. 2.で作成したグラフをゲーム画面に描画する 4. プレイヤーからの操作があるたびに以下を行う ○ 頂点の位置を変え、ゲーム画面を再描画する ○ 辺の交差を確認し、存在しない場合は5.に進む 5. ゲームクリアの処理を行う
処理の流れ 1. ゲーム画面を表すキャンバスを作る 2. 辺の交差なく描画可能なグラフを作る 3. 2.で作成したグラフをゲーム画面に描画する 4. プレイヤーからの操作があるたびに以下を行う ○ 頂点の位置を変え、ゲーム画面を再描画する ○ 辺の交差を確認し、存在しない場合は5.に進む 5. ゲームクリアの処理を行う
アルゴリズム 2.辺の交差なく描画可能なグラフを作る ● 左右それぞれについて、全ての辺のペアで一方が他方に 包まれるまたは包む関係になくてはならない 1 1 2 2 3 3 4 4 ✖ ◎
アルゴリズム 2.辺の交差なく描画可能なグラフを作る ● 新しく追加する辺が頂点nとm（n < m）を結んでいるとき、 既に存在している辺(n₁, n₂)と交差しないことは n₁≤nかつm≤n₂ (新しい辺が内側) または n≤n₁かつn₂≤m (新しい辺が外側） を確認することでわかる n₁ n ● 新しく追加する辺と同じ側にある既存の辺の すべてと成り立つか確認する n n₁ ○ 成り立てば辺を追加しても平面のまま！ m n₂ n₂ m
アルゴリズム 2.辺の交差なく描画可能なグラフを作る Fáry's theorem Wagner(1936),Fáry(1948),Stein(1951) 任意の単純な平面グラフは、 その辺が直線となるように交差なく描くことができる → ゲームで辺を曲線で描けるようにする必要はない！
アルゴリズム 辺の交差を判定する ● 線分ABと線分CDが交差するかどうかは 「直線ABと線分CDが交差して かつ 線分ABと直線CDが交差する」 と同値である ● 直線と線分の交差判定は、直線を一次関数で表し、 線分の端点が直線によって分けられる 2つの領域それぞれ入るかで判定できる ● また、ベクトルの外積を用いても 同様の式によって判定できる y=ax+b y>ax+b y<ax+b 参考 ：https://qiita.com/zu_rin/items/e04fdec4e3dec607210
展望 ● 現状１ステージ完結なので、 メニュー画面を作ったりしてゲームっぽくしたい！ ● タイムアタックとかを作りたい！