チワ裏

とあるゲーム作りたい人のチラシの裏

開発日記 その6 自作迷路生成アルゴリズム step3

第6回です。
1週間ほど体調が悪かったので久しぶりの更新です。

こんかいはアルゴリズムのstep3について書いていきます。

step3

このステップでは迷路を作っていきます。
これまで、step1で不定形な領域をつくり、step2で、生成した領域ができるだけ長くなるような接続関係をつくりました。

迷路を作るまえの最後の前準備として、領域の境界に壁を作っていきます。
さらに、step2で連結が定義された領域同士は、壁に穴を開けて移動が可能にしていきます。


こんな感じになります。いまのところstep2ではジグザグな経路になりやすいので赤線のような経路になります。

次にようやく迷路生成にはいります。

迷路生成アルゴリズム

最後のシメとして、各領域に迷路を作っていきます。
適当に作っても、これまでの前準備によって、ある程度長い迷路が作られます。

注意点として、迷路の領域が不定形なので既存のアルゴリズムは工夫しないと使えません。
今回は迷路の幅に依存しないバックトラック法を用いました。
参考リンク
Buckblog: Maze Generation: Recursive Backtracking

↑のサイトのプログラムをそのまま使ったところ、何故か迷路ができなかったので、考え方だけ借りて自作しました。また、再帰アルゴリズムを非再帰に直しています。

迷路の生成結果

いままでのステップのまとめ動画

経路探索にはAstarアルゴリズムを使っています。
参考リンク
よくわかるA*(A-star)アルゴリズム (Unity2Dのサンプルコードつき) - Qiita

おわり

以上で自作迷路生成アルゴリズムの記事は終了です。
まだ処理速度とか安定性に難があって、改良すべきところがいくつかありますが、一応このアルゴリズムを今回作るゲームの中核にすえていきたいと思います。

次回からはゲームデザインとか、グラフィックの進捗なんかを記事にしていきます。

アルゴリズム部分だけは別プロジェクトで作っているので、もうちょっとコードを改良したらプロジェクトごと公開する予定です。
それと解説もかなり適当な感じになってしまっているので、後でもっと分かりやすく解説できるようにします。

開発日記 その5 自作迷路生成アルゴリズム step 2

第5回です。順調に更新が遅れています。
予想以上にstep 2の実装が大変でした...。

今回は自作迷路生成アルゴリズムのstep 2について書いていきます。

step 2

前回のstep 1までで、フィールドを不定形な形に分割することが実現できました。
こんな感じですね。↓


step 1では領域同士が何も関係をもっていないので、今回は連結する際に必要な情報を生成していきます。

連結の方針としては、

  • step 1で生成された情報を用いて接続できるセルを判定
  • 出来るだけ最長経路に(経由するセルの数が多く)なるように調整する
  • デットエンド(行き止まり)の長さを短く

を目標にして実装していきます。

step 1の生成する情報

step 1ではセルを成長させていって、セルが他の領域に衝突したときに、衝突した領域の番号と座標、方向を記録しています。
特に、領域番号からはどの領域同士が連結できるかを知れるので活用していきます。

ただしここで注意点↓

f:id:tiwaluna:20171214225905p:plain

上図にあるように、領域の形が不定形なので、いくつかの特徴が現れます。
図の左は領域の並びになっています。

不定形でない、各領域が正方形で敷き詰められていた場合、あるセルから上下左右の領域に接続できることは自明ですが
今回の場合、図の赤矢印にあるように、本来は接続できた10番↔15番の接続が16番の領域が遮るせいでできなくなっています。
また、図の青矢印では、8番↔12番が斜めに接続できるようになっています。

特に赤矢印の性質により、接続の難易度が上がっています。
解決策としては、必ず上下左右の領域がくっつくように調節するなどがとれるかと思いますが、今回は未接続な状況のまま接続に挑戦しました。

経路をできるだけ長く作る

このアルゴリズムの大きな目標として、迷路の長さを保証する。というものを設定しました。

領域同士の接続からできるだけ長くなるような経路をつくることで実現しようと思います。
単純に考えて、それぞれの領域に「重み」をつけることで、接続経路を誘導することが可能だと思ってました。
いざ実装しようとイキってコードを書いていましたが...


甘かったです。


上の図で説明したように、そもそも領域同士が接続できている保証が無いという致命的な状態になっています。
なので、単純な方法で接続しようとすると、

  • 経路生成失敗 25%
  • 経路が短すぎる(失敗) 35%
  • いちおう形になる 40%

