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
  21 #include <config.h>
  22
  23 #include <stdlib.h>
  24 #include "as.h"
  25
  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);
  29
  30 /*
  31  * Take a list of neighbor coordinates and winnow them down into
  32  * an interesting list of neighbor nodes.  This means:
  33  *
  34  *      For each neighbor,
  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.
  42  */
  43 int
  44 as_winnow(struct as_data *adp, struct as_coord *coords, int ncoords)
  45 {
  46     int i = 0;
  47     int fix_pointer;
  48     double knowncost;
  49     double incknowncost;
  50     double lbcost;
  51     double inclbcost;
  52     double seccost;
  53     struct as_coord *cp;
  54     struct as_coord *end;
  55     struct as_queue *qp;
  56     struct as_node *np;
  57
  58     for (cp = coords, end = coords + ncoords; cp < end; cp++) {
  59         fix_pointer = 0;
  60         incknowncost = adp->realcost(adp->head->np->c, *cp, adp->userdata);
  61         knowncost = adp->head->np->knowncost + incknowncost;
  62         /*
  63          * If this neighbor is already in the queue, we can
  64          * save some time.
  65          */
  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 */
  70             continue;
  71         lbcost = knowncost + inclbcost;
  72 #ifdef DEBUG
  73         fprintf(stderr, "\tneighbor %d, %d, lbcost %f ", cp->x, cp->y,
  74                 lbcost);
  75 #endif /* DEBUG */
  76         /*
  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.
  81          */
  82         if (qp) {
  83             if (qp->np->lbcost <= lbcost) {
  84 #ifdef DEBUG
  85                 fprintf(stderr, "old, loses to %f\n", qp->np->lbcost);
  86 #endif /* DEBUG */
  87                 continue;
  88             } else {
  89 #ifdef DEBUG
  90                 fprintf(stderr, "old, wins over %f\n", qp->np->lbcost);
  91 #endif /* DEBUG */
  92                 if (qp->np->flags & AS_TRIED) {
  93                     /* should "never happen" */
  94                     return 0;
  95                 }
  96                 /*
  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.
 101                  */
 102                 /* Delete from main queue */
 103                 qp->prev->next = qp->next;
 104                 if (qp->next)
 105                     qp->next->prev = qp->prev;
 106
 107                 /* Add to subsumed queue */
 108                 if (adp->subsumed) {
 109                     adp->subsumed->prev = qp;
 110                     qp->next = adp->subsumed;
 111                 } else {
 112                     qp->next = NULL;
 113                 }
 114                 adp->subsumed = qp;
 115                 adp->subsumed->prev = NULL;
 116                 fix_pointer = 1;
 117                 /*
 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.
 121                  */
 122             }
 123         }
 124 #ifdef DEBUG
 125         else {
 126             fprintf(stderr, "new\n");
 127         }
 128 #endif /* DEBUG */
 129
 130         if (qp)
 131             seccost = qp->np->seccost;
 132         else
 133             seccost = adp->seccost ?
 134                 adp->seccost(*cp, adp->to, adp->userdata) : 0.0;
 135         np = as_newnode(adp->head->np, *cp, inclbcost, lbcost,
 136                         knowncost, seccost);
 137         if (np == NULL)
 138             return 0;
 139         if (fix_pointer) {
 140 #ifdef DEBUG
 141             fprintf(stderr, "Fixing pointer for %d, %d\n",
 142                     adp->subsumed->np->c.x, adp->subsumed->np->c.y);
 143 #endif
 144             adp->subsumed->np->back = np;
 145         }
 146         adp->neighbor_nodes[i++] = np;
 147
 148     }
 149     adp->neighbor_nodes[i] = NULL;
 150
 151     return i;
 152 }
 153
 154
 155 static struct as_node *
 156 as_newnode(struct as_node *backp, struct as_coord c,
 157            double inclbcost, double lbcost, double knowncost,
 158            double seccost)
 159 {
 160     struct as_node *np;
 161
 162     /* Got an interesting coordinate; make a node for it. */
 163     AS_NEW_MALLOC(np, struct as_node, NULL);
 164     np->flags = 0;
 165     np->c = c;
 166     np->inclbcost = inclbcost;
 167     np->lbcost = lbcost;
 168     np->knowncost = knowncost;
 169     np->seccost = seccost;
 170     np->step = backp->step;
 171     np->back = backp;
 172
 173     return np;
 174 }