git.pond.sub.org Git - empserver/blob - src/lib/as/as_search.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  * 11/09/98 - Steve McClure
  22  *  Added path list caching structures
  23  */
  24
  25 #include <config.h>
  26
  27 #include <stdlib.h>
  28 #include "as.h"
  29
  30 /*
  31  * Basic A* search function.  "adp" should have been initialized by
  32  * as_init (any previously allocated data will be freed by as_reset here),
  33  * and adp->from and adp->to should be set accordingly.  On success,
  34  * returns 0, with adp->path set to a linked list of coordinates to target.
  35  * If we can't find target, return -1; if malloc fails, return -2.
  36  */
  37 int
  38 as_search(struct as_data *adp)
  39 {
  40     int iter = 0;
  41     struct as_queue *head;
  42     struct as_node *np;
  43 #ifdef DEBUG
  44     int i;
  45     struct as_queue *qp;
  46     struct as_path *pp;
  47 #endif /* DEBUG */
  48
  49     as_reset(adp);
  50
  51     /*
  52      * Jump start the queue by making first element the zero-cost
  53      * node where we start.
  54      */
  55     AS_NEW_MALLOC(head, struct as_queue, -2);
  56     adp->head = head;
  57     head->next = head->prev = NULL;
  58     AS_NEW(np, struct as_node, -2);
  59     np->c = adp->from;
  60     head->np = np;
  61     as_setcinq(adp, head->np->c, adp->head);
  62
  63     for (;;) {
  64         iter++;
  65         /* see if we're done, one way or another */
  66         if (head == NULL)
  67             break;
  68
  69 #ifdef DEBUG
  70         fprintf(stderr, "Iteration %d, head at %d, %d\n", iter,
  71                 head->np->c.x, head->np->c.y);
  72 #endif /* DEBUG */
  73
  74         /* Add it to the cache */
  75         as_add_cachepath(adp);
  76
  77         if (head->np->c.x == adp->to.x && head->np->c.y == adp->to.y)
  78             break;
  79
  80         /* extend queue by neighbors */
  81 #ifdef DEBUG
  82         fprintf(stderr, "\tExtending queue\n");
  83 #endif /* DEBUG */
  84         adp->head = head = as_extend(adp);
  85         /* FIXME leaks when as_extend() returns NULL without adding to tried */
  86
  87 #ifdef DEBUG
  88         fprintf(stderr, "queue:\n");
  89         i = 0;
  90         for (qp = head; qp; qp = qp->next) {
  91             fprintf(stderr, "\t%d, %d so far %f lb %f sec %f\n",
  92                     qp->np->c.x, qp->np->c.y,
  93                     qp->np->knowncost, qp->np->lbcost, qp->np->seccost);
  94             i++;
  95         }
  96         fprintf(stderr, "\tqueue len %d\n", i);
  97 #endif /* DEBUG */
  98
  99     }
 100
 101     if (head == NULL) {
 102 #ifdef DEBUG
 103         fprintf(stderr, "Failed\n");
 104 #endif /* DEBUG */
 105         return -1;
 106     }
 107
 108     as_makepath(adp);
 109
 110 #ifdef DEBUG
 111     fprintf(stderr, "Succeeded, iter %d, cost %f!\n", iter,
 112             head->np->knowncost);
 113     fprintf(stderr, "Path:\n");
 114     for (pp = adp->path; pp; pp = pp->next) {
 115         fprintf(stderr, "\t%d, %d\n", pp->c.x, pp->c.y);
 116     }
 117     fprintf(stderr, "Tried queue:\n");
 118     for (qp = adp->tried; qp; qp = qp->next) {
 119         fprintf(stderr, "\t%d, %d\n", qp->np->c.x, qp->np->c.y);
 120     }
 121     fprintf(stderr, "Subsumed queue:\n");
 122     for (qp = adp->subsumed; qp; qp = qp->next) {
 123         fprintf(stderr, "\t%d, %d\n", qp->np->c.x, qp->np->c.y);
 124     }
 125 #endif /* DEBUG */
 126
 127     return 0;
 128 }
 129
 130 /*
 131  * Work backwards through the list of nodes (starting at head)
 132  * to produce a path.
 133  */
 134 void
 135 as_makepath(struct as_data *adp)
 136 {
 137     struct as_path *pp;
 138     struct as_node *np;
 139
 140     for (np = adp->head->np; np; np = np->back) {
 141         pp = malloc(sizeof(struct as_path));
 142         pp->c = np->c;
 143         pp->next = adp->path;
 144         adp->path = pp;
 145     }
 146 }