AStar3D Returning the Wrong Path

Help Navigation
, ,
1

Godot Version

Godot 4.4 and Godot 4.5

Question

I am making a turn based tactical strategy game. I was working on implementing A* for 3D using the built in A* class. However even tho when i print the graph and its edges properly. it does not return the proper path. Sample project here. I am not sure if this is an issue with my logic or with the AStar3D class itself. Any help is greatly appreciated.

Code

This is the main code that handles finding the path I have it set as an autoload in my project

extends Node
## An auto load to allow the access to the [GridMap]
##
## from anywhere in the testing. It also is in charge of
## creating the [AStar3D] connecting edges and finding
## the path through the grid map.

var grid_map: GridMap
var astar: AStar3D
var dirs: Array[Vector3i] = [
	Vector3i(1, 0, 0),
	Vector3i(0, 0, 1),
	Vector3i(-1, 0, 0),
	Vector3i(0, 0, -1),
]


## Call this function in the main levels node. This assigns the
## [GridMap] and initializes the [AStar3D]
func setup(grid: GridMap):
	grid_map = grid
	print_grid_map()
	astar = AStar3D.new()
	create_vertices()
	connect_edges()
	print_astar_grid()
	assert(grid_map != null, "gridmap not set")


## Used to look at all the cell positions in the [GridMap]
func print_grid_map():
	print("-".repeat(60))
	print("Printing the GridMap")
	for cell in grid_map.get_used_cells():
		print(cell)


## Used to check all the nodes in the [AStar3D] and there edges.
func print_astar_grid():
	print("-".repeat(60))
	print("Printing the AStar3D Grid")
	var points = astar.get_point_count()
	print("Total Points: %d" % points)

	for point_id in astar.get_point_ids():
		var point_position = astar.get_point_position(point_id)
		print("Point ID: %d, Position: %s" % [point_id, point_position])
		var connected_points = astar.get_point_connections(point_id)
		print("   Connected to:")
		for p in connected_points:
			print("   Position: %s. ID %s"%[astar.get_point_position(p), p])


## Populates the [AStar3D] grid with the cells from the [GridMap].
func create_vertices():
	for cell in grid_map.get_used_cells():
		var cid = hash_cell(cell)
		astar.add_point(cid, cell)


## Used to connect the appropriate edges in the [AStar3D]
## based off the [GridMap].\
## Used to connect the appropriate edges in the [AStar3D]
## based off the [GridMap].
func connect_edges():
	var used_cells = grid_map.get_used_cells()

	for cell in used_cells:
		var cid = hash_cell(cell)

		for d in dirs:
			var n_cell = cell + d
			if used_cells.has(n_cell):  ## Check if the neighbor cell is in the used cells
				var nid = hash_cell(n_cell)

				## Ensure the points are not the same before connecting
				if cid != nid and not astar.are_points_connected(cid, nid):
					# Use grid distance for weight (always 1 for adjacent cells)
					print("Connected: %s -> %s" % [cell, n_cell])

					
## Used to convert a Vector3 cell into a hash
func hash_cell(cell: Vector3i):
	return cell.x * 10000 + cell.y * 20000 + cell.z


## Takes in gridmap coordinates and returns a path in the world space.
func find_path(start: Vector3i, end: Vector3i):
	print("Start %s, End %s"%[start, end])
	if start == null or end == null:
		print("WHY ARE THEY NULL")
	if grid_map == null:
		print("GridMap is Null")
	print("calling map to local in findPath")
	var sid = astar.get_closest_point(grid_map.map_to_local(start) * grid_map.cell_size)
	print("calling for end")
	var eid = astar.get_closest_point(grid_map.map_to_local(end) * grid_map.cell_size)
	print("done calling map to local in findPath")
	var p = astar.get_point_path(sid, eid)
	print("Raw Path %s"%p)
	print("Printing Path as Cells")
	for i in p:
		print(grid_map.local_to_map(i))
	
	return p

Console Output

