Lispを活用したゲーム開発、第2部: ダンジョンとインターフェース

 (gitlab.com)
2 ポイント 投稿者 GN⁺ 2024-10-19 | 1件のコメント | WhatsAppで共有
  • Common Lispのゲーム開発環境の上で、ECSアーキテクチャとメタ言語的プログラミングを実際のダンジョンクローラーの例へ拡張してみるチュートリアル
  • Tiled XMLマップをcl-tiledで読み込んだ後、CLOSオブジェクトをそのまま使わずECSコンポーネントへ移し、レンダリング、衝突、メモリ管理を分離する
  • タイルプレハブ、画像ポインタ、親子インデックス、finalizerを組み合わせ、重複ロードとdouble freeを避けつつ、Tiledのカスタムプロパティをデータのように活用する
  • プレイヤーと敵はECSシステムで移動、アニメーション切り替え、衝突処理を行い、敵はcl-astarベースのA*経路探索で壁を避けて追跡する
  • NuklearベースのUIとナラティブオブジェクト、一時停止、勝利条件まで加え、約500行規模の小さなダンジョンクローラーの例を完成させる

プロジェクトの開始と基本実行

  • Part 1で扱ったEntity-Component-Systemアーキテクチャとメタ言語的プログラミング手法を用いて、UI付きの小さなダンジョンクローラーを作る
  • 実行可能なデモバイナリとソースコードはecs-tutorial-2 GitHubリポジトリにある
  • 開発環境はPart 1のCommon Lispゲーム開発環境を前提とし、SBCL REPLでQuicklispディストリビューションを更新する
    • (ql-util:without-prompting (ql:update-all-dists))
  • cookiecutter-lisp-gameテンプレートで新しいプロジェクトecs-tutorial-2を作成し、例ではバックエンドとしてliballegroを選択する
  • プロジェクトディレクトリをQuicklispのlocal-projectsに接続した後、src/main.lispのウィンドウサイズを1280×800に変更する
  • (ql:quickload :ecs-tutorial-2)と(ecs-tutorial-2:main)を実行すると、指定した解像度の黒いウィンドウとFPSカウンタが表示される

TiledマップとECSストレージ

  • ダンジョンマップの作成には、オープンソースのマップエディタTiledを使用する
    • Tiledはクロスプラットフォーム・クロスエンジンのツールであり、マップデータをXMLで保存する
    • Common Lispではcl-tiledがTiledファイルをLispオブジェクトとしてロードする
  • 例のタイルセットにはDungeon Tileset II - Extendedを使用する
    • 元の16×16タイルは小さいため、ImageMagickで200%拡大し、32×32タイルとして使う
    • level1.tmxとタイルセットファイルは、チュートリアルで提供されるResources.zipから入手できる
  • ecs-tutorial-2.asdにcl-tiled依存関係を追加し、src/map.lispを新しく作ってマップの読み込み・表示コードを分離する
  • src/package.lispではcl-tiledをtiledというローカルニックネームとして登録する

CLOSオブジェクトをECSコンポーネントへ移す理由

  • cl-tiledはマップデータをCLOSオブジェクトとして返すため、REPLで探索しやすい
  • ゲームループでこれらのオブジェクトを直接使うと、ランタイムディスパッチのコストが大きくなる可能性がある
    • 1280×800ウィンドウを32×32タイルで埋めるには、最低でも40×25 = 1000個のタイルが必要になる
    • 別のデモでは、12コアのRyzen 5 3600でマップレンダリングを有効にすると、FPSが20,000から600まで落ちる
    • 1フレームあたり約1/600 - 1/20000 = 0.0016秒、つまり1.5ms以上が追加される
  • cl-tiledが読み込んだデータをcl-fast-ecsストレージへ移すことで、ディスパッチを減らしCPUキャッシュの活用を改善できる
  • cl-fast-ecs依存関係を追加し、initでecs:make-storage、updateでecs:run-systemsを呼び出す

