add polar coordinate calculation

[hexagon] / astar.c

diff --git a/astar.c b/astar.c
index 107a9869ec38505cf40605f0318affbdfc0812a9..fd92bfcc8ddc24f611ff3d7b71980a119fead6c4 100644 (file)
--- a/astar.c
+++ b/astar.c
@@ -31,7 +31,6 @@ struct HL_astar *HL_astar_init(struct HL_astar *state) {
                if (!state) return NULL;
                state->malloced = 1;
        }
-       state->sets = 0;
        state->open = 0;
        state->closed = 0;
        state->nodes = 0;
@@ -49,11 +48,21 @@ struct HL_astar *HL_astar_init(struct HL_astar *state) {
 }
 
 /*
- * Reset a state to enpty.  Doesn't free memory, so it
- * can be reused.
+ * Reset a state to enpty.
  */
 struct HL_astar *HL_astar_clear(struct HL_astar *s) {
+       struct HL_astar_hex *hex;
        if (!s) return NULL;
+       while (s->open) {
+               hex = s->open->next;
+               free(s->open);
+               s->open = hex;
+       }
+       while (s->closed) {
+               hex = s->closed->next;
+               free(s->closed);
+               s->closed = hex;
+       }
 
        s->open = 0;
        s->closed = 0;
@@ -64,7 +73,19 @@ struct HL_astar *HL_astar_clear(struct HL_astar *s) {
 }
 
 void HL_astar_free(struct HL_astar *s) {
-       free(s->sets);
+       struct HL_astar_hex *hex;
+       /* free open and closed lists */
+       while (s->open) {
+               hex = s->open->next;
+               free(s->open);
+               s->open = hex;
+       }
+       while (s->closed) {
+               hex = s->closed->next;
+               free(s->closed);
+               s->closed = hex;
+       }
+
        if (s->malloced) {
                free(s);
        }
@@ -72,29 +93,26 @@ void HL_astar_free(struct HL_astar *s) {
 
 static struct HL_astar_hex *add_open(struct HL_astar *s, int hex) {
        struct HL_astar_hex *node;
+#ifdef DEBUG_ASTAR
+               fprintf(stderr, "add to open %d\n", hex);
+#endif
 
-       if (!s || s->error) return NULL;
-
-       /* TODO check in open or closed */
+       if (!s || s->error) {
+#ifdef DEBUG_ASTAR
+               fprintf(stderr, "returning null\n");
+#endif
 
-       if (s->nodes == s->allocated) {
-               int newalloc;
-               struct HL_astar_hex *alloc;
-               if (s->allocated) {
-                       newalloc = s->allocated * 2;
-               } else {
-                       newalloc = 16;
-               }
-               alloc = realloc(s->sets, newalloc * sizeof *node);
-               if (!alloc) {
-                       s->error = 1;
-                       return NULL;
-               }
-               s->sets = alloc;
-               s->allocated = newalloc;
+               return NULL;
        }
+#ifdef DEBUG_ASTAR
+               fprintf(stderr, "mallocing node(%zd)\n", sizeof *node);
+#endif
 
-       node = &s->sets[s->nodes++];
+       /* TODO check in open or closed */
+       node = malloc(sizeof *node);
+#ifdef DEBUG_ASTAR
+               fprintf(stderr, "add to open %d = %p\n", hex, node);
+#endif
 
        node->hex = hex;
        node->g = 0.0;
@@ -102,7 +120,9 @@ static struct HL_astar_hex *add_open(struct HL_astar *s, int hex) {
        node->h = 0.0;
        node->open = 1;
        node->parent = 0;
-       if (s->open) s->open->prev = node;
+       if (s->open) {
+               s->open->prev = node;
+       }
        node->next = s->open;
        node->prev = NULL;
        s->open = node;
@@ -168,7 +188,7 @@ static struct HL_astar_hex *lowrank(struct HL_astar *s) {
 }
 
 #ifdef DEBUG_ASTAR
-void dump_list(char *name, HL_astar_hex *x) {
+void dump_list(char *name, struct HL_astar_hex *x) {
        fprintf(stderr, "%s list: ", name);
        for(; x; x = x->next) {
                fprintf(stderr, "(%d,%d)",  HL_cantor_x(x->hex), HL_cantor_y(x->hex));
@@ -221,15 +241,23 @@ int HL_findpath(struct HL_astar *s, int loops) {
                        break;
                }
                closehex(s, x);
+
                for (dir = 0; y = s->neighbor(x->hex, dir),dir<6; dir++) {
                        if (y == 0) continue; /* no hex in that direction */
                        if (in_closed(s, y)) {
                                continue;
                        }
+#ifdef DEBUG_ASTAR
+                       fprintf(stderr, "checking dir %d, hex (%d, %d)\n", dir,
+                                       HL_cantor_x(y), HL_cantor_y(y));
+#endif
 
                        cost = x->g + s->metric(x->hex, y);
 
                        yopen = in_open(s, y);
+#ifdef DEBUG_ASTAR
+                       fprintf(stderr, "checking inopen = %p\n", yopen);
+#endif
                        if (!yopen) {
                                yopen = add_open(s, y);
                                tent_better = 1;
@@ -258,6 +286,7 @@ int HL_findpath(struct HL_astar *s, int loops) {
 #endif
                        }
                }
+
        }
 
        /* error no path ? */