A* Pathfinding in a 2D Sidescroller

Question

I'm currently attempting to utilize A* pathfinding in my 2D-sidescroller-procedurally generated world game (think Terraria-like terrain).

I've been using this resource: http://www.redblobgames.com/pathfinding/a-star/introduction.html

And have been mainly using the following pseudocode given:

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

My question is: in a 2D-sidescroller with a large procedurally-generated world, how do I choose the frontier? The path to a specific tile could be any distance away, and it obviously seems unwise to iterate over the entire map.

I'm trying to do this efficiently, so any assistance would be appreciated!

Answer 1

I have never heard it being called "frontier", it has always been "open list" and you put there all nodes you can travel to - neighbours.

Performance-wise things i have used:

1) Put the calculation in another thread: (not co-routine) check out the ThreadedJob here http://answers.unity3d.com/questions/357033/unity3d-and-c-coroutines-vs-threading.html It will create lag - the result will be few frames after you call it, either: a)just wait; b)start going in the general direction of target and change path once results are ready; c) go to first node of the path even the rest is not yet ready.

2) Cache the results: Dictionary<Vector4, List<Vector2>> pathCache; where key, Vector4, is startPosX,startPosY,finishPosX,finishPosY, and the value List is the result of A*. Because path is symmetrical, you should also check cache for B->A and reverse the path, when you are looking for path from A to B.