Changed A* exit condition, added 2 tests for it

A* now exits when next node from open set with least cost happens to be end_point,
not when node with least cost has end_point as a neigbour.

Added two tests for astar:
* ABC tests case where start and end node are
neigbours
* ABCX tests case with intermediate nodes

1 files changed, 5 insertions, 17 deletions

diff --git a/core/math/a_star.cpp b/core/math/a_star.cpp
index 021391da83..09472059b1 100644
--- a/core/math/a_star.cpp
+++ b/core/math/a_star.cpp
@@ -249,14 +249,9 @@ bool AStar::_solve(Point *begin_point, Point *end_point) {
 		n->distance = _compute_cost(begin_point->id, n->id) * n->weight_scale;
 		n->last_pass = pass;
 		open_list.add(&n->list);
-
-		if (end_point == n) {
-			found_route = true;
-			break;
-		}
 	}
 
-	while (!found_route) {
+	while (true) {
 
 		if (open_list.first() == NULL) {
 			// No path found
@@ -276,13 +271,16 @@ bool AStar::_solve(Point *begin_point, Point *end_point) {
 			cost += _estimate_cost(p->id, end_point->id);
 
 			if (cost < least_cost) {
-
 				least_cost_point = E;
 				least_cost = cost;
 			}
 		}
 
 		Point *p = least_cost_point->self();
+		if (p == end_point) {
+			found_route = true;
+			break;
+		}
 
 		for (Set<Point *>::Element *E = p->neighbours.front(); E; E = E->next()) {
 
@@ -294,7 +292,6 @@ bool AStar::_solve(Point *begin_point, Point *end_point) {
 				// Already visited, is this cheaper?
 
 				if (e->distance > distance) {
-
 					e->prev_point = p;
 					e->distance = distance;
 				}
@@ -305,18 +302,9 @@ bool AStar::_solve(Point *begin_point, Point *end_point) {
 				e->distance = distance;
 				e->last_pass = pass; // Mark as used
 				open_list.add(&e->list);
-
-				if (e == end_point) {
-					// End reached; stop algorithm
-					found_route = true;
-					break;
-				}
 			}
 		}
 
-		if (found_route)
-			break;
-
 		open_list.remove(least_cost_point);
 	}