テーマ
地形コストを情報として持つマップにおいて、スタート地点とゴール地点までを最低コストで結ぶルートを探す。(例えば、SRPG系のゲームでは、平地、家屋、森、山へ移動するときに地形コストが考慮されている)
アルゴリズム
1) 座標と地形コストが対応した配列を用意(cost_map)
2) ゴール地点を始点として、各地点まで移動にかかるコストを求め、配列を作成(rout_cost)
3) 各地点の移動コスト(rout_cost)をもとに、スタート地点からコストの小さい点をたどる
注) 補足(プログラムを書く上で用いるテクニック)
再帰関数を用います。
実践
1) 例えば以下のような地形コストを持つマップにおいてスタート ( x3, y0 ) からゴール ( x1, y6 ) への最短経路を考える。
| y0 | y1 | y2 | y3 | y4 | y5 | y6 | |
|---|---|---|---|---|---|---|---|
| x0 | 4 | 3 | 1 | 1 | 1 | 2 | 3 |
| x1 | 3 | 2 | 1 | 2 | 1 | 1 | 1 |
| x2 | 2 | 1 | 3 | 3 | 2 | 3 | 2 |
| x3 | 2 | 3 | 5 | 3 | 2 | 4 | 3 |
地形コストを要素に持つ配列cost_map、さらに無限値を要素に持つ配列rout_costを用意する。
alg_01.py
s = [3,0]; g = [1,6] ## start and goal position
cost_map = [[4,3,1,1,1,2,3],\
[3,2,1,2,1,1,1],\
[2,1,3,3,2,3,2],\
[2,3,5,3,2,4,3]]
m = len(cost_map)
n = len(cost_map[0])
rout_cost = [[float("inf") for j in range(n)] for i in range(m)]
2) ゴール地点を始点として各地点までの移動コストを計算し、計算結果に基づいて上で用意したrout_costを更新する。
alg_02.py
def calc_rout_cost(x,y,cost_tmp):
cost_tmp += cost_map[x][y]
if cost_tmp < rout_cost[x][y]:
rout_cost[x][y] = cost_tmp
if y < n-1:
calc_rout_cost(x,y+1,cost_tmp)
if y > 0:
calc_rout_cost(x,y-1,cost_tmp)
if x < m-1:
calc_rout_cost(x+1,y,cost_tmp)
if x > 0:
calc_rout_cost(x-1,y,cost_tmp)
calc_rout_cost(g[0],g[1],-cost_map[g[0]][g[1]])
出来上がったrout_costは以下の通り。ゴール地点(x6,y1)はゼロになることに注意。
| x0 | x1 | x2 | x3 | x4 | x5 | x6 | |
|---|---|---|---|---|---|---|---|
| y0 | 12 | 8 | 5 | 4 | 3 | 3 | 3 |
| y1 | 10 | 7 | 5 | 4 | 2 | 1 | 0 |
| y2 | 10 | 8 | 8 | 7 | 4 | 4 | 2 |
| y3 | 12 | 11 | 13 | 9 | 6 | 8 | 5 |
3) 最後に、スタートからゴールまでの最短経路を探す。
alg_03.py
def search_rout(x,y):
tmp = rout_cost[x][y]
tmp_x, tmp_y = x, y
if x > 0 and rout_cost[x-1][y] < tmp :
tmp_x, tmp_y = x-1, y
tmp = rout_cost[tmp_x][tmp_y]
if x < m-1 and rout_cost[x+1][y] < tmp :
tmp_x, tmp_y = x+1, y
tmp = rout_cost[tmp_x][tmp_y]
if y > 0 and rout_cost[x][y-1] < tmp :
tmp_x, tmp_y = x, y-1
tmp = rout_cost[tmp_x][tmp_y]
if y < n-1 and rout_cost[x][y+1] < tmp :
tmp_x, tmp_y = x, y+1
tmp = rout_cost[tmp_x][tmp_y]
if rout_cost[x][y] == 0: return;
rout_list.append([tmp_x,tmp_y])
search_rout(tmp_x,tmp_y)
rout_list = []
rout_list.append(s)
search_rout(s[0],s[1])
最短経路は
result.py
print(rout_list)
## [[3, 0], [2, 0], [2, 1], [1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6]]
となる。
参考文献
柳井政和「プログラマのためのコードパズル」技術評論社 (2014)
詳しい説明は文献をあたってください。Javascriptで記述してあります。