XCOM-like arrow pathing optimization

dogot

I have a grid layout with AStar2D, to which I added the visuals to show the path it will take. It uses sprites from a png tileset of 4x4. Both $GridTerrain and $GridArrow are tilemaps.

The good news is it works flawless. However, as the code clearly shows, I gave up on a clever way to solve this, and simply brute forced everything in there.

How would you handle this? Is this code to slow to run every frame? Know of any tutorial or example code that will go in depth to grid based pathing?

extends Node2D var cellSize = Vector2(64, 64) var path: PoolVector2Array #these directly relate to the spritesheet (4x4), with all arrow pathing possibilities enum {PATH_CROSS, PATH_CENTER, PATH_WEST_EAST, PATH_SOUTH_NORTH, PATH_START_NORTH, PATH_START_EAST, PATH_START_SOUTH, PATH_START_WEST, PATH_NORTH_EAST, PATH_EAST_SOUTH, PATH_SOUTH_WEST, PATH_WEST_NORTH, PATH_END_NORTH, PATH_END_EAST, PATH_END_SOUTH, PATH_END_WEST} enum{NORTH, EAST, SOUTH, WEST} func _process(delta): var from = Vector2(7, 7) #just a random point to test the code var to = worldToGrid(get_viewport().get_mouse_position()) path = $GridTerrain.getPath(from, to) #this gets a PoolVector2Array filled by AStar2D drawPath() func drawPath(): $GridArrow.clear() if path.size() > 1: # is the path at least 2 segments long? var count = 0 var lastCardinal = NORTH for point in path: if count == 0: #start of path match cardinalNextCell(point, path[count + 1]): NORTH: $GridArrow.set_cell(point.x, point.y, 0, false, false, false, getPathTile(PATH_START_NORTH)) lastCardinal = SOUTH EAST: $GridArrow.set_cell(point.x, point.y, 0, false, false, false, getPathTile(PATH_START_EAST)) lastCardinal = WEST SOUTH: $GridArrow.set_cell(point.x, point.y, 0, false, false, false, getPathTile(PATH_START_SOUTH)) lastCardinal = NORTH WEST: $GridArrow.set_cell(point.x, point.y, 0, false, false, false, getPathTile(PATH_START_WEST)) lastCardinal = EAST elif count < path.size() - 1: #before the end point? var nextCardinal = cardinalNextCell(point, path[count + 1]) match lastCardinal: NORTH: if nextCardinal == SOUTH: $GridArrow.set_cell(point.x, point.y, 0, false, false, false, getPathTile(PATH_SOUTH_NORTH)) elif nextCardinal == WEST: $GridArrow.set_cell(point.x, point.y, 0, false, false, false, getPathTile(PATH_WEST_NORTH)) lastCardinal = EAST else: $GridArrow.set_cell(point.x, point.y, 0, false, false, false, getPathTile(PATH_NORTH_EAST)) lastCardinal = WEST EAST: if nextCardinal == WEST: $GridArrow.set_cell(point.x, point.y, 0, false, false, false, getPathTile(PATH_WEST_EAST)) elif nextCardinal == SOUTH: $GridArrow.set_cell(point.x, point.y, 0, false, false, false, getPathTile(PATH_EAST_SOUTH)) lastCardinal = NORTH else: $GridArrow.set_cell(point.x, point.y, 0, false, false, false, getPathTile(PATH_NORTH_EAST)) lastCardinal = SOUTH SOUTH: if nextCardinal == NORTH: $GridArrow.set_cell(point.x, point.y, 0, false, false, false, getPathTile(PATH_SOUTH_NORTH)) elif nextCardinal == EAST: $GridArrow.set_cell(point.x, point.y, 0, false, false, false, getPathTile(PATH_EAST_SOUTH)) lastCardinal = WEST else: $GridArrow.set_cell(point.x, point.y, 0, false, false, false, getPathTile(PATH_SOUTH_WEST)) lastCardinal = EAST WEST: if nextCardinal == EAST: $GridArrow.set_cell(point.x, point.y, 0, false, false, false, getPathTile(PATH_WEST_EAST)) elif nextCardinal == SOUTH: $GridArrow.set_cell(point.x, point.y, 0, false, false, false, getPathTile(PATH_SOUTH_WEST)) lastCardinal = NORTH else: $GridArrow.set_cell(point.x, point.y, 0, false, false, false, getPathTile(PATH_WEST_NORTH)) lastCardinal = SOUTH else: #the end point match lastCardinal: NORTH: $GridArrow.set_cell(point.x, point.y, 0, false, false, false, getPathTile(PATH_END_SOUTH)) EAST: $GridArrow.set_cell(point.x, point.y, 0, false, false, false, getPathTile(PATH_END_WEST)) SOUTH: $GridArrow.set_cell(point.x, point.y, 0, false, false, false, getPathTile(PATH_END_NORTH)) WEST: $GridArrow.set_cell(point.x, point.y, 0, false, false, false, getPathTile(PATH_END_EAST)) count += 1 func worldToGrid(target: Vector2) -> Vector2: var newCoord = Vector2.ZERO newCoord.x = floor(target.x / cellSize.x) newCoord.y = floor(target.y / cellSize.y) return newCoord func gridToWorld(target: Vector2) -> Vector2: var newCoord = Vector2.ZERO newCoord.x *= cellSize.x newCoord.y *= cellSize.y return newCoord func getPathTile(target: int) -> Vector2: #subtile from pathing tileset return Vector2((target % 4), floor(target / 4)) func cardinalNextCell(current: Vector2, next: Vector2) -> int: if current.x > next.x: return WEST elif current.x < next.x: return EAST elif current.y > next.y: return NORTH else: return SOUTH

dogot

I found some code online. Apparently using autotiles works just fine. This allowed me to remove just a few unnecessary lines of code.

Also I made it extend TileMap so now it can be attached to a grid, and simply feed it a path to draw.

The only obstacle left now, is the beginning and end point are the same. Have an idea how to solve this? Let me know.

extends TileMap

func drawPath(path: PoolVector2Array): #path is derived from AStar2D
	clear()
	for point in path:
		set_cellv(point, 0)
	update_bitmask_region()

dogot

I think I found a way to change the first tile placed, but still make it adhere to the autotile system. Both the start and end tiles for the arrow now have the same bitmask. This means the game will randomly choose one of those for that bitmask position. Now my idea was to change the priority of these tiles just before placing them. (Altough priority (weight) cant be 0 apparently, so I made it a difference from 1 to 9000)

But now I am stuck on this weird bug where it wont take the change into account within an if-statement. If I place it outside it does take the change into account.

extends TileMap

func drawPath(path: PoolVector2Array): #path is derived from AStar2D
	drawArrow(path)

func drawArrow(path):
	clear()
	var count = 0 #on count 0 we place the starting tile. So we select a different subtile through priority.
	for point in path:
		if count == 0: #set starting subtiles as high priority
			for subTile in [Vector2(0,1), Vector2(1,1), Vector2(2,1), Vector2(3,1)]:
				tile_set.autotile_set_subtile_priority(0, subTile, 9000)
			for subTile in [Vector2(0,3), Vector2(1,3), Vector2(2,3), Vector2(3,3)]:
				tile_set.autotile_set_subtile_priority(0, subTile, 1)
		elif count == 1: #set ending subtiles as high priority
			for subTile in [Vector2(0,1), Vector2(1,1), Vector2(2,1), Vector2(3,1)]:
				tile_set.autotile_set_subtile_priority(0, subTile, 1)
			for subTile in [Vector2(0,3), Vector2(1,3), Vector2(2,3), Vector2(3,3)]:
				tile_set.autotile_set_subtile_priority(0, subTile, 9000)
		
		#if i uncomment the next 10 lines it does take change into account.
		#even though the if-statement above does the exact same
