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