Godot Tactics RPG – 05. Pathfinding

It’s me 7thSage again. I’m back again for part 5. Pathfinding. I expect that this is probably the one a lot of you have been waiting for. Some of you may be expecting us to go down the road of A*(read as A Star), instead we’ll be using a simpler, and in this case faster, method. As we need to find all possible tiles a unit can move to, A* quickly bogs down because it is designed to find a single path from point A to B as quickly as it can, but finding a path from A to B-Z is a lot of individual paths. During our search instead of saving multiple paths, we leave trails of breadcrumbs that we can follow back from any tile we later choose.

That being said, while it won’t be in the scope of this series, I do think there is plenty of room to include A* as an option for certain search functions. Perhaps as a way to expand enemy AI in the future, or maybe some quality of life feature for movement where you want your character to move beyond their range over the course of multiple turns.

Directions

So here is another difference in Godot from Unity. There is no real global scope. So we can’t create an enum Directions, and just access it anywhere. We have a few options. We could create a global Object named Directions, and put a nameless enum inside it, which would give us access to things such as Directions.NORTH, which works decent, but because the enum itself has no name, we can’t use type completion in the editor or inspector. Another option We can create a global object named something, and create a named enum. The downside here is that we are losing the brevity that putting something in the global scope allowed, leaving us something like, Global.Directions.NORTH.

I’m not sure the best solution, but I’ll go with using Directions.Dirs.NORTH. Lets start by creating a subfolder in our Scripts folder named “Enums Exetentions”. Inside that folder create a script named “Directions.gd”. We’ll use this enum to compare directions and keep track of which direction the player is facing. Later on it can also be used for things like detecting if an attack is from the front or back.

class_name Directions

enum Dirs{
SOUTH, 
EAST,
NORTH,
WEST 
}

Directions Extensions

Gdscript doesn’t have extension methods like csharp does, but we can get much the same effect by creating a helper function. Instead of being able to call something like PointA.GetDirection(PointB), we’ll have to call Directions.GetDirection(PointA, PointB).

We’ll add this to the same script as the Dirs enum. We declare the function static so we can access it without having to create an instance of the class.

static func GetDirection(t1: Tile, t2: Tile):
	var dir:Directions.Dirs
	var toTile:Vector2i = t1.pos - t2.pos
	if abs(toTile.x) > abs(toTile.y):
		dir = Directions.Dirs.EAST if toTile.x < 0 else Directions.Dirs.WEST
	else:
		dir = Directions.Dirs.SOUTH if toTile.y < 0 else Directions.Dirs.NORTH
	
	return dir

static func ToEuler(d: Dirs):
	return Vector3(0, d * 90, 0)

With these functions we can get the general direction relationship between two tiles. This will let us do things like rotate toward the next tile. And ToEuler() will convert the direction into a format that rotation can use. Euler(pronounced Oiler) is one of the most common methods of rotation in games and animation, We have a rotation axis for x, y and z. We aren’t doing anything to get into any tricky situations here, but this system can get into gimbal lock situations where an axis is rotated in such a way, that it lines up and rotates the same direction as another axis. The other primary method is quaternions, which don’t have that issue, but tend to be less simple to work with.

Tile

We created the Tile class in an earlier lesson, but now we need to add just a couple things to it. Each tile will be responsible for holding the reference of whichever unit is on it, and we also need to save a reference to which tile is previous to this one in our search. The breadcrumbs mentioned earlier. We also need a variable to save the distance traveled so we can keep track of range.

Toward the beginning of the script with the other variables we’ll place a variable for content, prev and distance.

var content: Node

var prev: Tile
var distance: int

Unit

We’ll start by create a script called “Unit.gd” inside the “View Model Component” folder. Once we’ve created our script, open up our Hero and Monster prefab. On the root “Hero” node, attach the Unit.gd script in both of them.

While we are in our prefabs, under the Hero node, create a new child node named “Movement”. We’ll be attaching a script to this node toward the end of the lesson.

As the Tile keeps track of what unit is on top of it, the unit also keeps track of what tile it is on. This way when we have a reference to the unit, we can use it to look up what tile it is on. We also store what direction it is facing. For now we just have two functions, one to position the unit, and another to switch which tile the unit is on. Later on we can also add things like stats to the Unit. Also note we are extending Node3D on this one, as we’ll use it later on to access the position properties of the node along with the Unit specific data.

extends Node3D
class_name Unit

var tile: Tile
var dir: Directions.Dirs = Directions.Dirs.SOUTH

