クイックソート VS 挿入ソート、ファイッ！

昇順に並べたいクイックソートと降順に並べたい挿入ソートが殴り合う動画です pic.twitter.com/YxsN1aSI0A
— ABA (@abagames) 2020年1月18日

コードとライブデモはこちら。

アルゴリズムの王道ソートアルゴリズムでコードバトリングをしてみたかったので作った。左（赤）のコードが昇順に、右（青）のコードが降順に同一の配列をソートしようとして戦う。昇順に揃ったら左の勝ち、降順に揃ったら右の勝ち。

コードは普通のJavaScriptとして書く。以下の2つの特殊な関数がある。

get(i): 配列からi番目の要素を取得する
swap(i, j): 配列のi番目とj番目の要素を交換する

setはできない。setを許すとコード内のメモリに配列を逃しておいてソート、一気に書き込むというインチキができるから。右の降順側のgetは要素のマイナスの値が帰ってくるので、右のコードもアルゴリズム自体は昇順にするものを書けば良い。

コードは左と右で交互に実行する。実行はJS-Interpreterのstep()で行う。

コードはなるべく実行速度が速く、頻繁にswapして配列をかきまわせる方が強い。速度はJS-Interpreterのstep()の解釈粒度に依存するが、コードがコンパクトな方がもちろん速い。

クイックソートと挿入ソートだと挿入ソートの方が圧倒的にコンパクトで、配列の長さが10くらいだとその実行速度でクイックソートを圧倒して勝つことが多い。配列が長くなると多分勝敗は変わってくるんだろうけど、試していない。

ソートアルゴリズムは別のアルゴリズムが配列をいじるなんてことは想定していないので、実行が終わった時点でちゃんとソートされている保証は無い。なので実行が終わったあとは実行状態をリセットして再度実行される。クイックソートは実装によっては外部から配列をいじられると配列のバウンダリを超えた操作が発生してエラーになることもある。その場合も再実行。

で、これがちゃんとしたゲームとして成り立つかというと、どうだろう。このアルゴリズムがこのアルゴリズムに強い、みたいな三すくみ的な面白さがあるかというと、微妙だ。あとは相手方向に揃いそうだったら積極的に崩す、とかいう防御的仕組みを入れたバトリング向け特殊ソートアルゴリズムが強かったりするなら面白そうなんだけど、そういった工夫をする余地があるかなあ。

2019-08-02

いい感じのビジュアルをランダムになんとなく作り出す

なにかを作った。めざせジェネレーティブアートジェネレータ！

クリック／タップで別の絵を作ります。

この手のものの難しさは、

>RT
ランダムにものを作ると自由度と打率のトレードオフになると思うんですが、この自由度でこの打率はかなりすごい気がします……
しかもパラメータがURLに埋め込まれている！（例 https://t.co/w4Ov3PXkY7 ）
しかも p5.js + TypeScript！
— FAL @STG制作とプログラミングお絵かき (@falworks_ja) 2019年7月30日

という具合に自由度を高くしていろんなバリエーションを作ろうとすると見てて面白いものができあがる打率が減って、逆に打率を上げようと面白くなさそうなものをフィルタリングしていくと自由度が低くなること。

自由度を高くするにはランダムにするものを増やせばいい。今回は座標と線の太さと色を表す数式を乱数で作った。といってもあまりに適当にすると打率が下がるから、

パラメトリック方程式

この辺に出てくる数式をぐっとにらんでよく使われてそうな関数を適当にチョイスする。今回は

a + b, a - b, a * b, a / b, 
sin(a), cos(a), exp(a), pow(a, b), noise(a), 
a > b ? c : d

を使った。noiseはp5.js組み込みのパーリンノイズ。あと、sinとcosはパラメトリック方程式に頻出しているような印象があるので多少出現頻度を上げる。

a, b, c, dのところには、

上記関数を再帰的に、ただし再帰が深くなるにつれ抑制する
開始からの秒数を表す変数t
先頭から何番目の点であるかを表す変数i
2から10のランダム整数aまたはb