マップ、タイル、プレハブコンポーネント

  • mapは、ロードされたマップエンティティを表すタグコンポーネントである
  • map-tileは個々のタイルを表し、壁や閉じたドアのような障害物かどうかを示すobstacleブールスロットを持つ
  • parentコンポーネントは、タイルとマップ関連オブジェクトがどのマップエンティティの子なのかを示す
    • entityスロットに:index childrenを指定し、特定の親の子エンティティを高速に見つける
    • インデックスはオープンアドレス法のハッシュテーブルベースなので、平均**O(1)**の検索を提供するが、生成・削除時には更新コストがある
  • ecs:*entity-deleting-hook*にフックを追加し、親エンティティが削除されるとchildrenインデックスで見つけた子エンティティも一緒に削除する
  • imageコンポーネントはALLEGRO_BITMAPへのCポインタだけを保存する
    • タイルセット画像はal_create_sub_bitmapで32×32の断片を作成し、そのポインタを保存する
  • map-tile-prefabは、TiledタイルのグローバルID gidを持つタイルプレハブである
    • gidには:index map-tile-prefab :unique tを指定し、IDで単一のプレハブエンティティを見つける
    • マップ上の実際のタイルはプレハブのimageなどをコピーする一方、位置は別のpositionコンポーネントとして持つ
  • image finalizerは、エンティティがmap-tile-prefabである場合にのみal_destroy_bitmapを呼び出す
    • 同じALLEGRO_BITMAPポインタを複数のマップタイルが共有するため、double freeを避けるためである
  • positionとsizeは、画面座標とサイズをsingle-floatで保存する
    • liballegroがOpenGL互換性のために画面座標を単精度浮動小数点で扱うので、同じ方式に従う

画像レンダリングとマップ読み込み

  • render-imagesシステムは、positionとimageを持つエンティティをレンダリングする
    • al_hold_bitmap_drawingでsprite batchingをオン・オフする
    • al_draw_bitmapで指定座標に画像を描画する
    • プレハブはpositionを持たないため、このシステムでは処理されない
  • load-bitmapは、al_load_bitmapをal:ensure-loadedでラップした画像読み込み関数である
  • tile->specは、タイルプレハブ生成のためのECSオブジェクト仕様を作る
    • 親マップエンティティ
    • タイル画像の断片
    • TiledグローバルタイルID
    • タイルサイズ
  • load-tile-prefabは、map-tile-prefabインデックスで既に読み込まれたプレハブかどうかを確認し、なければmake-objectで生成する
  • load-tileは、実際のマップタイルエンティティを作る際にプレハブからコンポーネントをコピーし、positionを追加する
  • load-mapは、tiled:load-mapで読み込んだCLOSオブジェクトからタイルセットとレイヤーを走査する
    • タイルセット画像を読み込み、各タイルをプレハブとして生成する
    • タイルレイヤーの各セルをエンティティにし、プレハブデータをコピーする
  • Tiledのレイヤー順序はエディタ順のまま維持され、make-entityは増加するエンティティ番号を保証する
    • システムは古いエンティティから処理するため、上位レイヤーのタイルは後で描画され、下位レイヤーを覆う
  • すべてのタイルを個別エンティティとして保存する方式が唯一の答えではなく、静的マップをバッファへ事前レンダリングする方法も可能である

タイルアニメーション

  • Tiled はアニメーションタイルをサポートしているため、松明や魔法の噴水のような要素を表現できる
  • common.lisp と animation.lisp を追加し、共通コンポーネントとアニメーション関連のコンポーネント・システムを分離する
  • animation-frame コンポーネントはアニメーションの1フレームを表す
    • sequence はアニメーション名で、keyword 型として保存する
    • sequence-frames インデックスで特定アニメーションのフレームを探す
    • duration は秒単位のフレーム持続時間である
  • animation-state は実際のマップ上のアニメーションタイルの現在状態を保存する
    • 現在の sequence
    • 現在の frame
    • 現在フレームの duration
    • 現在フレームが表示されてからの elapsed 時間
  • let-plus 依存関係を追加し、フレーム切り替えコードを簡潔に記述する
  • update-animations システムは dt 分だけ elapsed を増やし、持続時間を超えると次のフレームへ切り替える
    • フレーム時間は大きな dt より短い場合があるため、floor で何フレーム飛ばすべきかを計算する
    • truncate によりフレーム番号がリスト長を超えたら先頭に循環するようにする
    • image の bitmap ポインタを次フレームのプレハブの bitmap に変更する
  • アニメーションの持続時間は Tiled ではミリ秒で保存されるため、animation->spec で秒単位に変換する
  • instantiate-animation は実際のタイルエンティティに animation-state を作成し、同じアニメーションが完全に同期しないよう elapsed を 0 と duration の間の乱数で初期化する
  • アニメーションタイルは Tiled のプロパティ "sequence" を持っている必要がある
    • このプロパティがないと NIL 名で読み込まれ、想定したアニメーション名で見つけられず、型エラーが発生する可能性がある

プレイヤーキャラクターと操作

  • character.lisp を追加し、移動可能なキャラクター向けの character コンポーネントを定義する
    • speed は1秒あたりのピクセル速度である
    • target-x、target-y は移動目標座標である
    • 初期目標値は single-float-nan にして、新しいキャラクターが理由なく左上へ移動しないようにする
  • player タグコンポーネントは bit スロットと :index player-entity :unique t を使う
    • (player-entity 1) でプレイヤーエンティティを O(1) で見つけるための構造である
    • グローバル変数にプレイヤーエンティティを保存しない
  • 初期実装ではタイルセットからオーク画像を切り出して player.png を作り、load-player でプレイヤーをハードコードして生成する
    • 位置は (64.0, 64.0)
    • サイズは 32×32
    • 速度は 100.0
  • move-characters システムは目標地点までキャラクターを移動させる
    • NaN の目標座標があれば現在位置で初期化する
    • 浮動小数点の直接比較の代わりに approx-equal を使う
    • atan、cos、sin、速度、dt で新しい座標を計算する
  • control-player システムは W、A、S、D キー入力を読み取って目標座標を更新する
    • al:with-current-keyboard-state と al:key-down を使う
    • clamp で画面境界の外に出ないようにする
    • :after (move-characters) にして移動システムの後で実行し、NaN 初期化の問題を避ける

Tiled のプロパティによる衝突判定とオブジェクト読み込み

  • 当初は壁が床タイルと同じ通常画像だったため、プレイヤーが壁をすり抜けていた
  • Tiled のカスタム型として map-tile クラスを作り、obstacle Boolean メンバーを追加する
    • 壁タイルのプロパティとして map-tile を追加し、obstacle をチェックする
  • properties->spec 関数は Tiled のプロパティハッシュテーブルを ECS オブジェクト仕様に変換する
    • Tiled のカスタムクラスはコンポーネントとして扱われる
    • クラスメンバーはコンポーネントスロットとして扱われる
    • 例は ((:map-tile :obstacle t)) という形式である
  • load-tile-prefab は properties->spec の結果をプレハブ仕様に含める
    • プロパティがなければ spec-adjoin によりデフォルトの map-tile コンポーネントが追加され、obstacle はデフォルト値 nil を持つ
  • position コンポーネントに tile-hash スロットと tiles インデックスを追加する
    • tile-hash は x、y を整数化した後、1つの64ビット整数にパックする
    • 特定タイルの左上座標にあるすべてのエンティティを tiles インデックスで探す
  • tile-start は任意の座標が属するグリッドタイルの左上座標を返す
  • tile-obstacle-p は同じ座標のエンティティ群の中に、map-tile かつ obstacle が真のタイルがあるかを確認する
  • obstaclep は任意座標について、そのタイルが障害物かどうかを検査する
  • control-player は移動方向に応じてキャラクター矩形の関連する角のタイルを調べ、障害物があれば目標座標を現在位置に戻す
  • この衝突方式は完全ではない
    • キャラクターの中心座標を基準に設計すれば、数学とコードを単純化できる可能性があるが、この例では複雑さを避けるため現行方式を維持している

マップからのプレイヤーとアニメーションキャラクターの読み込み

  • Tiled に character と player のカスタムクラスを追加する
    • character は speed float メンバーだけを持つ
    • target-x、target-y はデフォルト値を使うため省略する
    • player はデフォルト値 1 の player int メンバーを持つ
  • Tiled のオブジェクトレイヤーにタイルオブジェクトとしてプレイヤーキャラクターを配置し、character と player のプロパティを付与する
  • load-map は tiled:object-layer も処理するよう拡張される
    • オブジェクトプロパティを properties->spec で ECS コンポーネントに変換する
    • tiled:tile-object は load-tile でタイルデータとアニメーションをコピーし、位置を設定する
    • Tiled のオブジェクト座標は左下基準なので、y からオブジェクトの高さを引いて左上基準に合わせる
  • ハードコードされた load-player 呼び出しと関数は削除される
  • この構造は Tiled のマップデータを ECS オブジェクトとして直接読み込む方式であり、データ駆動プログラミングに近づいている
  • キャラクターアニメーションは、オークの orc-idle と orc-run シーケンスをタイルセットで定義して使用する
  • change-animation-sequence はエンティティの現在アニメーションを変更する
    • すでに同じシーケンスなら何もしない
    • 新しいシーケンスの先頭フレームを sequence-frames インデックスで探し、animation-state と image-bitmap を更新する
  • move-characters はキャラクターが停止していれば :orc-idle、移動していれば :orc-run に切り替える

敵、ゲームオーバー、A* 経路探索

  • enemy コンポーネントは敵の行動に必要な2つのスロットを持つ
    • vision-range: プレイヤーを視認して反応し始める距離
    • attack-range: 攻撃範囲
  • ゲーム終了のために *should-quit* グローバル変数を追加し、メインループはこの値が真なら終了する
  • handle-enemies システムはプレイヤー座標を取得して敵と比較する
    • プレイヤーが視界範囲内にいれば、敵の目標座標をプレイヤー位置に設定する
    • プレイヤーが攻撃範囲内にいれば、*should-quit* を真に設定し、You died ネイティブメッセージボックスを表示する
  • 敵アニメーションは demon-idle、demon-run シーケンスを使う
    • move-characters は has-player-p の結果に応じて、プレイヤーにはオークのアニメーション、敵にはデーモンのアニメーションを選択する
  • 直接追跡方式では敵も壁を通り抜けてしまうため、A* 経路探索を追加する
  • cl-astar を依存関係に追加する
    • このライブラリは、問題に合わせて最適化された経路探索関数をマクロで生成する
  • 経路はコンポーネントスロット内の配列として保存せず、各経路点を個別のエンティティとして表現する
    • path-point は x、y、traveller を持ち、traveller には path-points インデックスがある
    • path は最終目的地 destination-x、destination-y を保存する
    • character の目標座標は次の経路点、path は最終目的地を表す
  • follow-path システムは最初の経路点を取得し、キャラクターをその地点へ移動させる
    • 地点に到達したら、その path-point エンティティを削除する
    • それ以上地点がなければ、path コンポーネントを削除する
  • find-path は a*:define-path-finder で定義される
    • ワールドサイズはウィンドウサイズをタイルサイズで割って計算する
    • row-major インデクサを使う
    • 目標到達判定はタイル座標が同じかどうかで行う
    • 隣接ノードは8方向で列挙する
    • 障害物、または障害物をまたぐ斜め移動には most-positive-single-float コストを与え、事実上不可能にする
    • ヒューリスティックには octile distance を使う
    • 既存の経路があれば経路点を削除し、新しい path を割り当てる
    • 結果の経路の各点は、path-point と parent を持つエンティティとして生成される
  • handle-enemies は、敵がプレイヤーを視認した際に既存の経路目的地がプレイヤー位置と異なっていれば find-path を呼び出す
  • 変更後、敵はプレイヤーを追いかけつつ障害物を避けて移動する