func Place(target: Tile):
	#Make sure old tile location is not still pointing to this unit
	if tile != null && tile.content == self:
		tile.content = null
	
	#Link unit and tile references
	tile = target
	
	if target != null:
		target.content = self

func Match():
	self.position = tile.center()
	self.rotation_degrees = Directions.ToEuler(dir)

Board

The main part of our pathfinding will happen on the BoardCreator script. Here our goal will be to create a list of tiles a unit can walk to. Later on we’ll filter out any tiles that a unit can’t stop on, such as occupied tiles. During our search we also set previous tiles so we can find our way back to the start point no matter where we end up.

  • Green – Tiles in the queue
  • Blue – Tile currently checking
  • Grey – Tile already added to our list
  • Plus Icon/Greyed out Icon – These are the icons we are attempting to add to the queue. Greyed out icons have already been visited and skipped.
  1. We start our search by adding our start tile to the queue. We set the distance to 0 and no previous tile because it’s our starting tile.
  2. We officially begin our search and attempt to add the 4 tiles surrounding our tile. We set the distance to 1 more than the tile we are currently checking, in this case 1(0+1) and on each we set the previous tile to this one.
  3. All the tiles in the previous step have been added to the queue, and we are working on checking the first value in the updated list. This time the first tile we checked has already been checked so it is greyed out so there is no need to add that one to the queue. All the tiles being added this round will have their distance set to 2 and this tile will be set as their previous tile.
  4. Again, the two new tiles marked with plusses will be added to the queue and their distance will be set as 2 again, because all 4 of these original tiles had a distance of 1. We have two tiles skipped this time. The original start point, and one tile that has already been added to the queue in the previous step.
  5. We continue checking each tile in the queue.
  6. This time we’ve only got one tile we can add to the queue and so that is the last of the original 4 tiles we added. After this we’ll continue to check through the tiles added in steps 2-6.

Now let’s begin implementing the search in code. In the BoardCreator.gd script, we’ll start by adding a couple functions that we will need in the search function, that way we won’t have to jump out while we’re working on the actual search.

We’ll start with the ClearSearch() function. Because our search is saved directly on the tiles in the map, we need to reset the data related to searching on each of the tiles. We set each prev tile to null, because there is no trail to any previous tiles yet. The optimal path to each tile will be based on the smallest distance to each tile, so we start it with a high number, and if we reach it with a lower number, we update our tile. In csharp we can set this as int.MaxValue, but in GDScript we’ll put the same number in manually. We could theoretically set a higher number, but this is plenty high enough, even if we add 100 to each search tile instead of 1(this has the advantage of being able to use int math later on instead of float, if you wanted to change things up)

func ClearSearch():
	for key in tiles:
		tiles[key].prev = null
		tiles[key].distance = 2147483647 #max signed 32bit number

The next function we need to create is the GetTile() function somewhere in the BoardCreator script. This will return the tile based on its location.

func GetTile(p: Vector2i):
	return tiles[p] if tiles.has(p) else null

Now we can start the Search() function. The object calling this will give two parameters, a start tile, and a callable, which will point to some function on the object(not in the BoardCreator script). Generally we’ll be using ExpandSearch() as the function we’ll be passing into the search function. The ExpandSearch function will be responsible for letting our search know whether the next tiles are valid, and ultimately stopping the search.

When we get to that point, as an example, the Search function will call something like addTile(tileA, tileB) which will in turn call for instance, movement.ExpandSearch(tileA, tileB) and return the value, a bool to the Search function.

For the first few lines of the function. We have a variable to store the list of tiles we will be returning, which right off the bat we add our start tile. We call our ClearSearch function to set things up, and we create an array to hold our queue. GDScript does not have a specific queue object, but instead the functionality is built into the standard array.

func Search(start: Tile, addTile: Callable):
	var retValue = []
	retValue.append(start)	
	ClearSearch()
	var checkNext = []

Next we’ll start by setting the distance of the original start tile to 0, and adding it to the queue. It goes into both the queue and the return array. We’ll be adding values to the end of the array with push_back(), and later we’ll be removing and using them from the front with pop_front(), which gives us the first in, first out we need with the queue. We also need to create an array of points for each cardinal direction relative to the tile we are checking. We’ll add this array outside of the main search loop so we are not needlessly creating and destroying the array each time we use it.

start.distance = 0
checkNext.push_back(start)

var _dirs = [Vector2i(0,1), Vector2i(0,-1), Vector2i(1,0), Vector2i(-1,0)]