Godot Engine v4.4.1.stable.official.49a5bc7b6 - https://godotengine.org
Vulkan 1.3.289 - Forward+ - Using Device #0: AMD - AMD Radeon Graphics (RADV RENOIR)

------------------------------------------------------------
Printing the GridMap
(0, 0, 0)
(0, 0, 1)
(0, 0, 2)
(1, 0, 0)
(1, 0, 1)
(1, 0, 2)
(2, 0, 0)
(2, 0, 1)
(2, 0, 2)
Connected: (0, 0, 0) -> (1, 0, 0)
Connected: (0, 0, 0) -> (0, 0, 1)
Connected: (0, 0, 1) -> (1, 0, 1)
Connected: (0, 0, 1) -> (0, 0, 2)
Connected: (0, 0, 1) -> (0, 0, 0)
Connected: (0, 0, 2) -> (1, 0, 2)
Connected: (0, 0, 2) -> (0, 0, 1)
Connected: (1, 0, 0) -> (2, 0, 0)
Connected: (1, 0, 0) -> (1, 0, 1)
Connected: (1, 0, 0) -> (0, 0, 0)
Connected: (1, 0, 1) -> (2, 0, 1)
Connected: (1, 0, 1) -> (1, 0, 2)
Connected: (1, 0, 1) -> (0, 0, 1)
Connected: (1, 0, 1) -> (1, 0, 0)
Connected: (1, 0, 2) -> (2, 0, 2)
Connected: (1, 0, 2) -> (0, 0, 2)
Connected: (1, 0, 2) -> (1, 0, 1)
Connected: (2, 0, 0) -> (2, 0, 1)
Connected: (2, 0, 0) -> (1, 0, 0)
Connected: (2, 0, 1) -> (2, 0, 2)
Connected: (2, 0, 1) -> (1, 0, 1)
Connected: (2, 0, 1) -> (2, 0, 0)
Connected: (2, 0, 2) -> (1, 0, 2)
Connected: (2, 0, 2) -> (2, 0, 1)
------------------------------------------------------------
Printing the AStar3D Grid
Total Points: 9
Point ID: 20000, Position: (2.0, 0.0, 0.0)
   Connected to:
Point ID: 10002, Position: (1.0, 0.0, 2.0)
   Connected to:
Point ID: 10001, Position: (1.0, 0.0, 1.0)
   Connected to:
Point ID: 2, Position: (0.0, 0.0, 2.0)
   Connected to:
Point ID: 0, Position: (0.0, 0.0, 0.0)
   Connected to:
Point ID: 20002, Position: (2.0, 0.0, 2.0)
   Connected to:
Point ID: 10000, Position: (1.0, 0.0, 0.0)
   Connected to:
Point ID: 1, Position: (0.0, 0.0, 1.0)
   Connected to:
Point ID: 20001, Position: (2.0, 0.0, 1.0)
   Connected to:
Start (0, 0, 0), End (0, 0, 2)
calling map to local in findPath
calling for end
done calling map to local in findPath
Raw Path [(2.0, 0.0, 2.0)]
Printing Path as Cells
(1, 0, 1)
2

I fixed some issues in the code I had. I still havent gotten it to work right but I made progress. If i fix it I will upload my code and close the issue

3

Solution

So I was able to fix my issue I think it was how I was passing Vector3 and Vector3i’s between the methods. My current code which is far from perfect is

Code

extends Node
## An auto load to allow the access to the [GridMap]
##
## from anywhere in the testing. It also is in charge of
## creating the [AStar3D] connecting edges and finding
## the path through the grid map.

var grid_map: GridMap # The Grid map to give to [AStar3D]
var astar: AStar3D
var dirs: Array[Vector3i] = [
	Vector3i(1, 0, 0),
	Vector3i(0, 0, 1),
	Vector3i(-1, 0, 0),
	Vector3i(0, 0, -1),
]


