diff options
| -rw-r--r-- | Hex.gd | 4 | ||||
| -rw-r--r-- | HexBoard.gd | 52 | ||||
| -rw-r--r-- | Map.gd | 8 | ||||
| -rw-r--r-- | README.md | 2 | ||||
| -rw-r--r-- | Tile.gd | 1 | ||||
| -rw-r--r-- | assets/short.png | bin | 0 -> 1188 bytes |
6 files changed, 65 insertions, 2 deletions
@@ -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() @@ -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) @@ -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) @@ -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 Binary files differnew file mode 100644 index 0000000..cb91627 --- /dev/null +++ b/assets/short.png |