Next up is the main loop where we check go through the queue. We are using a while loop here as we will continue the loop until we run out of values in the queue. We will have to be careful on two points here so we don’t end up with an infinite loop. We have to make sure we actually delete objects from the queue, and we have to make sure we’re actually adding valid tiles and not for instance, thousands of duplicate tiles already in the queue. The first thing we do is remove the first item off the queue, so we shouldn’t have to worry about the part about deleting elements, so all that’s left is being careful about not adding infinite items to the queue.

while checkNext.size() > 0:
	var t:Tile = checkNext.pop_front()
	#Add more code here

I know we just added the array outside our main search loop so we wouldn’t do a bunch of extra stuff every single time, but if you want your characters to follow a more interesting looking path and aren’t worried about the extra memory and processor usage, which shouldn’t be too terrible probably? We can shuffle the _dirs array before we loop through it to give a more interesting looking path. This will only change the order when multiple tiles have the same distance reaching it. Anyway, it’s up to you whether you include this line.

_dirs.shuffle() #Optional. May impact performance

Still in the while loop. We create a for loop, looping once for each direction in our _dirs array. We use GetTile with the position of the current tile, plus one of the values in the _dirs array to give us the 4 surrounding tiles. Then we check to make sure that the tile is not null, and to see if the tile has not already been searched, or has already been added to the queue. We do this by comparing the distance. If the distance is the same or less than the one’s we’re currently checking, that means another tile has already added it to the queue, or its already been searched.

for i in _dirs.size():
	var next:Tile = GetTile(t.pos + _dirs[i])
	if next == null || next.distance <= t.distance + 1:
		continue
	#More code here

Still in the for loop. Here is where we’ll be using that callable. This will call a function on the object that initiated the search and return a bool, which will determine whether we add the tile. We need to set the distance for the tile, which is one tile away from the current tile. We also set the current tile as the previous tile on the new tile so we can find our way back. After that, we add the new tile to both the queue, and the array of tiles to return.

if addTile.call(t, next):
	next.distance = t.distance + 1
	next.prev = t
	checkNext.push_back(next)
	retValue.append(next)

Now the only thing left to do is return our list of tiles. This goes outside the for and while loops.

return retValue

Tile Colors

We’ll be using the tiles returned from our search to highlight them on the board. We’ll do this by adding a tint color to the tile’s material. At the beginning of the BoardCreator script, create a variable for both the selected color, and a default tint to return to.

var selectedTileColor:Color = Color(0, 1, 1, 1)
var defaultTileColor:Color = Color(1, 1, 1, 1)

We also need two functions, that will take our list of tiles to highlight, and un-highlight our tiles.

func SelectTiles(tileList:Array):	
	for i in tileList.size():
		tileList[i].get_node("MeshInstance3D").material_override.albedo_color = selectedTileColor

func DeSelectTiles(tileList:Array):
	for i in tileList.size():
		tileList[i].get_node("MeshInstance3D").material_override.albedo_color = defaultTileColor

We just need to do one last thing for these functions to work. In the Tile.tscn prefab scene, select the MeshInstance3D and in the inspector under the section GeometryInstance3D, expand the Geometry section if it isn’t and under Material Override, click on the picture of the sphere displaying our material to expand the properties. Go down most of the way to Resource and expand it to see the options. Check the box that says “Local to Scene”. This will let us highlight each tile individually, instead of just highlighting all of them at the same time.

Movement

Start off by creating a subfolder under “Scripts->View Model Component” named “Movement”. Inside that folder, we’ll create a new script, “Movement.gd”. This will be our base class for our different movement methods. We won’t be using it directly, but instead we’ll build specific movement types on top of it, such as Walk Movement, Fly Movement, and Teleport Movement.

Start off by defining a class_name. This will let our other movement types inherit it. We need a variable for range and jump height so we know how far each unit can move. We’ll set these values up when we add the units to the board at least for the time being. Next we need a reference to the unit component for getting and updating the position, and the Jumper node to provide secondary movement for animation.

extends Node
class_name Movement

var range: int
var jumpHeight: int
var unit: Unit
var jumper: Node3D

We assign the references to unit and jumper in the _init() function. Jumper is a sibling node to Movement, so we first go up a level to the parent, then back down to Jumper.

func _init():
	unit = get_node("../")
	jumper = get_node("../Jumper")

Next up is a what we’ll use to actually call our search. We store the results in an array that this function will pass on to whatever is using the movement component. We pass two values to the Search() function, the first the tile the unit is on, and ExpandSearch, which while it looks like a variable, in this case is an entire function. When passing a function as a callable, we don’t use the parenthesis.

ExpandSearch()’s job is to return true if it is a valid location to move to. It doesn’t get called from in the movement script directly, but instead gets called from inside the Search() function.