失敗率60%という散々な結果になってしまいました。

解決策

失敗した方法での原因は、重みつきで制限されながらすべての領域を巡回しようとしていたことでした。
そもそもゴールにたどり着けていないこと(経路生成失敗)が多いので、
改善するために

  • とりあえずゴールまでたどり着きやすくする
  • おおまかにジグザグな経路を取らせることである程度の経路を保証できるように
  • 余ったセルはデットエンドとして処理する

という考えでアルゴリズムを組みなおしました。

図示するとこんな感じです↓

大まかに横幅2マスごとにエリア(A0 ~ A2)を定義します。
エリア内でゴールとなる座標、G0 ~ G2を目指します。
ゴールに着いたら、右に一マス移動することで、次のエリアに移動できます。
G2は迷路全体のゴールなので、たどりついた時点で処理を終了させます。

以上のアルゴリズムにより、おおまかに上→下→上のジグザグした動きを作れます。
通路幅があるので、失敗率も低くすることができます。可能ならば横に移動させることを優先させて、経路を長くしやすくできます。
また、図では縦方向のみですが、横方向からも考えられます(右→左→右)
縦方向への生成が失敗したら、横方向からの接続を試すこともで成功確率を上げます。

以上の改良によって、失敗確率が4.6%程度に減少し、失敗しなかった場合は最低17個の領域を巡回する経路を得られるようになりました。

接続に使われなかった領域は適当な隣接領域と接続することで、セル全体が繋がれるようにできます。この場合には短いデットエンドを得ることができます。

まとめ

これで領域同士の接続ができるようになりました。
非常に長々とした分かりにくい説明でもうしわけないです。

欠点としては、低確率で失敗することがあることですね。
二回連続で失敗する確率は約0.2%になりますが、0%にするにはstep 1を改良する必要がありますね。

結構ノリで考えている迷路生成アルゴリズムなので、まともに使えるアルゴリズムの制作難度の高さを痛感しています...。

次回にstep 3を実装してこの迷路生成アルゴリズムは終了になります。
今回はここまでです。めっちゃ疲れた...

開発日記 その4 自作迷路生成アルゴリズム step 1

第四回です。
今回はこのゲームの根幹となるアルゴリズムについて書いてきます。

迷路生成のアルゴリズムはネット上にかなりの数がありますよね。
しかし、そのまま利用しただけでは普通の迷路ゲームになってしまいます。
今回の制作するゲームとしては不十分ですし、再帰処理で行われてるとゲーム要素の注入が面倒になります。

そこで、前に書いた再帰分割法の「分割」という考え方や、既存の迷路のアルゴリズムを組み合わせてオリジナルのものを作っていこうと思います。

方針

このゲームでは迷路をランダムな形状で最短距離の指定の長さを保証し管理しやすい構造で、作っていくことが目標です。
上記を実現するためにこのアルゴリズムは 3つのstep に分かれています。

  • step 1 不定形セルの生成
  • step 2 領域の接続
  • step 3 領域内を迷路で埋める

今回はstep 1を解説していきます。

Step 1

まず、ランダムな形状を実現するために平面のフィールドを不定形なエリアに区切っていきます。
計算で不定形な図形を生成するのは非効率なので、乱数を使って実現します。


(フィールドのイメージ)

f:id:tiwaluna:20171210144331p:plain
このようにフィールドのある座標に開始点を付けます。(図では赤く着色)
このアルゴリズムでは1マスを「セル」と名付けます。

上下左右の方向に確率でセルを伸ばしていきます。


等間隔に開始点を発生させて、セルごとに伸びる確率をランダムに設定するとこうなります。
これによって、不定形な形状の領域が作れました。
また、領域ごとに通し番号をつけます。画像の場合、領域が全部で25個あるので、左下が0で右上が24になります。


次に情報の生成です。
次のstep 2では生成したセル同士を連結したいので、連結に必要な情報を抽出します。
必要な情報は、領域同士が隣り合う境界部分です。(画像の色つけした領域の境界部分の座標)

  • 隣の領域の番号
  • 座標
  • 連結方向

を取得します。

取得するタイミングは、セルを伸ばすときに別のセルに衝突したときに取得します。
そのときの衝突した領域の番号、伸ばした方向、座標を取得します。


境界部分を着色するとこうなります。
連結時には、連結先の領域番号を参照して、座標と方向から連結処理を行えます。


