# Find a path centered on the edge between traversable tiles

I'm trying to implement a pathfinding system in a simple tower defense game I'm working on. I've a 15x8 tilemap where each cell is of size 64x64.

image 1 A is the start point, B is the end point, the green blob is the bad guy, the brown tiles are the route and the green tiles are the "walls".

So basically I want to auto find a grid-based path from point A to point B for the enemy, similar to this:

image 2

Down below are the scripts I've implemented in the game, should be a bit messy...

Main script

func _astar_search(graph, source, target):
var q = Heap.new()
var nodes = {}
nodes[source] = Vertex.new(source, null, 0)
q.insert(source, 0)

while not q.empty():
var current = q.extract_min()

if current == target:
break

for next in graph.neighbors(nodes[current]):
if nodes.has(next) == false:
nodes[next] = Vertex.new(next)

var new_cost = nodes[current].get_cost() + graph.weight(nodes[current], nodes[next])
if new_cost < nodes[next].get_cost():
nodes[next].set_cost(new_cost)
nodes[next].set_parent(current)

if q.contains(next) == false:
q.insert(next, nodes[next].get_cost() * _heuristic(target, next))

return nodes

func _find_path(nodes, source, target):
var path = []
var current = target

while current != source:
path.append(nodes[current])
current = nodes[current].get_parent()

path.append(nodes[source])
path.invert()
#_dir.invert()
return path

func _heuristic(a, b):
return abs(a.x - b.x) + abs(a.y - b.y)


Graph class

func neighbors(vertex):
var cell = vertex.get_cell()
var result = PoolVector2Array([
cell + Vector2.UP,
cell + Vector2.LEFT,
cell + Vector2.DOWN,
cell + Vector2.RIGHT,
])

#if fmod(cell.x + cell.y, 2) == 0:
#   result.invert()

result = _filter("_in_bounds", result)
result = _filter("_walkable", result)
return result

func _in_bounds(cell):
return cell.x >= 0 and cell.x < size.x and cell.y >= 0 and cell.y < size.y

func _walkable(cell):
return obstacles.has(cell) == false


It's not working properly. I need the path to be centralized in between the two "roads" just like the image 2, but what I've now is:

image 3

The blue line is the path generated by the algorithm and the red dots are the same path but centered at tile's position

Do you have any suggestions on how could I center the path?

Your problem lies in generating the graph, before any actual pathfinding takes place. It looks like you want the intersections of tiles to be considered the nodes of your graph, and only want intersections where all four adjacent tiles are ground.

If you do it correctly, the pathfinder in your example will have only one valid path to choose from.

If I understand correctly, you want the algorithm to return a path that touches the center of each grid (the red dots, in your last image) rather than one that goes along the grid lines (the blue line, in your last image).

To accomplish this, you need only to add the half-size of your node to the node's world position. For example: Given a node whose grid position is at (0, 0) in grid that is centered at world position (10, 10), and your nodes are 3 world units wide, then the center of the given node would be at (11.5, 11.5).

Note that you may need to subtract the half-size from one or both axes instead of adding depending on the pivot position of your nodes. If your nodes pivot from the bottom-left, you would do it the same as in my example. However, if the pivot position were to be top-left, you would add to the x-axis and subtract from the y-axis instead.

However, a much easier solution, as noted by one of the other answers, is to simply offset your terrain tiles so that the grid lines touch the center of each tile instead. This way no math is necessary and the apparent result is the same.

• Do you mean like this? i.imgur.com/IlUtPQd.png – CrazY D Jun 11 '20 at 20:58
• Yep! That's exactly what I mean. – Agent Tatsu Jun 12 '20 at 5:42

So after much effort I finally get it working, although I'm not sure if I did it the best way. Tried to do what Agent Tatsu suggested but it didn't work. I did something based on what I understood from the BlueRaja's answer.

Basically I took every walkable tile of the map and "packed" each with its three adjacent tiles to form a "bigger tile". Each of these big tiles became a node in the graph, which I positioned at the center between the 4 small tiles.

That's it, took like 30 hours but easy right

Joking aside, thank you all for the help, stay safe
EDIT: I can't upvote right now but will once I've 15 reputation