Search()’s function is to create a list of tiles that a unit can reach, while Filter()’s function is to remove tiles from that list that can’t be stopped on.

func GetTilesInRange(board: BoardCreator):
	var retValue = board.Search(unit.tile, ExpandSearch)
	Filter(retValue)
	return retValue

func ExpandSearch(from:Tile, to:Tile):
	return from.distance + 1 <= range

func Filter(tiles:Array):
	for i in range(tiles.size()-1, -1, -1):
		if tiles[i].content != null:
			tiles.remove_at(i)

Next we have two more functions. Traverse(), which we’ll just leave as a blank stub that we will be overriding in our different movement types, and Turn(). We’ll actually give a complete implementation of Turn() in this one, as it will be used in most of our movement types.

The if/elif at the beginning of the function we do a check to see which direction we are starting at and ending. There are two special cases that we check for, whether we are crossing over from 0 degrees going counter clockwise to 270, and going from 270 clockwise to 0. If we did nothing the rotation would take the long way around simply interpolating between the values, so instead, before we start the rotation, we set our start point with a 360 degree offset in those instances.

The next bit has a couple new pieces and is what actually moves the character. A tween is an animator that we set a start and end point, and then we let the computer fill in everything in-between… or tween all the values in the middle over a set time. At the end of the tween we use an await command that will continue the function later on once the condition has been met, in this case, the tween finishing it’s animation.

func Traverse(tile:Tile):
	pass

func Turn(dir:Directions.Dirs):
	if unit.dir == Directions.Dirs.SOUTH && dir == Directions.Dirs.WEST:
		unit.rotation_degrees.y = 360
	elif unit.dir == Directions.Dirs.WEST && dir == Directions.Dirs.SOUTH:
		unit.rotation_degrees.y = -90
	
	var tween = create_tween()
	unit.dir = dir
	tween.tween_property(
		unit,
		"rotation_degrees",
		Directions.ToEuler(dir),
		.25,
	).set_trans(Tween.TRANS_QUAD).set_ease(Tween.EASE_IN_OUT)
	await tween.finished

Tweens have undergone quite a bit of overhaul in Godot, especially from version 3 to 4, but even from 4.0 there have been a few changes, mostly simplifying the creation process, so if you find examples online, the setup may be a bit less now. At it’s simplest, a tween takes 4 parameters, the object you want to animate, the property to animate, the value we are going to, and last the duration. There used to be additional parameters for transition and ease type, but those are now added with .set_trans() and .set_ease() at the end instead. While the standard parameters set what you are animating and how long it takes, the transition and easing control how it gets there. Does it accelerate slow and stop suddenly, or immediatly start at full speed and then gradually slow to a stop, does it overshoot the target and bounce back. All those questions change the feel and look. Most of the time we can base these values on the physics of the motion we are aiming for, and others we just choose what we like the look of.

Walk Movement

We’ll start off with our first concrete movement type. In the folder “View Model Component->Movement” create a new script “WalkMovement.gd”. Extend Movement, and give a class_name.

extends Movement
class_name WalkMovement

We’ll override the ExpandSearch() function. At the end we call the base class with super() to make sure the tile is in range, and before it we add two more checks to determine if the tile is not too high to jump, and if the tile has a unit on it. In the future we will add the ability to check if the unit is an ally, but for now we will block all units as if they are enemies.

func ExpandSearch(from:Tile, to:Tile):
	#skip if the distance in height between the two tiles is more than the unit can jump
	if abs(from.height - to.height) > jumpHeight:
		return false
	
	#skip if the tile in occupied by an enemy
	if to.content != null:
		return false
	
	return super(from, to)

While this is called WalkMovement, there are actually three different things a unit will do to make up this movement type. Turn, Walk and Jump. We already have a function for Turn in the base Movement class, so we just need Walk and Jump. We’ll create the Walk() function first. This will work just like the Turn() function, but we won’t need to worry about any edge cases this time.

func Walk(target:Tile):
	var tween = create_tween()

	tween.tween_property(
		unit,
		"position",
		target.center(),
		.5,
	).set_trans(Tween.TRANS_LINEAR)
	await tween.finished

The Jump() function is a little bit more complicated. There are two values that we are animating. The position value of the whole unit itself that will move it from its current tile to it’s new position. This will move the unit in a straight line from the top of one tile to the next. To make it look like a jump, we need to raise the unit up a little in the middle. Instead of worrying about calculating the height in the middle, we will instead animate the height of the child node that holds the geometry, Jumper. Animating this let’s us go whatever height we want in the middle using local values instead of world position that we use with the main unit.

