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  *
  29 as_newnode(struct as_node *backp, struct as_coord c,
  30            double inclbcost, double lbcost, 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, lbcost);
  78 #endif /* DEBUG */
  79                 /*
  80                  * If this neighbor is already in the queue, check to
  81                  * see which has the lower cost.  If the one already in
  82                  * the queue is cheaper, skip this neighbor as bad.  If
  83                  * the neighbor does, delete the one in the queue.
  84                  */
  85                 if (qp) {
  86                         if (qp->np->lbcost <= lbcost) {
  87 #ifdef DEBUG
  88 fprintf(stderr, "old, loses to %f\n", qp->np->lbcost);
  89 #endif /* DEBUG */
  90                                 continue;
  91                         } else {
  92 #ifdef DEBUG
  93 fprintf(stderr, "old, wins over %f\n", qp->np->lbcost);
  94 #endif /* DEBUG */
  95                                 if (qp->np->flags & AS_TRIED) {
  96                                         /* should "never happen" */
  97                                         return (0);
  98                                 }
  99                 /*
 100                  * The neighbor is better than a previously visited coordinate;
 101                  * remove the old coordinate from the queue and add it to
 102                  * the subsumed nodes queue.  To get here at
 103                  * all we can't be the head, thus qp->prev is defined.
 104                  */
 105                                 /* Delete from main queue */
 106                                 qp->prev->next = qp->next;
 107                                 if (qp->next)
 108                                         qp->next->prev = qp->prev;
 109
 110                                 /* Add to subsumed queue */
 111                                 if (adp->subsumed) {
 112                                         adp->subsumed->prev = qp;
 113                                         qp->next = adp->subsumed;
 114                                 } else {
 115                                         qp->next = NULL;
 116                                 }
 117                                 adp->subsumed = qp;
 118                                 adp->subsumed->prev = NULL;
 119                                 fix_pointer = 1;
 120                 /*
 121                  * At this point, the as_iscinq code may contain bogus pointer
 122                  * refs.  They'll be fixed when as_merge merges the new
 123                  * neighbors into the main queue.
 124                  */
 125                         }
 126                 }
 127 #ifdef DEBUG
 128 else {
 129 fprintf(stderr, "new\n");
 130 }
 131 #endif /* DEBUG */
 132
 133                 if (qp)
 134                         seccost = qp->np->seccost;
 135                 else
 136                         seccost = (adp->seccost) ?
 137                                 (*adp->seccost)(*cp, adp->to, adp->userdata) :
 138                                 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", adp->subsumed->np->c.x,
 146 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, double seccost)
 162 {
 163         struct as_node  *np;
 164
 165         /* Got an interesting coordinate; make a node for it. */
 166         AS_NEW_MALLOC(np, struct as_node, NULL);
 167         np->flags = 0;
 168         np->c = c;
 169         np->inclbcost = inclbcost;
 170         np->lbcost = lbcost;
 171         np->knowncost = knowncost;
 172         np->seccost = seccost;
 173         np->step = backp->step;
 174         np->back = backp;
 175
 176         return (np);
 177 }