のどれかを当てはめる。これで簡単にランダムな数式が作れる。

この数式をつかって点のX/Y座標、線の太さ、色（HSB）を算出する。点は10～100個用意し、その間を線でつなぐ。

あとX/Y座標の数式のパターンとして、X座標のsin, cosをcos, sinに入れ替えてY座標の数式とするという小細工を半分の確率でする。数式を作っているコードは以下。

formula.ts

打率を制御するのは難しい。面白いかどうかはコンピュータには分からないから。

まあでも画面に何も写っていないのは面白くないだろう。なので数式から出る数値を多少いじる。

X/Y座標、線の太さ、色の各点の数値の最小値と最大値を記録しておいて、それら数値が所望の範囲に収まるように補正する。X/Y座標は画面サイズの横／縦のピクセル数、先の太さは画面サイズの1/8くらいまで、色を表すHSBは0～360, 50～100, 50～100に。以下のコードのformulaRangesを使ってその辺の調整をしている。

main.ts

それ以外の調整はしてない。あとはひたすらクリック。なので現状たまに面白いビジュアルが出るのは、たまたまだね。たまたま出た面白パターンをGitHubのREADMEに置いてある。

https://github.com/abagames/folmura

こうやって何かを作る手法を、個人的にガチャ指向プログラミングと呼んでいる。ランダムに絵や音やレベルやゲームが出てくる仕組みを作って、あとはひたすら面白いものが出るまでガチャを引き続ける。プログラムを書くことなくいろんなバリエーションを得ることができるから最高に楽だ。問題は、そのガチャの仕組みを作るのが楽じゃないところだね。というかこれはプログラムパラダイムではないね。

2019-05-02

マップを書くだけでゲームが作れる環境が欲しかった

ので、テキストでタイルマップを書くとゲームになるrj-10ってのを作った。ブラウザで遊べる。

rj-10 screenshot

これを作ろうと思ったのはPix64っていうファンタジーコンソールを見つけたから。Pix64は画像1枚を描くだけでゲームが作れる。ピクセルの色がプレイヤーとか敵とかの種別を決めているのと、矢印状のパターンを書くと矢印の方向にパターンが進むというルールを使ってゲームを作る。

Pix64 screenshot

画像を描くのすら面倒な私は単にテキストを使うことにした。以下のようなテキストを書くと、

-----------
|  v   v o|
   r   r g
|         |
|         |
|         |
|@   ^    |
 c   r
-----------

以下のゲームになる。

lv3

テキストは基本レベルのタイルマップを表しているけど、途中のrとかgとかだけからなる列は特殊で、その上の列のテキストに色を付ける働きをする（redとgreen）。

いくつかルールがある。

色が付いたテキストはアクター（ゲーム内オブジェクト）になる
cyan, blueはプレイヤー、red, purpleは敵、yellow, greenはゴール、grayは壁
プレイヤーがゴールに到達するか、ゴールが無い場合は10秒敵を避ければ勝ち
アクター内のキャラクタがアクターの動作を規定する
@のキャラクタは矢印キーで操作可能
^Z>nvz<Nのキャラクタは向いている方向に進み、-|/\にぶつかると反射
RLのキャラクタは右／左手法で壁沿いに進む
Fのキャラクタは隣接する別のアクターを一定時間ごとに発射する
同色の隣接するテキストは一つのアクターになる
sfに隣接するキャラクタはその動作が遅く／速くなる

これらを駆使すると、

謎の跳ねながら実を落とす木、

lv6

かろうじてシューティングゲーム、

lv8

フラッピ鳥めいたなにか、

lv13

などを作ることができる。

まあほぼレベルエディタなんだけど、ルールを駆使することによって、ちょっと毛色の違ったレベルを作ることもできるので、かろうじてゲーム開発環境と呼べなくもない、のか？

こういったタイルマップを描くことでゲームを作れる環境って他にどんなのがあるんだろう。タイルマップのエディタが備わっているゲームはいにしえの倉庫番とかからあるけれど、

Sokoban

これはやはりレベルエディタそのもので、ルールの違う別のゲームを作れる感じはしない。