The next problem we have is that while the character is moving constantly from the start of the animation until it reaches the end, the height is going up the first half, and down the second half. Ideally we’d be able to set the tween to ping pong with one tween, but so far that isn’t an option inside of Godot, so we’ll have to chain two tween’s together for this motion. When using the same tween object, each tween created after the original is chained by default. When we create a second tween object, they will run in parallel.

At the end of this function we set an await command for the tween we created to set the overall position. We don’t need to set one for both as they should be finishing at the same time. Duration is .5 for the first one, and the two halves are both .25 seconds each.

func Jump(to:Tile):
	var unitTween = create_tween()

	unitTween.tween_property(
		unit,
		"position",
		to.center(),
		.5,
	).set_trans(Tween.TRANS_LINEAR)
	
	var jumperTween = create_tween()
	
	jumperTween.tween_property(
		jumper,
		"position",
		Vector3(0,Tile.stepHeight * 2,0),
		.25
	).set_trans(Tween.TRANS_QUAD).set_ease(Tween.EASE_OUT)

	jumperTween.tween_property(
		jumper,
		"position",
		Vector3(0,0,0),
		.25
	).set_trans(Tween.TRANS_QUAD).set_ease(Tween.EASE_IN)
	
	await unitTween.finished

Once we’ve completed our search and chose a tile, this is where we move the unit. We start off by setting the unit’s owner to the new tile.

When we click a destination, we want our unit to move from it’s current tile, to that location. However, we don’t know how to get to that location, we only know how to return home from any tile. So, before we go anywhere, we need to build out a list of tiles in the correct order. We do this by starting with the destination tile, and instead of adding it to the end of the list, we add it to the beginning. Leaving us with a list of tiles to travel in the correct order.

After that we loop through that new list and move our character from tile to tile, turning, walking and jumping between each as required. We need to be sure to add an await to each of the functions Turn(), Walk() and Jump(). Otherwise they will assume the functions are finished when they hit the first pause and continue moving before the animation is finished.

I’ve also added a couple notes of where you’d most likely switch what animation is playing if you are planning on using a fully animated character instead of our slimes. Just be sure to set it to play before the await command, or it will switch after the animation is supposed to be finished.

func Traverse(tile: Tile):
	unit.Place(tile)

	#Build a list of way points from unit's
	#starting tile to the destination Tile
	var targets = []
	while tile != null:
		targets.push_front(tile)
		tile = tile.prev
		
	#move to each waypoint in succession
	for i in range(1, targets.size()):
		var from:Tile = targets[i-1]
		var to:Tile = targets[i]
		
		var dir: Directions.Dirs = Directions.GetDirection(from, to)
		
		if unit.dir != dir:
			#This is where you would start playing turn animation if there is one
			await Turn(dir)
		
		if from.height == to.height:
			#This is where you would start playing walk animation if there is one
			await Walk(to)
		else:
			#This is where you would start playing jump animation if there is one
			await Jump(to)

	#When for loop is finished, return to idle animation if there is one

Inside the for loop I think would also be a good location to potentially interrupt movement on the path, such as landing on a trap. The trick might then be determining what tile the unit ends up on if that location is not valid to stop on. You’ll have to move the unit.Place(tile) someplace a bit later in the function so it can get the new tile first. But again, that’s not in the scope of this tutorial, but I thought I’d mention it in case someone wanted to try implementing something like it on their own.

Range Search

I mentioned before that I think A* would be a good addition to the code in certain circumstances, and while that still isn’t here, I do think we may benefit from a second search method. The initial search has one drawback. The search radiates out from a single point, expanding one tile at a time. The problem with this is that if there are gaps in the board, or if there are unit’s blocking a specific tile, it could shorten the range of things like flying units. So this is my solution to that problem. We create a new search function that instead of checking with a queue, we just loop through all tiles within range. While this does add a bit more code to our already somewhat large BoardCreator script, this search should actually be faster running than the standard search.

So, let’s go back to our BoardCreator script and add this new function. It starts off pretty similar to the original search function. We create a list to hold the tiles, we clear the search and set the start distance to 0. After that we create a couple for loops. We loop through the y value plus or minus the range. The x value we add a little trick to loop less the further away from the center y is. So if our total movement is 5 and our y value is 5, then our x has to be 0. If our Y value is 4, then x could be -1,0 or 1.

Inside the loop we skip and add tiles much the same as we did in the original search function. The biggest difference is that we set the distance to the absolute value of x + the absolute value of y instead of using previous tile + 1. We also set all tile in range, except the start tile to have a prev tile as the start tile.

