사각형 격자에서 영역의 면적을 계산하기위한 알고리즘

Question

나는 타일 맵을 사용하는 게임을하고 있습니다. 지도의 사각형은 벽이거나 비어있을 수 있습니다. 내가 개발하려고하는 알고리즘은지도에서 한 지점을 가져 와서 해당 지점에서 도달 할 수있는 셀의 수를 반환해야합니다 (지점을 포함하는 섹터의 영역과 같습니다).

알고리즘을 수행하는 함수가 2 차원 배열의 형태로 x 좌표, y 좌표 및 맵을 사용한다고합시다.

function sectorArea(x_coord,y_coord,map) { ... } 

는 (의 벽을 나타내는 경우 1)지도는 다음과 같습니다 말 :

map = [0,0,1,0,0,0], 
     [0,0,1,0,0,0], 
     [1,1,1,0,0,0], 
     [0,0,0,0,0,0] 

그런 sectorArea(0,0,map) == 4 및 sectorArea(4,0,map) == 15을.

내 순진 구현은 재귀 적입니다. 대상 셀은 go 함수에 전달되며,이 함수는 비어있는 모든 인접 셀을 반복하여 결국 섹터의 모든 빈 셀에 퍼집니다. 실행 속도가 너무 느리고 호출 스택 제한에 도달하는 속도가 매우 빠릅니다.

function sectorArea(x_coord,y_coord,map) { 
    # First convert the map into an array of objects of the form: 
    # { value: 0 or 1, 
    # visited: false } 
    objMap = convertMap(map); 

    # The recursive function: 
    function go(x,y) { 
     if (outOfBounds(x) || outOfBounds(y) || 
      objMap[y][x].value == 1 || objMap[y][x].visited) 
      return 0; 
     else 
      objMap[y][x].visited = true; 
      return 1 + go(x+1,y) + go(x-1,y) + go(x,y+1) + go(x,y-1); 
    } 
    return go(x_coord,y_coord); 
} 

더 좋은 알고리즘을 제안 할만한 사람이 있습니까? 비 결정적 솔루션은 속도가 주요 쟁점 (알고리즘은 단일 틱 동안 다른 지점에서 3 ~ 4 번 호출 될 수 있기 때문에)이 정확하면 실제로는 괜찮습니다.

Answer 1

아마도 알고리즘 자체의 속도를 높일 수 있습니다. Wikipedia은 스캔 라인 방식이 효율적이라는 것을 제안합니다.

반복 호출 : 매번 영역 계산을 다시 실행할 필요가 없도록 결과를 캐시 할 수 있습니다.

타일과 나란히 정수 영역 맵을 유지하는 방법이 있습니다. 이것은 여러 영역을 나타내며, 예를 들어 -1은 특수 값으로 지역을 의미하지 않습니다. 이 지역지도는 visited 속성으로도 사용됩니다.이 외에도 영역이있는 짧은 배열을 유지하십시오. 당신이 (0, 0)의 면적을 계산하면

• , 당신은 북서쪽 모서리에있는 네 개의 타일에 0을 할당합니다 : 위의 예에서

  . 영역 배열에 영역 4도 추가합니다. 영역을 계산할 때 해당 좌표의 영역 맵 값이 -1이 아니라 0임을 알 수 있습니다. 이는 해당 지역이 이미 계산되었음을 의미합니다.

• (4, 4) 영역을 계산할 때 영역 맵에서 -1을 찾습니다. 이는 해당 지역이 아직 계산되지 않았 음을 의미합니다. 그렇게하면, 영역을 1로 표시하고 새로운 영역 인 15를 영역 배열에 추가합니다.

보드가 얼마나 자주 바뀌는 지 알 수 없습니다. 영역을 다시 계산해야 할 경우 영역 맵을 비우고 배열 목록을 비 웁니다.

지역 맵은 한 번만 생성되며 모든 진드기마다 다시 만들어지지 않습니다. (objMap을 덮어 쓰는 대신 자주 다시 작성하면 코드에서 병목 현상이 발생할 수 있습니다.)