#		tile_set.autotile_set_subtile_priority(0, Vector2(0,1), 9000)
#		tile_set.autotile_set_subtile_priority(0, Vector2(1,1), 9000)
#		tile_set.autotile_set_subtile_priority(0, Vector2(2,1), 9000)
#		tile_set.autotile_set_subtile_priority(0, Vector2(3,1), 9000)
#		tile_set.autotile_set_subtile_priority(0, Vector2(0,3), 1)
#		tile_set.autotile_set_subtile_priority(0, Vector2(1,3), 1)
#		tile_set.autotile_set_subtile_priority(0, Vector2(2,3), 1)
#		tile_set.autotile_set_subtile_priority(0, Vector2(3,3), 1)
#		print("tileStart (2, 1) priority : ", tile_set.autotile_get_subtile_priority(0, Vector2(2, 1)))
#		print("tileEnd (0, 3) priority   : ", tile_set.autotile_get_subtile_priority(0, Vector2(0, 3)))
		
		set_cellv(point, 0)
		count += 1
	update_bitmask_region()

dogot

I found a different solution. I removed the bitmask from for the start tiles from the autotile. Next I made a new autotile in the same tileset. This one only has the start tiles, with bitmask. Now the first time a cell is set, it does this with the new autotile. The rest uses the original autotile. To make these different autotiles, autotile with each other I had to add some scripting.

The script attached to the TileMap:

extends TileMap

func drawPath(path: PoolVector2Array): #path is derived from AStar2D
	drawArrow(path)

func drawArrow(path):
	clear()
	var count = 0
	for point in path:
		if count == 0: #second autotile in tileset for first cell
			set_cellv(point, 1)
		else: #first autotile in tileset for the rest
			set_cellv(point, 0)
		count += 1
	update_bitmask_region()

I got this next code from the internet, and I dont really understand how it works. But what it does is allow for different autotiles to react to each others bitmask. This script has to be attached to the TileSet used by the TileMap for the autotiling:

extends TileSet

func _is_tile_bound(drawn_id, neighbor_id):
	return neighbor_id in get_tiles_ids()

Left to do now is getting an overlay visible to show the maximum range for a move. Ofcourse this needs to take pathfinding in account, so it cant go through walls.

dogot

Unfortunately I still could not find a proper example or tutorial, so I made an attempt at a solution. It now displays the reach of movement, and on every tile it displays how many movement points you have left should you move there. This also takes into account the weight of tiles. However this is calculated from the startpoint and simply expands outward. This means it does not take pathfinding in consideration. Here is an example of the flawed solution:

The only other thing I can think of is to floodfill by max movement points, and then Astar every cell to check actual movepoints needed. This would probably be even slower then the current code.

Should anyone have functioning tactics-grid-movement code ready I would really like to take a look at it. Or a comprehensive tutorial on the matter, also nice.

Here is the (horribly slow) code I came up with for its calculation. Its the getReach function I have been working on:

extends TileMap
class_name AstarScript

var usedCells = get_used_cells()
onready var astar = AStar2D.new()
var path: PoolVector2Array

var done = {}
var doing = {}
var todo = {}
const neighbours = [Vector2(1, 0), Vector2(-1, 0), Vector2(0, -1), Vector2(0, 1)]

func _ready():
	addPoints()
	connectPoints()

func addPoints():
	var terrainType = Vector2.ZERO
	for cell in usedCells:
		terrainType = get_cell_autotile_coord(cell.x, cell.y)
		if terrainType.x == 0: #grass
			astar.add_point(id(cell), cell, 1.0)
		elif terrainType.x == 1: #sand
			astar.add_point(id(cell), cell, 5.0)

func connectPoints():
	for cell in usedCells:
		for neighbour in neighbours:
			var nextCell = cell + neighbour
			if usedCells.has(nextCell):
				astar.connect_points(id(cell), id(nextCell), false)

