A * 2D Sidescroller의 길 찾기

Question

현재 2D- sidescroller- 절차 적으로 생성 된 세계 게임 (Terraria와 유사한 지형)에서 A * 길 찾기를 활용하려고합니다.

나는이 자원을 사용하고 : http://www.redblobgames.com/pathfinding/a-star/introduction.html

을 주로 주어진 다음 의사 사용하고 있습니다 :

frontier = PriorityQueue() 
frontier.put(start, 0) 
came_from = {} 
cost_so_far = {} 
came_from[start] = None 
cost_so_far[start] = 0 

while not frontier.empty(): 
    current = frontier.get() 

    if current == goal: 
     break 

    for next in graph.neighbors(current): 
     new_cost = cost_so_far[current] + graph.cost(current, next) 
     if next not in cost_so_far or new_cost < cost_so_far[next]: 
     cost_so_far[next] = new_cost 
     priority = new_cost + heuristic(goal, next) 
     frontier.put(next, priority) 
     came_from[next] = current 

내 질문은 : 많은 절차 적으로 생성 된 세계와 차원 - 횡 스크롤의를 , 내가 어떻게 국경을 선택합니까? 특정 타일에 대한 경로는 멀리 떨어져있을 수 있으며 전체지도를 반복하는 것이 현명하지 못한 것처럼 보입니다.

나는 이것을 효율적으로하기 위해 노력하고 있으므로 어떤 도움을 주시면 감사하겠습니다!

Answer 1

"프론티어 (frontier)"라는 말을 결코 들어 본 적이 없으며, 항상 "열린 목록"이었습니다. 여행 할 수있는 모든 노드 (이웃)를 배치했습니다. 내가 사용하고

성능 현명한 일 :

1) 다른 스레드에서 계산을 넣어 : (안 코 루틴) 체크 아웃 여기에 ThreadedJob 이 지연을 생성합니다 http://answers.unity3d.com/questions/357033/unity3d-and-c-coroutines-vs-threading.html - 결과는 몇 프레임이 될 것입니다 당신이 그것을 부른 후에, 다음 중 하나 : a) 그냥 기다리십시오. b) 목표물의 일반적인 방향을 시작하고 결과가 준비되면 경로를 변경합니다. c) 나머지가 아직 준비되지 않은 경우에도 경로의 첫 번째 노드로 이동하십시오.

2)의 결과를 캐시 : Dictionary<Vector4, List<Vector2>> pathCache; 키 Vector4가 startPosX, startPosY, finishPosX, finishPosY이고 값리스트 A *의 결과이다. 경로가 대칭이므로 경로를 A에서 B로 찾을 때 B-> A에 대한 캐시를 확인하고 경로를 뒤 바꾸어야합니다.