implement shortest path

6 files changed, 65 insertions, 2 deletions

diff --git a/Hex.gd b/Hex.gd
index 57a1a19..32e4083 100644
--- a/Hex.gd
+++ b/Hex.gd
@@ -59,3 +59,7 @@ func show_los(b) -> void:
 func show_move(b) -> void:
 	if 6 < get_child_count():
 		enable_overlay(6, b)
+
+func show_short(b) -> void:
+	if 7 < get_child_count():
+		enable_overlay(7, b)
diff --git a/HexBoard.gd b/HexBoard.gd
index b4bf01c..b28a2b7 100644
--- a/HexBoard.gd
+++ b/HexBoard.gd
@@ -405,3 +405,55 @@ func possible_moves(piece : Piece, from : Tile, tiles : Array) -> int:
 				dst.road_march = rm
 				stack.push_back(dst)
 	return tiles.size()
+
+func shortest_path(piece : Piece, from : Tile,  to : Tile, tiles : Array) -> int:
+	tiles.clear()
+	search_count += 1
+	from.acc = 0
+	from.parent = null
+	from.search_count = search_count
+	if from == to or not is_on_map(from.coords) or not is_on_map(to.coords): return tiles.size()
+	var road_march_bonus : int = piece.road_march_bonus()
+	from.road_march = road_march_bonus > 0
+	stack.push_back(from)
+	while(not stack.empty()):
+		var src : Tile = stack.pop_back()
+		if (src == to): break
+		# warning-ignore:return_value_discarded
+		build_adjacents(src.coords)
+		for dst in adjacents:
+			if not dst.on_board: continue
+			var o : int = to_orientation(angle(src, dst))
+			var cost : int = piece.move_cost(src, dst, o)
+			if (cost == -1): continue # impracticable
+			cost += src.acc
+			var total : float  = cost + distance(dst.coords, to.coords)
+			var rm : bool = src.road_march and src.has_road(o)
+			if rm: total -= road_march_bonus
+			var add : bool = false
+			if dst.search_count != search_count:
+				dst.search_count = search_count
+				add = true
+			elif dst.f > total or (rm and not dst.road_march and abs(dst.f - total) < 0.001):
+				stack.erase(dst)
+				add = true
+			if add:
+				dst.acc = cost
+				dst.f = total
+				dst.road_march = rm
+				dst.parent = src
+				var idx : int = IMAX
+				for k in range(stack.size()):
+					if stack[k].f <= dst.f:
+						idx = k
+						break
+				if idx == IMAX: stack.push_back(dst)
+				else: stack.insert(idx, dst)
+	stack.clear()
+	if to.search_count == search_count:
+		var t : Tile = to
+		while t != from:
+			tiles.push_front(t)
+			t = t.parent
+		tiles.push_front(from)
+	return tiles.size()
diff --git a/Map.gd b/Map.gd
index 1eda9e8..eb0c056 100644
--- a/Map.gd
+++ b/Map.gd
@@ -8,6 +8,7 @@ const MAPV : String = "res://assets/map-v.png"
 const BLOCK : String = "res://assets/block.png"
 const BLACK : String = "res://assets/black.png"
 const MOVE : String = "res://assets/move.png"
+const SHORT : String = "res://assets/short.png"
 const GREEN : String = "res://assets/green.png"
 const TREE : String = "res://assets/tree.png"
 const CITY : String = "res://assets/city.png"
@@ -23,6 +24,7 @@ var p0 : Vector2
 var p1 : Vector2
 var los : Array
 var move : Array
+var short : Array
 var unit : Unit
 var show_los : bool
 var show_move : bool
@@ -45,7 +47,7 @@ func get_tile(coords : Vector2, k : int) -> Tile:
 	var hex : Hex = Hex.new()
 	hex.roads = get_road(k)
 	hex.rotation_degrees = hex_rotation
-	hex.configure(board.center_of(coords), coords, [GREEN, BLACK, CITY, TREE, MOUNT, BLOCK, MOVE])
+	hex.configure(board.center_of(coords), coords, [GREEN, BLACK, CITY, TREE, MOUNT, BLOCK, MOVE, SHORT])
 	hexes[k] = hex
 	$Hexes.add_child(hex)
 	return hex
@@ -142,7 +144,11 @@ func update() -> void:
 		$Los.setup($Tank.position, $Target.position, ct)
 		for hex in los: hex.show_los(true)
 	for hex in move: hex.show_move(false)
+	for hex in short: hex.show_short(false)
 	if show_move:
 		# warning-ignore:return_value_discarded
 		board.possible_moves(unit, board.get_tile(p0), move)
+		# warning-ignore:return_value_discarded
+		board.shortest_path(unit, board.get_tile(p0), board.get_tile(p1), short)
 		for hex in move: hex.show_move(true)
+		for i in range(1, short.size() -1): short[i].show_short(true)
diff --git a/README.md b/README.md
index 129bdc6..b05f144 100644
--- a/README.md
+++ b/README.md
@@ -13,7 +13,7 @@ base map made with [gimp](https://www.gimp.org) and my plugin [hexmap](https://g
     - [x] Adjacents
     - [x] 3D Line Of Sight
     - [x] Reachable Tiles ::: BFS
-    - [ ] Shortest Path ::: A*
+    - [x] Shortest Path ::: A*
     - [ ] Range Of Influence (LOS - Fire Power)
     - [ ] Battle lines (Kruskal + farthest apart units are the flank units)
 
diff --git a/Tile.gd b/Tile.gd
index 5127058..0aaa0de 100644
--- a/Tile.gd
+++ b/Tile.gd
@@ -8,6 +8,7 @@ var blocked : bool
 var on_board : bool = false
 
 var acc : int
+var f : float
 var parent : Tile
 var road_march : bool
 var search_count : int
diff --git a/assets/short.png b/assets/short.png
new file mode 100644
index 0000000..cb91627
--- /dev/null
+++ b/assets/short.png