プロフィール

Na-7

Author:Na-7
SE(システムエンジニア)として約15年間システム系ソフト会社を勤めあげ、2008年3月退社。現在、ゲーム制作会社設立を目指して活動中。


アクセスカウンター


最新記事


最新コメント


最新トラックバック


月別アーカイブ


カテゴリ


DATE: CATEGORY:スポンサー広告
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
| BLOG TOP |
DATE: CATEGORY:三国志軍記開発
最短経路の例題
最短経路の例題
エースター法で前回の例題を探索するサンプルを作成した。エースター法はダイクストラ法より効率が良いとのこと。



◎概要調査

今回は、ダイクストラの改良版であるエースターアルゴリズムについて調査します。

こちらによると、エースターは『ダイクストラ法を推定値が小さい方ものから順に探索するよう改良したもの』とあります。‘ヒューリスティック関数’というものがポイントらしいのですが、こちらの記述ではよくわかりません。

次に参照したのはこちら。読みやすい文章なので、何となくわかったような気になりましたが、「ではこの文章を具体的にコード化できるか?」と自身に問いかけると、やはりまだあいまいな部分が多いようです(汗)



◎ヒューリスティック関数とは?

まず大前提として、以下の式があります。

f*(n) = g*(n) + h*(n)

これを変形すると、以下のようになりますよね?

ヒューリスティック関数:h*(n)
h*(n) = f*(n) - g*(n)

上記の数式イメージが先行するあまり、ヒューリスティック関数がなかなか理解できませんでした。ヒューリスティック関数が理解できないと、エースターは理解できません。


その後、他の資料を漁ったり1から考え直したりして、ようやく誤解に気付きました。先の数式イメージは、数学的に正しくても、ヒューリスティック関数としては不正解です。

ヒューリスティック関数の具体例は、前述の資料に記述されてました。

「地点nからゴール地点までの直線距離をh*(n)とすることが多いようです。」

ちなみに、この記述は私の脳内で「スタートからゴールまでの直線距離」と誤変換されてました(爆)



◎エースターの概要

ヒューリスティック関数を理解すると、エースターも理解できるようになりました。

例えば、ウィキペディアの

「アルゴリズムの流れ」の6-1に「また g*(n) は g*(n) = f*(n) - h*(n) で求めることができる。」

とありますが、これは

「出発点からゴールまでの直線距離 - 地点nからゴールまでの直線距離」

のようにイメージすると理解しやすいです。

また、g*(n)の値が小さい方が低コストとして優先されるので、

「地点nからゴールまでの直線距離が近い経路を優先する効果がある」

と言えそうです。


こちらの「◆A*って具体的には何なのよ?」にエースターの概要が簡潔にまとめられています。これを読んでから他の資料と組み合わせて理解すると良いでしょう。



◎サンプルが動かない?

概要は把握したので、こちらのサンプルコードを動かそうとしたのですが、コピペするとエラーになります。ソース一式をダウンロードすると、.slnファイルが開けません。XNAのバージョン違いによるものでしょうか?

ソースを解析するという選択肢もありますが、統合エディタで開けない&解説無いのでちょっと気後れします。

他のサンプルコードも探してみたのですが、見当たりません。

…うむむ、自作した方が早いかも?



◎サンプル作成

というわけで、ウィキペディアのアルゴリズムに沿ってコーディングしました。

・結果
root:F ← E ← B ← A コスト:5

おお正解!
出来たっぽいですよ!!



◎不正解1件

スタートとゴールを変えて10パターン以上試したら、1件だけ不正解がありました。

○ スタート:A、ゴール:F F ← E ← B ← A  コスト:5
○ スタート:F、ゴール:A A ← B ← E ← F  コスト:5
○ スタート:B、ゴール:F F ← E ← B  コスト:4
× スタート:F、ゴール:B B ← E ← C ← F  コスト:5

他は正しいのに、何故4番目だけ不正解になるのでしょうか?

