• Andrew Jonhardt

I tried custom A* (or Astar) pathfinding in Godot

For almost a month of weekends (and some weekdays) I've been chipping away at the problem of how to get pathfinding working in Mask of Undying. I tried the Astar2D node built into Godot, a custom A* solution, and eventually remembered Navigation2D exists and gave it shot.


I'll cover my experience with the Astar2D node briefly: I'm not a fan. The level of information in the wild at the moment only seems to be enough for experts to figure it out. It was literally easier for me to drop the Astar2D node entirely and make a custom solution than attempt to customize Astar2D to my needs.


The Astar2D node must be created in code:

onready var astar = AStar2D.new()

Each Astar2D node that is created is supposed to be tied to 1 object in a scene. At least, this Reddit post claims as much, and I can't figure out how to effectively pass a created Astar2D node, or an Astar2D map, to other scripts and objects.


It might be performant to have a dozen enemies mapping out the same terrain at the same time so long as you use the Astar2D node in Godot, but I don't even wanna go there.


With Astar2D abandoned, I moved on to referencing A* implementations in Python to see if I could convert something to Godot's GDScript. Turns out, there's 2 major issues with attempting to move between base Python and the Python-inspired GDscript for A*:

  1. Python's massive module library: Most of the Python A* scripts I found make use of 3rd-party math or graphing modules. Python modules can't be imported into GDscript by default. This muddies or adds rabbit-holes to the process of figuring out how a particular script works.

  2. Linked Lists: If you don't know what the hell a Linked List is, you're as new as I was a few weeks ago. I only know what a Linked List looks like thanks to Harvard's free CS50 course on edx.org (online learning is awesome!). I don't understand Linked Lists effectively enough to use them in Godot yet, though, so my script is an attempt to work around what is apparently a typical implementation.


For more reading on linked lists and A*, here's a Gamasutra article:

https://www.gamasutra.com/view/feature/131505/toward_more_realistic_pathfinding.php

This mostly-working implementation of A* was built when I was in the midst of getting sick of it, so I was simply importing all of my test objects into 1 script:

extends Node2D

onready var tilemap = $BlueTiles
onready var seeker = $Seeker
onready var target = $Target

We've got a tilemap (which may be easily generated using Tilesetter or combining a few squares in GIMP or something), a "seeker" to do the pathfinding and a target for the pathfinding. Easy enough so far.


Now, the global variables:

var path = []
var g = 0

var timer = 0
var timer_max = 100

path and the timer variables should be clear enough (I'm storing a path and making a simple timer in code later on). But, what's g?


One of the hardest parts of implementing A*, for me, was understanding the formula behind it. This is the most descriptive version of the formula I've seen:

f(n) = g(n) + h(n)

n = a node, typically one near the starting position (the seeker, in this case) or a node in the path or near the path to the target position.

g = cost, so far, to reach node n.

h = estimated cost from n to goal.

f = total estimated cost from node n to goal.


h was actually the easiest to find:

func heuristic(a,b): 
#apparently, this is taxicab geometry/Manhattan distance
	#finds h(euristic) using (x1,y1) = a & (x2,y2) = b
	return abs(a.x - b.x) + abs(a.y - b.y)

There's another way to calculate h I think, but I saw this taxicab formula pop up the most so it's the one I went with. I don't fully understand the math.


Through trial and error, it seems that the best place to declare g is outside my other functions, so I put it with my global variables at the top of my script.


Now, here's my A* function:

func a_star(start_tile,end_tile,map=[]):
	var star_path = []
	var tile_size = 32
	var dir = [Vector2(-tile_size,0),
				Vector2(0,-tile_size),
				Vector2(tile_size,0),
				Vector2(0,tile_size)]
	g +=1 #increase g outside while loop for clarity
	var w_count = 0
	var w_max = 50
	while w_count < w_max: 
		var lowest_check = 1000
		var lowest_val = Vector2()
		var temp_path = {}
		w_count += 1
		for move_dir in dir.size(): 
		#start with the number of dir to reduce runtime
			for pos in map.size(): 
			#start search through map
				if start_tile.distance_to(map[pos]) <= tile_size:
				#compares player tile to map tiles
					var h = heuristic(end_tile,map[pos])
					var f = g+h
					temp_path[f] = map[pos]
		for opt in temp_path.keys():
			if opt < lowest_check:
				lowest_check = opt
				lowest_val = temp_path[opt]
		if start_tile != lowest_val:
			start_tile = lowest_val
			path.push_back(lowest_val)
		elif w_count >= w_max: 
			print("Pathing fail!")
			return star_path
		elif lowest_val.distance_to(end_tile) <= 64:
			print("Complete?")
			return star_path

The above script steps through a number of tiles in my tilemap from a starting position until it reaches the end position or exceeds a search-allotment variable. It took me a loooonnnngggg time, and it's still not perfect. Seriously, if you see the error, you get a digital cookie. Let's walk through it:

  • The function expects to be provided a start position, an ending position, and a map of coordinates as an array.

  • There's a path variable local to the function, called star_path, that I use to return a path to whatever calls the function.

  • A variable called tile_size (the size of the tiles in my scene) works with the variable dir to define what directions astar will search in, and within what distance away any neighbors are expected to be. Essentially, these variables work in 2 for loops to isolate which tiles, out of every tile in the whole freaking map, are neighbors to the starting position.

  • The w variables, count and max, work to ensure the while loop I've set up doesn't run forever. This is the first while loop I've actually gotten working in Godot for some reason.

  • lowest_check is set to a high value, because it's going to compared to the f I generate for every tile and will be reduced in size to help isolate the neighbors of a tile.

  • lowest_val temporarily holds the positions of the tiles with the lowest f.

  • temp_path is a Dictionary, which in Python/GDscript means you can use it to store a value, in this case the Vector2 position of a single tile, with a key, in this case f. So, I use temp_path to make a collection of the lowest f tiles. Later, I extract the tile with the very lowest f and feed it into the star_path array as part of building a path to my goal.

  • Finally, I've got conditions that run in the path is complete or if the path fails.


In order to generate the start position, ending position, and a map of coordinates as an array, I use 2 different functions. The first is my array of map coordinates:

func get_map(tile_map):
	#gets the pos of every single tile from a tilemap 
	#and puts the pos into an array
	var tile_repac = []
	for i in tile_map.get_used_cells().size():
		var tiles = tile_map.map_to_world(tile_map.get_used_cells()[i])
		tile_repac.append(tiles)
	if tile_repac.size() == tile_map.get_used_cells().size():
		return tile_repac

Technically you don't need this portion, as tile_map.get_used_cells() is an array of the kind I need. However, I found it to be easier to understand what was happening with things like tile_map.get_used_cells() resolved externally to the A* function.


This next function I used to find the tiles near any given object, so that objects don't have to start directly over tiles or any of that nonsense:

func find_tile(obj_global_pos, map=[]):
	#files the tile closest to provided pos
	var tile_close
	var closeness = 30 #less than per-tile size
	var tile_cor = Vector2()
	for t in map.size():
		tile_close = obj_global_pos.distance_to(map[t]) #checking distance to all tiles in array, within array size, for closest match.
		if tile_close < closeness:
			tile_cor = map[t]
			return tile_cor

Just compare the global position of an object to the coordinates supplied from a map array in a for loop. Easy peasy.


All of the above (mostly) works when run from a _ready(): function. However, if you attempt to run the above every frame of the game, it'll fail. So, I made a (bad, cause it doesn't use delta and therefore may vary by computer) timer:

