git.pond.sub.org Git - empserver/blob - src/lib/as/as_winnow.c

   1 /*
   2  *  A* Search - A search library used in Empire to determine paths between
   3  *              objects.
   4  *  Copyright (C) 1990-1998 Phil Lapsley
   5  *
   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.
  10  *
  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.
  15  *
  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
  19  */
  20 #include <stdio.h>
  21 #include <stdlib.h>
  22 #include "as.h"
  23
  24 #if !defined(lint) && !defined(SABER)
  25 static char sccsid[] = "@(#)as_winnow.c 1.8     11/13/90";
  26 #endif /* not lint */
  27
  28 static struct as_node *as_newnode(struct as_node *backp, struct as_coord c,
  29                                   double inclbcost, double lbcost,
  30                                   double knowncost, double seccost);
  31
  32 /*
  33  * Take a list of neighbor coordinates and winnow them down into
  34  * an interesting list of neighbor nodes.  This means:
  35  *
  36  *      For each neighbor,
  37  *              Compute a lower bound on the total cost to target.
  38  *              If this neighbor is already in our queue,
  39  *                      See if the new neighbor is cheaper.
  40  *                      If so, add it to queue and move the
  41  *                      old node to the subsumed list.
  42  *                      If not, ignore this neighbor.
  43  *              If this neighbor isn't in the queue, add it.
  44  *
  45  */
  46 int
  47 as_winnow(struct as_data *adp, struct as_coord *coords, int ncoords)
  48 {
  49     int i = 0;
  50     int fix_pointer;
  51     double knowncost;
  52     double incknowncost;
  53     double lbcost;
  54     double inclbcost;
  55     double seccost;
  56     struct as_coord *cp;
  57     struct as_coord *end;
  58     struct as_queue *qp;
  59     struct as_node *np;
  60
  61     for (cp = coords, end = coords + ncoords; cp < end; cp++) {
  62         fix_pointer = 0;
  63         incknowncost = (*adp->realcost) (adp->head->np->c, *cp,
  64                                          adp->userdata);
  65         knowncost = adp->head->np->knowncost + incknowncost;
  66         /*
  67          * If this neighbor is already in the queue, we can
  68          * save some time.
  69          */
  70         qp = as_iscinq(adp, *cp);
  71         inclbcost = qp ? qp->np->inclbcost :
  72             (*adp->lbcost) (*cp, adp->to, adp->userdata);
  73         if (inclbcost < 0.0)    /* skip bad cases */
  74             continue;
  75         lbcost = knowncost + inclbcost;
  76 #ifdef DEBUG
  77         fprintf(stderr, "\tneighbor %d, %d, lbcost %f ", cp->x, cp->y,
  78                 lbcost);
  79 #endif /* DEBUG */
  80         /*
  81          * If this neighbor is already in the queue, check to
  82          * see which has the lower cost.  If the one already in
  83          * the queue is cheaper, skip this neighbor as bad.  If
  84          * the neighbor does, delete the one in the queue.
  85          */
  86         if (qp) {
  87             if (qp->np->lbcost <= lbcost) {
  88 #ifdef DEBUG
  89                 fprintf(stderr, "old, loses to %f\n", qp->np->lbcost);
  90 #endif /* DEBUG */
  91                 continue;
  92             } else {
  93 #ifdef DEBUG
  94                 fprintf(stderr, "old, wins over %f\n", qp->np->lbcost);
  95 #endif /* DEBUG */
  96                 if (qp->np->flags & AS_TRIED) {
  97                     /* should "never happen" */
  98                     return (0);
  99                 }
 100                 /*
 101                  * The neighbor is better than a previously visited coordinate;
 102                  * remove the old coordinate from the queue and add it to
 103                  * the subsumed nodes queue.  To get here at
 104                  * all we can't be the head, thus qp->prev is defined.
 105                  */
 106                 /* Delete from main queue */
 107                 qp->prev->next = qp->next;
 108                 if (qp->next)
 109                     qp->next->prev = qp->prev;
 110
 111                 /* Add to subsumed queue */
 112                 if (adp->subsumed) {
 113                     adp->subsumed->prev = qp;
 114                     qp->next = adp->subsumed;
 115                 } else {
 116                     qp->next = NULL;
 117                 }
 118                 adp->subsumed = qp;
 119                 adp->subsumed->prev = NULL;
 120                 fix_pointer = 1;
 121                 /*
 122                  * At this point, the as_iscinq code may contain bogus pointer
 123                  * refs.  They'll be fixed when as_merge merges the new
 124                  * neighbors into the main queue.
 125                  */
 126             }
 127         }
 128 #ifdef DEBUG
 129         else {
 130             fprintf(stderr, "new\n");
 131         }
 132 #endif /* DEBUG */
 133
 134         if (qp)
 135             seccost = qp->np->seccost;
 136         else
 137             seccost = (adp->seccost) ?
 138                 (*adp->seccost) (*cp, adp->to, adp->userdata) : 0.0;
 139         np = as_newnode(adp->head->np, *cp, inclbcost, lbcost,
 140                         knowncost, seccost);
 141         if (np == NULL)
 142             return (0);
 143         if (fix_pointer) {
 144 #ifdef DEBUG
 145             fprintf(stderr, "Fixing pointer for %d, %d\n",
 146                     adp->subsumed->np->c.x, adp->subsumed->np->c.y);
 147 #endif
 148             adp->subsumed->np->back = np;
 149         }
 150         adp->neighbor_nodes[i++] = np;
 151
 152     }
 153     adp->neighbor_nodes[i] = NULL;
 154
 155     return (i);
 156 }
 157
 158
 159 static struct as_node *
 160 as_newnode(struct as_node *backp, struct as_coord c,
 161            double inclbcost, double lbcost, double knowncost,
 162            double seccost)
 163 {
 164     struct as_node *np;
 165
 166     /* Got an interesting coordinate; make a node for it. */
 167     AS_NEW_MALLOC(np, struct as_node, NULL);
 168     np->flags = 0;
 169     np->c = c;
 170     np->inclbcost = inclbcost;
 171     np->lbcost = lbcost;
 172     np->knowncost = knowncost;
 173     np->seccost = seccost;
 174     np->step = backp->step;
 175     np->back = backp;
 176
 177     return (np);
 178 }