알고리즘은 격자의 모든 셀에 대한 최단 경로를 찾습니다.

Question

격자가 [40 x 15]이고 그 위에 2 ~ 16 개의 단위가 있으며 알 수없는 장애물이 있습니다.
내 유닛 위치에서 모든 유닛에 대한 최단 경로 찾는 법.

나는 우리가 (1)

• getMyLocation (O로 고려할 수있는 두 개의 헬퍼 메소드)가 - (x, y)를 반환 그리드
• investigateCell (X, Y에 내 위치 좌표를) - (x, y) 좌표에서 셀에 대한 정보를 반환합니다.

A* search 알고리즘을 구현했으며 모든 방향으로 동시에 검색합니다. 마지막에는 각 셀이 내 위치로부터의 거리를 나타내는 숫자와 그리드의 모든 유닛을 모아 놓은 그리드를 출력합니다. 그것은 O (N)과 함께 수행합니다. 여기서 N은 제 경우의 세포 수 - 600입니다.

AS3을 사용하여이 기능을 구현했지만 불행히도 컴퓨터를 30-50 밀리 초로 계산합니다.

다음은 내 소스 코드입니다. 나에게 더 나은 방법을 제안 해 줄 수 있니?

package com.gazman.strategy_of_battle_package.map 
{ 
    import flash.geom.Point; 

    /** 
    * Implementing a path finding algorithm(Similar to A* search only there is no known target) to calculate the shortest path to each cell on the map. 
    * Once calculation is complete the information will be available at cellsMap. Each cell is a number representing the 
    * number of steps required to get to that location. Enemies and Allies will be represented with negative distance. Also the enemy and Allys 
    * coordinations collections are provided. Blocked cells will have the value 0.<br><br> 
    * Worth case and best case efficiency is O(N) where N is the number of cells. 
    */ 
    public class MapFilter 
    { 
     private static const PULL:Vector.<MapFilter> = new Vector.<MapFilter>(); 
     public var cellsMap:Vector.<Vector.<int>>; 
     public var allys:Vector.<Point>; 
     public var enemies:Vector.<Point>; 
     private var stack:Vector.<MapFilter>; 
     private var map:Map; 
     private var x:int; 
     private var y:int; 
     private var count:int; 
     private var commander:String; 
     private var hash:Object; 
     private var filtered:Boolean; 

     public function filter(map:Map, myLocation:Point, commander:String):void{ 
      filtered = true; 
      this.commander = commander; 
      this.map = map; 
      this.x = myLocation.x; 
      this.y = myLocation.y; 
      init(); 
      cellsMap[x][y] = 1; 
      excecute(); 
      while(stack.length > 0){ 
       var length:int = stack.length; 
       for(var i:int = 0; i < length; i++){ 
        var mapFilter:MapFilter = stack.shift(); 
        mapFilter.excecute(); 
        PULL.push(mapFilter); 
       } 
      } 
     } 

     public function navigateTo(location:Point):Point{ 
      if(!filtered){ 
       throw new Error("Must filter before navigating"); 
      } 
      var position:int = Math.abs(cellsMap[location.x][location.y]); 
      if(position == 0){ 
       throw new Error("Target unreachable"); 
      } 
      while(position > 2){ 
       if(canNavigateTo(position, location.x + 1, location.y)){ 
        location.x++; 
       } 
       else if(canNavigateTo(position, location.x - 1, location.y)){ 
        location.x--; 
       } 
       else if(canNavigateTo(position, location.x, location.y + 1)){ 
        location.y++; 
       } 
       else if(canNavigateTo(position, location.x, location.y - 1)){ 
        location.y--; 
       } 
       position = cellsMap[location.x][location.y]; 
      } 

      return location; 
      throw new Error("Unexpected filtering error"); 
     } 

     private function canNavigateTo(position:int, targetX:int, targetY:int):Boolean 
     { 
      return isInMapRange(targetX, targetY) && cellsMap[targetX][targetY] < position && cellsMap[targetX][targetY] > 0; 
     } 

     private function excecute():void 
     { 
      papulate(x + 1, y); 
      papulate(x - 1, y); 
      papulate(x, y + 1); 
      papulate(x, y - 1); 
     } 

     private function isInMapRange(x:int, y:int):Boolean{ 
      return x < cellsMap.length && 
       x >= 0 && 
       y < cellsMap[0].length && 
       y >= 0; 
     } 

     private function papulate(x:int, y:int):void 
     { 
      if(!isInMapRange(x,y) || 
       cellsMap[x][y] != 0 || 
       hash[x + "," + y] != null || 
       map.isBlocked(x,y)){ 
       return; 
      } 

      // we already checked that is not block 
      // checking if there units 
      if(map.isEmpty(x,y)){ 
       cellsMap[x][y] = count; 
       addTask(x,y); 
      } 
      else{ 
       cellsMap[x][y] = -count; 
       if(map.isAlly(x,y, commander)){ 
        hash[x + "," + y] = true; 
        allys.push(new Point(x,y)); 
       } 
       else { 
        hash[x + "," + y] = true; 
        enemies.push(new Point(x,y)); 
       } 
      } 
     } 

     private function addTask(x:int, y:int):void 
     { 
      var mapFilter:MapFilter = PULL.pop(); 
      if(mapFilter == null){ 
       mapFilter = new MapFilter(); 
      } 

      mapFilter.commander = commander; 
      mapFilter.hash = hash; 
      mapFilter.map = map; 
      mapFilter.cellsMap = cellsMap; 
      mapFilter.allys = allys; 
      mapFilter..enemies = enemies; 
      mapFilter.stack = stack; 
      mapFilter.count = count + 1; 
      mapFilter.x = x; 
      mapFilter.y = y; 
      stack.push(mapFilter); 
     } 

     private function init():void 
     { 
      hash = new Object(); 
      cellsMap = new Vector.<Vector.<int>>(); 
      for(var i:int = 0; i < map.width;i++){ 
       cellsMap.push(new Vector.<int>); 
       for(var j:int = 0; j < map.height;j++){ 
        cellsMap[i].push(0); 
       } 
      } 
      allys = new Vector.<Point>(); 
      enemies = new Vector.<Point>(); 
      stack = new Vector.<MapFilter>(); 
      count = 2; 
     } 
    } 
} 

Answer 1

당신은 포인트의 모든 쌍의 최단 경로를 찾을 수 Floyd Warshall를 사용할 수 있습니다. 이것은 O(|V|^3)이 될 것이고, 각 유닛마다 한번씩 돌릴 필요는 없습니다. 그것은 단순한 알고리즘으로, 각 장치에 대해 BFS/Bellman Ford과 같은 것을 실행하는 것보다 실제로 더 빠를 것이라고 생각합니다.