ロードランナーとか、

Lode_Runner

レベルによってパズル寄りだったりアクションゲーム寄りだったりするタイプのゲームだと、ちょっとゲームを作っている感じが出てくる。

この手のもので一番進んでいるのはスーパーマリオメーカーかなあ。

Super_mario_maker

スーパーマリオメーカーは膨大なキャラクタ＋その組み合わせを用意することでありとあらゆるギミックを可能にしている。

〇〇とisと××を組み合わせるパズルゲームであるBaba Is Youも、

Baba_is_you

レベルエディタができたらかなりのバリエーションが作れそう。これも××のバリエーションがかなりある。

作れるものの柔軟性で考えればマインクラフトのレッドストーン回路とか、Factorioの運送ネットワークとかはかなり複雑なギミックも作れるんだろうけど、あまりゲーム作り向きではなさそうな印象を受ける。

個人的な理想は、キャラクタそのもののバリエーションは最小だけど、それらの組み合わせかたは柔軟で、いろんな種類のゲームを簡単に作ることができるタイルマップ型エディタなんだけど、なかなか見つけられない。そういう感じのゲームや開発環境、どこかにありませんかね。

2018-09-14

理想のマイコン機械語開発環境を夢見て

PC-6001やMSXの機械語開発時代にREPL (Read-Eval-Print Loop)環境があったらという妄想のもと、Z80のREPLを作った。

ブラウザ上でZ80 ニーモニックを実行できるREPL。実用性は無い。LDIRがメモリを埋める様子がたまらん人向け https://t.co/Q3lLMNn7Cq pic.twitter.com/Y2r2QzYO7H
— ABA (@abagames) 2018年9月8日

ブラウザ上で遊べる。

ソースはGitHubのabagames/z80-replに置いた。

コマンドラインからZ80 ニーモニックを書いてEnterを押せば、それが機械語に変換されてPC（プログラムカウンタ）が指すメモリに書き込まれ、そのまま実行される。実行結果は画面上のメモリマップやレジスタリストに反映される。すぐJR -2とかいう悪さをする人がいるかもしれんが、64回ループを回った時点で一時停止する。Enterを単に押せば現在のPC上の機械語がそのまま実行される。ブラウザから開いてそのまま連打すればNOP, NOP, NOPだ。TABを押せばニーモニックの候補も出る。レジスタを直接操作する手段はないので適宜LD、PCを操作する手段も無いので適宜JPすること。

ツイートに書いたように多分これ単体ではあまり実用性はなく、アセンブラのエディタの脇でChrome DevToolsかのようにこのREPLが開いて、動作検証ができるようになっていれば、当時相当楽できたのではないかと思える。ブレークポイントなどのデバッガ機能と統合されていればなお良い。

実際の当時の機械語開発環境といえば、ハンドアセンブルだ。ノートとかにニーモニックを鉛筆で書いて、

LD DE,D0H
LD HL,80H
LD BC,0AH
LDIR
RET

インストラクションセット表を見ながら機械語に手で変換し、BASICのDATA文として書く。

1000 DATA 11,D0,00,21,80,00,01,0A,00,ED,BD,C9,//

DATAを読み取りPOKEで書き込み、EXECだ。

10 RESTORE 1000
20 A=&HE000
30 READ V$
40 IF V$="//" THEN 70
50 POKE A,VAL("&H"+V$)
60 A=A+1:GOTO 30
70 EXEC &HE000

MSX-DOS時代はアセンブラがあったからまだだいぶマシだが、それでも前記のJR -2のようなコードが混入した時点でコードは暴走、プログラムはおしゃかだ。マイコンをリセットし、テープからプログラムを読み直さないといけない。

これらの時代と比べれば今はChrome DevToolsのような超高度なREPL、デバッガ、プロファイラが付いてくるのが当たり前で、とてもいい時代になったものだ。でもたまに昔のアセンブラやBASICを思い出して古き良き時代を思い出したくなることもある。そういったノスタルジーを簡単にちょっとだけ満たすためのツールでした。ノスタルジーを通り越して現役の血が蘇った人は組み込み勢やレトロPC現役開発勢になだれ込むと良いかと思います。

