GPUとセルオートマトンで経路探索問題を解いてみる | POSTD

前回は、グラフィックカード上だけで コンウェイのライフゲームを実行するアイデアを説明しました 。このアイデアは、3つ以上の状態を有するオートマトンを含め、 どのような セルオートマトンにも当てはめることができます。今回の投稿では、二次元グリッドの 最短経路問題 をGPUだけで解決するのに、このアイデアを活用してみたいと思います。CPUによる従来の検索と比べても、その速さは遜色ありません。 JavaScript側の状態は基本的に以前と同様なので（2つのテクスチャと、それらを繋いでオートマトンを次のステップに進めるフラグメントシェーダ）、ここでは説明は割愛します。変更したのは次の2点、（オートマトンの全ての状態を表現する）セルの状態のエンコーディングと（新しいルールをプログラムする）フラグメントシェーダです。 オンラインデモ （ ソース ） デバッグや実験のために使ったセルオートマトンの純粋な

[hcnkino]

第２回全国小中学生プログラミング大会　蓼沼諒也君　「僕のドラえもん」グランプリ

[boxheadroom]

翻訳されてたー

[piro_suke]

GPUとセルオートマトンで経路探索問題を解いてみる | プログラミング | POSTD

[banana-umai]

GPUとセルオートマトンで経路探索問題を解いてみる | プログラミング | POSTD

[Untouchable]

WebGLでGPGPUする。並列コンピューティングを体験するにはライフゲームなどセルオートマトン系はちょうど良さそうな課題だ

[bleu-bleut]

1. 一つしか白の隣を持たない白を塗りつぶしていくと経路が見つかるが、ループなどがある場合最短経路とは限らない。 2. スタート地点から元来た方向を示す矢印をつけながら塗りつぶしていくと最短経路が見つかる。

[endo_5501]

すげえ！

[roomba]

その発想はなかった

[doublehorn93]

GPUとセルオートマトンで経路探索問題を解いてみる

[y___u]

GPU方面は割と変態的な世界だと思ってたし実際変態で、原理は理解できてもGPU上での処理が想像つかない。シェーダがセルオートマトンとして振る舞うってこと…？