func RangeSearch(start: Tile, addTile: Callable, range: int):
	var retValue = []
	ClearSearch()
	start.distance = 0
	
	for y in range(-range, range+1):
		for x in range(-range + abs(y), range - abs(y) +1):
			var next:Tile = GetTile(start.pos + Vector2i(x,y))
			if next == null:
				continue
				
			if next == start:
				retValue.append(start)
			elif addTile.call(start, next):
				next.distance = (abs(x) + abs(y))
				next.prev = start
				retValue.append(next)
	
	return retValue

Fly Movement

Now that we have a second search method, let’s use it for our FlyMovement. In the folder “View Model Component->Movement” create a new script “FlyMovement.gd”. Start by extending Movement, and give a class_name, and this time we’ll override GetTilesInRange() to use our new search instead of the normal one. We’ll also extend ExpandSearch() to properly calculate the distance from tile to tile since we’re moving more than one tile away at a time, though technically speaking we’re already doing this in the search function itself, so we can probably just return true here?

extends Movement
class_name FlyMovement

func GetTilesInRange(board: BoardCreator):
	var retValue = board.RangeSearch(unit.tile, ExpandSearch, range )
	Filter(retValue)
	return retValue

func ExpandSearch(from:Tile, to:Tile):
	return abs(from.pos.x - to.pos.x) + abs(from.pos.y - to.pos.y) <= range

Traverse in the fly method is somewhat similar to the walk method, except we aren’t looping through individual tiles. There aren’t any overlapping animations here. We take off, fly, then land. Because of this we can use a single tween object to move everything in turn, although we are recreating it after calling Turn() because it will have destroyed itself when it finished the previous tween and didn’t have another lined up.

func Traverse(tile: Tile):	
	#Store the distance  and direction between the start tile and target tile
	var dist:float = sqrt(pow(tile.pos.x - unit.tile.pos.x, 2) + pow(tile.pos.y - unit.tile.pos.y, 2))
	var dir:Directions.Dirs = Directions.GetDirection(unit.tile, tile)
	unit.Place(tile)
	
	#Fly high enough not to clip through any ground tiles
	var y:float = Tile.stepHeight * 10
	var duration:float = y * 0.25
	
	var tween = create_tween()
	
	tween.tween_property(
		jumper,
		"position",
		Vector3(0, y, 0),
		duration
	).set_trans(Tween.TRANS_QUAD).set_ease(Tween.EASE_IN_OUT)
	
	await tween.finished
	
	#Turn to face the general direction
	await Turn(dir)
	
	#Move to the correct position
	tween = create_tween()
	tween.tween_property(
		unit,
		"position",
		tile.center(),
		dist * .5
	).set_trans(Tween.TRANS_QUAD).set_ease(Tween.EASE_IN_OUT)

	#Land
	tween.tween_property(
		jumper,
		"position",
		Vector3(0, 0, 0),
		duration
	).set_trans(Tween.TRANS_QUAD).set_ease(Tween.EASE_IN_OUT)
	
	await tween.finished

Teleport Movement

In the folder “View Model Component->Movement” create a new script “TeleportMovement.gd”. Teleport will be functionally the same as FlyMovement, but will have a different visual feel to it. In an actual game, each could be given different limitations to make them more unique. Perhaps adding hight limits to flying, or line of sight for teleport.

So, for now, the same as Flymovement. Extend Movement, give class name and override GetTilesInRange() and ExpandSearch().

extends Movement
class_name TeleportMovement

func GetTilesInRange(board: BoardCreator):
	var retValue = board.RangeSearch(unit.tile, ExpandSearch, range )
	Filter(retValue)
	return retValue

func ExpandSearch(from:Tile, to:Tile):
	return abs(from.pos.x - to.pos.x) + abs(from.pos.y - to.pos.y) <= range

Tweens spread out on multiple lines make this one look fairly complex, but its actually the simplest one of the bunch. We are animating two things happening at the same time, spinning and scaling, so we’ll create two tween objects. It is also possible to use one tween object and set the second animation to play in paralell, but for now just using two objects is fine.

We spin and scale down to disappear, then we set our unit’s new location, and reverse the process, spinning and scaling back up to our original value.

I’m doing both the scale and spin on the Jumper to keep the transforms on the unit a bit more clean. That way we can do things like attach the camera to it without worrying about how different values will impact it.