## Give the [GridMap] node a script and in its [method Node._ready] function call this function.
## This assigns the [GridMap] and initializes the [AStar3D]
func setup(grid: GridMap) -> void:
	grid_map = grid
	print_grid_map()
	astar = AStar3D.new()
	create_vertices()
	connect_edges()
	print_astar_grid()
	assert(grid_map != null, "gridmap not set")


## Takes in gridmap coordinates and returns a path in the world space.
func find_path(start: Vector3i, end: Vector3i) -> PackedVector3Array:	
	#TODO: ADD ERROR CHECKS
	
	var sid: int = hash_cell(start)
	var eid: int = hash_cell(end)
	
	if not astar.has_point(sid):
		print("START POINT DOES NOT EXIST")
	if not astar.has_point(eid):
		print("END POINT DOES NOT EXIST")
		
	var p: PackedVector3Array = astar.get_point_path(sid, eid)
	
	# Debugging
	print("-".repeat(20) + "Find Path" + "-".repeat(20))
	print("Start Local: %s, End Local:  %s"%[start, end])
	print("Start Cell: %s, End Cell: %s"%[GridmapManager.grid_map.local_to_map(start),
		GridmapManager.grid_map.local_to_map(end)])
	
	print("Printing path as Locals")
	print(p)
	print("Printing Path as Cells")
	for i in p:
		print(grid_map.local_to_map(i))
	
	return p


#region Initalizing ----------------------------------------
## Populates the [AStar3D] grid with the cells from the [GridMap].
func create_vertices() -> void:
	print("-".repeat(20) + "Create Vertices" + "-".repeat(20))
	for cell in grid_map.get_used_cells():
		var cid: int = hash_cell(cell)
		var wp: Vector3 = grid_map.map_to_local(cell)
		print("Adding ID %s, Point %s"%[cid, wp])
		astar.add_point(cid, wp)


## Used to connect the appropriate edges in the [AStar3D]
## based off the [GridMap].
func connect_edges() -> void:
	print("-".repeat(20) + "Connect Edges" + "-".repeat(20))
	var used_cells: Array[Vector3i] = grid_map.get_used_cells()
	for cell in used_cells:
		var cid: int = hash_cell(cell)
		for d in dirs:
			var n_cell: Vector3i = cell + d
			# This check is slow optimize it.
			if used_cells.has(n_cell): # makes sure a start has the neighbor in memory.
				var nid: int = hash_cell(n_cell)
				# Ensure the points are not the same before connecting
				# else it will push a warning.
				if cid != nid and not astar.are_points_connected(cid, nid):
					# Use grid distance for weight (always 1 for adjacent cells)
					print("Connected: %s -> %s" % [cell, n_cell])
					astar.connect_points(cid, nid)


#endregion -------------------------------------------------

#region Helpers --------------------------------------------
## Used to convert a Vector3 cell into a hash
func hash_cell(cell: Vector3i) -> int:
	return cell.x * 10000 + cell.y * 20000 + cell.z

#endregion -------------------------------------------------

#region Debug ----------------------------------------------
## Used to look at all the cell positions in the [GridMap]
func print_grid_map() -> void:
	print("-".repeat(60))
	print("Printing the GridMap")
	for cell in grid_map.get_used_cells():
		print(cell)


## Used to check all the nodes in the [AStar3D] and there edges.
func print_astar_grid() -> void:
	print("-".repeat(60))
	print("Printing the AStar3D Grid")
	var points = astar.get_point_count()
	print("Total Points: %d" % points)

	for point_id in astar.get_point_ids():
		var point_position = astar.get_point_position(point_id)
		print("Point ID: %d, Position: %s" % [point_id, GridmapManager.grid_map.local_to_map(point_position)])
		var connected_points = astar.get_point_connections(point_id)
		print("   Connected to:")
		for p in connected_points:
			print("   Position: %s. ID %s"%[
				GridmapManager.grid_map.local_to_map(
					astar.get_point_position(p)
				), p]
			)

#endregion -------------------------------------------------
4

This topic was automatically closed 30 days after the last reply. New replies are no longer allowed.