func timer(delta):
	if timer < timer_max:
		timer += 1
	else:
		timer = 0

Finally, everything is called and brought together in a process function, where I also happen to be controlling the movement of my seeker in my test scene:

func _process(delta):
	var speed = 50
	timer(delta)
	if timer == timer_max-1:
		var map_array = get_map(tilemap)
		var p_pos = seeker.global_position
		var p_tile = find_tile(seeker.global_position, map_array)
		var t_pos = target.global_position
		var t_tile = find_tile(target.global_position, map_array)
		path = a_star(p_pos,t_pos,map_array)
	if path.size() > 1:
		var path_next = path[0]
		var direction = (path_next-seeker.position).normalized()
		seeker.position += direction*speed*delta
		if seeker.position.distance_to(path_next) < 2:
			path.remove(0)
	elif path.size() == 1:
		print(path)
		var path_next = path[0]
		var direction = (path_next-seeker.position).normalized()
		seeker.position += direction*speed*delta
		path.clear()
	else:
		pass

The process function above has the seeker re-find the target every time the timer hits a certain value, which is good cause I changed the target so it could move (setup outside this script).


After all that, the A* function I've made does work when the seeker and target are at angles with each other or directly connected over space. However, if the seeker and target are ever directly facing over an area without tiles, like this:


the seeker in the above image (the grey/blue square, the target is the pink/red square) will move forward, stop, and then the script will report a pathing fail. Alot of Mask's levels are going to look like this, and the behavior is reproducible even when the seeker and target are otherwise close, like this:










I have no idea how to fix this bug at the moment, and I cannot have this freezing behavior in the final game. So, having been reminded that Navigation2D exists in my research, I decided to give it a shot.


I fixed my problem with 1 fucking line of code:

path = nav_2d.get_simple_path(seeker.position,target.position)

Goddammit.


All I had to do was set my scene up like this:

Reset my main script to be this:

extends Node2D

onready var tilemap = $BlueTiles
onready var seeker = $Seeker
onready var target = $Target
onready var nav_2d = $Navigation2D

var path = []

var timer = 0
var timer_max = 20

func _process(delta):
	var speed = 50
	timer(delta)

	if timer == timer_max -1:
		path = nav_2d.get_simple_path(seeker.position,target.position)
	
	if path.size() > 1:
		var path_next = path[0]
		var direction = (path_next-seeker.position).normalized()
		seeker.position += direction*speed*delta
		if seeker.position.distance_to(path_next) < 1:
			path.remove(0)
	elif path.size() == 1:
		pass

func timer(delta):
	if timer < timer_max:
		timer += 1
	else:
		timer = 0

And, now I've got this:

The result isn't perfect (the seeker is clearly hugging the edge of the tilemap, and would be running into traps and the like in my game), but I'm sure there's a solution or hack out there I can use.


I learned alot from trying to implement my own A*, but I'm done experimenting with pathfinding for now. I've got a game to finish.


The 3rd of May, I'll be covering... something else! I've been focused on pathfinding for so long I'm going to have to re-orient to my project. Until then!

© 2023 by Andrew Jonhardt. Proudly created with Wix.com