func Traverse(tile: Tile):
	unit.Place(tile)

	var spinTween = create_tween()
	spinTween.tween_property(
		jumper,
		"rotation",
		Vector3(0,360, 0),
		.5
	).set_trans(Tween.TRANS_LINEAR)

	var scaleTween = create_tween()
	scaleTween.tween_property(
		jumper,
		"scale",
		Vector3(0,0,0),
		0.5
	)
	await scaleTween.finished

	unit.position = tile.center()

	spinTween = create_tween()
	spinTween.tween_property(
		jumper,
		"rotation",
		Vector3(0,0, 0),
		.5
	).set_trans(Tween.TRANS_LINEAR)

	scaleTween = create_tween()
	scaleTween.tween_property(
		jumper,
		"scale",
		Vector3(1,1,1),
		0.5
	)  
	await scaleTween.finished

Battle Controller

We’ll add a couple things to our BattleController.gd script. First, a reference to our Hero prefab so we can instantiate a few heroes around the board. In an earlier lesson I mentioned that you couldn’t drag a prefab into the inspector, but if we set the variable type correctly, that is actually possible, as mentioned in the comments of Part 2. Thanks Adrian. So we’ll add @export and set the variable type to PackedScene. Next open up the battle scene and select the battle controller. Now drag the Hero prefab onto the slot in the inspector.

Eventually this will get moved to another place when we have a more complete implementation of a spawner that will load the correct model for each unit. We also need a variable to store the current unit, and a reference to the current tile, which grabs the location from the board.

#var heroPrefab = preload("res://Prefabs/Hero.tscn")#replaced by @export/PackedScene
@export var heroPrefab: PackedScene

var currentUnit:Unit

var currentTile:Tile: 
	get: return board.GetTile(board.pos)

Init Battle State

We need to make a couple changes to InitBattleState.gd. First up, the @export var at the top is changed from moveTargetState to selectUnitState. Next, after SelectTile(p) we need to add a call to SpawnTestUnits() and finally we need to swap out the state we are swapping to with ChangeState(). All that’s left after that is to create the function for SpawnTestUnits()

extends BattleState
@export var selectUnitState: State #This is changed

func Enter():
	super()
	Init()

func Init():
	var saveFile = _owner.board.savePath + _owner.board.fileName
	_owner.board.LoadMap(saveFile)
	
	var p:Vector2i = _owner.board.tiles.keys()[0]
	SelectTile(p)
	
	SpawnTestUnits() #This is new
	
	_owner.cameraController.setFollow(_owner.board.marker)
	
	_owner.stateMachine.ChangeState(selectUnitState) #This is changed

For SpawnTestUnits() we start by creating an array of our various move types. We can use the class_name values we gave each here so we don’t need to include the full paths.

After that, we loop through once for each movement type in our array. We create a copy of our hero prefab, add it as a child to the battle controller. Next we get the first tiles in our map array. As mentioned in the previous lesson, it isn’t sorted, so these tiles will be somewhat random, depending on how the map was created. We place our unit on the board and finally we set up our movement. We attach the script to the node we created earlier with “m.set_script()” and once set, we can set the variables we need. “m.set_process(true)” isn’t needed at the moment, but if you want to use the _process() function inside any of the movement states, we’d use this to activate it, otherwise the engine won’t run it on frame update.

func SpawnTestUnits():
	var components= [WalkMovement, FlyMovement, TeleportMovement]
	for i in components.size():
		var unit:Unit = _owner.heroPrefab.instantiate()
		_owner.add_child(unit)
		
		var p:Vector2i = Vector2i(_owner.board.tiles.keys()[i].x,_owner.board.tiles.keys()[i].y)

		unit.Place(_owner.board.GetTile(p))
		unit.Match()
		
		var m = unit.get_node("Movement")
		m.set_script(components[i])
		m.range = 5
		m.jumpHeight = 1
		m.set_process(true)

Select Unit State

In the Battle scene, create a child node of the “State Machine” node named “Select Unit State”. Now let’s create a script in the folder “Scripts->Controller->Battle States” named “SelectUnitState.gd” and attach it to the node we just created.

This state will be replaced later on once we have turn order set up, but for now, this will let us move the selection indicator onto any unit and select the unit with any of the “Fire” buttons we set up earlier with the input controller.

extends BattleState

@export var moveTargetState: State

func OnMove(e:Vector2i):
	var rotatedPoint = _owner.cameraController.AdjustedMovement(e)
	SelectTile(rotatedPoint + _owner.board.pos)

func OnFire(e:int):
	print("Fire: " + str(e))
	if _owner.currentTile != null:
		var content:Node = _owner.currentTile.content
		if content != null:
			_owner.currentUnit = content
			_owner.stateMachine.ChangeState(moveTargetState)

