Sorry if this is the wrong place to ask this, but because I'm asking how to approach a problem rather than how to solve it, I couldn't figure out where was most correct. I'm fairly new to Godot, so I'm not well-versed in its specifics.

I'm attempting to build an air traffic control simulation game, and am trying to figure out how to pathfind along dynamically loaded runways and taxiways. I threw together a quick proof of concept in pygame that reads a JSON list of line segments and constructs a net out of them for the airplanes navigation, but I was hoping to make use of Godot's built-in pathfinding. I also need to be able to specify the route taken - for example an airplane may taxi from A to D through either B or C - and this needs to be specified by the controller. Also, planes have a large turning radius and can't move backwards, so this needs to be considered as well.

So the main question: How can I pathfind dynamically loaded objects? I'll basically have a list of line segments and that's it - is there a way to get the planes to pathfind along this? Right now all my segments are just control nodes with custom draw functions, though this can be changed to suit the pathfinding method's requirements.

Thanks for any help!

  • xyz replied to this.

    Thanks for the reply!
    It looks like I'll need to build a net out of my line segments and collect a list of intersections between the taxiways, etc..., then feed those points into A*. Reading through the documentation, it doesn't appear as though there is a way to prefer a route including a given node - the player in the game needs to be able to prioritize some routes over others, irrespective of their distance. Is there a way to do this with A*? Even if it's just to return a list of possible paths sorted by length and then manually filter them based on including this node?

    • xyz replied to this.

      GrateJames When querying A* for a route, make multiple queries for each part of the route between mandatory points.
      Godot's A* is weighted so if a point is important you can set its weight to a high (low) value. You can also implement AStar*D:: _compute_cost() to interject the cost computation and add any additional logic there.

        Yes, in A* you can give each node a weight scale. The last time I wrote a bunch of A* code used weight scale heavily to make paths that made more sense: avoid for example terrain that has piles of debris. It is a great mental exercise to get it all up and running.

        "The weight_scale is multiplied by the result of _compute_cost() when determining the overall cost of traveling across a segment from a neighboring point to this point. Thus, all else being equal, the algorithm prefers points with lower weight_scales to form a path."

          Erich_L the godot pahtfinding is designed to work with navmesh. for something were you have a premade "structure", it is easier to just write a pathfinding algorithm in gdscript, like I did.

          this is one of the less specialized ones I made, you can customize a pathfinding algorithm to your needs very easily:

          extends Node

func find_shortest_path(closest_node : Vector2i, target : Vector2i) -> PackedVector2Array:
	var map_size_shift : Vector2i = Vector2i(TerrainMap.hmapsiz, TerrainMap.hmapsiz)#terrain.map_size/2)
	closest_node += map_size_shift
	target += map_size_shift
	var node_parents : Dictionary = Dictionary()
	var follow_path : PackedVector2Array = PackedVector2Array()
	var goal : Vector2i
	goal = find_path(closest_node, target, node_parents)
	
	if goal == closest_node:
		follow_path.append(closest_node - map_size_shift)
		print("failed find path")
		return follow_path
	
	var curr : Vector2i = goal
	while(curr != closest_node):
		follow_path.append(curr - map_size_shift)
		curr = node_parents.get(curr)
		#print("found path")
	return follow_path

var directions : Array[Vector2i] = [Vector2i.DOWN, Vector2i.LEFT, Vector2i.UP, Vector2i.RIGHT]

func sort_ascending(a, b) -> bool:
	if a[0] > b[0]:
		return true
	return false

func order_by_size(direc : Array[Vector2i], goal : Vector2i):
	#astar
	if direc:
		var distance : Array = []#Array()# : Array[float, Vector2i]
		#var positions : Array[Vector2i]
		for i : Vector2i in direc:
			distance.append([abs(goal - i).length(), i])
		distance.sort_custom(sort_ascending)
		direc.clear()
		for i in distance:
			direc.append(i[1])

func check_adjacents(pos : Vector2i) -> Array[Vector2i]:
	var arr : Array[Vector2i] = []
	if pos.x > 1 and pos.x < TerrainMap.map_size-1 and pos.y > 1 and pos.y < TerrainMap.map_size-1:
		for i : Vector2i in directions:
			var cpos : Vector2i = pos + i
			var direc : int = TerrainMap.Voxel_road[(cpos.y * TerrainMap.map_size) + cpos.x]
			if direc == 1:
				arr.append(cpos)
	return arr

func find_path(pos : Vector2i, goal : Vector2i, node_parents : Dictionary):
	var queue : Array[Vector2i] = []
	var exploredNodes : Dictionary = Dictionary()
	
	var curr_node : Vector2i
	
	queue.push_front(pos)
	while(queue.size() != 0):
		curr_node = queue.pop_front()
		if curr_node == goal:
			#reach destination
			return curr_node
		#terrain.Voxel_road[(goal.y * terrain.map_size) + goal.x]
		var neigh : Array[Vector2i] = check_adjacents(curr_node)
		#order by size
		order_by_size(neigh, goal)
		if neigh:
			for i : Vector2i in neigh:
				if exploredNodes.get(i, null) == null:
					exploredNodes[i] = true
					node_parents[i] = curr_node
					queue.push_front(i)
	return pos #no path found

          I think you have to replace check_adjacents with a way to find the nodes connected to the current node, and use your nodes instead of Vector2i, since mine was designed around tiles.

            I'll try a weighted A* first and see if that can meet my needs, and come back and update the thread if I have any problems. Thanks for all the advice!