Nuklear ベースのゲーム UI

  • ナラティブ要素のために GUI が必要だが、Qt や GTK のような従来型 GUI ライブラリは、liballegro のグラフィックスコンテキスト上に描画されるゲーム UI には向いていない
  • UI ライブラリとして Nuklear を使う
    • liballegro と併用するための Common Lisp バインディング cl-liballegro-nuklear がある
    • バインディングは宣言的インターフェース用の DSL も提供する
  • cl-liballegro-nuklear/declarative 依存関係を追加し、src/narrative.lisp を新規ファイルとして追加する
  • パッケージには ui ローカルニックネームを登録し、cl-liballegro-nuklear/declarative を短く参照する
  • UI フォントとして Google Fonts の Alegreya を使い、ファイル名を alegreya-sc.ttf に変更する
  • ui:defwindow narrative はナラティブウィンドウ関数を定義する
    • ウィンドウ位置は画面中央領域として計算する
    • ui:label-wrap で自動改行テキストを表示する
    • ui:button-label "Ok" はクリック時に真を返す
  • Nuklear は immediate mode UI ライブラリである
    • ウィジェットオブジェクトをメモリに保持する retained mode ではなく、毎フレーム描画と処理を行う
    • ボタンクリックはコールバックではなく、毎フレームの戻り値と条件で処理する
  • main.lisp では UI フォントを読み込み、nk:allegro-init で UI コンテキストを初期化する
    • イベントループでは nk:input-begin、nk:allegro-handle-event、nk:input-end を呼び出す
    • レンダリング時には nk:allegro-render を呼び出す
    • 終了時には nk:allegro-shutdown、nk:allegro-font-del を呼び出す

UI スキンとナラティブオブジェクト

  • デフォルト UI は単調なため、Kenney の fantasy-ui-borders 画像アセットを使ってスタイルを付ける
  • *window-background*、*button-normal-background*、*button-hover-background*、*button-active-background* グローバル変数に UI 画像を保存する
  • load-ui は nk:allegro-create-image で画像を読み込み、unload-ui は nk:allegro-del-image で C 側の画像リソースを解放する
  • init で load-ui を呼び出し、メインループ終了時に unload-ui を呼び出す
  • ui:defwindow の :styles 引数で背景、ボタン各状態の画像、テキスト色を指定する
  • narrative コンポーネントは環境ストーリーテリング用オブジェクトを表す
    • text: 表示するテキスト
    • shown: すでに一度表示されたかどうか
    • active: 現在ウィンドウが有効化されているかどうか
    • active には active-narratives インデックスを持たせる
  • show-narrative システムは、プレイヤーがナラティブオブジェクトの近くにいるとウィンドウを表示する
    • インタラクト距離は +interact-distance-factor+ とプレイヤーのタイルサイズから計算する
    • ウィンドウがすでに有効化されているか、まだ一度も表示されていないか、E キーが押された場合に表示する
    • Ok ボタン、Esc、Space、Enter のいずれかでウィンドウを閉じる
  • Tiled には narrative カスタムタイプを作成し、text string メンバーを追加する
  • 衝突判定と位置合わせのため、通行不可オブジェクトはタイルグリッドに座標を合わせる必要がある
  • ナラティブウィンドウが表示されている間もダンジョンが動き続ける問題は、システム実行条件で防ぐ
    • move-characters と control-player に :when (null (active-narratives t)) を追加する
    • 有効なナラティブがある場合、移動と操作システムは実行されない
  • 勝利条件は win タグコンポーネントとして追加する
    • narrative と一緒に付いたオブジェクトでウィンドウを閉じると、*should-quit* が真に設定されてゲームが終了する

まとめとスコープ

  • 最終サンプルは cl-fast-ecs、cl-tiled、cl-astar、cl-liballegro-nuklear を使い、環境ストーリーテリング、敵 AI、GUI を備えた Souls-like ダンジョンクローラーを構成する
  • 実装規模は約 500行のコード である
  • 全コードは GitHub リポジトリ にあり、チュートリアルコード以外に declaim を用いた任意の型宣言も含まれる
  • サウンドデザイン、カットシーン、メインメニュー、レベル遷移、"door problem" などは扱わない
  • Autumn Lisp Game Jam 2024 は 2024年10月25日に itch.io で開催され、Lisp 方言で10日間ゲームを作り、互いに評価・フィードバックするイベントである
  • このパートは Spring Lisp Game Jam 2023 出品作 Thoughtbound をベースにしている
  • 次のパートでは規模を広げ、さらに高度な AI を追加してリアルタイムストラテジーゲームを作る挑戦を予告している

