キュー操作解説

前回の記事にてキューの説明は省いていたので
今回はキューについての解説を行いたいと思います。

■キュー

キューによって実現できる処理について解説していきます。

例えば、リプレイ処理を実装するときに有効です。

←↑↓→キーで自機が移動するとして
ステージが終了した時点で今回のリプレイを保存する処理を考えます。

毎フレーム、入力されたキー情報をキューに入れていきます。
例えば　『←』が押された場合
『←』に該当する値をキューに入れます。
これを続けていくことにより、毎フレームの操作履歴がキューの中に格納
されます。

リプレイを再生するときは
キューから値を取り出すことによって
操作された順にキー情報を取得できます。
あとは取得した情報をもとに自動でキーを入力する
ようにすれば、リプレイ再生の完成です。




他にも例を挙げると
以下のような文字列が記述された
スクリプトファイルがあるとします。

@message
あいうえお
@wait 2
@message
かきくけこ

上記は
@messageで文章を表示
@waitでウェイトを実行する処理とします。

この場合、『あいうえお』と表示されてから
次に２ウェイトおいてから
『かきくけこ』と表示される処理です。

このファイルを処理するときに逐一読み込んで処理するのも
方法の１つですが、あらかじめ全てデータを読み込む方法も
あります。

後者の場合キューを用います。
まずは@messageを命令格納用のキューに入れます。
そして次の『あいうえお』を別の文字列用のキューに入れます。
次は@waitを命令格納用のキューに入れます。
その後、更に別の数値用のキューに『2』を入れます。
↓
@message　を命令格納用に入れる
↓
『かきくけこ』を文字列用に入れる

とすることによって
全てのスクリプトデータを読み込むことができます。
あとは命令格納用キューから順に命令を読み出して
命令の種類によって処理していくようにすれば
順番に命令を実行していくことが可能になります。

あらかじめ読み込んでおくことによって
残りの実行命令数なども管理できるので
管理性が高まります。


以上がキューの使用例の一例です。


このほかにもキューには
環状キュー(リングバッファとも言う)というものもあります。
これはデータの先頭と末尾がつながっているデータ構造に
なりますが、これを使うことで
ログの管理なども行えます。
末尾にどんどんデータが追加され、データがいっぱいになった場合
先頭のデータに上書きされていくため古いデータが自動的に削除
されていき、最新のデータだけが保存されるようになります。

スタック/キュー操作コモン公開

「スタック操作コモン」と「キュー操作コモン」公開したので
ブログの方でもまとめておきます。

それぞれのコモンについては以下のコモンイベント集の
登録先にて確認してください。
スタック操作コモン
キュー操作コモン


一応ここで
スタックとキューを使用すれば何が実現できるのかを大まかに
説明しようと思います。
とはいえ使い方は数えきれないほどありますし、説明として
的確なものを考えるのもの大変ですので
代表的なものを説明していきたいと思います。

まずはスタックから説明していきたいと思います。


■ スタック

代表的なものの１つとして構文解析があります。
例えば以下のような文字列があるとします。

if( A > (B + 1) ){
　B += 1;
}

このとき
『if』の次出てくる『()』で囲まれた文字列を取得したい場合
この場合『 A > (B + 1) 』が取得したい文字列に該当しますよね。