今回はここまでです...
次回の更新でstep 2の解説をします!(step 2の実装に詰まっている)

メモ

今回の記事で使用した画像は、アルゴリズムのデバック用のスクリプトで生成したものです。
step 1で生成されたセル番号を配列に格納しておいて、
それをスクリプトで参照して、値の変更が行われたら対応する色(マテリアル)で着色しています。
コルーチンを使ってオブザーバーパターン的に実装してます。

一からアルゴリズムを作っていくのは今回が初めてなんですが、こういった視覚的なデバックがあるととても便利ですね。
文字のみ(Debug.Log)だとレイアウトが崩れたり、柔軟な表示ができないので、デバックコードの重要性がわかりました。

(step 2の実装はデバック用のコードをはじめに作らなかったせいで5時間ほど無駄してしまった...)

開発日記 その3 巨大な迷路を3Dオブジェクトで表現する

第三回です。
意外と順調に更新ができているので自分でも驚きです。

さて、今回は1000*1000の迷路を3Dオブジェクトで表現する方法について書いていきます。

方法1 1000*1000個のゲームオブジェクトを用意する!

結論から言って無理です。
流石にこんな阿呆な実装をする人はいませんが、いちおう試して消費メモリを計測してみました。
f:id:tiwaluna:20171205210014p:plain

1.54GBになります。デデドン(絶望)
ちなみに本当に1000*1000個の生成をするとゲーム自体が起動しなかったので、上のスクショは500*500=250000個のゲームオブジェクトの生成したときの結果です。

想像通りの結果ですね。

目標のメモリ消費量

256MBです。
理由として、WebGLでゲームを作る際にこんな設定があります。 (ProjectSettings->Player->WebGL)
f:id:tiwaluna:20171205210901p:plain

ここで設定する値がブラウザ上で確保されるメモリ量だと思われます。256MBより多く設定すると32bit環境で動かないなどという警告がでますね。
なので超軽量なUnityゲームのメモリ消費量は256MB以下なんじゃないかなーと思ってます。
今回はカジュアルに遊べるようなスマホゲームを目指しているので目標はこれぐらいを目指しています。
Unity - マニュアル: WebGLを対象とした場合に必要なメモリへの配慮

方法2 オブジェクトプールの考え方を用いる

オブジェクトプールとは、単純にいうとオブジェクトを使いまわすことです
具体的には、初めに十分な数のオブジェクトを用意しておいて、アクティブと非アクティブの切り替えを行うことをします。
これにより、毎回DestroyやInstantiateをすることがなくなるので効率化することが可能です。

また、使いまわすという考え方を応用して、以下のような方法を考えます。
f:id:tiwaluna:20171205212934p:plain

この考え方を用いると、カメラの視界に収まる数のオブジェクトのみで迷路のフィールドを表現することが可能です。

まず、カメラの視界内に収まる十分な量のオブジェクトを生成します。今回は10*10個用意しました。
プレイヤーが右に動いた場合、左端の列が視野外に出ます。また、右端の列にオブジェクトが表示されていない状態になります。
ここで、図に示したように、左端の列を右端に移動することによってグラフィックが途切れないようにすることが可能です。
その他の方向についても同様になります。

続いて、迷路の壁の表現について考えます
今回のゲームではいわゆる「壁マス」というものは存在せず、マスとマスの間に壁が存在します。
壁がどこに存在するかについては、マスごとに判定しています。
各マスごとに壁のある方向、「下」または「右」を設定して壁を作っています。
ここで、オブジェクトプールの考え方を利用して、あらかじめ下と右方向の壁を用意しておきます。
各マスの壁の方向をデータで保持して、必要に応じて表示、非表示を切り替えていきます。
図にすると以下のようになります。
f:id:tiwaluna:20171205214411p:plain

これらの考え方を利用すると、オブジェクト数が、3 * 10 * 10 = 300個で済みます。
データは
GameObject配列 [300]
方向用データ [1000 * 1000]
になりました。今回のゲームでは方向のデータをビットフラグを利用してint型1つで表現しています。

最後にメモリ消費量の測定結果です。
f:id:tiwaluna:20171205214748p:plain

約63MBに削減できました。
これから色々な要素を詰め込んでいきたいのでこの軽量さはとてもうれしいですね。

おわりに

実際に動かした結果

