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.

좋은 웹페이지 즐겨찾기