すでに独自のパズルゲームを作成しようとしている場合、ゲームルールの実装とコーディングは非常に簡単ですが、レベルの作成は複雑で時間がかかる作業であることにすでに気付いているかもしれません。 さらに悪いことに、特定のタスクを挿入しようといくつかのレベルを作成するのに多くの時間を費やしましたが、友達がそれらをプレイしようとすると、これらのレベルはまったく異なる方法で、またはあなたがそれらについても考えもしなかったような簡単なトリックで経験しました。
コンピューターが時間を節約し、上記の問題を解決する方法を見つけることは素晴らしいことです...そして、これが手続き型世代が救いに来るところです！
たとえば、ベクトルを合計する方法は1つしかなく、それを必要とするプログラマーは同じルールに従う必要があることを言わなければなりません。 ただし、手続き型生成の場合は、完全に無料です。 正しい方法と間違った方法はありません。 主なものは結果です。
フルーツデート-ルールと機能
ほんの少し前に、iOSデバイス用のFruit Datingをリリースしました（ Androidおよび未リリース（ゲームのリリース時）Tizenでも利用可能です）。 これはシンプルなルールのパズルゲームです。 彼女の目標は、画面上で指をスワイプして同じ色の果物のペアを接続することです。 指を動かすことは、希望する方向への運動場の傾斜に対応します。 プレーヤーがタスクを完了しようとすると、石、車、その他の果物などのさまざまな障害物が邪魔になります。 すべての移動オブジェクトは一方向に移動します。 下の写真は、果物をつなぐために3つの動きが必要な最初のレベルを示しています。
時間が経つにつれて、新しい機能が追加されます。
 | 一方向の通路はタイルの境界に配置され、オブジェクトを移動できる方向を制限します。 |
 | アリクイは異なる方向を見ることができますが、この方向は一定であり、レベル中は変化しません。 果実がアリクイの視線の方向にくると、舌で「シュート」し、果実を引き寄せます。 |
 | 石、車、樽は水たまりを移動できますが、果物は移動できません。 果物が水たまりに入ると、果物は汚れ、日付はキャンセルされます！ |
 | 寝ているハリネズミはタイルの上に立ち、何かが彼に当たると目を覚ます。 樽、石、または機械が彼にぶつかると、彼は食べられないので再び眠りに落ちます。 しかし、果物が彼に当たると、ハリネズミはそれを食べます。 |
