Skip to content

Instantly share code, notes, and snippets.

@goblinJoel
Last active May 21, 2022 00:06
Show Gist options
  • Save goblinJoel/6f1658e4e9595aa0e075084c6ded1e9a to your computer and use it in GitHub Desktop.
Save goblinJoel/6f1658e4e9595aa0e075084c6ded1e9a to your computer and use it in GitHub Desktop.
Customized Godot Dijkstra map showing input_is_destination not affecting paths or directions
extends TileMap
var dijkstramap: DijkstraMap
var id_to_pos: Dictionary = {}
var pos_to_id: Dictionary = {}
var tile_draw: int = 0
var terrain_weights: Dictionary = {0: 1.0, 1: 4.0, 2: INF, 3: 1.0}
var dragging: bool = false
func _ready() -> void:
var event: InputEventMouseButton = InputEventMouseButton.new()
event.button_index = BUTTON_LEFT
InputMap.add_action("left_mouse_button")
InputMap.action_add_event("left_mouse_button", event)
dijkstramap = DijkstraMap.new()
var bmp: Rect2 = Rect2(0, 0, 23, 19)
pos_to_id = dijkstramap.add_square_grid(bmp)
for pos in pos_to_id:
id_to_pos[pos_to_id[pos]] = pos
# custom test: how do 1-directional weights work?
# make 8 more spaces in the bottom-right
var next_id = pos_to_id[Vector2(22, 18)] + 1
print("adding new points starting with id " + str(next_id))
var next_pos := Vector2(23, 15)
dijkstramap.add_point(next_id, 0)
pos_to_id[next_pos] = next_id
id_to_pos[next_id] = next_pos
next_id += 1
next_pos += Vector2.DOWN
dijkstramap.add_point(next_id, 0)
pos_to_id[next_pos] = next_id
id_to_pos[next_id] = next_pos
next_id += 1
next_pos += Vector2.DOWN
dijkstramap.add_point(next_id, 0)
pos_to_id[next_pos] = next_id
id_to_pos[next_id] = next_pos
next_id += 1
next_pos += Vector2.DOWN
dijkstramap.add_point(next_id, 0)
pos_to_id[next_pos] = next_id
id_to_pos[next_id] = next_pos
next_id += 1
next_pos += Vector2(1, -3)
dijkstramap.add_point(next_id, 0)
pos_to_id[next_pos] = next_id
id_to_pos[next_id] = next_pos
next_id += 1
next_pos += Vector2.DOWN
dijkstramap.add_point(next_id, 0)
pos_to_id[next_pos] = next_id
id_to_pos[next_id] = next_pos
next_id += 1
next_pos += Vector2.DOWN
dijkstramap.add_point(next_id, 0)
pos_to_id[next_pos] = next_id
id_to_pos[next_id] = next_pos
next_id += 1
next_pos += Vector2.DOWN
dijkstramap.add_point(next_id, 0)
pos_to_id[next_pos] = next_id
id_to_pos[next_id] = next_pos
# then connect them so going right to the 1st column weighs 2, and the rest are 1
# (don't bother doing up-down connections)
# Note: terrain weight is averaged between from and to, then multiplied by
# the connection weight. So, from t4 via c1 to t4 costs 4, t1 via c2 to t4
# costs 5, and t4 via c1 to t1 costs 2.5. Formula: (t'+t")/2 * c
# Thus, entering and leaving slow terrain both get half penalty.
# See https://github.com/MatejSloboda/Dijkstra_map_for_Godot
# If input_is_destination, 1-directional weights use the weight moving toward
# the origin(s). Else, they use weight moving from the origin(s).
for i in range(15, 19):
var from = pos_to_id[Vector2(22, i)]
var to = pos_to_id[Vector2(23, i)]
print("connecting " + str(from) + " to " + str(to))
dijkstramap.connect_points(from, to, 2.0, false)
dijkstramap.connect_points(to, from, 1.0, false)
from = to
to = pos_to_id[Vector2(24, i)]
print("connecting " + str(from) + " to " + str(to))
dijkstramap.connect_points(from, to, 1.0, false)
dijkstramap.connect_points(to, from, 1.0, false)
update_terrain_ids()
recalculate()
func recalculate() -> void:
var targets: Array = get_used_cells_by_id(3)
var target_ids: Array = []
for pos in targets:
target_ids.push_back(pos_to_id[pos])
var input_is_destination = true
dijkstramap.recalculate(target_ids, {"terrain_weights": terrain_weights, "input_is_destination": input_is_destination})
print("recalculated with input_is_destination=" + str(input_is_destination))
# custom tests: check costs to / dirs from 2nd row of extra test cells
var test_a = pos_to_id[Vector2(23, 16)]
var test_b = pos_to_id[Vector2(24, 16)]
print("testing points A: %s and B: %s" % [ id_to_pos[test_a], id_to_pos[test_b] ])
# Visualize
var costs: Dictionary = dijkstramap.get_cost_map()
# these costs change (correctly) with input_is_destination
print("costs of point A: %s and B: %s" % [costs[test_a], costs[test_b]])
var costgrid: TileMap = get_node("costs")
costgrid.clear()
for id in costs.keys():
var cost: int = int(costs[id])
cost = min(32, max(0, cost))
costgrid.set_cell(
id_to_pos[id].x, id_to_pos[id].y, 0, false, false, false, Vector2(cost, 0)
)
var dir_to_tile: Dictionary = {
Vector2(1, 0): 0,
Vector2(1, -1): 1,
Vector2(0, 1): 2,
Vector2(1, 1): 3,
Vector2(-1, 0): 4,
Vector2(-1, 1): 5,
Vector2(0, -1): 6,
Vector2(-1, -1): 7
}
var dir_ids: Dictionary = dijkstramap.get_direction_map()
# these directions do not change with input_is_destination (but they should?)
print("direction map at point A: %s and B: %s" % [ id_to_pos[dir_ids[test_a]], id_to_pos[dir_ids[test_b]] ])
print("direction at A: %s" % id_to_pos[dijkstramap.get_direction_at_point(test_a)])
print("direction at B: %s" % id_to_pos[dijkstramap.get_direction_at_point(test_b)])
print("shortest path from A: %s" % dijkstramap.get_shortest_path_from_point(test_a))
print("shortest path from B: %s" % dijkstramap.get_shortest_path_from_point(test_b))
var dirgrid: TileMap = get_node("directions")
dirgrid.clear()
for id1 in dir_ids.keys():
var pos: Vector2 = id_to_pos[id1]
var vec: Vector2 = id_to_pos.get(dir_ids[id1], Vector2(NAN, NAN)) - pos
var tile: float = dir_to_tile.get(vec, NAN)
if not (is_nan(tile)):
dirgrid.set_cell(pos.x, pos.y, 1, false, false, false, Vector2(tile, 0))
func update_terrain_ids() -> void:
for id in id_to_pos.keys():
var pos: Vector2 = id_to_pos[id]
dijkstramap.set_terrain_for_point(id, self.get_cellv(pos))
func _on_terrain_selection_item_selected(index: int) -> void:
tile_draw = index
func _unhandled_input(event: InputEvent) -> void:
if event.is_action_pressed("left_mouse_button"):
dragging = true
if event.is_action_released("left_mouse_button"):
dragging = false
if (event is InputEventMouseMotion or event is InputEventMouseButton) and dragging:
var pos: Vector2 = get_local_mouse_position()
var cell: Vector2 = world_to_map(pos)
# custom test: edited to extend x-width
if cell.x >= 0 and cell.x < 25 and cell.y >= 0 and cell.y < 19:
self.set_cellv(cell, tile_draw)
dijkstramap.set_terrain_for_point(pos_to_id[cell], tile_draw)
recalculate()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment