2 * A* Search - A search library used in Empire to determine paths between
4 * Copyright (C) 1990-1998 Phil Lapsley
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
26 static struct as_node *as_newnode(struct as_node *backp, struct as_coord c,
27 double inclbcost, double lbcost,
28 double knowncost, double seccost);
31 * Take a list of neighbor coordinates and winnow them down into
32 * an interesting list of neighbor nodes. This means:
35 * Compute a lower bound on the total cost to target.
36 * If this neighbor is already in our queue,
37 * See if the new neighbor is cheaper.
38 * If so, add it to queue and move the
39 * old node to the subsumed list.
40 * If not, ignore this neighbor.
41 * If this neighbor isn't in the queue, add it.
44 as_winnow(struct as_data *adp, struct as_coord *coords, int ncoords)
58 for (cp = coords, end = coords + ncoords; cp < end; cp++) {
60 incknowncost = adp->realcost(adp->head->np->c, *cp, adp->userdata);
61 knowncost = adp->head->np->knowncost + incknowncost;
63 * If this neighbor is already in the queue, we can
66 qp = as_iscinq(adp, *cp);
67 inclbcost = qp ? qp->np->inclbcost :
68 adp->lbcost(*cp, adp->to, adp->userdata);
69 if (inclbcost < 0.0) /* skip bad cases */
71 lbcost = knowncost + inclbcost;
73 fprintf(stderr, "\tneighbor %d, %d, lbcost %f ", cp->x, cp->y,
77 * If this neighbor is already in the queue, check to
78 * see which has the lower cost. If the one already in
79 * the queue is cheaper, skip this neighbor as bad. If
80 * the neighbor does, delete the one in the queue.
83 if (qp->np->lbcost <= lbcost) {
85 fprintf(stderr, "old, loses to %f\n", qp->np->lbcost);
90 fprintf(stderr, "old, wins over %f\n", qp->np->lbcost);
92 if (qp->np->flags & AS_TRIED) {
93 /* should "never happen" */
97 * The neighbor is better than a previously visited coordinate;
98 * remove the old coordinate from the queue and add it to
99 * the subsumed nodes queue. To get here at
100 * all we can't be the head, thus qp->prev is defined.
102 /* Delete from main queue */
103 qp->prev->next = qp->next;
105 qp->next->prev = qp->prev;
107 /* Add to subsumed queue */
109 adp->subsumed->prev = qp;
110 qp->next = adp->subsumed;
115 adp->subsumed->prev = NULL;
118 * At this point, the as_iscinq code may contain bogus pointer
119 * refs. They'll be fixed when as_merge merges the new
120 * neighbors into the main queue.
126 fprintf(stderr, "new\n");
131 seccost = qp->np->seccost;
133 seccost = adp->seccost ?
134 adp->seccost(*cp, adp->to, adp->userdata) : 0.0;
135 np = as_newnode(adp->head->np, *cp, inclbcost, lbcost,
141 fprintf(stderr, "Fixing pointer for %d, %d\n",
142 adp->subsumed->np->c.x, adp->subsumed->np->c.y);
144 adp->subsumed->np->back = np;
146 adp->neighbor_nodes[i++] = np;
149 adp->neighbor_nodes[i] = NULL;
155 static struct as_node *
156 as_newnode(struct as_node *backp, struct as_coord c,
157 double inclbcost, double lbcost, double knowncost,
162 /* Got an interesting coordinate; make a node for it. */
163 AS_NEW_MALLOC(np, struct as_node, NULL);
166 np->inclbcost = inclbcost;
168 np->knowncost = knowncost;
169 np->seccost = seccost;
170 np->step = backp->step;