関連記事

1件のコメント

 
GN⁺ 2024-10-19
Hacker News のコメント

  • すべての技術チュートリアルがこんなふうだったらいいのに。構成がよく、文法ミスもほとんどなく、新しいトピックを紹介するたびにちょうどよい分量で説明し、完全なコード例と、そのコードが実際に何をしているのかを示すビジュアル資料までそろっている。
    内容を深く扱うのに十分な長さがありつつ、パート1を読んでおらず、数年前に Common Lisp を数か月触った程度でもついていけるくらい独立している。Clojure と Emacs Lisp はかなりやったことがある。
    Bravo, awkravchuk/Andrew :^)
    （https://mxjn.me/2024/10/17/1 からのクロスポスト）

    • 何よりも動画ではなく文章である点が大きい。コピー＆ペーストでき、はっきり読めて、自分のペースで追いかけられ、静かに消費できる。
      オフライン利用や保存用に簡単に保存して注釈も付けられ、検索もしやすいという利点がある。

  • Common Lisp についての優れたプロジェクトや記事ほど、技術分野で心を動かされるものはめったにない。本当に大きな贈り物のような記事だ。
    パート1が出たときに読んだので、今回のパートを読むのも本当に楽しみだ。著者に賛辞を送りたい。

  • package.sh と全般的な3つのOS向けビルド管理だけでも、それ自体がマスタークラスだ。GitHub リポジトリをざっと見るだけでも多くを学べた。
    普段は SBCL や LispWorks で Common Lisp のコマンドラインアプリをビルドしているが、次は ECL でやってみてもよさそうだ。macOS と Linux の両方のビルドがそろっているのは素晴らしいし、新しいことを試す楽しさもありそうだ。

    • ここ数年、CL インフラの上にそのCI 構成を積み上げているが、壊れ続けているらしい :D

  • とても良い記事だ。Lisp、正確には ClojureScript でマルチプレイヤーの三人称・呪文ベースのシューターを開発している。Web ベースの 3D ゲームで、プロジェクトのために作ったツールや抽象化も含めて、その道のりをブログに書く予定だ。
    興味があればデモはここにある: https://wizardmasters.io

    • Jon Blow も昔、こういうゲームを作ろうとしていた。どうやって、なぜ失敗したのかを見てみると学べるかもしれない。

  • 記事自体は本当にしっかりしているが、パート1のセットアップ手順が Common Lisp 本体、Python、C と複数段階にわたっているのを見ると、なぜ CL が特に若いプログラマーにあまり人気がないのかが表れているように思う。
    残念なことだし、誰かがインストール面でこの言語をもっと手に取りやすくする労力を払ってくれるといいのだが。

    • まったく同じ問題を狙っているとは言いにくいが、https://ciel-lang.org/ は少なくとも手順が多すぎる問題の一部を解決しようとする試みだ。
      私の理解では、選択肢が多すぎることや、古いデフォルトが時代遅れに見えることのほうに焦点を当てている。

  • イベントループは、loop がどれほど本格的な反復用ドメイン特化言語であるかを示す素晴らしい例だ。好きでも嫌いでも ;)

    • loop の代わりに https://iterate.common-lisp.dev/ を使えばいいのでは？ S式ではない見慣れない構文もなく、Lisp 構文に戻るために do も必要ない。
      見苦しい else/end なしに通常の if/when を使え、全体として便利な機能も追加されている。
    • 最初は笑っていたが、数年 Common Lisp でプログラミングしてみると、loop は CL の構成要素の中でも特に好きなものの一つになった。

  • この記事は「Caves of Clojure」を思い出させる: https://stevelosh.com/blog/2012/07/caves-of-clojure-01/

  • ちょうど今週 Python でローグライクの開発を始めたところだが、Lisp でやってみるのも面白そうだ。

  • だまされた気分だ。簡単なゲームの作り方を学びに来たのに、コンピューティング全般についてものすごく多くのことを学んでしまった。
    本当に良い。