I need Path-Finding

I need Path-Finding

• Euclidez

  Thanks for the algorithm. I think I may be able to get that working. Right now I am working on a way to determine the cost from each square to each other square.
  

• Corgalore

  Thank you! That clears it up :)
  
  

• sachin.pithode

  How precise must the shortest path be Do you need to find an absolute shortest path or only good path
  
  If you need an absolute shortest path, and if you can't find a simpler way, I can help you get started on a Dijkstra graph algorithm.  But I'd be interested in an easier method as well...
  
  Dijkstra's algorithm is well suited when you have a grid with medium to large squares, a fairly large amount of obstacles, and need an absolute shortest path.
  
  Let's hope someone comes along and makes your life simpler though.
  

• mfdiqwer

  Yes, sorry, I missed one line: you need to add the start position onto the open list before entering the loop.
  
  A-star is not specific to regular grids, but regular grids are often used as examples. In the case of a regular grid, the "neighbors" are your N,E,W,S neighbors (that are actually reachable). You can handle blocked paths by saying that that is not a neighbor, or by setting an infinite cost (so they will be pushed to the end of the chain).
  
  Calculating the cost uses actual cost of traversal -- in a regular grid with no terrain types, this will always be 1. If traveling uphill is more expensive than traveling downhill, downhill cost might be 1, but uphill cost might be 2.
  
  Estimating the cost uses a heuristic. This can be pythagoras, but surprisingly, manhattan distance (abs(delta-X) plus abs(delta-Y)) will also work (as long as you can only walk N,E,W,S). The important bit is that the heuristic must not over-estimate the cost of the remaining path to the goal. If it does, A-star may not find the cheapest path, but it will still find a path.
  
  
  
  
  
  

• Trish

  Jon Watte wrote:

  Pos p = startPos; Pos g = theGoal; PriorityQueue<Pos, Cost> open = new PriorityQueue<Pos, Cost>(); Set<Pos> closed = new Set<Pos>(); while (!open.Empty) { closed.Add(p); if (p == g) { Success(); break; } foreach (Pos n in p.Neighbors) { if (!closed.Contains(n)) { n.ActualCost = p.ActualCost + CalcCost(p, n); open.Add(n, n.ActualCost + EstimateCost(n, g)); } } p = open.DequeueFront(); }

  
  
  That really is the simplest A* I've seen, but I haven't been able to implement one yet, so still have some questions.
  
  1. Could you give a little more insight on some particular points, namely, the difference between calculating the cost and estimating the cost. If two tiles are adjacent (for instance, (3,3) and (4,3)), is the cost "1", or it's a different way of approaching it And I'm guessing that estimating the cost between n and g would be using Pythagoras. Is that correct
  
  2. A Neighbour is every adjacent tile that isn't blocked, or should I also add blocked tiles to the neighbour list Also, in my game, the character can't walk diagonally, so should I add only the N S E and W tiles to the neighbour list, or add the diagonals too
  
  3. At the start the open list is created, and then you have "while(!open.Empty)". So if open isn't empty when starting, then what should be the initial value
  
  Sorry if these are terribly simple questions, I'm fairly new at game programming, and it's the first time I'm trying to implement something like this, so I need to know the details.
  
  

• Aleniko29139

  Check this out...

  http://www.policyalmanac.org/games/aStarTutorial.htm

  
  

• ConfigSSIS

  A-star is usually better than Dijkstra, even for "guaranteed shortest path." That's because it won't examine nodes that can't possibly be part of the shortest path. Dijkstra calculates global costs (examine all nodes).
  
  A-star is really simple, though. It looks something like:
  
  Pos p = startPos;
  Pos g = theGoal;
  PriorityQueue<Pos, Cost> open = new PriorityQueue<Pos, Cost>();
  Set<Pos> closed = new Set<Pos>();
  while (!open.Empty) {
  closed.Add(p);
  if (p == g) {
  Success();
  break;
  }
  foreach (Pos n in p.Neighbors) {
  if (!closed.Contains(n)) {
  n.ActualCost = p.ActualCost + CalcCost(p, n);
  open.Add(n, n.ActualCost + EstimateCost(n, g));
  }
  }
  p = open.DequeueFront();
  }
  
  That's it! You need to have a Set and a PriorityQueue, though, and you need an ability to find the neighbors of a given cell, and you need to be able to calculate the actual cost between two neighbors, and to estimate the cost between a position and its goal, without that estimate being an over-estimate.
  
  
  

• Pascal Jette

  thanks.. thats a whole lot simpler than djikstra...
  
• I need Path-Finding