「元に戻す」のしくみ 【ゲーム・プログラミング】【JavaScriptサンプル】
Вставка
- Опубліковано 21 лип 2024
- 意外と作る機会が多い「元に戻す」機能をどうプログラミングするかを、数学を用いてシンプルに作ります。なるべく直感的に理解できるよう編集しています。
■サンプルプログラム（JavaScript、インストール不要）
editor.p5js.org/AosagiHeron/s...
※デバッグツールを使いたいときはこちら
editor.p5js.org/AosagiHeron/p...
■もくじ
00:00 ごあいさつ
01:08 愚直な（よくある）やり方
02:06 関数を合成していくやり方
03:48 サンプルについて、デバッグツール(dev tool)について
07:40 おわりに
■ライセンス Licenses
- Gray Heron photo
Photo by Denise Duplinski from Pexels
/ dduplinski
ゲーム以外でも応用できそうですね
参考にさせて頂きます！
今回の合成関数、すごく参考になりました！
他にも。こうやれば実は上手くいく、みたいなお話を聞きたいです！
プログラミングに初めて興味を持ちました。ありがとうございます。
おかげで学校に遅刻しました
ポルポトなのに学術的なものに興味を持つな
面白かったです、毎回計算させるんですねー。
これくらいならいいけど戻る時だけ再計算させるとか工夫が入りますね
関数の有用性と単機能にしておく必要性がよくわかりました
似た考え方はEvent Sourcingパターンで理解していましたが、根源的に合成関数まで帰着出来ることに気づかせていただきました。ありがとうございます☺️
自分も踏んだ経験があるのですが、良くある方法は逆関数的な手法であるがゆえにルールによっては実装出来ない事すらありますよね（なんなら今回の倉庫番ですら不可能）
荷物を荷物で押した瞬間、「あっ……」って気づきますよね🐤
趣味で絵を書いててふと気になったのですが、ペイントツールの「乗算」や「オーバーレイ」などの色の計算方法の解説をしていただきたいです！
色のRGBAから有限体かなんかの代数構造を定義して演算を定義してるんでしょうかね？
ほかにも実装法がありそう🤔
各ゲーム状態のログをとったり、
元に戻すための計算を実装したり（アプリによっては元に戻せない状態のことも！？）
画像編集ソフトとかどうやってるんだろう
数学的な実装？で面白かったです😊
このイントネーション好き
わかる、なんかこのイントネーションを聞きに来ちゃうｗｗ
「プ↑ログラム」は私も初めて聞きました。どこ出身なんでしょうかね。
ちなみに英語では「プロ↑グラム」です。
「プ↑ログラム」は、もしかしたらここでしか聞けないかもしれません。
これってdrawの度に関数を合成する回数分計算するから、n回まで描画するときO(n^2)かかっちゃいますよね…。ただし、メモはしてないのでメモリはあんまり使いませんけど。
計算量が増えそうだなと思ったけど、大体は戻れる回数に上限持たせるだろうから、最古の状態を初期ステータスに随時置き換えていけば、計算量の上限は一定になるから問題なさそう。勉強になりました。
0:21 真夏の夜の…
「行動(やったこと)」のログをとるのが合成関数、
「状態(行動した後の結果、座標)」のログをとるのが愚直な方法ってことかな？
愚直な計算しか思いつかなかったので本当に目から鱗でした、素晴らしい動画をありがとうございます！！！！
「1つ戻す」機能を呼び出すたびに毎回、初期状態にいったん戻してから
最後の操作の一つ手前までの操作を全部もう一度やり直すってことですよね。
スマートではない気もしますが、実装は簡単・単純・確実ですね。
ソースコードをよく見ると実は「一つ進む」も、毎回、初期状態にいったん戻してから
最後の操作の一つ手前までの操作を全部もう一度やり直しているっぽい。
つまり進むのも戻るのも同じロジックで動いてる。
全てを初期状態からの差分で表してるってことですね。
戻すたびに初期状態からやりなおすようなやり方だともとに戻す操作が激重になるのが予想されるので、
n回関数を適用する度結果を保存しておくんでしょうか。メメントパターンですね
独学でJS入門をやり終えた人にはちょうどいい難易度。なかなかこういう生きた教材はない
どうやって戻すのかの方法も幾つか出て来ると楽しそうな気もします。
イントネーションをイン・トネーションっていう強強エンジニア臭がしますね。
複雑な計算式になってしまった場合、1つ手前の作業に戻す手順を組み込みたいと考えた際にはどうすればいいのでしょう?
1個1個読み込む方法以外にも良い選択肢があるのなら知りたいです。
式が複雑になりすぎる場合は、おそらくその後者の方法が最適ですね🐤
作業を行うごとに状態を全て保存（例えばペイントソフトなら画像をまるごと保存）する感じですね
@@heron-no-suugaku なるほど...ありがとうございます。
これから専門学生として学んでいく身ですので、自分でも調べつつこれからも参考にさせていただきます。m(__)m
「Xする」
「XしてYする」
「XしてYしてZする」
とした状態で、一つ戻すためには「XしてYする」をすればいいのか。
そして、JSのような第一級関数をサポートする言語なら、[X, Y, Z]のような配列を持っておけばいいということか。
「状態」を配列に持つのではなく「関数」を配列に持つってのが面白いです！！
あと個人的に面白いと思ったのはここです！
calculate(funcs) {
let c = this.copy();←ここ！（副作用があることを無視すればわざわざcopyしなくてもよさそう）
for(let f of funcs) {
c = f(c);
}
return c;
}
game = new Game().calculate(inputs); ←new？！
これ状態を保持しているんじゃなくて、実質的には「書き換えられたあとのゲームの状態」を返り値として受け取り、常にそれを自分自身に再代入し続けているってことですよね。世界観が関数型言語チックで目からうろこでした。
動画内では説明がありませんでしたけど、この考えを応用すれば、例えば5手進めたうちの3手目だけを無かったことにする……なんてこともできそうですね。
その場合って3手目が抜けた分元々の4手目が新しい3手目として認識されるみたいに、抜けた3手目以降の手が全体的に一つ繰り下がって、最終的な状態が再計算されるんですかね。
Javascript 触ったことないのでトンチンカンなこと言ってたらすみません...
@@Bird.jp_Love-English-Fixes-plz
その通りかと思います。
私もJSはほとんど触ったことがありませんが、この動画で紹介されている考え方はほぼすべての言語に適用できる内容ですので、その調子でどんどん結果を予想してみると面白いかもしれませんね。
後で調べ直しているうちに分かったのですが、実際、一部の3DCADソフトなどでは手順のうちから任意の操作だけをなかったことにするという機能が存在しているものもあるようです。
なんかめっちゃ重そう
Hi Heron, I am a big fan of you and I really like your content. I also learned a lot of Japanese new words from your channel. However, I think you made a teeny tiny mistake with the thumbnail used for this video. The thumbnail says [fn-1(...(f3(f2(f1(i)))...))]. We usually use the notion [n-1] with zero-based numbering system. But since you used f1 to denote the first function; the last one is supposed to be fn NOT fn-1. I am really sorry, I know this is a useless thing to add to the great content you've made but it is my wat to say I really like you and I really want to see more of your videos ... All the best
thank you, I very appreciate that you pointed out. 🐤
I used n-1 to represent "undo", is this not a good representation?
like below (i = inital state):
current game state:
fn( ... f3(f2(f1(i)))) ... )
undo a time:
fn-1 ( ... f3(f2(f1(i))) ... )
C++でオセロゲームに待った機能を付けたかったけど、合成関数の手法が使えそう？
盤面を別の配列に全部記憶させる方針でいこうとしていたけど、どっちのほうがいいだろうか。
1手戻る機能をつけるだけなら、配列で全部記憶する方が簡単ではありますね
ただ、例えばリプレイ機能をつける場合は、関数合成の方が良いですね
関数合成した式がそのままリプレイデータとなりますし、
式を "黒先攻,e6,f6,c4" みたいな感じに変換すれば、ツイッターとか経由でリプレイデータを共有可能になり、夢が広がります🐤
オセロならいいけど、将棋は殺されるのでやめた方がいいですよ。
Switchのスーファミエミュレータ、巻き戻し機能ってどうやって実現してるのかな…と思ってたけど、この仕組みなのかな。
数秒に一度メモリのスナップショットを取りつつ、それ以外のタイミングではボタン入力だけ保存しておく。そして巻き戻しが呼び出されたらスナップショット時点から超高速でユーザー操作を再現する、と。
いやでもスーファミくらいなら愚直にメモリ内容を毎秒保存した方が簡単なのかな。
操作を記憶する配列を作るから出るバグなので、単に人と荷の座標を記憶する配列をそれぞれ用意すれば良さそう？あくまでこのゲームの場合の話だけど
ただ、これだと空間計算量が無視できなそう
・操作だけを記憶する（空間計算量が最小）
・n歩ごとにキャッシュする（空間/時間計算量のトレードオフ）
・1歩ごとにキャッシュする（時間計算量が最小）
ゲームやアプリによって使い分けるのが良いですね🐤
ありがとうございます！とても参考になります！
ただ、少し気になるのですが、これを実際にゲームに使うとプレイヤーが試行錯誤のために移動した回数分だけの長さで合成関数が作成され、
それが何万ステップともなれば、1歩動くたびにゲームが固まる、というような問題が起きる可能性はないでしょうか？
もちろん、実際に固まるかは処理速度に依存するとは思いますが、どんどん1歩ごとの負荷が高くなるのでは？ということが気になりました！
よければご教示ください。
100歩ごとにキャッシュを作れば、どんなに歩いても0～99回の計算しか要らなくなるので、固まらなくなりますよ🐤
ただしキャッシュはゲームの状態そのものなので、メモリをそこそこ食うという欠点があります（例えばオセロなら8x8の盤面すべてをキャッシュする必要がある）
オセロくらいなら無問題ですが、キャッシュひとつが1GBとかあるゲームだと問題になるかもです
@@heron-no-suugaku なるほど！目から鱗でした！ありがとうございます～！応援しています😍
pythonでも動画をアップしてほしいです！！
Wordなどの編集ソフトは流石にこの手法じゃないよなあ、どうやってるんだろうか
なんか、確率漸化式を思い出した。
この形で書くと毎回初期位置から合成関数を使って現在位置を計算してるから、操作回数が増えれば増えるほど計算量が増大するかと思うんですけど
計算量を抑えるには、戻せる回数に制限を設けて、その都度初期位置を更新すればいいんですかね？
一定回数操作するごとにキャッシュcを作れば、戻せる回数に制限をかけずに、計算回数が増えすぎることを防げますね。
i = 初期状態
c1 = (f3∘f2∘f1)(i)
c2 = (f6∘f5∘f4)(c1)
c3 = (f9∘f8∘f7)(c2)
……という具合です。何手目から「元に戻す」をしても、0～3回の計算で済みます。
ただしキャッシュが多いほどメモリを食うので、計算回数とのトレードオフになります。
倉庫番くらいならまったく無問題ですが、ひとつの状態が1GBあるゲームとかだと問題になるかもです🐤
@@heron-no-suugaku DBの増分バックアップのイメージに近いですね。
RPGなんかのセーブデータは「愚直な方法」に近いでしょうか。
特に「復活の呪文」は現在の進行状況 (操作キャラの位置や持ち物、フラグの回収状況等) をその時点で記録するんでしょうね。
それならそれで、状況を再現するようにプレイすれば同じ復活の呪文が生成されるのか気になります。
乱数のないゲームなら、同じプレイをすると同じ進行状況になりますね🐤
乱数があってもシード値を合わせればOKです
大変勉強になりました。
ちょっと理解が出来なかった部分があるので教えてください。
動かすごとに毎回copyで複製して複製したもので計算して返してますが、
copyをせずにthisに直接計算結果を渡して繋いでいき、thisを返すのではいけないのでしょうか？
もしcopyじゃないとダメな理由があるのなら教えて頂きたいです。
calculate関数のコピーのことでしたら、ご指摘の通り不要ですね。
let c = this.copy(); ではなく let c = this; で十分です。🐤
movePlayer関数でわざわざコピーしているのは、5:39からの実演のためですね。
例えば関数s（南に1歩歩いた後の状態を計算する関数）が、引数をコピーせずに変更してしまうと
s(i) という式で、iが変更されてしまいます。
この実演において i は常に初期状態を表してほしいので、それではマズいのです。
とはいえ通常はやらない手法なので、なぜコピーしているのか動画内で触れるべきでしたね🐤
@@heron-no-suugaku
iの初期状態がe(e(i)).drawとかした後でもiが初期状態を維持できるように、
コピーした値で実演しているといった解釈であっていますでしょうか？
「愚直な方法」は、毎回盤面全体を保存、のほうがそれっぽいかも？
Commandパターンってのもありますね
数ある日本語のプログミングのチャンネルで唯一このチャンネルだけがきちんとプログラミングしてる。他は金の話ばっかでつまらん。
すいません、他に面白いチャンネル知ってたりしませんか？
毎回初期値からってことか
岡チャンネルにイントネーションが似てる
リフレクション的なのかとおもた
OSの操作を全部函数にすれば，OS単位で「元に戻す」みたいなことも可能……いや，非現実的すぎるけどw
そういうアーキテクチャがあってもおかしくなさそう
一つ一つの命令とか手続きが複雑になるから重そうだけど
@@sage_goes1504 もし実現するとしたら，OSの上で動く応用プログラムにはOSが用意したAPI以外触らせない，とかそういう規制も必要そう。
o(y(i(o(k(o(y(i(i(114514)))))))))
この動画を見なきゃハイパー愚直に盤面の列を残すところだったゾ
calculate関数の実体はどこにあるの？
どうしても連想してしまう
ｸﾊﾟｧ
戻っているのではなく、最初からやり直している？
荷を押したの？この中の中で？(合成関数)
さりげなく淫夢ぶっ込んでくるな
あっこれかぁ！(f○g(x))
関数スタックにおまかせの実装はどうかと
へー、わかんね
内容は面白かったけど最初臭そうな雰囲気がありましたね
アクセントだけ合っててrとかlとかvの発音gmなのマジで気になる...w
いやいやいや、盤面を含む必要な全状態をUNDO可能回数分記憶していく、以外にまともな解法は無いでしょう、どう考えても。
合成関数風な記述は数学的にはシンプルで大変結構ですが、初期状態から一々計算し直すのは無駄杉る。