erlang - Astar 알고리즘
4520 단어 알고리즘
%%%-------------------------------------------------------------------
%%% Module : astar_trace
%%% Author :
%%% Description : A
%%%-------------------------------------------------------------------
-module(astar_trace).
-export([generate_route/8,generate_route/7,generate_route/5])。
-define(EXPAND_POINTS(X,Y),[{X-1,Y},{X-1,Y-1},{X ,Y-1},{X+1,Y-1},{X+1,Y},{X+1,Y+1},{X,Y+1},{X-1,Y+1}]). %%
-record(point, {x = 0, y = 0, g = 0, h = 0, f = 0, p_x = 0, p_y = 0}).
generate_route(StartX,StartY,TargetX,TargetY,SceneId) ->
generate_route(StartX,StartY,TargetX,TargetY,SceneId,50,50).
generate_route(StartX,StartY,TargetX,TargetY,SceneId,MaxTraceRangeX,MaxTraceRangeY) ->
generate_route(StartX,StartY,TargetX,TargetY,SceneId,MaxTraceRangeX,MaxTraceRangeY,0).
generate_route(StartX,StartY,TargetX,TargetY,SceneId,MaxTraceRangeX,MaxTraceRangeY,Flying) ->
%%
CostH = calculate_cost(StartX,StartY,TargetX,TargetY),
CostG = 0,
OpenPoints = [#point{x=StartX, y=StartY, g=CostG,h=CostH,f = CostG + CostH}],
%%
case search(OpenPoints,[],#point{x = TargetX, y = TargetY},SceneId,MaxTraceRangeX,MaxTraceRangeY,Flying) of
false ->
false;
{Point,ResultOpenPoints,ResultClosePoints} ->
PosList = [{P#point.x, P#point.y}||P
false;
search(OpenPoints,ClosePoints,TargetPoint,SceneId,MaxTraceRangeX,MaxTraceRangeY,Flying)->
[Point | NewOpenPoints] = lists:keysort(#point.f, OpenPoints),
NewClosePoints = [Point | ClosePoints],
case is_target(Point,TargetPoint) of
true->
{Point,NewOpenPoints,NewClosePoints};
false ->
%% ,
AddOpenPoints = expand(NewOpenPoints,NewClosePoints,Point,TargetPoint,SceneId,MaxTraceRangeX,MaxTraceRangeY,Flying), %%
search(AddOpenPoints ++ NewOpenPoints,NewClosePoints,TargetPoint,SceneId,MaxTraceRangeX,MaxTraceRangeY,Flying)
end.
%%
expand(OpenPoints,ClosePoints,#point{x=X, y=Y, g=G},#point{x = TargetX,y = TargetY},SceneId,MaxTraceRangeX,MaxTraceRangeY,Flying) ->
CostG = G + 1,
F = fun({X1,Y1},AccIn) ->
case is_blocked(X1,Y1,TargetX,TargetY,SceneId,MaxTraceRangeX,MaxTraceRangeY,Flying) of
true ->
AccIn;
false ->
case [true || #point{x = OpentX,y = OpentY}
case [true || #point{x = CloseX,y = CloseY}
CostH = calculate_cost(X1,Y1,TargetX,TargetY),
[#point{x = X1,y = Y1,g = CostG,h = CostH,f = CostH + CostG,p_x = X,p_y = Y} | AccIn];
_ ->
%% close
AccIn
end;
_ ->
%% opent
AccIn
end
end
end,
lists:foldl(F,[],?EXPAND_POINTS(X,Y)).
%%
generate_solution(#point{p_x = X,p_y = Y} = Point,SolutionPoints,Points)->
case [Info || #point{x = X2,y = Y2} = Info
SolutionPoints;
[NewPoint | _] ->
generate_solution(NewPoint,[Point | SolutionPoints],lists:delete(NewPoint,Points))
end.
%%
calculate_cost(X1,Y1,X2,Y2) ->
((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2)).
%% ,
is_target(#point{x = StartX,y = StartY}, #point{x = TargetX, y = TargetY}) ->
StartX == TargetX andalso StartY == TargetY.
%% abs(StartX - TargetX) =< 1 andalso abs(StartY - TargetY) =<1.
%% check is block
is_blocked(X,Y,TargetX,TargetY,SceneId,MaxTraceRangeX,MaxTraceRangeY,_Flying)->
case abs(TargetX - X) > MaxTraceRangeX orelse abs(TargetY - Y) > MaxTraceRangeY of
true -> %% ,
true;
false -> %%
not is_block(SceneId, X, Y)
end.
is_block(_SceneId, _X, _Y) ->
false.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.