レベルはタイルで構成されていることにお気づきでしょう。 これにより、各レベルを小さなグリッドとして表現できるため、作業が簡単になります。 最大サイズは8x8タイルですが、境界線は常に固定されているため、「有用な」領域は6x6タイル以下です。 これは少し見えるかもしれませんが、そのような分野では非常に複雑なタスクを作成できることが証明されています。
基本的なルールに基づいて（後で追加機能が追加されたため）、独自のジェネレーターの作成を開始しました。 もちろん、最初は、世界の誰かがすでに同様の問題を解決していると思っていたので、パズルレベルの手続き型生成のためにインターネットを検索し始めました。 この問題はあまり広く考慮されていないことが判明しました。 私にとって有用な記事はごくわずかでした。 彼らは主に倉庫番のレベルの生成/解決に焦点を合わせました。 例：
1 つと2つ 。
また、それらのほとんどが科学者によって書かれたことも興味深いことでした（倉庫番教授:-)）。 これらの記事から、2つの原則を学びました。まず、何かをランダムに生成する場合は、少し対称性を導入して、結果をより積極的に認識できるようにすることをお勧めします。 第二に、アルゴリズムの選択はあなた次第ですが、どれも完璧ではありません。
パズルツール
明らかに、生成された各レベルはテスト（解決可能かどうか、およびそれがどれほど難しいかを理解するため）を受ける必要があるため、最初にレベルを解決するためのツールを作成することにしました。 当時は、追加機能なしで基本的なルールのみを考慮していたため、「ソルバー」について次のアイデアがありました。
a）開始位置から、任意の方向（左、右、上、下）に移動を開始できます。
b）次の位置から再び任意の方向に進むことができます。
c）任意の位置で、フルーツ化合物がチェックされ、一致するフルーツがフィールドから削除され、パラグラフb）がいくつかのフルーツがフィールドに残るまで続きます。
ご覧のとおり、これは単純なブルートフォースアプローチです。 したがって、フィールド上の可能な位置の数は、4、4 * 4 = 4 2、4 * 4 * 4 = 4 3 、... 4 nでした。 移動10では、フィールドの100万を超える組み合わせが判明し、移動25では-1125899906842624の組み合わせになりました。 それでは、移動の最大数を、たとえば10に制限できます。これより難しいレベルには興味がありませんが、ここでは別の危険があります。 パズルのいくつかは、最初に悪い動きをしたプレイヤーがレベルを完了できないような方法で作成または生成できます。 または、一部のレベルでは、フィールドで状態のループが発生する場合があります。 アルゴリズムの分岐が早すぎる場合、より単純なソリューションでより短い分岐がある場合でも、レベルを解決不能としてマークできます。 また、アルゴリズムが解決策を見つけた場合、それが最短であるという保証はありません。最短の解決策を見つけるには、すべてのブランチを完了する必要があります。 さらに、特定の方向に移動しても何も変わらないというフィールドでは、このような状態がしばしば発生します。 「フルーツデート-ルールと機能」セクションの3番目の図を見てください。左に移動しても何も変わりません。
したがって、ルールが変更されました。
a）現在位置から任意の方向に移動しようとする;
b）フィールドの状態が変更された場合、そのような状態が新しいかどうか、または既に変更されているかどうかを確認します。
c）状態が新しい場合、ソリューションの深さ（そのような状態になるために必要な移動の数）とともに保存します。
d）以前にそのような状態があり、解の深さが現在以下であった場合、現在のブランチを削除します。 そうでない場合は、古い状態を置き換え（より少ない移動で取得したため）、続行します。
また、他のルールもあります。たとえば、果物の一致をチェックし、解決策を見つけたときにプロセス全体を終了します。 さらに、追加機能に関連する他のルールが後で発生しましたが、基本的なソリューションツールについて説明しました。 彼は解決策なしに枝全体をすばやく切断しました。 ソリューションの深さに加えて、フィールドの状態ごとに保存されている親の位置もチェックするため、最後にソリューションを簡単に印刷できます。 ゲームの最初のレベルの例を見てみましょう：
開始位置から、動きは4つの可能な方向に分岐します。 それらを1-1、1-2、1-3、1-4としてマークします。 アルゴリズムは常に、右、上、左、下の順序で移動しようとします。 格納された状態をさらに調べるためにスタックを使用する必要があるため、最初の継続状態は最後にスタックに転送されます（この場合は1-4）。 繰り返しますが、最初の動きは右へのシフト（2-1）であり、これは新しい状態なので、スタックに書き込まれます。 次はシフトアップで、2-2の状態になります。 最初の反復ではすでにこの状態にありました。 したがって、ルールd）を適用してこのブランチを終了します。スタックには何も書き込まれません。 次は左への移動の試みです。 新しい状態（2-3）につながり、スタックにプッシュされます。 最後の動きは下向きのシフトですが、1-4と2-4に違いはないため、スタックには何も配置しません（ルールb）...新しい状態はありません=何もしません）。 スタックの最上位の状態は2〜3です。 それから、右に移動し、状態2-1に等しい状態3-1になります。 しかし、2-1では2回目の反復であったため、このブランチを切り取りました。 それから上に移動すると、果物は隣のタイルにあり、それが唯一のペアだったので、ゲームは終了します。
アルゴリズムは機能しますが、最短経路が見つからない場合があります。 彼は最初に見つかった解決策を単純に採用します。 これを修正するために、最初に移動の最大数を30に制限しました。解決策が見つからない場合は、レベルが通過できないと考えます。 15番手などで解決策が見つかった場合、最大解答深度14（15-1）で「ソルバー」を再度開始します。 解決策が見つからない場合、15が最短パスです。 たとえば、13の移動で解決策が見つかった場合、最大深さ12（13-1）でツールを実行します。 何らかの解決策が返されるまでプロセスを続けます。 最後に返されたソリューションは、最短のソリューションです。
発電機
「ソルバー」を作成しました。ジェネレーターに移動して、生成されたすべてのパズルを確認できます。
生成フェーズは2つの部分で構成されます。
- 壁の生成
- フィールドでオブジェクトを生成する
壁の生成は、常に固定フィールドの境界線の描画から始まります。
壁が一度に1タイルずつ塗装されるか、それとも2タイルずつ塗装されるかを示すランダムパラメーターが生成されます。 2つのタイルの場合、ランダムな対称性が生成されます。 2番目のタイルを配置する場所-垂直、水平に反射するか、90度回転するか、変換の組み合わせがあるかを示します。 次の図の最初のグリッドでは、一度に1つのタイルのみがペイントされます。 他のすべてのグリッドでは、2つのタイルのランダムな対称性のさまざまな例が示されています。
壁の数、長さ、方向はランダムです。 各壁は、境界上のランダムなポイントから始まります。 各壁は1回以上の繰り返しで描画されます。 最初の反復の後、0から（壁の長さ）-1の間で数値がランダムに選択されます。ゼロの場合、反復サイクルは停止します。 ゼロよりも大きい場合、この数値は壁の次の部分の長さになります。 壁の現在の部分のランダムな点が選択され、壁の現在の部分に直交する方向がランダムに選択され、壁の次の部分が描画されます。 結果は次のようになります（数字は反復を示します）。
この写真は、壁の次の各部分が短くなっていることを示しているため、ある時点で壁が終了することを確認できます。
すべての壁はフィールドの境界から始まるため、個々のタイルは境界に接続されていました。 私には退屈そうに見えたので、内壁が生成される別のステップを追加しました。 内壁は、既存のタイルに接続されていません。 ステージは、ランダムなタイルを選択し、それが空いていてタイルが3x3以内にあるかどうかを確認することから始まります。 その場合、壁はグリッドに配置され、次のタイルがランダムな方向に従って選択されます（この方向は、最初のタイルをテストする前にランダムに選択されます）。 空き3x3タイルの条件が満たされない場合、サイクルは中断されます。 上記で強調された「意志」という言葉に注意してください。 すぐに壁をグリッドに配置し、次のタイルの処理を続行すると、壁を配置しただけなので、3x3内の領域が解放されることはありません。 したがって、すべての壁タイルを一時的な配列に保存し、同時にループの終了後にそれらをグリッドに配置します。
壁を生成するとき、それらの一部は重なり合う可能性があり、小さなスペースが作成されるか、元のエリアでさえ、接続されていない複数のエリアに分割される可能性が非常に高くなります。 もちろん、これは望ましくありません。 したがって、次のステップでは、どの連続領域が最大であるかを確認し、残りを壁で埋めます。
このチェック中に、フィールドのグリッド全体を調べて、タイルが空いている場合、連続した領域全体をこの領域の識別子で再帰的に埋めます（無料のタイルは壁のないタイルで、これまでのところ領域の識別子でマークされていません）。 その後、フィールド全体をもう一度調べて、各エリア識別子でタイルをカウントします。 そして最後に、フィールド全体をもう一度調べて、タイルの数が最も多いエリアを除き、すべてのタイルにエリアIDを壁で埋めます。
このアニメーションでは、壁を生成するプロセス全体を見ることができます。 これは、壁の生成と内壁の生成を示しています。最後のフレームでは、領域の結合の段階で右下隅のボイドが埋められています。
壁の生成が完了したら、オブジェクトの生成を開始できます。 少なくとも1組の果物と0個以上の障害物（ゲームでは石、車、樽で表されます）が必要です。
果物がほとんどの場合、コーナー、廊下の端などの場所にあるとよいでしょう。 それらをオープンエリアの中央に配置することは時々面白いかもしれませんが、前者がより好ましいです。 これを実現するために、各フリータイルにフルーツの場所の魅力の観点から重みを追加します。
3つの側面でタイルに囲まれた廊下の端については、重み6 +ランダム（3）を選択しました。 水平または垂直の廊下のタイルの場合は、重み2を選択しました。コーナーの場合は、重み3 +ランダム（3）を選択し、空き領域-1を選択しました。
重みに基づいて、廊下の端にある果物の場所が最も可能性が高いことは明らかであり、コーナー、廊下、および空きエリアに配置があります。 生成されたレベルごとに、重みは1回だけ生成されます。
障害物（石、車、樽）は同様の方法で作成されますが、違いはそれらの重量が果物の重量から分離されていることです。 選択されている場合、レベル内の障害物の数を示す障害物の特定のランダムな密度もあります。
ところで、スケールの助けを借りて、他のトリックを行うことができます。 その後、私は眠っているハリネズミとアリクイを追加しました（その説明は記事の冒頭にあります）。 廊下の中央に配置することは意味がないため、廊下の場合は重み= 0です。
このアニメーションは、果物や障害物のレベルで場所を示しています。
最終的に生成されたレベルは、以下の静的画像に示されています。 それを解決するには、6つの動き（右、上、左、下、右、上）が必要です。 [生成]ボタンをクリックしてから1〜2分後、興味深いレベルが表示されます。6回の移動後に通過することができます（通過するのに30回の移動が必要なレベルは誰もプレイしません！）。 さらに、彼の検索のために少し苦しむ必要はありませんでした。 しかし...あなたはいつでも少し良くすることができます。 記事のこの時点から、レベルをより美しくしようとします。
エディター
前のパートでレベル生成が完了しました。 エディターはドラッグアンドドロップをサポートしているため、オブジェクトを簡単にドラッグアンドドロップして、より高いレベルの対称性を得ることができます。 たとえば、次のように：
変更を行った後、ソルバーを使用してレベルを再テストすることが重要です。 時々小さな変更がレベルの解決不能につながる可能性があります。 この例では、変更によりソリューションへの移動数が6から7に増加しました。
手動編集のこの段階では、レベルの手順生成へのアプローチが分岐します。 手動で変更を適用する必要がある場合は、レベルジェネレーターが時間を大幅に節約します。 このステップが必要ではなく、生成されたレベルが十分であると思う場合、ジェネレーターは最終的なゲームの一部になることができます。 プレイヤーは自分で新しいレベルを生成することができます。
最終結果
手続きレベルの生成により、時間を大幅に節約できました。 ジェネレーターはゴミを作成できるという事実-通過するのが難しすぎるか、難しすぎるレベル、障害物やorいレベルに満ちたレベル-にもかかわらず、多くの時間を節約できました。 彼はまた、私たちが好きではないレベルの一部を選択してドロップすることを許可しました。 手作業で行った場合、数か月の作業が必要になります。 この記事で生成されたレベルが最終ゲームでどのように見えるかを以下に示します。
著者について： Tomas Rychnovskyは、Android、iOS、およびTizen向けの小さなモバイルゲームのインディーデベロッパーです。