プロフィール

Na-7

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


アクセスカウンター


最新記事


最新コメント


最新トラックバック


月別アーカイブ


カテゴリ


DATE: CATEGORY:スポンサー広告
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
DATE: CATEGORY:三国志軍記開発
エースター法による移動経路実装07
開発中のメイン画面
経路探索中のフリーズ現象が解消され、プレイヤーが気持ちよくプレイできるようになった。但し、経路探索は従来より時間がかかるようになった。



◎フリーズ回避方針検討

今回は、遠距離経路探索時のフリーズ現象を回避する方法を検討します。

A案
 探索処理効率を上げて処理時間を短くする

B案
 遠距離探索を行わないよう探索条件に制限を設ける

C案
 探索処理を定期的に中断/再開して
 他の処理を並列的に進める

D案
 探索処理をスレッド化して
 他の処理を並列的に進める

まずA案ですが、フリーズ現象は長い場合4~5秒に及ぶことがあります。60fpsを目標とした場合、処理時間を5000ms→5ms=1/1000としなければなりません。さすがにこれは無理っぽいのでA案は却下します。

B案は有効な回避策の1つと思いますが、(Xbox360と異なり)PCは個体差が激しいので、PC性能によって探索時間が異なるという問題があります。例えば、CPUが2.6GHz程度であればマップの1/4ぐらいの距離までOKですが、低性能PCの場合は1/4でもNGです。1/4を切るとゲームデザインに支障を来してしまいますが、「CPU2.6GHz以上」という動作環境条件は厳しすぎるので、B案はなるべく避けたいですね。

C案は、経路探索中の部隊のみ停止します。他の処理は並列的に動くので、フリーズ現象は回避されるハズ(^^;
B案に比べて、動作環境や探索距離の制限が不要というメリットがありますが、プレイヤーが味方部隊に遠距離を指示した場合はしばらく待たされます。

D案は、実装に「スレッド化」という技法を用いる点はC案と異なりますが、方向性/メリット/デメリット等はC案と同じです。


こうして考えると、D案が一番スマートに出来そうな気がしますが、私はスレッド化未経験なので、1から勉強した上で大幅改修を覚悟する必要がありそうです。今の所他にスレッド化したい処理は無いので、今回はC案にします。



◎探索処理の中断/再開

C案を具体的に記述します。

・所要時間カウンタ/中断箇所マーカーを設ける

・探索処理中に所要時間カウンタをチェックし、
 一定時間が経過したら処理を一時中断する
 (中断箇所をマーカーに記録する)

・中断すると、他の処理が通常通り行われる

・次フレームUpdateの際に、中断箇所マーカー位置から
 探索処理を再開する

今回の改修にあたり、地形種別情報クラスと最短経路探索クラスを分離しました。移動コストは地形種別に依存するので1つのクラスだったのですが、デカくなりすぎたので分離したら、プログラムが把握しやすくなりました。



◎デバッグ

改修後に動かすと、フリーズ現象が解消されないばかりか、エラーが出るようになりました。
あちこち手を入れ過ぎたかなぁ?

とりあえず一時中断箇所をコメント化すると、従来通り正常動作しました。中断/再開処理の何かがおかしいようです。

その後の調査で、エラーの原因は「経路が2地点を永久ループしオーバーフローに至る」という所まで判明したのですが、何故そうなるかは不明です。

試しに部隊数を1部隊に限定すると、フリーズ現象は解消されないものの、エラーは発生しなくなりました。
わけがわかりません(--;

…いや、ちょっと待てよ?
よく見ると、コマ送りで動いてるっぽいので、もしかしたら一回のタイムリミットが長すぎるのかも?

タイムリミットを 16ms→1ms としたら、フリーズ現象が解消されました!でも、フレームレートは8fpsで思いっきりカクカクします(処理落ち現象)。タイムリミットを1msとしたのに、Update()が16msとなる理由は不明。



◎システム時刻の取得

Update内でシステム時刻を取得するコードはこんな感じです。

DateTime timeLimit = DateTime.Now.AddMilliseconds(1);
while (true)
{
  if (DateTime.Now > timeLimit)
  ~


ところが、ループ内でDateTime.Nowを出力して確認すると、値が変わりません。どうやら、System.DateTimeの値は1フレーム内で更新されない模様。

フリーズ現象が解消されなかった原因はコレか(--;



◎Stopwatchを利用する

1回のUpdate内で正確な経過時間を取得する方法が無いかとネットを調べたのですが、希望に沿ったものはなかなか見つかりません。しかしふと「タイムルーラーが1フレーム内の経過時間を正確に測定している」ことに気が付いて、ソースを解析すると、Stopwatchクラスを利用してました。

あれ?以前も調べたような…デジャブ?w
とにかく実装しましょう。

// ストップウォッチの宣言
Stopwatch stopwatch = new Stopwatch();
// ストップウォッチのリセット
stopwatch.Reset();
// ストップウォッチ開始
stopwatch.Start();

while (true)
{

  // ストップウォッチのチェック
  if (stopwatch.ElapsedMilliseconds > 3)
  ~


エースター法による移動経路実装06

実行すると、60fps(Updateは4.2ms)を綺麗にキープ!!

経路探索中は部隊の位置が停止(アニメや操作は有効)し、経路決定後に移動が始まります。

やりました!フリーズ現象解消です!^^



◎エラーの原因と対策案検討

しかし、部隊を増やすと経路探索処理でエラー発生。

原因は、経路探索インスタンスが1つしかないので、複数部隊が共有すると経路がゴッチャになるからでした(>_<)

というわけで、対応策を検討します。

A案(並列処理方式):
・探索要求毎にインスタンスを作成する
・メモリ効率が非常に悪い
・探索時間は経路の長さに比例する

B案(待ち行列方式):
・探索中に他の探索要求が来ると待ち行列に記録する
・探索要求は受付順に処理される
・探索距離が近くても、長時間待たされることがある

C案(単一処理方式):
・探索中に他の探索要求が来ても無視する
・探索が終わると、次の探索要求を受け付ける
・他の探索処理が全て終わるまで待たされることがある

A案が最も公平で理想的な印象を受けますが、問題はメモリ効率の悪さです。100部隊の探索要求が同時に発生した場合、単純計算でメモリ100倍喰うので、これは避けた方が無難ですね。

次に公平と思われるのはB案ですが、よく考えるとこのゲームではあまり意味が無さそうです。

・ゲーム開始時のみ探索要求が大量発生する
・ゲーム開始後は探索要求が重なることは少ない

ゲーム開始時の順番を制御しても意味がありません。
(全部隊の探索完了後にゲーム開始が理想)
というわけで、C案とします。



◎実装

C案を実装し、80部隊で試してみました。

エースター法による移動経路実装07

最初は全部隊停止状態ですが、60fpsで(フリーズ現象なく)アニメは動き続け、経路探索が終わった部隊から移動開始します。

気になるのは、5分経っても移動しない部隊が半分以上いることです。以前はフリーズ状態(経路探索に16ms使用した状態)で3~4分かかりましたが、今は経路探索に3msしか使用していないので、20分ぐらいかかるかもしれません。



◎次回予告

フリーズ現象は回避できましたが、ゲーム開始時の80部隊経路探索が20分もかかるのは問題です。とりあえず他の課題を片付けてから時間短縮を図りましょう。

前回ラストに記述した懸案A~Bを解消したので、次回は懸案C~Dに取り組みます。

スポンサーサイト

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

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック


この記事にトラックバックする(FC2ブログユーザー)



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