2018-03-07

256文字ゲームくらいならコンピュータが作って欲しい

最近作った256文字ゲームを見ながらこんくらいコンピュータ様が自動的に作ってくれないかと思っている https://t.co/JeRvlRwzqc
— ABA (@abagames) 2018年3月6日

あとは2つのゲームのメカニズムを適当に混ぜ合せるっていうアプローチもあるけど、混ぜてゲームとして成り立つ組み合わせってほとんど無いのではという気もする
— ABA (@abagames) 2018年3月6日

でも物によっては混ぜられないこともない。

例えば

f:id:ABA:20180307173815g:plain

と

f:id:ABA:20180307174036g:plain

を混ぜて

f:id:ABA:20180307174059g:plain

というゲームにしたり、

これ

f:id:ABA:20180307174158g:plain

と

f:id:ABA:20180307174213g:plain

を混ぜて

f:id:ABA:20180307174231g:plain

というゲームにしたり、だ。

混ぜ方としては、ゲームを2つのパーツに分ける。マウス操作が反映されるプレイヤー側パーツと、それ以外の物を動かすパーツ。で、2つのゲーム間でそれらを入れ替える。そうするとたまに新しいゲームになる。

もちろんうまくいかないパターンの方が多くて、

f:id:ABA:20180307174249g:plain

と

f:id:ABA:20180307174306g:plain

を混ぜると

f:id:ABA:20180307174330g:plain

車が無限に落ちる虚しいゲームができる。

こういう混ぜ方でうまくいくのは古典的な避けゲーくらいな気もする。プレイヤーの動作と障害物の動作のバリエーションで新しいゲームを作る。でもそれは避けゲーのステージバリエーション的なもので、新しいゲームと呼ぶのは厳しい気もする。あと動作自体のバリエーションを新しく生成することもできない。

前途多難である。

2018-03-03

JavaScript256文字でのゲーム作り

Tiny Art in Less Than 280 Characters

ggplot2で280文字以内で作られた美しい幾何学模様。

sc140

SuperColliderで140文字以内で作られた楽曲群。

Dwitter

JavaScript140文字以内でできた作品集。

短いコードで作られた作品は情報がギュッと詰まった感じが美しい。最低限の構成要素で最大限の効果を得る工夫が詰め込まれている。

グラフィックスや音楽だけでなくて、ゲームでも同じように短いコードで書けるといいな、と思っていたらDwitter上の以下の作品を紹介してもらった。

Crossy tortoise

クロスハイウェイならぬクロスかめ。ワンキーゲームを140字で実現しているのがすごい。でもスコアは無くて一度渡りきったらそこで終わりという潔い作り。

ゲームを名乗るからには以下の要素は入れたい。

スコアがある
ゲームオーバーがある
難度が上昇する
できれば音も鳴る

と思ったときのショートコーディング向けの妥当なレギュレーションはどんなもんだろう、ということを考えてみた。

JavaScript256文字以内で毎フレームのアップデート用関数を書く
p5.jsの関数を使って良い。あとTone.jsとlodash.rangeをライブラリとして導入
p5.mouseIsPressed, p5.mouseX, p5.mouseY, p5.random(), Tone.synth.triggerAttackRelease(), _.range()に1文字のエイリアスを与える
Sにスコアを入れると画面上部に表示、Tを参照すると経過フレーム数が分かるでそれで難度調整

このレギュレーションに沿った開発環境とサンプルを以下のリポジトリに置いた。

jsgame256

サンプルゲームの一つ、クリックでジャンプするゲームspringcar。

springcar

clear(),T||(s=A(9).map(i=>[10*i]),y=v=0),d=1+T/999,s.map(u=>text("🔩",u[0]=u[0]<99?u[0]+d:-R(30),80)),y+=v+=(M?.1:.2)*d,get(74,y)[3]+get(82,y)[3]>0&&(v=-1,y=72,S++,N(333,.1)),y>70&&v<1&&M&&(v=-3,N(444,.2)),y>95&&(S=y=T=0,N(222,.5)),text("🚗",75,y)