ですが該当する文字列の中にも『()』があります。
もし『if』の次の『(』から『)』までの文字列を取得した場合
『 A > (B + 1』
が取得されてしまいます。

この問題を容易に解決する手法の１つとしてスタックを
利用する方法があります。

まず『if(』の『(』をスタックに入れます。
そして右へ右へ文字列を調べていきます。
もし『(』が出てきた場合、さらにスタックに入れます。
今回の場合『(B』の部分の『(』がそれに該当します。
そして『)』が出てきた場合、スタックから『(』を取り出します。
もしこのとき、まだスタックに『(』が入っている場合続行します。
そしてスタックの中身が空になるまで続けます。
中身が空になった場合、その箇所の『)』が先頭にあった『(』と組に
なることがわかります。

これで『 A > (B + 1) 』を取り出すことが可能になりました。

今回の例の場合、できる限り分かりやすくするために
単純なパターンに限定しましたが、
いろいろな種類の括弧が出てくる場合などにとても役に立つと思います。
その場合は取り出した括弧が同じ種類の括弧かどうか調べるなど
すれば対応できるでしょう。

この原理を使えば数式の計算などにも用いれます。
1 + ( 5 × ( 4 + 1 ) )
上記の様な場合でも『4 + 1』のところから取り出して～～～
って言う感じで計算を行っていくことができます。
こういった数式計算についての詳しいことは『逆ポーランド記法』等で
調べるとよいでしょう。

迷路のスタートからゴールを求める探索処理などにも
スタックが用いられます。

他にも編集ソフト等で
アンドゥ、リドゥで操作を元に戻したりする処理も
スタックによって実現されています。


次にキューの説明……と言いたいところだけど
すごく長くなりそうなのでまた次回にでも書こうと思います。
（※たぶん）

線形補間移動コモンイベント

線形補間移動コモンイベントを作成しました。
以下からダウンロードできます。
http://silsec.sakura.ne.jp/WolfRPGEditor/CommonList/html/tdv226.html#14246095107201

ブログの方でもまた書き込むのめんどくさいから
以下はコモンイベント集に登録した内容のコピペ
=============================================

値を目標の値まで指定した処理フレームで変化させる
コモンイベントです。
値の変化方法は以下の４パターン用意されています。
・直線移動
　　　：目標値まで一定の速度で変化させます。
・加速移動
　　　：緩やかに変化が始まり目標値まで徐々に加速していきます。
・減速移動
　　　：一定速度で変化が始まり目標値まで徐々に減速していきます。
・加減速移動
　　　：緩やかに変化し中央値で最速になり徐々に減速して目標値まで
　　　　変化させます。

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

コモンイベントの引数（入力値）
１.　初期値　　　：値の初期値
２.　目標値　　　：変化後の値
３.　経過フレーム：現在の経過フレーム
４.　処理フレーム：変化にかける処理時間
返り値　：　上記引数をもとに求めた現在の経過フレームにおける値

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

<< 例 >>----------------------------------------------------------

　変化方法　　　直線移動
　初期値　　　　0
　目標値　　　　100
　経過フレーム　20
　処理フレーム　50
　とした場合「0」を「100」まで「50フレーム」かけて値を
　変化させることになる。
　経過フレームが「20」なので
　「20フレーム」経過している場合の値を「返り値」として返す
　この場合は「40」が返り値として返る。

---------------------------------------------------------------------

この説明を見てもよく分からない方は
ピクチャの処理時間をイメージすると良いと思います。
X座標が「0」にあるピクチャを
X座標「100」にして、処理時間に「50」を設定した場合が
上記の例と同じ状態になります。
20フレーム経過した場合ピクチャが自動的に
そのフレーム時の座標に移動していますが
このコモンイベントでは、その値を実際に返してくれます。

ピクチャの処理時間と違い
値の変化に「加速」「減速」「加減速」があるため、
より表現が広げられると思います。

---------------------------------------------------------------------

■以下にサンプルプログラムを置いておきます
サンプルプログラム

指定フレームで値を指定値まで変化させる処理

今回は指定したフレームで値を指定した値まで変化させるときの
現フレームの値を求める処理について書きます。

さっそくですが計算式書きます。
『新しい現在の値 = (相対値 * 現在の経過フレーム数) / 処理フレーム + 初回値』

上記の式で求めることができます。

たとえば

X座標20のオブジェクトAを60フレームかけて
X座標100まで移動したい。
このときの24フレーム経過後のオブジェクトAの
X座標は？
   
これを求めるとした場合

「24フレーム後のX座標 = ((100-20) * 24) / 60 + 20」

という風な式になります。

最初X座標が20なので
初回値には「20」を割り当てています。

X座標が20→100と変化させたいので
相対値には「80」を割り当てています。
もし100→20と移動させたい場合は相対値を「-80」にします。



これでなぜ座標が求まるかというと
経過フレームと処理フレームの割合をもとに算出されているからです。

「経過F/処理F」によって割合が求まります。
この割合と最大値を掛け算することによって
割合に応じた値が算出されます。

分かりやすく例えると

「６＊(1/2) = 3」
これは6＊1/2、つまり6の半分の値が求まります。
この「1/2」が割合に相当します。

これがもし「2/2」だった場合、1になり
「6＊1 = 6」
最大数の6が求まるわけです。

この計算を処理に応用した式が
『新しい現在の値 = (相対値 * 現在の経過フレーム数) / 処理フレーム + 初回値』
というわけです。

描画順序を求める処理

久しぶりのブログ更新

とはいえウディタでの開発は一時中断中なので書くことがないので
アルゴリズムの記事でも書こうかなっと

とりあえず
描画に関するアルゴリズムについて今回は書こうと思います。

描画とはいえいろいろあるわけですが、
この画像のようにキャラがオブジェクトの後ろ側か手前側かで
描画順序を変える処理（描画順序を求める処理）についてまとめたいと思います。


マップ上で不特定多数のキャラと不特定多数のオブジェクト同士の
描画順序を求めるアルゴリズムという感じですかね。

というわけで本題に入ります。

まず描画グループとグループ同士の描画順序を設定します。
ここでは例として

描画グループは
・主人公や味方
・敵
・オブジェクト
の３つ。

各グループの描画順序は
(前面)>「主人公や味方」>「敵」>「オブジェクト」>(背面)
とします。

また、
マップ上の３２ピクセルを１座標(１マス)とした
マップ座標系でこの描画順序を管理し、

ピクチャは１０００枚まで使用可能。
（この描画順序処理において描画できる最大の枚数的な感じ）

マップは縦１０マス横１０マスとします。

とりあえず例としての設定はこんな感じで。


じゃあこれでどうやって順序を求めるかというと
割と単純な話で
各マップY座標別に描画IDを割り当てるという感じになります。


これだと説明不足なので細かく説明していきたいと思います。

まずマップが縦１０マス（Y座標0~9）なので
それらの各Y座標にグループを割り当てます。
次に割り当てたグループに描画IDを割り当てます。
データ構造のイメージは以下のような感じです。
 
まぁ描画IDというか描画できる枚数というかそんな感じかも。

もっと詳細に書くと
Y座標０～９にそれぞれ３つのグループを割り当てる(主人公味方,敵,オブジェクト)
その３つのグループはそれぞれ最大でN個ピクチャを登録できるように設定する。

ここでN個の求め方だけど
まずピクチャ(描画)は最大で１０００枚まで登録可能で
マップは縦１０マス、グループは３つ。
つまり
『N = (1000/10)/3』

(1000/10)は各座標に割り当てれるピクチャの最大数
その最大数をグループの数、３で割ることで
各グループに割り当てれるピクチャの最大数が求まる。

この例の場合
(1000/10)/3 = 33（小数点以下は切り捨て

よって
１グループにつき３３枚まで登録が可能になる。

で
もうこれで終わりになります。
あとは登録して描画するだけ。

Y座標が２の主人公のピクチャを登録するときは
Y座標「２」のグループ「主人公味方」に登録。

次にY座標が同じく２の味方を登録するとしたら
Y座標「2」のグループ「主人公味方」に登録。
このとき「主人公のピクチャ」がすでに登録されているので
次のIDに味方を登録するようにする。
よって以下のようなデータ構造になります。


あとはこの登録したデータをもとに描画処理を行います。

マップ上でY座標が0に近づけば近づくほど（マップ上側）背面
Y座標が9に近づけば近づくほど（マップ下側）前面に描画されるべきなので
ウディタであればピクチャ番号の配分を
「Y座標が小さい方」の登録データを小さいピクチャ番号
「Y座標が大きい方」の登録データを大きいピクチャ番号になるように
割り当てて描画すればいい感じ。

ウディタとかのピクチャ番号という概念がない場合は
マップY座標0から順に描画していく。

もちろんグループ内の順序も忘れなく。

ちなみにここでは描画の順序を決める処理を書いただけで
実際に描画処理と連携する部分は書いていないのでその辺は自分で考えましょう
（書くのめんどい）

ウディタならちょっとめんどくさいことになりそうな予感はするけどね。

あくまでこの処理はC言語で実装した処理なので
ウディタで使いやすいように最適化はしていないので注意。


あと登録するときに主人公等のY座標をもとに登録してたけど、
この場合主人公の足元の座標のマップY座標を使うようにしないと
描画が変なことになるので注意ね。

ここまで書いて思ったけどアルゴリズムというより
単なる描画順序保存用のデータ構造の例だよねこれｗ

あとなんかいろいろ説明が変な気もする。
まぁ細かいことは気にしない。
というわけでこの辺で終わりにしたいと思います。

（今回の説明ではデータとして登録していく流れで説明したけど
　それとは別の方法をとって
　各座標の各グループの各描画IDを全て１つの連番IDにまとめて
　そのIDを計算で吐き出す処理に書き換えれば
　ウディタとかのピクチャ番号を計算する処理もできると思う）