hinekure.net が http://hspdev-wiki.net/ から自動クローリングした結果を表示しています。画像やリソースなどのリンクが切れています。予めご了承ください。 |
SRPG(シミュレーションRPG)やSLG(シミュレーションゲーム)などで見られるようなマップ内のある地点から他の地点への移動などに関する技術に関する説明です。
このページの文章では以下の用語はここに示す事柄を意味するものとして使われています。
(各マスが各地点を意味し、上段左の文字が地点名、上段右の数値が移動コストです。)
a : 1 ??? | b : 1 ??? | c : 1 ??? |
d : 1 ??? | e : 1 ??? | f : 1 ??? |
g : 1 ??? | h : 1 ??? | i : 1 ??? |
(各マスが各地点を意味し、上段左の文字が地点名、上段右の数値が移動コストです。)
a : 1 ??? | b : 2 ??? | c : 1 ??? |
d : 3 ??? | e : 1 ??? | f : 3 ??? |
g : 1 ??? | h : 2 ??? | i : 1 ??? |
(各マスが各地点を意味し、上段左の文字が地点名、上段右の数値が移動コスト、
下段の数値が四方向移動のときのa地点からその地点への到達コストです。)
a : 1 0 | b : 1 1 | c : 1 2 |
d : 1 1 | e : 1 2 | f : 1 3 |
g : 1 2 | h : 1 3 | i : 1 4 |
(各マスが各地点を意味し、上段左の文字が地点名、上段右の数値が移動コスト、
下段の数値が四方向移動のときのa地点からその地点への到達コストです。)
a : 1 0 | b : 2 2 | c : 1 3 |
d : 3 3 | e : 1 3 | f : 3 6 |
g : 1 4 | h : 2 5 | i : 1 6 |
SRPG・SLGなどでのユニットの移動に関する処理のいくつかは到達コストマップを使用することで簡単に行うことができます。
そのためにはまず到達コストマップを作成しなければならないので到達コストマップの作成方法について説明します。
前述のアルゴリズムの実装例です。
汎用性のためモジュール化してあります。mod_reachcostmap.hsp として保存してください。
+ | モジュール mod_reachcostmap.hsp ソースコード |
|
モジュール mod_reachcostmap.hspを使い到達コストマップを作成・表示するサンプルコードです。
+ | 到達コストマップ作成のサンプルコード |
|
SRPG・SLGなどではあるユニットがその時点で移動可能な全ての地点を検索し、移動可能範囲としてまとめる処理が必要な場合があります。
ここでは移動可能範囲の判定を行う方法について説明します。
移動可能範囲は上記の到達コストマップの作成>アルゴリズム1と同じ考え方のアルゴリズムで判定できます。
ただし移動できない範囲まで調べるのは無駄なので到達コストが移動力以下の範囲のみ調べるようにします。
上記の到達コストマップの作成>アルゴリズム1>実装例1のモジュール mod_reachcostmap.hspは
移動力を指定しての検索を行える設計なのでそのまま移動可能範囲の判定に使用します。
モジュール mod_reachcostmap.hspを使い移動可能範囲の判定を行うサンプルコードです。
+ | 移動可能範囲の判定のサンプルコード |
|
SRPG・SLGなどではユニットがある地点から他の地点に移動する際には多くの場合複数の経路が存在し、
実際に移動を行う際にはそのような複数の経路の中から移動に要する移動力の合計値が最も小さくなる経路を選ぶ場合が良くあります。
ここではそのような経路(最小コスト経路)を見つけるための方法について説明します。
マップ内のある地点Aから他の地点Zへの経路について考えます。
経路の始点や途中、必要な移動力の合計値を考えずに地点Zへの経路の最終段階にのみ注目すると
『地点Zに隣接する地点のうちのどこか一つの地点』→地点Z
という移動経路になり、その場合の地点Aから地点Zまでの移動に要する移動力の合計値は
地点Aから『地点Zに隣接する地点のうちのどこか一つの地点』まで移動するのに要した移動力の合計 + 地点Zの移動コスト
となります。そしてこの値を最小にする経路とはすなわち
地点A→(途中経路、現時点では詳細不明)→『地点Zに隣接する地点のうちで地点Aからその地点までの到達コストが最も小さい地点』→地点Z
というものになります。
つまり地点Aから地点Zに隣接する全ての地点への到達コストをそれぞれ求め『地点Zに隣接する地点のうちで地点Aからその地点までの到達コストが最も小さい地点』を特定すれば、地点Zはわかっているので具体的な最小コスト経路の最終段階が判明します。
このようにすれば最小コスト経路の最終段階は判明するので次にその一つ前の段階を考えます。
『地点Zに隣接する地点のうちで地点Aからその地点までの到達コストが最も小さい地点』を地点Yとし、
最終段階の時と同様の考え方で『地点Yに隣接する地点のうちで地点Aからその地点までの到達コストが最も小さい地点』を特定すれば最小コスト経路の最終段階の一つ前の段階が判明します。
以降は地点Aに到達するまで同様の処理を繰り返し各段階で判明した経路をつなぎあわせたものが最小コスト経路となります。
このように最小コスト経路を見つけるには経路の終点から始点まで、その周囲で最も始点からの到達コストが小さい地点を探しながら遡っていきます。
前述のアルゴリズムは経路始点からの到達コストマップがあれば簡単に最小コスト経路を見つけることができます。
ここでは例として前述のアルゴリズムに基づき具体的なマップと到達コストマップを使って最小コスト経路を探します。
次のマップと到達コストマップから四方向移動のときのa地点からi地点への最小コスト経路を探します。
(各マスが各地点を意味し、上段左の文字が地点名、上段右の数値が移動コスト、
下段の数値が四方向移動のときのa地点からその地点への到達コストです。)
a : 1 0 | b : 2 2 | c : 3 5 |
d : 3 3 | e : 1 3 | f : 2 5 |
g : 2 5 | h : 3 6 | i : 1 6 |
まずi地点に隣接する地点で到達コストの最も小さい地点を探します。
i地点に隣接する地点はf、hの2地点、そのうち到達コストが最も小さいのはf地点なのでfiという経路が判明します。
次にf地点に隣接する地点で到達コストの最も小さい地点を探します。
f地点に隣接する地点はc、e、iの3地点、そのうち到達コストが最も小さいのはe地点なのでさきほどのものとあわせてefiという経路が判明します。
さらにe地点に隣接する地点で到達コストの最も小さい地点を探します。
e地点に隣接する地点はbdfhの4地点、そのうち到達コストが最も小さいのはb地点なのでさきほどのものとあわせてbefiという経路が判明、
さらにb地点はa地点に隣接しているのでabefiという経路が判明しこれがa地点からi地点への最初コスト経路になります。
a : 1 0 | b : 2 2 | c : 3 5 |
d : 3 3 | e : 1 3 | f : 2 5 |
g : 2 5 | h : 3 6 | i : 1 6 |
前述のアルゴリズムの実装例です。
移動の開始地点からの到達コストマップを使い目標地点までの最小コスト経路の探索を行います。
汎用性のためモジュール化してあります。mod_mincostroute.hsp として保存してください。
+ | モジュール mod_mincostroute.hsp ソースコード |
|
モジュール mod_reachcostmap.hspで到達コストマップを作成し、
モジュール mod_mincostroute.hspで最小コスト経路の探索を行うサンプルコードです。
+ | 最小コスト経路の探索のサンプルコード |
|