hinekure.net が http://hspdev-wiki.net/ から自動クローリングした結果を表示しています。画像やリソースなどのリンクが切れています。予めご了承ください。
マップ内での移動 - HSP開発wiki
トップ    編集凍結 差分バックアップ添付複製名前変更リロード   新規一覧単語検索最終更新   最終更新のRSS

小ワザ

マップ内での移動

SRPG(シミュレーションRPG)やSLG(シミュレーションゲーム)などで見られるようなマップ内のある地点から他の地点への移動などに関する技術に関する説明です。

このページの文章では以下の用語はここに示す事柄を意味するものとして使われています。

移動力
SRPG・SLGなどで各ユニットに対して設定される値です。
ユニットが一回の移動で移動できる距離を示します。
 
移動コスト
SRPG・SLGなどでマップの各地点に対して設定される値です。
隣接する地点からその地点へユニットが移動するのに必要な移動力を示します。
 
到達コスト
SRPG・SLGなどでユニットがマップ内のある地点から他の地点まで移動するのに必要な移動力の合計値のことです。
ただし移動経路によって必要な移動力の合計値は変化してしまうのでその中の最小のものを到達コストとします。
例えば次に示すマップで四方向移動の場合、
a地点からe地点への到達コストは2、a地点からi地点への到達コストは4になります。

(各マスが各地点を意味し、上段左の文字が地点名、上段右の数値が移動コストです。)

a : 1
???
b : 1
???
c : 1
???
d : 1
???
e : 1
???
f : 1
???
g : 1
???
h : 1
???
i : 1
???

また次に示すマップで四方向移動の場合では、
a地点からi地点への到達コストは6になります。
(abehiという経路で移動する場合に必要な移動力の合計です。それ以外の経路だと移動力の合計値は6より大きくなります。)

(各マスが各地点を意味し、上段左の文字が地点名、上段右の数値が移動コストです。)

a : 1
???
b : 2
???
c : 1
???
d : 3
???
e : 1
???
f : 3
???
g : 1
???
h : 2
???
i : 1
???
 
到達コストマップ
マップ内のある一地点からマップ内の他の全ての地点への到達コストを計算した結果をまとめたデータのことです。
例えばあるマップに対して、四方向移動のときのa地点からの到達コストマップを作成し図示すると次のようになります。
(マップデータと到達コストマップをまとめて示しています。)

(各マスが各地点を意味し、上段左の文字が地点名、上段右の数値が移動コスト、
下段の数値が四方向移動のときの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地点からその地点への到達コストです。)

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などでのユニットの移動に関する処理のいくつかは到達コストマップを使用することで簡単に行うことができます。
そのためにはまず到達コストマップを作成しなければならないので到達コストマップの作成方法について説明します。

アルゴリズム1

実装例1

前述のアルゴリズムの実装例です。
汎用性のためモジュール化してあります。mod_reachcostmap.hsp として保存してください。

+  モジュール mod_reachcostmap.hsp ソースコード

モジュール mod_reachcostmap.hspを使い到達コストマップを作成・表示するサンプルコードです。

+  到達コストマップ作成のサンプルコード

移動可能範囲の判定

SRPG・SLGなどではあるユニットがその時点で移動可能な全ての地点を検索し、移動可能範囲としてまとめる処理が必要な場合があります。
ここでは移動可能範囲の判定を行う方法について説明します。

アルゴリズム1

移動可能範囲は上記の到達コストマップの作成>アルゴリズム1と同じ考え方のアルゴリズムで判定できます。
ただし移動できない範囲まで調べるのは無駄なので到達コストが移動力以下の範囲のみ調べるようにします。

実装例1

上記の到達コストマップの作成>アルゴリズム1>実装例1のモジュール mod_reachcostmap.hsp
移動力を指定しての検索を行える設計なのでそのまま移動可能範囲の判定に使用します。

 

モジュール mod_reachcostmap.hspを使い移動可能範囲の判定を行うサンプルコードです。

+  移動可能範囲の判定のサンプルコード

最小コスト経路の探索

SRPG・SLGなどではユニットがある地点から他の地点に移動する際には多くの場合複数の経路が存在し、
実際に移動を行う際にはそのような複数の経路の中から移動に要する移動力の合計値が最も小さくなる経路を選ぶ場合が良くあります。
ここではそのような経路(最小コスト経路)を見つけるための方法について説明します。

アルゴリズム1

マップ内のある地点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
実装例1

前述のアルゴリズムの実装例です。
移動の開始地点からの到達コストマップを使い目標地点までの最小コスト経路の探索を行います。
汎用性のためモジュール化してあります。mod_mincostroute.hsp として保存してください。

+  モジュール mod_mincostroute.hsp ソースコード

モジュール mod_reachcostmap.hspで到達コストマップを作成し、
モジュール mod_mincostroute.hspで最小コスト経路の探索を行うサンプルコードです。

+  最小コスト経路の探索のサンプルコード

関連ページ

コメント

  • 地形別移動コストは計算されていますか? -- 2008-01-28 (月) 08:24:28
    • どういったもののことを言っていますか?
      到達コスト関連の説明は用語の説明にすぎないので地形ごとに異なる移動コストの概念を省略していますし、
      モジュールおよびサンプルコードは説明のためのものなので [マップデータの地形ID = その地形の移動コスト] のマップを想定したものになっていますが地形ごとの移動コストを考慮した処理になっているはずです(たぶん)。 -- naznyark 2008-01-29 (火) 02:21:11

URL B I U SIZE Black Maroon Green Olive Navy Purple Teal Gray Silver Red Lime Yellow Blue Fuchsia Aqua White

更新メモ(ソースコード関連)

  • 到達コストマップモジュールの更新・名前変更、最小コスト経路探索をモジュール化、それに伴い各サンプルコードも修正。 -- 2008-01-31 (木) 01:58:40

トップ    編集凍結 差分バックアップ添付複製名前変更リロード   新規一覧単語検索最終更新   最終更新のRSS
Last-modified: 2008-01-31 (木) 01:58:40 (2138d)