子供たちの夢または日曜大工パックマン
彼の人生の誰もが彼自身の自転車を作りました。 それをしたいという願望を正当化するために、私たちは人々がこれを定期的にしなければ、世界は単に多くのことを見ないだろうとしか言えません。
私自身のゲーム、またはむしろゲームの人工知能（AI）を作成するのはかなり前のことでした。 私はカンニングしません。最初は知識の平凡な不足があり、それから奇妙なことに、時間がありました。 子供時代の夢を実現するために、比較的自由な時間を数週間過ごしました。
何が起こったのかを説明し、私がたどった道と、その過程で行った観察についても説明します。 コードを説明するのではなく、夢を実現する過程で遭遇した考慮事項、思考、問題について説明することをすぐに予約します。
構造計画段階
生息地の構造を計画するとき、AIはすぐに拡張性と少なくともある程度の普遍性を築こうと試みました。 可能な限り、オブジェクト指向プログラミング手法を広く使用して、すべてを動的配列で実行することが決定されました。
AI環境のクラスの階層は、クラスのいくつかのペアに基づいていました。
- 重要な点は、パスグラフリンクの交差点を反映するクラスです。
- パスは、キーポイント間の接続を提供するクラスです。
- オブジェクトは、キーポイントクラスから派生したクラスであり、そのインスタンスはパスに配置されます。
- サブジェクト -同じクラスオブジェクトは、そのインスタンスに意思決定機能があります。
Worldクラスはクラスのリストを閉じ、リストされたすべてのクラスをフレーム化して、相互の相互作用を整理します。
仕事には、複雑なゲームコンセプトではなく、特定のゲームコンセプトが必要でした。 そして、そういうものとして、単純な一連のルールのために、 パックマンゲームのコンセプトが選ばれました。
ゲームのオブジェクトとサブジェクトの追加のサブクラスがすぐに特定されました。
- パックマンの主題はそのパックマンです。
- フルーツオブジェクトは、Pakmanのものです。
- ゴーストの対象は、Pakmanがゲームで作成される対象です。
作業計画フェーズ
表面的な分析が示したように、ゲームの本格的な操作に必要なコードの量は、わずかなシステム機能にもかかわらず、非常に大きいことが判明しました。 タスクを多くの孤立したサブタスクに分割する必要があり、少なくとも大騒ぎのいくつかの結果を見ることができるという自然な結論が下されました。
次の実装段階がすぐに特定されました。
- 人工知能が住む世界の機能を確保するクラスの作成（クラスワールド、キーポイント、パス）;
- 世界を描くと同時に、データの視覚化のための機能の基礎を作成します。
- Objectクラスの作成、環境との相互作用。
- オブジェクトの最初のインスタンス、つまりFruitとそのレンダリングの作成。
- オブジェクトをサブジェクトに変えるためのオブジェクトの機能追加の作成。
- Pakmanのインスタンスを作成します。 レンダリング。 ゲームにルールを追加します。
- ユーザーインタラクションコードの開発、「リアルタイム」でのシステムの動作の編成。
- 最短パス検索アルゴリズムの実装。 パクマンの管理と彼のつながり、そして彼の状態の時間による自動変更。
- Ghostのインスタンスを作成します。 レンダリング。 ゲームにルールを追加します。
- システムを詳細に改善します。
- 楽しんでください。
この計画で、私は働き始めました。
実装
最初の2つの段階は簡単でした。 World、Key Point、Pathの3つのクラスが編成されました。それらのコンストラクタ、デストラクタ、参照によってクラスのインスタンス間のリンクの作成を提供するいくつかの関数、そして実際にはすべてです。
Mirクラスのインスタンスは5つのポイントで作成され、パスは中心点がずれたエンベロープを形成するため、ポイント間の距離は明らかに異なる長さでした。 レンダリングは非常に控えめに行われました：線と円を使用して-世界で何が起こっているかを理解できる限り正確に。
ステージ番号3および4も、それほど困難を引き起こしませんでした-果物は走らず、害はありませんでしたが、横たわっていただけです。
ステージ5から開始して、主要な作業が行われました。 サブジェクトの機能は、オブジェクトクラスを使用して、サブジェクトが実行したいタスクのリストの形式で記述されました。 ワールドクラスの機能が追加されました。これは、被験者の事柄のリストを監視し、被験者のタイムクォンタムと被験者の行動に課せられた制限とルールの枠内でそれらを実行しました。
ステージ6 Pakmanインスタンスの外観が奇妙ではないという問題は発生しませんでした。 被験者のタイプのインスタンスが表示され、円の目的の座標でディスプレイに描画されます。 そして、フルーツを食べるためのルールが追加されました。
ステージ7でも、マウスが指定された座標への「実行」コマンドの形式で1つのタスクを生成したとき、問題はありませんでした。 最も近いポイントが検索されました。これは、Pakmanがすでに立っていたパスに落ち、Pakmanは素直にそこに行きました。
冒険はステージ番号8から始まり、最短経路探索アルゴリズムの実装が行われました。 最短経路検索機能は、動的配列およびグラフ構造に適合した修正リーアルゴリズムでした。 主な困難は、逆方向の移動が実装されたコードを書くときでした。 オブジェクトのインスタンスを移動する際のグラフ構造の再配置の数を減らすために、オブジェクトはパスで接続されたノードのキーポイントとしてではなく、パスに属するキーポイントとして作成されました。 執筆時点で動作するコードを持っていることは、選択したソリューションの正確性についてまだ不明です。 これは簡単です。世界のグラフをローカルで再構築すると同時に、グラフの変更されたフラグメントを移動するサブジェクトのルートを作成するか、サブジェクトとオブジェクトのクラスをパスの不変グラフに配置します。
もちろん、作業のすべての段階で、メモリアクセスエラーは常に点滅していました。 最も残酷なケースは、ゲームの途中でメッセージが飛び出したときでした。 ウェイと食べられたときに破壊されたフルーツのコピーとのリンクを削除するのを忘れました。 エラーは、メモリを上書きするときに食べてからしばらくしてから現れました。 破壊されたオブジェクトのデータはそこに保存され、新しい動的オブジェクトによって上書きされませんでしたが、すべてが正常でした。 プログラムの崩壊は瞬時ではありませんでした。
最後に、 ステージ9で最初のゴーストが追加されました。 目的地は常にパックマンの座標でした。 すでに記述されている最短パス検索機能が使用されました。これは、1秒間に24回絶えず呼び出されていました。 アクションのリストを生成した後、システム（ワールド）によってゴーストの動きが自動的に実行されました。
彼がステージ番号10に来たとき、彼らが言うように、そりは急いだ！
ランダムなカードジェネレーターが作成されました。 パスを生成するためのマップを作成するとき、許容される作成のいくつかの基準が作成されました：ノードがポイントで交差するパスは4つ以下であり、ノードが特定の距離の既に配置されたパスに近づいてはならず、パスが特定の定数より長くないようにする必要があります。
その後、Pakmanを頑固に悩ませるゴーストがいくつか追加されました。
そのような幽霊と遊ぶことは単に非現実的でした。 そして、「戦争の霧」が必要であることがわかりました。その後、ゴーストはより自然に振る舞い、マップの反対側のどこかでパクマンのルートをわずかに変更してもルートを根本的に変更しません。
最初の考えは、各被験者が世界の目に見える要素の配列を作り、被験者の記憶を完成させて、どこで、誰が、いつ見たのかを保存することでした。 考えてみると、ハエを食べたいクモにとっては、実装するのが非常に難しくて面倒だということに気付きました。
解決策は可能な限りシンプルであることがわかりました。 ランダムに、ゴーストが続いたマップ上のポイントがありました（したがって、マップをさまよい、パックマンを検索する単純な構成が行われました）。 Pakmanがゴーストの特定の（一定で指定された）可視範囲内にある場合、ゴーストには再構築されたルートがあります。 被害者が視界にいるとき、ゴーストは絶えずそのルートを再構築し、パックマンが視界を超えたとき、ゴーストは被害者が最後に見た場所を追跡し続けました。 このポイントに達すると、マップの周りを盲目的にさまよい始めました。
これで実際に停止し、静かに息をしました。
最後に、装飾要素が完成しました：「ゲームの終わり」（Pakmenを食べる）、カウントポイント（食べた果物の数）、「レベルの完了」（すべての果物を食べる）。
苦しみの結果。
大量の汗と血がこぼれたにもかかわらず、比較的小さな結果が達成されました。さらなる研究のために、世界の基礎が実現され、そこでは最も単純なクモのような捕食者の知性が生きています。 どうやら、既存のAIアルゴリズムの修正を作成して、「犠牲者」の動作（ゲーム内では、これらはPakmanから逃げる果物）と、Pakmanボットを作成し、電力を無駄にしない組み合わせAI（「Predator-Prey」）を実装する必要があります「プレイ」するが、この「コロボック」の試験管に投げ入れるのを見るのが楽しみだ。
何が起こったのかを直接見るには、「 ここ 」（Win32用の実行可能ファイル）*になります。 「マトリックスモード」トグルスイッチに注意してください。 電源を入れると、システムがどのように決定を下すかがわかり、ネオを少し感じることができます。 残念ながら、AIの動作をよりよく理解するために、第10段階で作成することを考えました。 以前にそれを行っていた場合、最短パスを見つけるためのアルゴリズムのデバッグに費やす時間を短縮しました。
PS経済的な実現可能性と最適性の理由ですべてが行われているわけではなく、常に行われているわけではありません。 グラフィックのシンプルさにもかかわらず、「彼女」が呼吸したとき、私は言葉で表せない喜びを経験しました。
*計画されたすべての作業を完了し、記事を書いた後、もう1つのまれにしか発生しないエラーを発見しました。 エラーが発生した場所は、問題がゲームワールドのシミュレーションが通常のタイマーハンドラーで実行され、Pakmenコントロールが通常のマウスハンドラーで実行されていることを示しています。 一般に、両方の機能でアクセスされるデータの整合性を保証する通常のセマフォやその他の同様の「難解な」ものはありません。
編集してくれてありがとう： evocatus 。