Index: trunk/src_plugins/acompnet/meshgraph.c
===================================================================
--- trunk/src_plugins/acompnet/meshgraph.c	(revision 22964)
+++ trunk/src_plugins/acompnet/meshgraph.c	(revision 22965)
@@ -28,8 +28,10 @@
 #include <stdlib.h>
 #include <genht/hash.h>
 #include "meshgraph.h"
+#include "error.h"
 
 #define INF_SCORE 9000000000.0
+#define SEARCHR PCB_MM_TO_COORD(25)
 
 void pcb_msgr_init(pcb_meshgraph_t *gr)
 {
@@ -53,10 +55,81 @@
 	return nd->id;
 }
 
+static double msgr_connect(pcb_meshnode_t *curr, pcb_meshnode_t *next)
+{
+	return curr->gscore + pcb_distance(curr->bbox.X1, curr->bbox.Y1, next->bbox.X1, next->bbox.Y1);
+}
 
-void pcb_msgr_astar(pcb_meshgraph_t *gr, long int startid, long int endid)
+static double msgr_heurist(pcb_meshnode_t *curr, pcb_meshnode_t *end)
 {
+	return pcb_distance(curr->bbox.X1, curr->bbox.Y1, end->bbox.X1, end->bbox.Y1);
+}
 
+int pcb_msgr_astar(pcb_meshgraph_t *gr, long int startid, long int endid)
+{
+	htip_t closed, open;
+	htip_entry_t *e;
+	pcb_meshnode_t *curr, *next, *end;
+
+	curr = htip_get(&gr->id2node, startid);
+	if (curr == NULL)
+		return -1;
+
+	end = htip_get(&gr->id2node, endid);
+	if (end == NULL)
+		return -1;
+
+	htip_init(&closed, longhash, longkeyeq);
+	htip_init(&open, longhash, longkeyeq);
+
+	htip_set(&open, startid, curr);
+	for(;;) {
+		pcb_rtree_box_t sb;
+		pcb_box_t *b;
+		pcb_rtree_it_t it;
+		double tentative_g;
+
+TODO("should pick the one with the lowest fscore")
+		/* get the best looking item from the open list */
+		e = htip_first(&open);
+		if (e == NULL) {
+pcb_trace("NO PATH\n");
+			return 0;
+		}
+		curr = e->value;
+		htip_delentry(&open, e);
+		if (curr->id == endid) {
+pcb_trace("found path\n");
+			return 1;
+		}
+		htip_set(&closed, curr->id, curr);
+pcb_trace("first: %ld\n", curr->id);
+
+		/* search potential neighbors */
+		sb.x1 = curr->bbox.X1 - SEARCHR;
+		sb.x2 = curr->bbox.X2 + SEARCHR;
+		sb.y1 = curr->bbox.Y1 - SEARCHR;
+		sb.y2 = curr->bbox.Y2 + SEARCHR;
+		for(b = pcb_rtree_first(&it, &gr->ntree, &sb); b != NULL; b = pcb_rtree_next(&it)) {
+			next = (pcb_meshnode_t *)b;
+			if (htip_get(&closed, next->id) != NULL)
+				continue;
+
+			tentative_g = msgr_connect(curr, next);
+			if (tentative_g < 0)
+				continue;
+
+			if (htip_get(&open, next->id) == NULL) /* not in open */
+				htip_set(&open, next->id, next);
+			else if (tentative_g > next->gscore)
+				continue;
+
+pcb_trace("add:   %ld\n", next->id);
+			next->came_from = curr->id;
+			next->gscore = tentative_g;
+			next->fscore = msgr_heurist(curr, end);
+		}
+	}
 }
 
 
Index: trunk/src_plugins/acompnet/meshgraph.h
===================================================================
--- trunk/src_plugins/acompnet/meshgraph.h	(revision 22964)
+++ trunk/src_plugins/acompnet/meshgraph.h	(revision 22965)
@@ -20,6 +20,6 @@
 
 void pcb_msgr_init(pcb_meshgraph_t *gr);
 long int pcb_msgr_add_node(pcb_meshgraph_t *gr, pcb_box_t *bbox);
-void pcb_msgr_astar(pcb_meshgraph_t *gr, long int startid, long int endid);
+int pcb_msgr_astar(pcb_meshgraph_t *gr, long int startid, long int endid);
 
 #endif