概要
とあるゲームを作っていて経路探索が必要そうなので、A*アルゴリズムを使ってみた話です。
アルゴリズム的には、関係ないけど tmlib.js で作ってるので tmlib.js と合わせて使用。他でも使えると思う。
A*アルゴリズム自体は、実装しようと思えばできるけど…
wiki参照
http://ja.wikipedia.org/wiki/A*
やっぱり大変だし、すでに(JavaScriptで)実装してる人がいないかな～？
と、検索したらありました。
ってことで、今回はこちらを使わせてもらいました。
javascript-astar 0.4.0
http://github.com/bgrins/javascript-astar
ライセンスは、MIT
作成中のゲームでは、2Dマップ上で、キャラクターの向きの概念があるので、右に１歩進む場合のコストは、１では無く、右を向いてから（コスト１）一歩前に進む（コスト１）で合計のコストが２になる感じ。
これがシミュレーション等でよく見る様に、マップがヘクス（六角形の升目）になるので、向きは６方向。
単純な2Dのままでは経路探索ができないので、対処が必要です。
AStar.js の実装は、単純な2D用ですが、中を見るとアルゴリズムがなかなかきれいに作られてる印象。少し実装すれば、今回、やりたい経路探索にも利用できそうです。
やりたい事まとめ
- マップは単純な2Dじゃなくて、ヘクス状に並べられた６方向に移動が可能なマップ。
- 向きの概念があり、１つ方向を変えるのにもコストがかかる（後ろを向くには、コスト３）
- 特定の場所で、ある方向を向いている状態から、特定の場所への最短経路を求める。
- 移動できないマスがあったりコストが普通よりかかるマスがあるのはいつも通り…
AStar.js の実装
A*アルゴリズムは、大ざっぱに言うと…
- ある２つの位置（ノード）を移動するのにかかる最小コストを仮に求める関数
- 各ノードに隣接するノード
- 隣接したノード間のコスト
以上がわかれば、アルゴリズムが動きます。
現実の地図で言うと交差点が１ノードで、そこに繋がる次の交差点（隣接ノード）とそこまでの距離（コスト）、今の位置から、目的地までの直線距離（仮のコスト）がわかれば、最短経路がわかると…目的地まで各ノードからのコストを計算しつつ経路を探索する、そんな感じです。
AStar.js もそのように実装されていて、具体的には以下を使う様です。
- astarオブジェクト
- Graphクラス
- GridNodeクラス(内部クラス)
graph = new Graph [
[1,1,1,1]
[0,1,1,0]
[0,0,1,1]
]
start = graph.grid[0][0]
end = graph.grid[1][2]
options = {}
result = astar.search(graph, start, end, options)
Graphクラスは、GridNodeクラスのインスタンスを、XYの2Dのノードマップとして管理していて、astar.search() の graph に、Graphクラスのインスタンスを指定する。
startとendは、graph で管理されてるノードの開始位置と終了位置のノード(GridNode)を指定する。
options.heuristic に funtion(node1, node2) と、GridNodeを２つもらって仮のコストを計算する関数を指定する。
（指定しない場合は、デフォルトの内部で持っているheuristic関数を利用）
結果(result)は、最短経路を示した GridNode の配列で返されます。
と、言うことで、今回は、astarは、そのままに、GraphとGridNodeを、再作成することで対応できそうです。
主に必要になるメソッドが以下のような感じ。
Graph.neighbors(node) # node に隣接するノードを Array で返す
Graph.markDirty(node) # 経路探索に使用した node を保存
Graph.cleanDirty() # 経路探索に使用した node をクリア（初期化）astar.cleanNode(node) を呼ぶ
GridNode.getCost(node) # 自ノード(this)に、指定されたノード(node)から移動する（入る）場合のコスト
GridNode.isWall() # 自ノード(this)が移動できないノードの場合 true
heuristic(node1,node2) # ２つのノード間の仮コスト
Graphクラス
Graphは、今回の場合、ヘクス状に並べられたマスにするのでそれを管理できるようにする。
と言っても、そんなに難しく考えず…X座標が偶数の場合に、Y座標を１つ少なく持つようにするだけ。
画面には、X座標が偶数の場合は、半分ずらして表示する。
問題の neighbors も単純に隣接する６ノードを探して返すのみ
class nz.Graph
constructor: (param = {}) ->
{
mapdata
chipdata
} = param
@nodes = []
@grid = []
@grid[x] = [] for x in [0...mapdata.width]
for y in [0...mapdata.height]
for x in [0...mapdata.width]
unless y == mapdata.height - 1 and x % 2 == 0
chipid = mapdata.data[y][x]
node = new nz.GridNode(x,y,chipdata[chipid])
@grid[x][y] = node
@nodes.push(node)
@clear()
neighbors: (node) ->
ret = []
x = node.x
y = node.y
if x % 2 == 0
ret.push(@grid[x ][y-1]) if(@grid[x ]?[y-1]?)
ret.push(@grid[x ][y+1]) if(@grid[x ]?[y+1]?)
ret.push(@grid[x-1][y ]) if(@grid[x-1]?[y ]?)
ret.push(@grid[x-1][y+1]) if(@grid[x-1]?[y+1]?)
ret.push(@grid[x+1][y ]) if(@grid[x+1]?[y ]?)
ret.push(@grid[x+1][y+1]) if(@grid[x+1]?[y+1]?)
else
ret.push(@grid[x ][y-1]) if(@grid[x ]?[y-1]?)
ret.push(@grid[x ][y+1]) if(@grid[x ]?[y+1]?)
ret.push(@grid[x-1][y ]) if(@grid[x-1]?[y ]?)
ret.push(@grid[x-1][y-1]) if(@grid[x-1]?[y-1]?)
ret.push(@grid[x+1][y ]) if(@grid[x+1]?[y ]?)
ret.push(@grid[x+1][y-1]) if(@grid[x+1]?[y-1]?)
# nz なノードを返す（６こ）
return ret
markDirtyとcleanDirtyは、ま～普通に、ほぼ元の実装のまま（継承してもいいくらい）
cleanDirty: ->
for node in @dirtyNodes
node.clean()
astar.cleanNode(node)
@dirtyNodes = []
markDirty: (node) ->
if @dirtyNodes.indexOf(node) < 0
@dirtyNodes.push node
A*は、各ノードにそのノードまでのコストを保存しながら経路探索するので、再利用時に汚しちゃったノードをクリアしておきたい感じですかね。
で、全ノードクリアだと量が多くて大変なので、本当に触ったノードだけクリアするようにマークしてると…
あと、heuristic 関数を元の実装では、Graphに作成していたので
今回の経路探索用の heuristic 関数を、Graphに作成。
nz.Graph.heuristic = (node1,node2) ->
hx = Math.abs(node1.x - node2.x)
hy = Math.abs(node1.y - node2.y)
hr = Math.ceil(hx / 2)
direction = node1.calcDirectionTo(node2)
hd = node1.getDirectionCost(direction)
if hy == hr
hy = 0
else if hy < hr
if hy != 0
hy = 1
if hd == 1
hd = 0
else
hy -= hr
hx + hy + hd
実は、これが難しい…とりあえず適当にそれぽくなるようにしているけれど
この辺は、後でリファクタリングと言うか、ちゃんと計算したい。
大抵の場合は、直線距離がそのまま仮コストになるんだけど、今回の場合は、向きの概念があるので、一歩前と一歩後ろでは、直線距離が一緒でもコストは全然違うってことに…
これをちゃんと意識しないとうまくアルゴリズムが動かないので、目的のノードがどの方向にあるのか確かめて、その方向を向くのにかかるコストを計算、さらにヘクス状に並べられた2Dマップのマンハッタン距離を求めるような感じでコストを出しています。
calcDirectionTo(node2)は、どの方向に指定されたノード(node2)があるか求める関数
getDirectionCost(direction)は、指定された方向に向きを変える場合のコストを求める関数
と、AStar.js には、元々ないけど、今回必要になる処理とかは、随時追加…
GridNodeクラス
GridNodeは、マップ上の１つのマス（ノード）を表すクラスで、位置情報とノードの状態を保持する。
経路探索中にどの方向への移動が一番近いか保存するために、向きの情報（direction）を用意して、それも考慮しつつ、コストを計算する感じ。
class nz.GridNode
:
getCost: (node) ->
cost = @weight
# 移動元からの方向
direction = node.calcDirection(@)
# 方向転換のコスト
cost += node.getDirectionCost(direction)
# ここまでのコストが今までのコストより低い場合方向を更新
if not @visited or node.g + cost < @g
@direction = direction
return cost
isWall: ->
return @weight == 0
isWallは、そのまま…
本当はさらに、キャラクター毎に水は侵入しやすいとか特性をつけたかったりするけど今はパス。
（付ける場合は、ここで何とかする）
あと、前進がコスト１なら、後退（バック）した場合は、コスト２とか言うのも入れたい…な
と、思ってます。getCost も直さなきゃだけど、もしかしたら、heuristicも直さなきゃかもしれない。（のーあいでぃあ）
動作サンプル
元の astar.search をそのまま使うと GridNode をそのまま使うことになるので、以下の様な関数を作成。
# 開始時に向いている方向(sd)、開始位置(sx,sy),目標位置(ex,ey)
searchRoute: (sd,sx,sy,ex,ey,op={closest:false}) ->
route = []
start = @grid[sx][sy]
end = @grid[ex][ey]
# 壁じゃなかったら探索
if (not end.isWall()) or op.closest
# search の中で、dirty node をクリアされるので
# 事前に開始位置だけ、dirty node から除外しておく
start.clean()
astar.cleanNode(start)
start.direction = sd # ノード検索時に向きが重要なので、開始位置の向きをクリアされると困る。
i = @dirtyNodes.indexOf start
@dirtyNodes.splice(i, 1) if i >= 0
op.heuristic = nz.Graph.heuristic unless op.heuristic?
result = astar.search(@, start, end, op)
for node in result
route.push {
mapx: node.x
mapy: node.y
direction: node.direction
cost: node.g
}
return route
と、言うことで上記の実装で、astar を使い経路探索ができるようになりました。
マップをクリックすると、その場所までの経路を探索してキャラクターを動かしてます。
（へふ～。疲れた…）