コミュニティアイコン プチコン 非公式コミュニティ プレイ日記

アバター
はる ◆75Vh4SY8TdKS
2019/1/14 19:37
http://twttr.com/!/status/1084776412853108737


迷路を棒倒し法で自動生成して、
それをA*アルゴリズムで自動で解くプログラムを作りました。

公開キー【H3RX1D】
短い公開キー取得。やったぜ。

コメント

アバター
はる 2019/1/14 19:40 ◆75Vh4SY8TdKS
このプログラムは3号とBIGの両方に対応しています。

小さくて見えないかもしれませんが青い点がありそこがスタートです。
青い点から赤い点を目指して緑が探索します。
複数の道を同時に探索したりなど、
普通の迷路ではありえない動きをしますが、
壁を飛び越えたりはしていないので迷路のルールには従っているはず。
(画像は探索が赤い点に達して探索が終了したものです)
遊び方はそれを眺めるだけです。
結構面白い動きをします。

たった2日で作ったものですがダウンロードして下さるとうれしいです。
アバター
こういち 2019/1/14 20:00 ◆ou0jbJnEJ0Kb
棒倒しって迷路の品質はともかく速度が魅力的なんだよな。(逆にUnionFindは品質高くて速度遅い)
A*もゴールまでの道のりを求めるだけならbfsより速いから気になる。
(UnionFindで生成してbfsで解いた人)
アバター
はやピー 2019/1/14 20:06 ◆WUk.BW.kE3Qp
おおー
アバター
Soybeanman 2019/1/14 21:01 ◆SDLkyXUP6WqK
私も似たようなのを公開していました。
[QDF5XXAD]
何故か漢字だけで表現されています。
アバター
はる 2019/1/14 21:02 ◆75Vh4SY8TdKS
こういちさん

確かに棒倒し法は速度が速いですね。
自分はめんどくさいから棒倒し法にしただけですが。


はやピーさん

ありがとうございます。


Soybeanmanさん

漢字だけってなんだろうと思ってダウンロードしました。
これはすごいですね。
アバター
KNTK 2019/1/15 16:15 ◆.O1reuuyjCCS
右手法という古い方法のプログラムしか組んだことの無い人←
それだとループするところがあったら無理だし、エースターってすごい。
アバター
はる 2019/1/15 17:41 ◆75Vh4SY8TdKS
A*アルゴリズムは迷路以外でも最短経路を求めるのに使えます。
これを使えば壁があってもそれを避けて追っかけてくる敵とか作れそう。
アバター
こういち 2019/5/24 8:24 ◆ou0jbJnEJ0Kb
迷路とか辺に重みが無い場合A*とbfsってどっちが速いのか気になる。
計算量的にはbfsの方が速いけど(A*はO((E+V)log(V)),bfsはO(V)合ってる自信はない)、A*は全部の辺を調べなくてもいい(=定数倍軽い)から速そう。
アバター
はる 2019/5/24 9:38 ◆75Vh4SY8TdKS
↖全然話についていけない人

コメントを書く

この投稿にはコメントできません。

- WEB PATIO -