awkで実装されたFPS 40
ストーリー by hylom
正直スゴイ 部門より
正直スゴイ 部門より
route127 曰く、
awk(gawk 4.0以上)で実装されたというシューティング(FPS)ゲーム「awkasterが話題になっている(awkで作られた3Dシューティングゲーム「awkaster」が凄い)。
記事中にもあるようにレイキャスティング法を用いているそうなのだが、レイトレーシングとの違いや647行で実装できるものなのか等スラド諸兄に聞いてみたい。
レイキャスティング (スコア:3, 参考になる)
レイキャスティングと言っても、タレコミのリンク先にあるような本格的なものじゃなく、Wolfenstein 3Dと同じ方式ですね。
Ray-Casting Tutorial [permadi.com]
(英語ですが、分かりやすい内容です)
このタイプでは、視線追跡に1次元(2次元マップ中にいるため)しか必要ありません。
(壁の高さは、距離から計算で求められる)
かつ、壁にぶつかった時点で追跡を打ち切っていますので(透過・反射なし)、計算量はさほど大きくならないはず。
注目すべきは入力処理 (スコア:1)
ascii 文字による描画なんてアルゴリズムにしたがって計算して
エスケープシーケンスを投げまくればいいだけなんだから、
その気になれば awk だろうが sh だろうが brainfuck だってできる。
わざわざ awk でそれをやるんか、というだけで、別にすごくはない。
こいつのすごいところは、行単位でしか入力を読み取ることができない仕様の
awk で実装されてるのに、キーボードからの入力をリアルタイムで
読み取ってるということなんだよ。
どうやって実装してるんだこれ、とコードを確認したら、
…うん、ぜんぜんすごくなかった。
awk でできないから外部コマンドに丸投げしてるだけ。
Re:注目すべきは入力処理 (スコア:2, すばらしい洞察)
「awk内部でなんでもできるもん」という言語を作ろうとしたらperlになっちゃったわけで、awkのプログラムが外部コマンドにおんぶにだっこなのは仕方ないんじゃ・・・。
Re: (スコア:0)
まあケチつけることに関しては、スラド民の右に出るものなしということで。
Re: (スコア:0)
ま、まぁ、こうなるわな…
Re: (スコア:0)
これをスゴイと思った人は何をどうスゴイと思ったのかちょっと興味があるな
awkはワンライナーしか書けないとか、もっとずっと遅いというイメージがあったとか?
Re: (スコア:0)
コード読めない人には魔法に見えるんじゃないっすか?
一番単純な実装だとこうだろうなぁ…でもすごいって言ってるからなんか違うのがあるのかも?
とかちょっと期待したのが悲しくなった
Re: (スコア:0)
awkって遅いかな?
単純な処理ならperlよりずっと速かったりして便利だった記憶があるけど
Re: (スコア:0)
思いついたことをとりあえずやってみる能力ですね。
大抵の人は、まずやらない言い訳を考えようとしますから。
Re: (スコア:0)
同人ソフトはおしなべて「思いついたことをとりあえずやってみた」産物ですが、いちいちスゴイとは言って回りませんよね
Re: (スコア:0)
やる気になれない、向かないことをあえてやった点が凄いのかと。
♯実験的にやるならいいけど、仕事ではイヤな部類。
Re: (スコア:0)
>awk でできないから外部コマンドに丸投げしてるだけ。
それはそれでawk的には正しいやり方に思えるが。
激走ラビリンス (スコア:0)
MSXの激走ラビリンスみたいやね
見た感じレイキャスティングとか言うの必要か?コレ
実質2次元に見えるので、左右でスィープして遠いところは短い棒、
近いところは長い棒を書けばこんな感じに表示できるっしょ
会社の研修の時にCASLでこんな感じの作ったわ
レイキャスティング法 (スコア:5, 参考になる)
紛らわしいのですが、
ストーリーに掲げられているリンク先で説明されている「レイキャスティング法」は、
ボリュームレンダリングを行うアルゴリズムの一つで、
一言で説明すれば「レイトレーシングを使ってボリュームを描画する」というものです。
例えば、「半減距離1000の半透明ボリュームを、レイが長さ500だけ横切った」場合には、
「そのボリュームの色を25%、そのボリュームの先にレイを飛ばして得た色を75%、ミックスした色」が
そのレイで得られる色になるってことです。でも、それは今回のストーリーとは関係ありません。
一方、FPSに使われている「レイキャスティング法」は、上記のボリュームレンダリングにおける「レイキャスティング」とはちょっと別物。
3Dダンジョンなどの「垂直な壁しかない空間」という状況限定で、非常に高速にレンダリングできる、というDOOM時代のFPSに使われた技術です。
一言で説明すれば、「中央部の水平1ラインだけレイトレーシングを行い、どの壁が見えるか判定」し、「その壁までの距離とその壁の高さに応じた長さの縦線を描画」するというものです。
> 左右でスィープして遠いところは短い棒、近いところは長い棒を書けばこんな感じに表示できるっしょ
それがまさに「レイキャスティング法」です。
Re:レイキャスティング法 (スコア:2)
説明が微妙に間違っていると思います
まず光線に沿って空間を走査する方法を
レイキャスティング法やレイトレーシング法と呼びます
https://en.wikipedia.org/wiki/Ray_casting [wikipedia.org]
呼び方が2つあるのは,
光線(Ray)を空間に飛ばす(cast)と捉えればレイキャスティング(ray casting)
光線で空間を走査する(trace)と捉えると レイトレーシング(ray tracing)と呼ばれるからです.やっていることは同じです
この方法を使って
コンピュータグラフィックスの分野では,ボリュームレンダリングという処理を実現するアルゴリズム
ゲームの分野では,FPS用のマップ表示アルゴリズム
が考案されています
つまり,前者は形状データを含む空間を光線で走査していて,
後者は壁で構成されたマップを含む空間を光線で走査していることになりますが
やっていることは大差ありません.
たとえば,前者のボリュームレンダリングの特殊な場合,
つまり空間が2Dで,半透明の壁が無くて,かつその空間を水平に走査する場合のアルゴリズムを考えると
それはDOOM時代のFPSのアルゴリズムと同じものになります.
Re:レイキャスティング法 (スコア:1)
一般的には
レイキャスティング(広義): レイ(光線)と物体などと交差判定を行うという3次元処理についての一般用語。
レイキャスティング(狭義): 画面の画素ごとに「視点から物体に向けて」レイを飛ばすことで隠面消去を行う、レンダリング(3D空間の2D画像生成)アルゴリズム。論文発表は1968年。
レイトレーシング: レイキャスティング(狭義)を拡張したレンダリングアルゴリズム。論文発表は1979年。レイキャスティング(狭義)では、画素ごとに1本のレイを飛ばすだけですが、反射・屈折・影などで再帰的にレイを増やすことで、よりリアルな画像生成ができます。反射屈折のないレイトレーシングはレイキャスティング(狭義)と同じなので、レイキャステイング(狭義)と同一視されることがある。
レイキャスティング(ボリューム): レイトレーシングを用いたボリュームレンダリングアルゴリズム。正しくはボリュームレイキャスティング法 [wikipedia.org]という名前になりますが、ボリュームレンダリング業界では「レイキャスティング」とだけ呼ばれる場合が多いです。
レイキャスティング(FPS): レイキャステイング(広義)を利用した「垂直な壁と水平な床しかない」という限定状況での高速レンダリングアルゴリズム。このアルゴリズムのキモはレイキャスティング(広義)を使っていることではなく「水平方向1ラインの最近面判定だけで2次元描画できる」という点。特にアルゴリズム名は付いてないため「レイキャスティング」と呼ばれる場合が多い。
という感じになるかと。
「レイキャスティング(狭義)」「レイキャステイング(ボリューム)」「レイキャスティング(FPS)」は、どれも「レイキャスティング(広義)」の応用ですが、それぞれのアルゴリズムのキモとなる部分は全然別。
以上を踏まえた上で、
ストーリー本文で、「レイキャスティング(ボリューム)」のページを参照してレイトレとの違いを疑問に思っているし、
親コメントでは「レイキャステイング法なんか使わなくても…」と言いながら、その後に「レイキャスティング(FPS)」のアルゴリズムについて説明をしてたりするんですから、
それがどれも「レイキャスティング(広義)」に属するアルゴリズムだからといって「やっていることは大差ありません」なんて書いてもなんの意味もないでしょう。
そこで、その差の部分について強調して言及したのが元コメントになります。細かい不正確さがあるのは覚悟の上。
Re: (スコア:0)
リンク先が同発音別用語とは思わんかったわ
Wolfenstein とかdoomも同じやったんやね、
まぁテクスチャ貼るだけやしな…
Re: (スコア:0)
原理は同じだから同じ名前になっちゃうんじゃね
Re: (スコア:0)
3Dダンジョンなどの「垂直な壁しかない空間」という状況限定で、非常に高速にレンダリングできる、というDOOM時代のFPSに使われた技術です。
一言で説明すれば、「中央部の水平1ラインだけレイトレーシングを行い、どの壁が見えるか判定」し、「その壁までの距離とその壁の高さに応じた長さの縦線を描画」するというものです。
DOOMって階段とか段差とかあったからそれだけじゃ描画できないよ。
Re: (スコア:0)
中央部と、段差のある部分に言い換えればOK
水平でない階段や段差はなかったでしょ
Re: (スコア:0)
その辺りの、不可能なはずだったことを、可能にしていく進歩あれこれが熱い時代だった。
レイキャストも壁のデータの持たせ方を工夫して、とかいろいろ解説されてた。
現在も続く、GPUをぶん回してよりかっこいいCGをレンダリングするための計算テク開発競争の走り。
Re: (スコア:0)
中央部と、段差のある部分に言い換えればOK
ちょっと何言ってるのかわからんですね。
Re: (スコア:0)
> 中央部の水平1ラインだけレイトレーシングを行い
段差が1段なら床が2面(水平)に段差の面(垂直)が1つだからそれぞれサンプルして3ラインをレイトレする
段差が床と平行でないならこうはいかないが
Re: (スコア:0)
段差が1段なら床が2面(水平)に段差の面(垂直)が1つだからそれぞれサンプルして3ラインをレイトレする
DOOM知らないということは分かった。
Re: (スコア:0)
激走ラビリンスってのは知らないけど、
wolfenstein 3dに見えた。
Re: (スコア:0)
プチコンでやってる方もいますね。
プチコンに激走ラビリンスを移植してみた [nicovideo.jp]
Re: (スコア:0)
SeeNaを思い出した
https://www.youtube.com/watch?v=cZKx6vbvy84 [youtube.com]
Re: (スコア:0)
WAYOUT [youtube.com]思い出した
Re: (スコア:0)
P6スペハリ(ry
https://www.youtube.com/watch?v=cpLFLWAoxvM [youtube.com]
Re: (スコア:0)
フッ、MZ-700版スペハリ [youtube.com]の滑らかさにはかないませんな。やはりMZ-700に不可能は(ry
Re: (スコア:0)
フッ、MZ-700版スペハリ [youtube.com]の滑らかさにはかないませんな。
節穴?
https://www.youtube.com/watch?v=_WYEpH-bKDs [youtube.com]
Re: (スコア:0)
FPSというよりダンジョンゲームに近い気がしますが…
https://www.youtube.com/watch?v=364J35Sk3zM [youtube.com]
Re: (スコア:0)
FPSって何の略か知ってる?
Re: (スコア:0)
一人称視点射撃遊戯。射撃要素が無いのならSは何になるだろ?
時は流れて (スコア:0)
Z-80 4MHz RAM 64kB の時代から
CPU は GHz RAM は 1GB超 なんだよなぁ。
Z-80 シミュレータを書いて1命令1000stepかけても Z-80 2MHz で
動くんだよなぁ。
Re: (スコア:0)
そうだね。
ときにPC-E200?それともAKI-80?
Re: (スコア:0)
システム全部がCPU内部キャッシュに入りますね
Re: (スコア:0)
Z80ってのIPCって1でしたっけ
Re: (スコア:0)
そういえば最低4サイクルじゃなかったっけ? IXとかいじるので最大20くらいだった気がします。
Re: (スコア:0)
最速のNOPでも4サイクル必要だったね