Because the cost to enter a sector is independent of the direction of
entry, we visit sectors at most once. Exploit that.
Beware: this is not the case for A*. Pitfall for any future
generalization to A*.
Speeds up distribution path assembly by 35-40% in my tests.
static natid pf_actor;
static double (*pf_sct_cost)(natid, int);
static natid pf_actor;
static double (*pf_sct_cost)(natid, int);
+#ifndef NDEBUG /* silence "not used" warning */
/* Is sector with uid UID open? */
static int
pf_is_open(int uid)
{
return pf_map[uid].visit == pf_visit;
}
/* Is sector with uid UID open? */
static int
pf_is_open(int uid)
{
return pf_map[uid].visit == pf_visit;
}
/* Is sector with uid UID closed? */
static int
/* Is sector with uid UID closed? */
static int
- if (pf_is_open(uid)) {
- i = pf_map[uid].heapi;
- DPRINTF("pf: reopen %d,%d %g %c %d\n", x, y, cost, dirch[dir], i);
- assert(cost < pf_map[uid].cost);
- } else {
- i = pf_nheap++;
- DPRINTF("pf: open %d,%d %g %c %d\n", x, y, cost, dirch[dir], i);
- pf_map[uid].heapi = i;
- pf_map[uid].visit = pf_visit;
- pf_heap[i].uid = uid;
- pf_heap[i].x = x;
- pf_heap[i].y = y;
- }
+ i = pf_nheap++;
+ DPRINTF("pf: open %d,%d %g %c %d\n", x, y, cost, dirch[dir], i);
+ assert(pf_is_unvisited(uid));
+ pf_map[uid].visit = pf_visit;
+ pf_heap[i].uid = uid;
+ pf_heap[i].x = x;
+ pf_heap[i].y = y;
pf_heap[i].cost = cost;
pf_sift_up(i);
pf_heap[i].cost = cost;
pf_sift_up(i);
nx = x_in_dir(x, DIR_FIRST + i);
ny = y_in_dir(y, DIR_FIRST + i);
nuid = XYOFFSET(nx, ny);
nx = x_in_dir(x, DIR_FIRST + i);
ny = y_in_dir(y, DIR_FIRST + i);
nuid = XYOFFSET(nx, ny);
+ /*
+ * Cost to enter NX,NY doesn't depend on direction of
+ * entry. This X,Y is at least as expensive as any
+ * previous one. Therefore, cost to go to NX,NY via X,Y
+ * is at least as high as any previously found route.
+ * Skip neighbors that have a route already.
+ */
+ if (!pf_is_unvisited(nuid))
+ continue;
c1 = pf_sct_cost(pf_actor, nuid);
if (c1 < 0)
continue;
c1 = pf_sct_cost(pf_actor, nuid);
if (c1 < 0)
continue;
- if (pf_is_unvisited(nuid) || cost + c1 < pf_map[nuid].cost)
- pf_open(nuid, nx, ny, DIR_FIRST + i, cost + c1);
+ pf_open(nuid, nx, ny, DIR_FIRST + i, cost + c1);