わざとオブジェクトの移動が見えるようにしていますが、実際にはカメラの視界やマスの大きさを調整することで自然な感じにできます。

今回はここまで。
過去最高の文字数の記事になったかも。

ようやくアルゴリズムの改善方法がまとまってきたので、次回はアルゴリズムの紹介をしたいと思います。

開発日記 その2 迷路の生成アルゴリズムとゲームデザイン

第二回です。
今回は迷路を生成するアルゴリズムとか今考えてるゲームデザインとかについて書いていきます。

再帰分割法

今回のゲームでは再帰分割法というアルゴリズムをうまく使っていきたいなーーと思っております。

参考元
Buckblog: A Better Recursive Division Algorithm


このアルゴリズム良い所は、マップを分割しながら作っていくというところですね。
参考元のサイトの迷路生成のアニメーションをぜひ見てもらいたいです すごくえっち...

ゲームデザイン

今回のゲームでは迷路にRPG要素をぶっこんでいきたいのです。
なので、こんな感じに
f:id:tiwaluna:20171203143407p:plain

分割されたマップ(エリア)ごとに色々と処理を加えていきたいと考えています。
上図では、エリアごとに敵のレベルを分けています。

あと、純粋な迷路生成では邪道?なのかもしれませんが、迷路にループを取り入れたいですね。
なにも考えずにループさせると迷路の複雑さがバラバラになるので、ある程度作為的に制御できるような形にしたいところです。

そのほかに今回のゲームではスタート地点とゴール地点の位置は固定にしようかなと思っています。
RPGなので、目的地に向かう途中によ寄り道したりする要素と、迷路をさまよいながら進む要素を合体できたらなーというのが理想です。

実現性?

んなこと知るか

上で色々と述べたんですが、このアルゴリズムが自分には難しいので実装できるかどうかわからんのですね。
結局実現したいことは「迷路をエリアごとに分けること」、「迷路の形状をコントロールできること」なので、再帰分割法でなくてもいい気もしてます。

正直、アルゴリズムがカッコイイという理由のみで決めています。
なので、ちょっとやって無理そうだったら、ランダムに領域を分ける処理と他の迷路生成でどうにか賄うことも考えてます。

最後に再帰分割法で作った30*30サイズの迷路の動画↓

結構30*30のサイズでも大きく見えますね。
キャラクターの移動速度をいい感じに調整して、可能な限り大きな迷路を作ったらやりごたえのあるゲームになるかもしれません。

ただ、N*Nの平面だとゲームオブジェクトの量がとんでもないことになりますね。
このへんの解決策も考えついてはいるんですが、実装が間に合ってないので次回に紹介します。

開発日記 その1

そろそろ12月に入り暇になるので開発日記のようなものをつけようかなと。
今回はマジでただの日記です。

動機とか

自分はUnityでゲームを作っているのですが、あまり制作状況をメモすることが無いので、制作中の記憶が結構飛んでいることがあったりします。
特に、今年4月~8月に作ってたゲームは某コンテストへのエントリーもあり、デスマしたので開発終盤あたりの記憶がゴッソリなくなってます。

12月から次回作の制作を始めるにあたって、前回の反省を踏まえて開発日記としてメモを残したいなーと思ってます。
あと文章を人並に書くための練習としても...

なに作るの?

今月はちょくちょくゲームの企画をまとめて企画書もどきを作ってました。 
ガバガバ文章力のおかげで到底ブログで見せられるもんでは亡くなった

今回の開発では

「迷路」+「RPG

的なものを作っていきたいなと思ってます。人にウケるかどうかは分かりません!


色々と元地にするアルゴリズムの選択とかはすでにやっているんですが...
そのへんは小出しにしていかないと日記を続けられる気がしないのでまた次回ということで。 

土日中にその2を投稿したいナー

Unityで3Dモデルを動かして剣で敵をぶっ飛ばす実装メモ

3Dモデルをちゃんと動かすゲームを作ってみたくなったので試しに作ってみました。

実装手順

まずは使用したアセット(無料のやつです)

キャラクター Strong Knight (つよそう)
いい感じの騎士?のアセット
https://assetstore.unity.com/packages/3d/characters/humanoids/strong-knight-83586

スクリプト Free Footsteps System
モデルの動きやアニメーションを思い通りに実装できるアセット
https://assetstore.unity.com/packages/tools/audio/free-footsteps-system-47967

アニメーションやエフェクトは適当にどうぞ

ヒエラルキーの構成