func Zoom(scroll: int):
	_owner.cameraController.Zoom(scroll)
	
func Orbit(direction: Vector2):
	_owner.cameraController.Orbit(direction)

Move Target State

Let’s give MoveTargetState a more complete implementation. This state is activated after a unit is selected, then here we’ll start the search and highlight the tiles that are returned. The state is changed when a valid move location is chosen. Before we exit the state, the highlighted tiles are returned to their default tint.

extends BattleState

var tiles = []
@export var MoveSequenceState: State

func Enter():
	super()
	var mover:Movement = _owner.currentUnit.get_node("Movement")
	tiles = mover.GetTilesInRange(_owner.board)
	_owner.board.SelectTiles(tiles)

func Exit():
	super()
	_owner.board.DeSelectTiles(tiles)
	tiles = null

func OnMove(e:Vector2i):
	var rotatedPoint = _owner.cameraController.AdjustedMovement(e)
	SelectTile(rotatedPoint + _owner.board.pos)

func OnFire(e:int):
	if tiles.has(_owner.currentTile):
		_owner.stateMachine.ChangeState(MoveSequenceState)
	print("Fire: " + str(e))

func Zoom(scroll: int):
	_owner.cameraController.Zoom(scroll)
	
func Orbit(direction: Vector2):
	_owner.cameraController.Orbit(direction)

Move Sequence State

Lets add one last state for now. Once a valid tile is chosen, this state is triggered and begins the path traversal. In the Battle scene, we’ll create another child node of the “State Machine” node named “Move Sequence State”. Now let’s create a script in the folder “Scripts->Controller->Battle States” named “MoveSequenceState.gd” and attach it to the node we just created.

There is no implementation of our input functions such as OnMove() or OnFire(), that way we don’t need to worry about input while our character is moving causing potential bugs.

Just before starting the move sequence, we set the camera to follow the unit itself instead of the selection indicator. If we followed the selection indicator, we might not see the initial part of the movement if the camera is too far zoomed in, since the indicator is locked at the destination tile. Once the movement is finished, we set the camera to follow the indicator again.

We need to be sure to include the await command when calling Traverse() or this will continue on and switch states before the animation finishes.

extends BattleState

@export var SelectUnitState:State

func Enter():
	super()
	Sequence()

func Sequence():	
	var m:Movement = _owner.currentUnit.get_node("Movement")
	_owner.cameraController.setFollow(_owner.currentUnit)
	await m.Traverse(_owner.currentTile)
	
	_owner.cameraController.setFollow(_owner.board.marker)
	_owner.stateMachine.ChangeState(SelectUnitState)

State Nodes

Now that we have finished creating our state nodes and scripts, we need to go back and assign the different states to each of the @export variables. Open the Battle scene and go to the inspector for each State. We edited a few states from the previous lesson, so be sure to check those states as well. Assign the corresponding state for each.

Summary

This was a big lesson. We got into coroutines with await, and created our first few tweens. We went through pathfinding and made use of functions as callables. But as a result, we should have three units on the board that can move around, each with their own movement types.

If you’d like to read up on pathfinding more, I’d suggest checking out some of the articles on https://www.redblobgames.com/, he has a ton of excellent articles that break down everything from pathfinding, dice probability, line drawing and many other concepts that fit really well within the tactics genre.

And as always, if there in any confusion with the code, feel free ask questions or check out the repository https://github.com/WeatheredSouls/GodotTactics

3 thoughts on “Godot Tactics RPG – 05. Pathfinding

  1. Great posts, I’ve followed your original tactics tutorial, and was really glad that I found these ones when I started going back to game dev and was learning Godot. Just one fyi, GDScript is usally written with snake_case for variables, functions and file names, they have some documentation about this: https://docs.godotengine.org/en/stable/tutorials/scripting/gdscript/gdscript_styleguide.html

    I initially was following your tutorial with PascalCase, like the one in C#, and it works fine, but when I converted the files to snake_case the editor would some times show some errors about files not found or case sentitivity

    1. Glad you are enjoying the series. It’s certainly been a learning experience for me. I learned Unity an CSharp from following along the original(I knew some CPP before that), and now I’m learning Godot translating it, and getting a much deeper understanding of the original which I’m also enjoying. I never really got used to snake case, and I’m already not all that consistent with naming so I just kinda stick with what makes sense to me. Not sure why different case would give errors though. Only thing I can think is that if you started with one and changed names, the editor may have lost the reference and you might either need to restart the engine, or worst case, recreate/reimport the file?

Leave a Reply

Your email address will not be published. Required fields are marked *