まあガチ勢から見るとユルユルである。バリバリにコードゴルフ頑張ります！、みたいな感じではなくて、256文字という制約があるからこんくらいのゲームしか作れないんだよねー困ったなー今回はこれで許して、的なノリである。

ガチ勢は一切の余計なライブラリを許さずJavaScriptを含むHTML全体のバイト数226バイトのポンを作ったりする。codegolf JSあたりを参照すると楽しい。

今回は楽して短いブラウザゲームを作ろうというノリなので、ビルドツール側でもいろいろと工夫した。

REPL screenshot

uglify-esを使って自動的にコード短縮
webpack-dev-middlewareを使ったdev serverを作って、ライブリロード時に自動的にuglify、現在のコードが短縮時に何文字になるかを表示
前に作ったREPL環境を導入するとともに、REPLから'//b'と入力するとビルド、単一のHTMLファイルをビルド結果として出力。ついでにその時のスクリーンショットをTwitter カードのイメージ用にも作成

uglifyは優秀でJavaScriptの一般的なショートコーディングテクニックは勝手にやってくれるのでチマチマしたところは工夫しなくて良くなる。人間はデータ管理の工夫とか重複データのコード上の重ね合わせとかもう少し広いコンテクストでの短縮を頑張れば良い。

このレギュレーションと開発環境ならばだいたい1時間くらいでなんらかのゲームを作ることはできる。もちろん256文字の制約は厳しくてちょっと凝った動きを実装しようとするとあっという間に文字数があふれる。あとellipseとか名前の長い関数を使うのがキツイ。配列とmapは神機能。

270文字くらいのゲームができたときが悲しくて、小手先のテクニックでは縮めきれないのでゲームシステムの方を縮小しなければいけないことがある。せっかく作ったのに。まあでも256文字制約が無いと無限に演出を付けられるしゲームバランスもいじり放題になるし、それらを諦めるための縛りなのだから悲しくても捨てることだ。

短時間でアウトプットが得られるという点ではこんくらいの縛りでのゲーム開発はなかなか面白い。まあゲームと呼べるかギリギリみたいなものが出来上がるのでそれで良しとするかみたいなところが微妙ではある。スキマ時間でゲーム開発がどうしてもしたいというゲームデベロップメントジャンキーにはオススメ。

2018-02-17

JavaScript向けブラウザREPLを試作した、けどREPLってゲーム開発に活用できる？

screenshot

前にClojureScriptのREPL駆動開発について書いたけど、REPL駆動開発環境自体は別にClojureScriptじゃなくJavaScript向けにもあるんじゃないか、と思ったけどこれが案外見つからない。なのでちょっと試作した。

browser-repl-test

作るのは別に難しくなくて

webpack-dev-middlewareを使ったdev serverを立ててその横でWebSocketサーバを立てる
ブラウザ側のコードからWebSocketサーバに接続
dev server上からコードを入力、WebSocketでブラウザ側に送ってeval、結果もWebSocketで返す
エディタからコードをdev serverに送るのはSendToREPL VS Code extensionってのがあるのでこれでできる

とやった。

で、ここまで作っておいてなんだが、これってゲーム開発に役立つかしらん。REPLはデータの加工をいろんな関数を使って試していってうまく行ったパターンをソースコードに落とす、みたいな使い方が普通だと思う。けどゲームにおいては1/60秒ごとのフレームでどんどん更新されるデータが検証対象であって、この関数を適用すると次はどうなる、みたいな確認を単体で行ってもあまり意味が無いことが多い。

結局複数フレームでの更新を追う必要があるのであれば、REPLじゃなくて十分に速いライブリロードがあって、ソースコードを変更するたびにすぐにその動作を確認できれば十分じゃないか、という気がしている。これは関数型言語とかの他の言語を使ったとしてもあまり変わらないんじゃないかと。

なにかゲーム開発でREPLをこう活用していますというベストプラクティスがどこかに落ちてないかしらん。