f:id:tiwaluna:20170919220127p:plain

・top_down_camera_pivot
Standert AssetのMultipurposeCameraRigみたいなやつっぽい。
Targetにtop_down_controllerを設定する。
f:id:tiwaluna:20170919220548p:plain

・top_down_controller
このオブジェクトの子にキャラクターの3Dモデル(kinghtprefab)を配置する。
f:id:tiwaluna:20170919220553p:plain

上記はFree Footsteps Systemのデモシーンのオブジェクトに既に設定されているので流用して改造できます。

アニメーションの実装

最終的なアニメーション図 f:id:tiwaluna:20170919221336p:plain

Free Footsteps Systemのスクリプトを改造していきます。
アセットに付いている、TopDownController.csでモデルの制御ができます。
これをアタッチすると、移動キーに合わせたオブジェクトの移動と回転が実装されます。すげぇ

次に任意のアニメーションを再生できるようにします。
TopDownController.csのコードでは歩行時にAnimatorのパラメーターのmoveをtrueにすることでアニメーションを遷移させています。
このスクリプトを以下のように改造して対応するアニメーションを増やします。


void UpdateAnimator() {
  …
  <既存のコード>
  …
  //移動キーのいずれかが押されていればtrue、押されてないならfalse
  isMoving = Input.GetButton(“Horizontal”) || Input.GetButton(“Vertical”);  

   //tureかfalseが設定される
  thisAnimator.SetBool(“move”, isMoving); //tureかfalseが設定される
}

これを応用すれば、
isRunning = isMoving && Input.GetKey(KeyCode.LeftShift);
isAttack = Input.GetKey(KeyCode.Z);

thisAnimator.SetBool(“run”, isMoving);
thisAnimator.SetBool(“attack”, isRunning);

みたいな感じでダッシュ、攻撃のアニメーションフラグを設定できます。 AnimationControllerにちゃんとパラメーターを用意するのも忘れないようにしましょう。


剣で敵を吹き飛ばせるようにする

キャラクターのモデルをこんな感じで改造してみました。

f:id:tiwaluna:20170919222829p:plain

変更した点は元モデルでは剣のモデル(dagger)を腰につけているんですが、daggerをR_elbowの子の位置に設定します。
僕の使ったアニメーションではこれで剣を振るう動きが作れました。
また、不要なパーツは非表示か削除しておきます。

daggerのメッシュに敵が当たったときに攻撃判定としたいので、daggerにMesh Colliderをアタッチします。
また、Mesh ColliderはOnTriggerEnterを使って接触の判定をしたいので、isTriggerを設定します。
そして敵を吹き飛ばすスクリプトを作ってアタッチします。

ブログ用 当たったオブジェクトを吹き飛ばすUnityスクリプト

解説

OnTriggerEnterで大体の処理を行ってます。

  • 敵の判定
    今回は敵にenemyタグをつけて判定するので、 if (other.gameObject.tag == “enemy”)で判定。

  • 攻撃アニメーションの判定
    if( (animatorStateInfo.IsName(“attack”) || animatorStateInfo.IsName(“jump attack”) )
    で攻撃アニメーションが再生されているかどうかを攻撃アニメーションの名前で判定します。

    • また、AnimatorStateInfoの情報は取得する前に
      rootAnimator.Update(0);
      で更新しないと最新のAnimatorの情報を取得できないので注意。
  • 攻撃判定
    0.2f < animatorStateInfo.normalizedTime && animatorStateInfo.normalizedTime < 0.8f
    animatorStateInfo.normalizedTimeで再生中のアニメーションの進捗を取得できます。
    0%(再生開始) ~ 100%(再生終了)
    今回は20%~80%の間で、剣を振っている最中のみ攻撃判定を出すようにします。

  • 吹っ飛ばす!
    rigit.AddForce(transform.root.forward * 25, ForceMode.Impulse);
    敵にRigitBodyがある前提ですが、こいつで吹き飛ばします。ForceMode.Impulseでは相手の質量(Mass)の影響を受けて、瞬間的に力を加えます。適切な値を設定します。

  • その他
    effectの部分は適当にすきなものをどうぞ。
    effectはプレハブを剣と敵の中間の位置に生成されます。


以上で実装は終わりです。正直ただのアセット紹介なんだよなぁ・・・。
説明が抜けていたらすみません。

完全にブログ放置してたからこれからは徐々に記事を書いていきたいなぁ…