func getPath(start: Vector2, end: Vector2) -> PoolVector2Array:
	path = astar.get_point_path(id(start), id(end))
	return path

func getReach(startPoint, movePoints) -> Dictionary:
	done.clear()
	doing[startPoint] = movePoints
	todo.clear()
	
	while doing.size() > 0:
		var current = doing.keys()[0]
		
		for neighbour in neighbours: #test all neighbouring cells for next move
			var neighbourToCheck = current + neighbour
			if done.has(neighbourToCheck):
				continue
			if todo.has(neighbourToCheck):
				continue
			if doing.has(neighbourToCheck):
				continue
			if astar.has_point(id(neighbourToCheck)): #found valid neighbour
				var cost = astar.get_point_weight_scale(id(neighbourToCheck))
				var pointsLeft = doing[current] - cost
				if pointsLeft <= 0: #no more movePoints, this trail is done
					pointsLeft = 0
					done[neighbourToCheck] = pointsLeft
				else: #still movePoints left, test neighbours next loop
					todo[neighbourToCheck] = pointsLeft
		
		#transfer current cell to done
		done[current] = doing[current]
		doing.erase(current)
		
		#transfer entire todo dict into doing
		for c in todo:
			doing[c] = todo[c]
		todo.clear()
	#end of while loop
	
	return done

func id(target: Vector2): #map two numbers into one unique number
	var a = target.x
	var b = target.y
	return (a + b) * (a + b + 1) / 2 + b

dogot

Just after my last post I got hit with a solution to the movepoints problem. Now when a neighbour is found to already be in the todo/doing/done dictionary, it checks if moving from the current cell would result in more movepoints then it already had. If so, it overwrites said dictionary value.

Although this works, the code still is messy and slow. Any refactor tips are welcome.

Next up the arrow for the chosen path needs a rework.

The updated getReach function:

func getReach(startPoint, movePoints) -> Dictionary:
	done.clear()
	doing[startPoint] = movePoints
	todo.clear()
	
	while doing.size() > 0:
		var current = doing.keys()[0]
		var cost = 0
		var pointsLeft
		
		
		for neighbour in neighbours: #test all neighbouring cells for next move
			var neighbourToCheck = current + neighbour
			if done.has(neighbourToCheck):
				cost = astar.get_point_weight_scale(id(neighbourToCheck))
				pointsLeft = doing[current] - cost
				
				#would this new trail result in more points?
				if pointsLeft > done[neighbourToCheck]:
					todo[neighbourToCheck] = pointsLeft #add to todo again
					done.erase(neighbourToCheck) #erase from done
				
			elif todo.has(neighbourToCheck):
				cost = astar.get_point_weight_scale(id(neighbourToCheck))
				pointsLeft = doing[current] - cost
				
				#would this new trail result in more points?
				if pointsLeft > done[neighbourToCheck]:
					todo[neighbourToCheck] = pointsLeft #overwrite value
				
			elif doing.has(neighbourToCheck):
				cost = astar.get_point_weight_scale(id(neighbourToCheck))
				pointsLeft = doing[current] - cost
				
				#would this new trail result in more points?
				if pointsLeft > doing[neighbourToCheck]:
					doing[neighbourToCheck] = pointsLeft #overwrite value
				
			elif astar.has_point(id(neighbourToCheck)): #found untouched neighbour
				cost = astar.get_point_weight_scale(id(neighbourToCheck))
				pointsLeft = doing[current] - cost
				
				if pointsLeft <= 0: #no more movePoints, this trail is done
					pointsLeft = 0
					done[neighbourToCheck] = pointsLeft
				else: #still movePoints left, test neighbours next loop
					todo[neighbourToCheck] = pointsLeft
		
		#transfer current cell to done
		done[current] = doing[current]
		doing.erase(current)
		
		#transfer entire todo dict into doing
		for c in todo:
			doing[c] = todo[c]
		todo.clear()
	#end of while loop
	
	return done