Miscellany

list_t *find_path (u32 start_x, u32 start_y, u32 end_x, u32 end_y,           u32 depth, heuristic h){   list_t *closed_list;   heap_t *open_list;   node_t *current, *adjacent, *end;   int dx, dy;   int update;   end = grid_at(grid_scale(end_x), grid_scale(end_y));   /* initialize structures */   closed_list = list_create();   open_list = heap_create(GRIDWIDTH * GRIDHEIGHT, node_compare);   /* create first node */   current = grid_at(grid_scale(start_x), grid_scale(start_y));   current->g = 0;   current->h = COST * h(current->x, current->y, end->x, end->y);   /* invalid start location */   if (current == NULL) {      heap_destroy(open_list);      list_destroy(closed_list);      return NULL;   }   heap_insert(open_list, current);   while (list_size(closed_list) < depth && heap_size(open_list) > 0) {      current = heap_extract_min(open_list);      /* add to path */      list_append(closed_list, current);      /* found end node */      if (current == end)         break;      if (list_size(open_list) == 0)         break;      /* add neighbours cells to open list */      for (dx=-1 ; dx <= 1 ; ++dx) {         for (dy=-1 ; dy <= 1 ; ++dy) {            /* skip current node */            if (dx == 0 && dy == 0)               continue;            adjacent = grid_at(current->x + dx, current->y + dy);            /* skip blocked and path nodes */            if (adjacent == NULL || adjacent->state == BLOCKED ||                list_contains(closed_list,adjacent)) {               if (adjacent->state == BLOCKED)               continue;            }            /* add node to the open list */            if (!heap_contains(open_list,adjacent)) {               adjacent->x = current->x + dx;               adjacent->y = current->y + dy;               /* compute estimation cost from this node to                 * end node */               adjacent->h = COST * h(adjacent->x, adjacent->y,                               end->x, end->y);               adjacent->g = current->g + COST;               heap_insert(open_list, adjacent);            }            /* update open list node if necessary */            else {               if ((current->g + COST) < adjacent->g) {                  adjacent->g = current->g + COST;                  heap_refresh(open_list, adjacent);               }            }         }      }   }   heap_destroy(open_list);   return closed_list;}