ヒューリスティック関数に問題があるのかなぁ…ブツブツ。



◎原因判明

なかなか原因特定に至らず、最後は全変数の値の変化を1ステップずつチェックして判明したのですが、

if (this.openList.IndexOf(m) > 0)

上記コードを下記のように修正したら直りました。

if (this.openList.IndexOf(m) != -1)

またしても、アルゴリズムと無関係のミスでした。ぐはっ!!



◎サンプルコード

サンプルコードをHPにUPしました。

A*(エースター:最短経路探索アルゴリズム)サンプル



◎次回予告

ようやくエースターのサンプルが作成できたので、次回はメインプログラムにエースターを実装します。

スポンサーサイト

テーマ : ゲーム製作 関連 - ジャンル : ゲーム

| BLOG TOP |
DATE: CATEGORY:三国志軍記開発
最短経路の例題
最短経路の例題
A地点からF地点までの最短経路は、A→B→E→F(1+1+3=5)である。このような最短経路探索のアルゴリズムの1つにダイクストラ法がある。



◎要件の確認

今回は、部隊の最短移動ルートを作成します。
まず、フィールドと移動規則を確認しましょう。

・フィールドの地形種別は、256×256の配列に格納済

・部隊は縦/横/斜めの8方向に移動可能

・侵入コスト(その地形に侵入するために要する時間)は、
 地形種別と移動タイプの組み合わせで決定される

・今回はフィールド高度を考慮しない
 →フィールド高度を移動コストに反映させるか後日検討

今回は、侵入コストが最も低いルートを作成します。



◎調査開始

最短ルートの探索方法についてネットで検索すると、こちらの「最短経路探索」にA*アルゴリズムが紹介されてました。

これはダイクストラ法の改良版らしいのですが、ウィキペディアの記述だとわかりにくいので、こちらでダイクストラ法について勉強しましょう。



◎最初のサンプル

文章の内容は一応理解したので、プログラム例をC#用に若干修正して動かすと、cost[]の値は全て0になりました。
…ああ、nに0以上の値をセットする必要があるのですね。

しかし、nに適当な数値をセットすると、無限ループに陥るらしく、いつまで待っても終了しません。
どういうことでしょうか?

しばらく悩んだ末、

if (!this.used[x] && min > this.cost[x])

上記の!を削除するとプログラムは正常終了し、以下のような結果になりました。

・プログラム1

・プログラム1の実行結果
i = 0 used = False cost = 1000000000
i = 1 used = False cost = 1000000000
i = 2 used = False cost = 0
i = 3 used = False cost = 1000000000
i = 4 used = False cost = 1000000000


goalを2としたので、「i=2, cost=0」は正しいです。しかし2以外のコストが全て上限値というのはおかしいですね。また、usedの値は全く更新されません。

修正ミスか?使い方の問題か?
最も不可解なのは、元のソースにusedの値を更新するコードが存在しないことです。

その後もあれこれ悩んだのですが、埒があかないので他のサンプルを探すことにしました。



◎他のサンプル

というわけで、こちらこちらを参考に、勉強し直しました。

なるほど、未確定ノードのうち最短のノードから順次確定していくのですね。こちらの方が、途中経過の解説が詳しくてわかりやすいです。

理論とサンプルコードを理解してから、最初のサンプルを見直すと…やはり、usedの値が更新されていないことが問題と思われます。

条件式を元に戻してusedの値を更新すると…全ノードの最短コストが算出されました!

・プログラム2

・プログラム2の実行結果
i = 0 used = True cost = 0
i = 1 used = True cost = 1
i = 2 used = True cost = 3
i = 3 used = True cost = 2
i = 4 used = True cost = 2
i = 5 used = True cost = 5


i=0をゴールとした場合、上記の結果となりました。他のノードをゴールにした場合でもOKです。
(注:最初の資料のゴールと、次の資料のスタートは同義)

