직선 코너 최적화 경로 검색을위한 A * 알고리즘

나는 RIP 도시 구축 게임을 기반으로 그리드에 도로를 배치하기위한 길 찾기에서 이미 길 찾기에 A * 알고리즘을 사용 했으므로 편리하다고 생각했습니다. 이 작업에도 사용하십시오.직선 코너 최적화 경로 검색을위한 A * 알고리즘

for (int x = -1; x <= 1; x++) 
     { 
      for (int y = -1; y <= 1; y++) 
      { 
       if (x == 0 && y == 0)) 
       { continue; } 
       //the rest of the code goes here

I : Roadplacement

원래 알고리즘마다 확인 그리드 광장과 같이 옆에 : 우리의 도로가 단순한 사각형이기 때문에 도로가 그림처럼 될 것이기 때문에 나는 원래 알고리즘을 사용 할 수 없습니다

for (int x = -1; x <= 1; x++) 
      { 
       for (int y = -1; y <= 1; y++) 
       { 
        if ((x == 0 && y == 0)|| (x != 0 && y != 0)) 
        { continue; } 
        //the rest of the code goes here

유일한 문제와를 : 그 대각선 게재 위치를 방지 할 수있는 가장 쉬운 방법을 생각하는 것은, 모든 그리드 광장 더하기 기호에서 8 개 주위 사각형 그러나 다만 4를 확인하지 않을 한 후 사용할 수있는 옵션을 차단했다 이것은 경로를 찾는 데 걸리는 시간이 극적으로 증가합니다. 즉, 큰 거리에서 6ms에서 70ms로 점프합니다. 누구나 사용할 수있는 해결책이 있습니까? 아니면 이런 종류의 문제에 더 적합한 다른 알고리즘에 대한 제안이 있습니까?

미리 감사드립니다.

출처

2017-12-28 IsolatedSushi

대각선 연결을 제거했음을 고려하여 경험적으로 조정 했습니까? – harold

harold의 말에 따르면이 검색에 대한 경험적 발견은 'abs (destination_x - x) + abs (destination_y - y)'(즉, "Manhattan distance")와 같아야합니다. 테스트 할 지점을 조금이라도 최적화 할 수는 있지만 변경 한 점은 더 적은 포인트를 확인하기 때문에 속도를 높여야합니다. – erickson

차량이 대각선 방향으로 움직일 수 있다면 길도 갈 수 있어야합니다. 당신이 보여준 그림은보기 흉하게 보이지만 그것은 적절한 대각선의 한쪽에 도로가 있고 다른쪽에 풍경이있는 타일이 필요하기 때문입니다. 본질적으로, 당신은 당신의 길을 에일 리 어스 될 필요가 있습니다. – erickson

당신이 줄을 최적화하기 위해 XOR를 사용할 수있는이 같은 수행하여

if ((x == 0 && y == 0)|| (x != 0 && y != 0))

을 :

if (!(x^y))

나는이 일을 속도를 얼마나 잘 모르겠어요,하지만 그것은 가치 샷!

출처

2017-12-28 23:37:59

직선 코너 최적화 경로 검색을위한 A * 알고리즘

답변

관련 문제