mieki256's diary

道路の自動生成アルゴリズムのヒントになりそうな何かが無いかとググっていたら、以下の動画に遭遇した。

_Creating Infinite Road For My Drifting Game (last time I swear) - Drifto Devlog - YouTube

無限に続く道路を生成する一例、とのことだけど、なるほどそういう手もあったかと目から鱗が落ちた。完全に道路の全てを自動生成するわけではなく、ブロック単位で事前に道路とその周辺を作っておいて、そのブロックを並べて道路を生成するらしい。

考えてみたらDAWソフトを使って波形データを並べて楽曲を作っていくソレに近いのかもしれない…？ 波形データ一つ一つは事前に何かしらで作ってあるものとする、みたいな。

ただ、道路ブロックを繋げていくうちに、今まで引いてきた道路とどこかでぶつかったり交差してしまう問題が発生するわけで…。前述の動画では、事前に道路ブロックを何個か試しに並べてみて、どこかでぶつかって行き止まりになったら前の位置に戻って別方向に進んでみる、という手順で解決しているらしいけど…。

コメント欄の中に、迷路生成と探索で解決するかも、という書き込みがあったような気がしたので、それってどういうことなんだろうと、迷路生成その他のアルゴリズムをググってみた。

以下のページが分かりやすそうな気がする。

_迷路の生成と自動探索をしてみました |ブログ|京都・滋賀・のシステム開発Auto-IDフロンティア株式会社
_Algoful - アルゴリズム初心者向けの基礎と入門(C#, Pythonとか)

たしかに、生成した迷路に対して自動探索して求めたルートは、それまで引いたルートとはぶつかったり交差していないように見える。この方法でもイケるのだろうか…？ 考えてみたら、前述の動画内で使われていた解決策は深さ優先対策の処理と似ている気もする…。

それはともかく。グリッド上でルートを作っていく方法では、任意の角度で道路を作れない気もする。緩やかなカーブと急なカーブの違いを表現できなかったりしないか…？