結局、最初のサンプルに問題があったようですね(^_^;



◎改良

最初のサンプルコードは、コスト情報を配列で管理していました。これだとメモリを無駄に喰う可能性があるので、ノードやエッジの情報を構造体で管理しましょう。また、経路情報も記憶して、最短ルートを出力しましょう。

しかしエラーが発生したり無限ループに陥ったりで、思うように動きません。何か勘違いしてる気がしてきたので、こちらで構造体について確認しました。

構造体は値型?うわー、参照型と思ってました。
自分で言うのも何ですが、プログラマーとしてかなり恥ずかしいレベルですね(汗)


構造体をクラスに変えると、問題が概ね解消しました。しかし経路情報(直前のノード番号)はまだおかしな値が散見されます。直前のノード番号を記憶しておいて、次回ループ時に設定するんじゃないのかな?

…そうか!接続先ノードのコスト情報を更新する際に、確定済みの情報を設定するんですね!

・プログラム3

・プログラム3の実行結果
i = 0 used = True cost = 0 from = 0 最短経路:A → A
i = 1 used = True cost = 1 from = 0 最短経路:B → A
i = 2 used = True cost = 3 from = 4 最短経路:C → E → B → A
i = 3 used = True cost = 2 from = 0 最短経路:D → A
i = 4 used = True cost = 2 from = 1 最短経路:E → B → A
i = 5 used = True cost = 5 from = 4 最短経路:F → E → B → A


正しい最短経路が出力できました^^



◎余談

Wikipediaの「探索」に、探索アルゴリズムが多数紹介されています。こんなにあるんですねぇ。



◎次回予告

ダイクストラ法はわりと単純なアルゴリズムだそうですが、理論とは別の問題で難儀したような(苦笑)

次回は、さらに効率的と思われるA*(エースターアルゴリズム)について調査します。

テーマ : ゲーム製作 関連 - ジャンル : ゲーム

| BLOG TOP |
DATE: CATEGORY:三国志軍記開発
三国志2
三国志2(正式名は三國志II)
配下武将の数だけコマンドを出せるようになり、戦略の幅が広がった。一騎討ち、伏兵、援軍等のシステムが追加され、新君主でプレイ可能となった。義理や相性など、画面上で確認できないマスクデータも搭載された。



◎進捗状況確認

三国志軍記の開発はスタートから2年半が経過しました。
現在の進捗状況を整理します。

○プログラム/データ関連
・地形モデル/マップオブジェクト/ユニット/武将関連の
 基礎部分は完了

・情報画面/任務選択画面の基本パターンを確立


○2DCG関連
・基本的なCGは全て完了


○3DCG関連
・XSIの基礎を修得し、XNA連携手順を確立

・上記以外は未着手


○音関連
・未着手


完了した作業項目は、全体の半分以下です(ー_ー;



◎振り返る

この2年半を一言で振り返ると、こんな感じです。

『3DCGもC言語も初心者レベルの人間が、(独学で)3D地形と数千体のモデルを60fpsで動かすのは予想以上に大変なことであった。』

他にもっと効率の良いやり方(学習方法等)があったかもしれませんが、今更そこを論じてもやり直しはできないので、今回は触れません。

ともかく一番難しい課題はクリアしたのですから、今後はガンガン進めていきましょう!



◎年間スケジュール

2009年度開発スケジュールをベースに、年間スケジュールを見直しました。作業項目に関する変更点は以下の通りです。

・作業項目「入力画面インターフェース」を削除

・作業項目「部隊戦」を削除

・任務(現7種類)毎に作業項目追加

画面系や部隊戦という括りをやめて、任務単位で作成することにしました。それ以外は変更ありません。

2011年度開発スケジュール(2011年5月版)

年末一次リリースを目標にスケジュールを組みましたが、正直厳しいです。まだこんなにやることあるんですね(笑)



◎次回予告

次回は部隊の移動ルートを作成します。
侵入不可地域の回避ってどうやるんですかね~?

テーマ : ゲーム製作 関連 - ジャンル : ゲーム

| BLOG TOP |
DATE: CATEGORY:三国志軍記開発
任務情報画面01
開発中の任務情報画面
従来はボタンのみであったが、現在の任務情報を確認しながら新しい任務を発信できるようになった。



◎駐留任務確認画面の調整

今回は、駐留任務関連の画面調整を行います。

最初は駐留任務確認画面です。駐留目標と移動方針が反映されるようにします。

駐留任務確認画面02

移動方針は複数項目存在するので、とりあえず上図のように枠を広げて対応しました。



◎連隊情報画面の調整

任務情報を保持するクラスは軍団/連隊/部隊の3種類あります。また、任務は駐留/攻撃/計略など現在7種類ありますが、任務の種類によって任務内容のパラメータが異なります。

任務保持者と任務にそれぞれどのようなインターフェースを持たせて、誰が何をどのタイミングでアクセスすべきか?
C#のインターフェースに不慣れなため、何度か作り直していたのですが、ようやく落ち着きました。

連隊情報画面05

連隊情報に任務情報を追加し、更新した内容を画面に反映しました。

しかし、この画面では詳細な内容が確認できませんね。
任務ボタンを押したら、現在の任務の詳細内容を確認できるようにしましょう。



◎任務情報画面の作成

従来は、任務を決定したタイミングで、任務インスタンスを作成していました。これだと、最初に任務ボタンを押したタイミングでは任務インスタンスが存在せず、エラーになってしまいます。

そこで、ゲーム開始時に全連隊にデフォルトで駐留任務を割り当てました。最終的には、シナリオや連隊毎に初期任務を設定可能とする必要がありそうです。

任務情報画面01

任務選択画面改め、任務情報画面としました。任務情報の確認と、新しい任務の指令/提案が可能です。



◎動画

任務指定フローが確立したので、久々に動画をUPします。

…あれ?やたら重いぞ?
そうか、原因は高解像度ですね。
録画時は1024×576に落としましょう。
(通常時は1280×720でも余裕で60fps出ます)

ウィンドウや文字の大きさは今の所固定なので、解像度を変えると表示面積に対する比率が変わりますね。その辺は最終段階で調整しましょう。



サクサク動いて違和感を感じないUI(応答画面)を心掛けて作成しました。いかがでしょうか?



◎次回予告

次回は年間スケジュールを見直します。

テーマ : ゲーム製作 関連 - ジャンル : ゲーム

| BLOG TOP |
DATE: CATEGORY:三国志軍記開発
三国志1
三国志1(正式名は「三國志」)
コーエー三国志シリーズ第一弾。「配下の人材」を登場させた画期的なゲームシステムで新ジャンルを開拓した。
土地強制交換や空白地のドサ廻り(金米回収)など、シリーズ中でも1独自のルールや戦略は多い。



◎4月の目標達成度

・活動時間月160時間以上

実績:96h(達成度:60%)

 (中間目標:4/15迄に80h以上)

実績:32h(達成度:40%)


・拠点データ調整(8h)

実績:4h(達成率:100%)


・ユニット選択メニュー作成(16h)

実績:6h(達成率:100%)


・移動メニュー仮作成(24h)

実績:26h(達成率:100%)


・履歴フロー検証(24h)
・企画見直し(16h)
・年間スケジュール見直し(16h)
・別件企画(8h)

実績:未着手(達成率:0%)


・ブログ更新/HP更新(48h)

実績:29h(達成率:100%)


・予定外作業

実績:10hで駐留任務確認画面作成(達成率:100%)
実績:4hで対話画面作成(達成率:100%)
実績:5hで拠点選択画面作成(達成率:100%)
実績:12hで移動方針選択画面作成(達成率:100%)



4月は絶不調でした。活動時間3桁届かず(>_<)



◎作業時間分析

作業時間集計2011年4月(PDF形式)


○良かった点
・メニュー画面の予定外の増加に対応した

○悪かった点
・活動時間少なすぎ(前半40%は過去最悪)
・集中力に欠け、1画面の開発に26hを要した
・未着手項目が多い
・HP未更新


活動時間少なく、時間効率も悪い。
サイアクですね(ーー;



◎不調の原因

気力(やる気)と集中力の低下が不調の原因です。
その要因を列挙します。

・震災関連情報収集
 →被災者の状況や政府の対策、現場の実態など、
  気になって他の事に集中できません(ーー;

・原発事故関連情報収集/分析
 →事故の長期化は自身の健康管理にも影響
 →政府や東電の発表信用できず自発的に情報収集分析

・道路工事(ガス工事)
 →轟音と震動。地震かと思った(笑)
 →同じ場所を2回掘り返した理由は不明

・春の陽気
 →実は一番の大敵?

・実家のデジタル化支援
 →工事や設定より年配者に操作覚えさせる方が大変w

・花粉症?ドライアイ?
 →酷い時は1日中目が痛くて開けられない
 →目薬で改善することが多いが、
  改善せず何もできない日もある


一番厳しいのは最後のパターンですが、月に数日程度なので、月間単位で考えると致命的ではありません。

しかし、上記が合わせ技で来てしまったので、気力や集中力が維持できませんでした。



◎対策案検討

震災後は、TVやツイッターの時間が大幅に増えました。
つまり、TVやツイッターの情報収集を止めて、震災/被災者/政治/原発事故等を全て忘れてしまえば、以前のペースを取り戻せるということです。

でも、それで良いのでしょうか?
政治や原発に対する無関心が原発事故を引き起こしてしまったのに、全てを忘れて開発に専念するというのは、国民の義務放棄と言うか、人として間違ってる気がします。


他に時間を費やしたことと言えば、ゲームやアニメです。これを減らして開発時間を確保するのが妥当な気もします。

しかし、震災/原発事故/節電/自粛ムードと精神的負荷が高まり、心は癒しを求めています。そもそも、ゲーム開発者が真っ先にゲーム時間を減らすのは自己否定に繋がるような…?(汗)


結局「どれも大切だ!」という結論になるのかなぁ?
しかし1日は24時間だけですし、家事や睡眠時間を削るわけにもいきません。残りの時間を配分するしかないでしょう。

 開発時間(目標):160h → 140h
 情報収集/ツイッター:先月より月20h減らす
 ゲーム/アニメ:先月より月20h減らす

震災/原発関連が落ち着くまで、上記を目安にします。



◎今後の予定

自分のやる気を引き出すために、今後の予定を楽観的に記述します。

上級ルールが気になる(これがプレイしたいから作ってますw)ので、まずこれを部分的に実装して、どんな感じになるか確認したかったのですが、それだと情報画面の実装に時間がかかってしまいます。その辺は後廻しとして、当面は初級ルールの開発を優先しましょう。

というわけで、「駐留任務と戦闘任務を6月末までに作成する」を当面の中期目標とします。これができれば、ゲームっぽい操作が可能な状態となります。但し

・戦闘アニメの開発は先送り
・武将の思考ロジックは先送り

なので、見た目はアレですが操作の確認はできるでしょう。



◎進捗状況チェック

スケジュールは凍結中です。今月中に見直す予定です。



◎5月の目標

・活動時間月140時間以上
 (中間目標:5/15迄に70h以上)

・駐留任務関連画面調整(8h)

・年間スケジュール見直し(16h)

・移動ルート作成ロジック実装(40h)

・部隊移動処理の実装(24h)

・ブログ更新/HP更新(40h)

・別件企画(12h)

今月中に駐留と移動を実装し、来月中に戦闘(アニメ除く)を実装できれば、来月末にはゲームっぽい操作が可能になります。



◎次回予告

次回は駐留任務関連の画面を調整します。

テーマ : ゲーム製作 関連 - ジャンル : ゲーム

| BLOG TOP |
DATE: CATEGORY:三国志軍記開発
移動方針01
開発中の移動方針選択画面
駐留/戦闘/計略など、部隊移動を伴う任務を指示/提案する際に選択可能。移動方針は戦局を左右する可能性があるものの、あまり細々と指示しすぎると武将の反感を買うことがあるので注意しよう。



◎テーブルイメージ取得ツールの改修

今回は移動方針選択画面を作成します。

まずテーブルイメージ取得ツールを改修し、複数のテーブルを切り替え可能とし、選択項目や選択肢の文字長に応じて横幅を自動調整します。



◎日本語の管理

XNA標準機能は日本語未対応のため、ひにけにXNAの日本語パイプラインを使用しています。これは「単純に元のテキストを空白行を区切りとした複数のメッセージに変換」という仕様のため、ExcelからCSV出力またはコピペした文字列を読み込むと、メッセージ番号と行番号が一致しません。

各行毎に空白行を挿入すれば回避可能ですが、(「項目名」「属性値」「会話メッセージ」など)様々なフォーマットで大量に扱う場合、毎回空白行を挿入するのは非効率です。
そこで、フォーマット毎に個別のCSVを用意し、C#の機能でファイルを読み込んでいます。

一方、スプライトフォントも登録する必要があります。関連制御コードを一元管理するために、登録ファイルを1種類とし、CSVファイルの内容を更新する度に、スプライトフォント登録用ファイルにコピペしてました。さらにテーブルイメージ取得ツールとメインプログラムで同様の操作を行うと、日本語を一部変更するだけで4度手間が発生します。

さすがに面倒なので、一元管理方式を諦めて登録ファイルを個別定義し、制御コードも処理単位に記述することにしました。また、CSVファイルはOSのショートカット機能で参照しました。これで4度手間が1度手間になりました。



◎続・日本語の管理

武将名、拠点名、属性名など従来の日本語も同様の方式に変更しかけたのですが、途中で考え込んでしまいました。

新方式では、データ登録時の手間は減りますが、プログラムはフォントを使い分ける必要があります。フォント保持インスタンスへのアクセスとか、文字幅の計算とか、難しくないけど地味に煩わしいような…?

ついでに言うと、フォントは最後に置き換える可能性がありますが、ファイルが分散していると置き換えが面倒ですね。

結局、データorプログラムどちらで手間をかけるかの問題かもしれません。武将名や拠点名はほぼ確定しデータ更新頻度は低いので、そちらはとりあえず従来方式とします。



◎日本語の管理(余談)

日本語管理の話になったので、ついでに記述します。

パラメータの内容は、英数字の場合enumに記述するだけでOKです。しかし日本語として表示する場合、日本語配列(描画文字列)と完全一致するenumがセットで必要です。
(理由:case等で数値を直接記述するのは好ましくない)

英単語を忘れかけていると、識別子や列挙子を考えるのも一苦労です。後できちんと思い出せるよう毎回コメントを添えると、日本語配列、英数字列挙子、日本語コメントと3重に記述することになります。また、五十音順でソートする場合など、標準機能がそのまま使用できないケースもあります。

要するに、日本語はちょっちメンドイってことですw



◎実装

ツールとメインプログラムを改修し、画像や文字を取得して実装しました。

移動方針01   駐留任務詳細03

中継点はミニマップで指定することを検討中です。移動方針を確定すると、前画面の駐留任務詳細画面に戻り、移動方針が「確定済」と表示されます。

ちなみに、移動方針は他の任務(戦闘、計略等)でも指定することがあるので独立画面としています。



◎次回予告

頭の回転が鈍い時に検討しても、なかなか結論が出ませんねぇ(ー_ー;

5月になったので、次回は「4月の総括と5月の目標」です。

テーマ : ゲーム製作 関連 - ジャンル : ゲーム

| BLOG TOP |

copyright © ゲーム制作の舞台裏 all rights reserved.Powered by FC2ブログ
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。