🚀 go-pugleaf

I forget the official name of this algorithm, but:

struct path_element {
  Cell *indicator;
  int cost;
  Cell *previous;
};

Set struct path_element Reached;

if (start_cell == target_cell) return; /* already there */
create path_element start;
start.indicator = &start_cell;
start.cost = 0;
start.previous = NULL;
Reached = start;
for (;;) {
  for each cell in Reached {
    find cheapest cell reachable from it that isn't already in Reached;
  }
  if (cheapest == target_cell) return; /* found it */
  add cheapest to Reached;
}


And that's it.  Details of implementation left as an exercise for the reader.


---
Brian Scearce                               bls@sector7g.eng.sun.com
        The above does not necessarily represent Sun policy.
          It's easier to get forgiveness than permission.