From: Nathan Wagner <nw@hydaspes.if.org>
Date: Thu, 25 Nov 2010 11:25:58 +0000 (+0000)
Subject: Implemented A-star path finding.
X-Git-Url: https://pd.if.org/git/?p=hexagon;a=commitdiff_plain;h=67fdcec57ab31e7a972ed624ab5f6df866313206

Implemented A-star path finding.
---

diff --git a/t/astar.c b/t/astar.c
new file mode 100644
index 0000000..bab342d
--- /dev/null
+++ b/t/astar.c
@@ -0,0 +1,53 @@
+#include <stdio.h>
+
+#include "hexmap.h"
+
+#include "tap.h"
+
+void pcheck(struct HL_astar *p, int x1, int y1, int x2, int y2, int expect) {
+	int from, to, dist;
+
+	from = HL_cantor_xy(x1,y1);
+	to = HL_cantor_xy(x2,y2);
+
+	HL_astar_init(p);
+
+	p->start = from;
+	p->goal = to;
+
+	dist = HL_findpath(p,0);
+	ok(p->error == 0, "found path from (%02d, %02d) to (%02d, %02d) with no error",
+		x1, y1, x2, y2);
+	ok(dist == expect,
+			"found path from (%02d, %02d) to (%02d, %02d) path length = %d (expect %d)\n",
+		x1, y1, x2, y2, dist, expect);
+}
+
+int main(void) {
+	struct HL_astar *p;
+	int length;
+
+	plan_tests(15);
+
+	p = HL_astar_init(0);
+	ok(p != NULL, "allocated astar struct");
+	ok(p->malloced == 1, "allocated astar sets malloced");
+	ok(p->open == NULL, "initial open list empty");
+	ok(p->closed == NULL, "initial closed list empty");
+
+	p->start = HL_cantor_xy(1, 1);
+	p->goal = HL_cantor_xy(1, 2);
+	
+	length = HL_findpath(p, 0);
+	ok(p->error == 0, "path finding returns no error");
+
+	pcheck(p, 1,1, 1,3, 2);
+	pcheck(p, 1,1, 2,1, 1);
+	pcheck(p, 1,1, 2,2, 2);
+	pcheck(p, 1,1, 3,1, 2);
+	pcheck(p, 1,1, 4,7, 8);
+
+	HL_astar_free(p);
+
+	return exit_status();
+}