【Defold】経路探索ライブラリ「A* Path Finding」

2020/05/292020/07/12Defold, DEVELOP

A*(AStar)は、マスのあるシミュレーションゲームなどで対象のいる場所までの最短距離を求める時などによく使うアルゴリズムの一種です。

アセットページ

https://defold.com/assets/apathfinding/

サンプルプロジェクト

https://github.com/selimanac/defold-astar-examples

ライブラリのURL

https://github.com/selimanac/defold-astar/archive/master.zip

依存するライブラリ

なし。

使い方

経路探索の方向は上下左右の4方向または、それに斜めを加えた8方向の2パターンに対応しています。経路探索する世界の広さ、探索方向を設定します。

マップデータのセットアップ

local map_width = 5
local map_height = 5
local direction = astar.DIRECTION_EIGHT
local allocate = map_width * map_height
local typical_adjacent = 8
local cache = true
astar.setup(map_width, map_height, direction, allocate, typical_adjacent, cache)

地図データを設定します。新しいマップデータを設定すると、現在のマップデータはリセットされます。

local world = {
2 ,2 ,0 ,1 ,0,
0 ,0 ,1 ,2 ,1,
0 ,0 ,2 ,0 ,0,
0 ,2 ,2 ,2 ,2,
2 ,1 ,1 ,0 ,1
}
astar.set_map(world)

最後に移動方向へのコストを設定します。

local costs = {
    [2] = {
        1.0, -- 右
        1.0, -- 上
        1.0, -- 左
        1.0, -- 下
        1.41, -- 右上
        1.41, -- 左上
        1.41, -- 右下
        1.41 -- 左下
    }
}
astar.set_costs(costs)

探索

astar.solve に開始地点、目標地点をセットし実行すると結果が返ります。

local start_x = 1
local start_y = 1
local end_x = 3
local end_y = 3
 
local result, size, total_cost, path = astar.solve(start_x, start_y, end_x, end_y)
 
if result == astar.SOLVED then
	print("SOLVED")
	for i, v in ipairs(path) do
		print("Tile: ", v.x .. "-" .. v.y)
	end
elseif result == astar.NO_SOLUTION then
	print("NO_SOLUTION")
elseif result == astar.START_END_SAME then
	print("START_END_SAME")
end