* Added path list caching structures
*/
-#include <stdio.h> /* for FILE */
-#include "misc.h" /* for s_char */
+#include <stdio.h> /* for FILE */
+#include "misc.h" /* for s_char */
/*
* Coordinate.
*/
struct as_coord {
- int x, y;
+ int x, y;
};
/*
* Path, made up of a linked list of coordinates.
*/
struct as_path {
- struct as_coord c;
- struct as_path *next;
+ struct as_coord c;
+ struct as_path *next;
};
/*
* Basic node, used internally by A* algorithm.
*/
struct as_node {
- struct as_coord c; /* our coordinate */
- double knowncost; /* cost so far */
- double lbcost; /* lower bound on cost to dest */
- double inclbcost; /* incremental lower bound cost */
- double seccost; /* used to break ties */
- int step;
- int flags;
- struct as_node *back;
+ struct as_coord c; /* our coordinate */
+ double knowncost; /* cost so far */
+ double lbcost; /* lower bound on cost to dest */
+ double inclbcost; /* incremental lower bound cost */
+ double seccost; /* used to break ties */
+ int step;
+ int flags;
+ struct as_node *back;
};
-#define AS_TRIED 1 /* we've tried this node before */
+#define AS_TRIED 1 /* we've tried this node before */
/*
* Linked list of nodes, used internally by A* algorithm.
*/
struct as_queue {
- struct as_node *np;
- struct as_queue *next;
- struct as_queue *prev;
+ struct as_node *np;
+ struct as_queue *next;
+ struct as_queue *prev;
};
/*
* coordinate before.
*/
struct as_hash {
- struct as_coord c;
- struct as_queue *qp;
- struct as_hash *next;
+ struct as_coord c;
+ struct as_queue *qp;
+ struct as_hash *next;
};
/*
* used by A* internals.
*/
struct as_data {
- int maxneighbors; /* max # of neighbors a cell can have */
- int hashsize; /* size of internal hash table */
-
- int (*hash)(struct as_coord); /* hash function (coord -> int) */
- int (*neighbor)(struct as_coord, struct as_coord *, s_char *); /* function to find neighbors */
- double (*lbcost)(struct as_coord, struct as_coord, s_char *); /* function to give lower bound cost */
- double (*realcost)(struct as_coord, struct as_coord, s_char *); /* function to give real cost */
- double (*seccost)(struct as_coord, struct as_coord, s_char *); /* function to secondary cost */
- char *userdata; /* user's data, passed to callbacks */
- struct as_coord from; /* from coordinate */
- struct as_coord to; /* to coordinate */
- struct as_path *path; /* solution */
-
- /* below are "private" to as_ routines */
- struct as_queue *head;
- struct as_queue *tried;
- struct as_hash **hashtab;
- struct as_queue *subsumed;
- struct as_coord *neighbor_coords;
- struct as_node **neighbor_nodes;
+ int maxneighbors; /* max # of neighbors a cell can have */
+ int hashsize; /* size of internal hash table */
+
+ int (*hash) (struct as_coord); /* hash function (coord -> int) */
+ int (*neighbor) (struct as_coord, struct as_coord *, s_char *); /* function to find neighbors */
+ double (*lbcost) (struct as_coord, struct as_coord, s_char *); /* function to give lower bound cost */
+ double (*realcost) (struct as_coord, struct as_coord, s_char *); /* function to give real cost */
+ double (*seccost) (struct as_coord, struct as_coord, s_char *); /* function to secondary cost */
+ char *userdata; /* user's data, passed to callbacks */
+ struct as_coord from; /* from coordinate */
+ struct as_coord to; /* to coordinate */
+ struct as_path *path; /* solution */
+
+ /* below are "private" to as_ routines */
+ struct as_queue *head;
+ struct as_queue *tried;
+ struct as_hash **hashtab;
+ struct as_queue *subsumed;
+ struct as_coord *neighbor_coords;
+ struct as_node **neighbor_nodes;
};
/*
struct as_topath {
coord x;
- struct as_path *path; /* Path from holder of this list to here */
+ struct as_path *path; /* Path from holder of this list to here */
struct as_topath *next;
};
struct as_frompath {
coord x;
- struct as_topath **tolist; /* List of nodes we have a path to */
- struct as_frompath *next;
+ struct as_topath **tolist; /* List of nodes we have a path to */
+ struct as_frompath *next;
};
/*
/* Functions that the user can call. */
-extern struct as_data *
-as_init(int maxneighbors, int hashsize,
- int (*hashfunc) (struct as_coord),
- int (*neighborfunc) (struct as_coord, struct as_coord *, s_char *),
- double (*lbcostfunc) (struct as_coord, struct as_coord, s_char *),
- double (*realcostfunc) (struct as_coord, struct as_coord, s_char *),
- double (*seccostfunc) (struct as_coord, struct as_coord, s_char *),
- s_char *userdata);
-extern int as_search(struct as_data *adp);
-extern void as_delete(struct as_data *adp);
-extern void as_reset(struct as_data *adp);
-extern void as_stats(struct as_data *adp, FILE *fp);
+extern struct as_data *as_init(int maxneighbors, int hashsize,
+ int (*hashfunc) (struct as_coord),
+ int (*neighborfunc) (struct as_coord,
+ struct as_coord *,
+ s_char *),
+ double (*lbcostfunc) (struct as_coord,
+ struct as_coord,
+ s_char *),
+ double (*realcostfunc) (struct as_coord,
+ struct as_coord,
+ s_char *),
+ double (*seccostfunc) (struct as_coord,
+ struct as_coord,
+ s_char *),
+ s_char *userdata);
+extern int as_search(struct as_data *adp);
+extern void as_delete(struct as_data *adp);
+extern void as_reset(struct as_data *adp);
+extern void as_stats(struct as_data *adp, FILE * fp);
extern struct as_path *as_find_cachepath(coord fx,
- coord fy,
- coord tx,
- coord ty);
+ coord fy, coord tx, coord ty);
/* Functions that are "private" to algorithm */
extern void as_enable_cachepath();
extern void as_disable_cachepath();
-extern void as_makepath(struct as_data *adp);
-extern void as_free_path(struct as_path *pp);
-
-extern int as_costcomp(struct as_node **n1, struct as_node **n2);
-extern struct as_queue *as_extend(struct as_data *adp);
-extern struct as_queue *as_merge(struct as_data *adp,
- struct as_queue *head,
- struct as_node **neighbors);
-extern struct as_queue *as_iscinq(struct as_data *adp, struct as_coord c);
-extern void as_setcinq(struct as_data *adp,
- struct as_coord c, struct as_queue *qp);
-extern void as_free_hashtab(struct as_data *adp);
-extern int as_winnow(struct as_data *adp,
- struct as_coord *coords, int ncoords);
+extern void as_makepath(struct as_data *adp);
+extern void as_free_path(struct as_path *pp);
+
+extern int as_costcomp(struct as_node **n1, struct as_node **n2);
+extern struct as_queue *as_extend(struct as_data *adp);
+extern struct as_queue *as_merge(struct as_data *adp,
+ struct as_queue *head,
+ struct as_node **neighbors);
+extern struct as_queue *as_iscinq(struct as_data *adp, struct as_coord c);
+extern void as_setcinq(struct as_data *adp,
+ struct as_coord c, struct as_queue *qp);
+extern void as_free_hashtab(struct as_data *adp);
+extern int as_winnow(struct as_data *adp,
+ struct as_coord *coords, int ncoords);
projects / empserver / blobdiff