Sugor Dev Almanac
doc 3 of 6

Part 02 — a grid that knows where the walls are

You will build: An AStarGrid2D built from a TileMapLayer, with solid cells marked from the tiles themselves, and an agent that walks the returned waypoints around the U-shaped wall that trapped the chaser in part 01. The path is drawn on screen, so you can see exactly what the search produced instead of guessing from the agent's behaviour.

In part 01 you built a chaser that steers straight at its target, and you found the shape that defeats it: a wall that opens away from the player. The chaser pressed into the wall and stayed there, because nothing in it could represent "there is a way around". This part gives it that representation.

One boolean per cell#

Here is the whole model before any code.

A* searches a graph. AStarGrid2D is a rectangular graph that Godot builds for you, one node per cell, connected to its neighbours. Its entire vocabulary for obstacles is a single boolean per cell: solid or not solid.

That sentence is worth sitting with, because it is where most confusion starts. There is no wall object in this system. Your StaticBody2D walls are invisible to it. Your collision layers are invisible to it. Your tiles are invisible to it. set_point_solid(id) is the wall, and if you never call it, the search will route straight through your level geometry and be entirely correct to do so, because as far as the grid is concerned that space was always empty.

Everything else in this part is bookkeeping around that one boolean: where the grid sits in the world, when the flags survive, and how to read cell coordinates back out.

The scene#

Two tile layers and an agent:

level (Node2D)
├── ground (TileMapLayer)      # every walkable tile, painted as a filled rectangle
├── walls (TileMapLayer)       # the U shape, painted on top
├── grid_pathfinder (Node2D)   # grid_pathfinder.gd
└── walker (CharacterBody2D)   # walker.gd
    └── CollisionShape2D

Paint ground as a solid block of floor first — its used rectangle is going to define the searchable area, so anywhere you do not paint is unreachable. Then paint the U on walls, opening away from where the player will stand.

Keep both layers at position (0, 0) with no scale or rotation. They will be converted between cell coordinates and pixels using the same numbers, and if their transforms differ, every cell lookup on one of them is silently offset from the other. That is not a permanent restriction, it is a restriction for today.

If you already have a level with one layer where walls are holes in the floor, that works too. The code below treats a missing wall layer as "no walls painted".

Three properties that place the grid in the world#

Before writing anything, know what the three geometry properties are for. Their defaults are all legal, all silent, and all wrong for your level.

region is a Rect2i measured in cells, not pixels. It answers "which cells exist at all". Its default is Rect2i(0, 0, 0, 0), a rectangle of zero size, which means a freshly constructed AStarGrid2D contains zero points. Query it and you get an empty array back, with no error, because you asked for a path across a graph with nothing in it. tile_layer.get_used_rect() hands you exactly the rectangle you want.

cell_size is the multiplier that turns a cell id into a position. It answers "how big is a cell in pixels". Its default is Vector2(1, 1), which means the positions you get back are numerically identical to the cell ids: a path across your level arrives as a handful of tiny numbers clustered near the origin, and your agent drifts up and to the left toward (0, 0). Set it to your tile size.

offset is added to every computed position afterward. Cells are addressed by their corner, so with no offset every waypoint lands on the top-left corner of a tile. The agent then hugs the corner of every tile it crosses, which reads as clipping and makes diagonal movement worse than it needs to be. An offset of half a cell puts waypoints in tile centres.

Those three are the grid's relationship to the world. Get them wrong and nothing errors; you only see it in the agent.

Build it in the order that feels natural#

Create grid_pathfinder.gd and attach it to the grid_pathfinder node. Assign ground and walls in the inspector.

Write this version first. It is wrong, deliberately, and running it teaches something that reading about it does not.

class_name GridPathfinder
extends Node2D

@export var ground_layer: TileMapLayer
@export var wall_layer: TileMapLayer

var _grid: AStarGrid2D = AStarGrid2D.new()


func _ready() -> void:
	z_index = 100
	rebuild()


func rebuild() -> void:
	var used: Rect2i = ground_layer.get_used_rect()

	_grid.region = used
	_grid.cell_size = Vector2(ground_layer.tile_set.tile_size)
	_grid.offset = _grid.cell_size / 2.0

	# Mark the obstacles. This feels like the important part, so it goes first.
	for y in range(used.position.y, used.end.y):
		for x in range(used.position.x, used.end.x):
			var cell: Vector2i = Vector2i(x, y)
			if wall_layer.get_cell_source_id(cell) != -1:
				_grid.set_point_solid(cell)

	# The docs mention update(), so call it before querying.
	_grid.update()

Run it and read the output panel before anything else.

Grid is not initialized. Call the update method.

Hundreds of them. One line for every cell the loop touched, because not one of those set_point_solid() calls did anything. Confirm it with a temporary print at the end of rebuild(), on a cell you know you painted a wall on:

	print(_grid.is_point_solid(Vector2i(5, 3)))

It prints false. You marked it. You watched the loop reach it. It is not solid.

The error text is the rule, handed to you by the engine before you asked for it. The next section is why the rule exists.

What update() actually does#

The class reference describes update() as preparing the grid according to its parameters. What that means in practice is that it rebuilds the point set from scratch. New points, fresh state, every flag back to its default. Your solid markings were attached to points that no longer exist.

So the rule, and it is a rule with a reason rather than a ritual:

Set region, cell_size and offset. Call update(). Then mark solid cells.

Anything about the grid's shape goes before the update. Anything about the grid's contents goes after it. If you later change region because the level grew, you call update() again and you re-mark every wall, because they are gone again.

is_dirty() tells you whether an update is still owed — the grid knows when a geometry property has changed since the last rebuild. It is useful in a rebuild() that might be called from several places, and it is useful in a breakpoint when you are not sure which of two systems touched the grid last.

Move the update() call up, above the loop, and run again. The print flips to true.

Marking the walls without leaving holes#

Now write the marking properly. Two things change from the first version.

First, a cell is solid if a wall tile sits on it or if there is no floor tile under it. get_cell_source_id(cell) returns -1 for an empty cell, and that single test means opposite things on the two layers: -1 on walls means walkable, -1 on ground means void. Marking the void matters more than it looks — without it, a path can route out through the gap in your floor and back in, which looks like the agent teleporting across a hole.

Second, every set_point_solid() call gets guarded by is_in_boundsv(). An id outside the region sets nothing and pushes an error naming the cell it rejected — one per call, so a loop that strays past the region does not report a problem once, it reports it four hundred times and buries whatever else you were reading. The guard costs one comparison and keeps the panel usable, which matters because the output panel is the only instrument you have in this part. It also means calling rebuild() again after the level grows is quiet rather than noisy.

func rebuild() -> void:
	if ground_layer == null or ground_layer.tile_set == null:
		push_error("GridPathfinder needs a ground layer with a TileSet.")
		return

	var used: Rect2i = ground_layer.get_used_rect()

	_grid.region = used
	_grid.cell_size = Vector2(ground_layer.tile_set.tile_size)
	_grid.offset = _grid.cell_size / 2.0
	_grid.update()

	_mark_solid_cells(used)
	queue_redraw()


func _mark_solid_cells(used: Rect2i) -> void:
	for y: int in range(used.position.y, used.end.y):
		for x: int in range(used.position.x, used.end.x):
			var cell: Vector2i = Vector2i(x, y)
			if not _grid.is_in_boundsv(cell):
				continue

			var has_floor: bool = ground_layer.get_cell_source_id(cell) != -1
			var has_wall: bool = wall_layer != null and wall_layer.get_cell_source_id(cell) != -1

			_grid.set_point_solid(cell, has_wall or not has_floor)

Note the second argument. set_point_solid(id) defaults to true, so the one-argument form blocks a cell. Passing the boolean explicitly means the loop both sets and clears, which is what you want from a function called rebuild — call it twice and you get the same result, rather than an accumulation of stale walls.

Expensive is not the same as impassable#

Solid is a hard no. There is a softer answer, and it is worth knowing about now rather than discovering later when you try to express it with walls.

set_point_weight_scale(id, weight) multiplies the cost of entering a cell. A weight of 3.0 means the search treats that cell as three tiles of walking, so it will route around a patch of mud if the detour is shorter than three tiles, and straight through if it is not. Deep water, brambles, a road that should be preferred at 0.5 — all of that is weight, not solidity.

func mark_slow_cells(slow_layer: TileMapLayer, weight: float) -> void:
	for cell: Vector2i in slow_layer.get_used_cells():
		if _grid.is_in_boundsv(cell):
			_grid.set_point_weight_scale(cell, weight)

Weights live on points, exactly like solid flags, which means the same ordering rule applies: call this after update(), and call it again after any rebuild. Add a slow layer now or leave it for later, but recognise the distinction. "Agents should avoid this unless the alternative is worse" is a different statement from "agents cannot go here", and reaching for solid when you meant weight produces levels where every route is either free or impossible.

Asking for a path#

Two methods answer the same question and differ only in what they hand back. This asymmetry causes more lost evenings than anything else in the class.

  • get_id_path(from_id, to_id) returns Array[Vector2i] — cell coordinates.
  • get_point_path(from_id, to_id) returns PackedVector2Array — positions, with cell_size and offset applied.

Both take Vector2i cell ids as arguments. The input type does not change. Only the return type does. Feed cell coordinates into movement code and your agent creeps toward (12, 7) in pixels; feed positions into a tile lookup and every lookup misses. In untyped code neither mistake produces an error, which is a decent argument for annotating your locals even when the annotation looks redundant.

Getting the starting cell needs one more conversion. local_to_map() expects local coordinates, so to_local(global_position) first. If the layer never moves, local and global happen to be equal and you can get away with passing global position — until the day someone nudges the level node, and then every path is wrong by a constant amount, which reads convincingly like an off-by-one in your grid.

The same applies coming back out. get_point_path() returns positions in the layer's local space, because that is the space cell_size and offset describe. Convert with to_global() on the layer before handing them to an agent.

func find_path(from_global: Vector2, to_global: Vector2, allow_partial: bool = false) -> PackedVector2Array:
	var from_cell: Vector2i = ground_layer.local_to_map(ground_layer.to_local(from_global))
	var to_cell: Vector2i = ground_layer.local_to_map(ground_layer.to_local(to_global))

	if not _grid.is_in_boundsv(from_cell) or not _grid.is_in_boundsv(to_cell):
		return PackedVector2Array()

	var local_points: PackedVector2Array = _grid.get_point_path(from_cell, to_cell, allow_partial)

	var world_points: PackedVector2Array = PackedVector2Array()
	for point: Vector2 in local_points:
		world_points.append(ground_layer.to_global(point))

	_debug_path = world_points
	queue_redraw()
	return world_points

The bounds check at the top is not defensive noise. A target outside the region is the normal case the moment your player can walk off the painted area, and returning empty here is clearer than letting the query decide.

Walking it#

The follow loop is smaller than people expect. Hold the array. Aim at element zero. When you are close enough, drop element zero. Repeat until empty.

walker.gd on the CharacterBody2D:

extends CharacterBody2D

@export var pathfinder: GridPathfinder
@export var target: Node2D
@export var speed: float = 90.0
@export var arrive_radius: float = 4.0
@export var repath_interval: float = 0.5

var _path: PackedVector2Array = PackedVector2Array()
var _repath_countdown: float = 0.0


func _physics_process(delta: float) -> void:
	_repath_countdown -= delta
	if _repath_countdown <= 0.0:
		_repath_countdown = repath_interval
		_request_path()

	velocity = _steer()
	move_and_slide()


func _request_path() -> void:
	if pathfinder == null or target == null:
		return
	_path = pathfinder.find_path(global_position, target.global_position)


func _steer() -> Vector2:
	while not _path.is_empty() and global_position.distance_to(_path[0]) <= arrive_radius:
		_path.remove_at(0)

	if _path.is_empty():
		return Vector2.ZERO

	return global_position.direction_to(_path[0]) * speed

arrive_radius has a floor and a ceiling, and both are set by numbers you already know. It must be larger than the distance the agent covers in one physics frame — at 90.0 pixels per second and 60 ticks, that is 1.5 pixels — or the agent overshoots the waypoint, turns around, overshoots again, and vibrates in place forever. It must be smaller than half a tile, or the agent skips waypoints it never got near and cuts across corners. Between those two bounds it is a taste question. Outside them it is a bug, and both failure modes look like "my pathfinding is broken" rather than "my threshold is wrong".

The while rather than an if matters when the path is regenerated: the first waypoint of a fresh path is often the cell the agent is already standing in, and a while consumes it in the same frame instead of spending one frame walking backward to a point behind it.

Repathing on a timer rather than every frame is the cheap default. A grid search over a small level is not expensive, but it is not free either, and half a second of staleness is invisible on a walking enemy. Part 04 goes into what changes when there are forty of them.

Draw the path, or work blind#

Add this to grid_pathfinder.gd:

var _debug_path: PackedVector2Array = PackedVector2Array()


func _draw() -> void:
	if _debug_path.size() < 2:
		return

	for i: int in range(_debug_path.size() - 1):
		draw_line(to_local(_debug_path[i]), to_local(_debug_path[i + 1]), Color(1.0, 0.45, 0.1), 2.0)

	for point: Vector2 in _debug_path:
		draw_circle(to_local(point), 3.0, Color(1.0, 0.85, 0.2))

The z_index = 100 set back in _ready() is what keeps this line on top of the tiles instead of under them.

Run it. An orange line should leave the agent, run around the outside of the U, and end at the player. Move the player and watch it snap to a new route twice a second.

This is the single highest-value habit in the whole shelf. Every remaining bug in this part — and most of the bugs in part 03 — is either obvious or invisible depending on whether the path is on screen. An agent that hesitates at a corner tells you nothing. An agent that hesitates at a corner while the drawn path visibly zigzags through the wall tells you exactly which of two systems to open.

Leave it in. Put it behind a flag if you must, but leave it in.

The agent clips a corner#

Set the player diagonally across the tip of the wall and watch closely. The line passes through the point where two solid cells meet at their corners, and the agent slides through a gap that has no width.

diagonal_mode defaults to DIAGONAL_MODE_ALWAYS, which connects every cell to all eight neighbours unconditionally. Two walls touching corner to corner leave a diagonal connection between the two open cells, and the search takes it, because by its own rules the move is legal.

Three alternatives, in increasing strictness:

  • DIAGONAL_MODE_AT_LEAST_ONE_WALKABLE allows the diagonal if at least one of the two cells you cut past is open. Agents can round an outside corner but cannot squeeze through a corner-to-corner pinch.
  • DIAGONAL_MODE_ONLY_IF_NO_OBSTACLES allows it only when both are open. Agents keep a full cell of clearance around every wall corner.
  • DIAGONAL_MODE_NEVER removes diagonals entirely and gives four-directional movement.

Neither of the middle two is the right answer in general. AT_LEAST_ONE_WALKABLE gives shorter, more natural-looking routes and is right for a small agent whose collision shape fits comfortably inside a tile. ONLY_IF_NO_OBSTACLES costs you some path length and buys clearance, which is what you want when the agent's collider is close to tile-sized, because a path that is geometrically legal for a point is not legal for a circle. The deciding question is how much of a tile your agent's collision shape actually occupies. Measure it before choosing.

DIAGONAL_MODE_NEVER is not a fallback for the other two — it is a different game. Choose it when the movement itself is four-directional, not to fix corner clipping.

Heuristics have to match the movement#

Two properties, and learners routinely merge them into one:

  • default_compute_heuristic is the cost of moving between two connected points. What a step actually costs.
  • default_estimate_heuristic is the guess at the remaining cost to the goal. What the search uses to decide where to look next.

Both default to HEURISTIC_EUCLIDEAN. Pair them with the movement you settled on above:

  • DIAGONAL_MODE_NEVER pairs with HEURISTIC_MANHATTAN, because when you cannot move diagonally, straight-line distance systematically underestimates the real cost.
  • Diagonal movement pairs with HEURISTIC_OCTILE or HEURISTIC_CHEBYSHEV, which price a diagonal step correctly rather than as two moves.

A mismatched estimate does not usually break anything outright. It produces paths that are legal and correct-length but visibly odd — the agent takes an unmotivated dogleg, or hugs a wall for no reason, because the search explored the space in a strange order and the tie between two equal-cost routes broke the wrong way. With the path drawn on screen, this is a thing you notice. Without it, it is a thing you attribute to your steering code.

The finished configuration block:

	_grid.region = used
	_grid.cell_size = Vector2(ground_layer.tile_set.tile_size)
	_grid.offset = _grid.cell_size / 2.0
	_grid.diagonal_mode = AStarGrid2D.DIAGONAL_MODE_AT_LEAST_ONE_WALKABLE
	_grid.default_compute_heuristic = AStarGrid2D.HEURISTIC_OCTILE
	_grid.default_estimate_heuristic = AStarGrid2D.HEURISTIC_OCTILE
	_grid.update()

When there is no path#

Wall the player in completely, with no gap. Then look at what your code does with the result.

allow_partial_path defaults to false, and with it false an unreachable destination returns an empty array. Not a partial route, not a nearest approach. Empty. Any code that reaches for path[0] without checking dies on an index error, and it dies on the frame a door closes, which is rarely the frame you are testing.

Passing true changes the contract: you get a path to the reachable point closest to the target. That is the right behaviour for a guard who should press toward the player and wait at the door, and the wrong behaviour for an enemy who should give up and go back to patrolling — a partial path is indistinguishable from a real one at the call site, so "closest reachable point" quietly becomes "walks up to the wall and stands there", which is precisely the part 01 behaviour you came here to remove.

Whichever you choose, check is_empty(). The _steer() function above already does, which is why it survives this test by standing still rather than crashing. Decide what standing still should look like: an idle animation, a return to patrol, a shrug. Empty path is a real game state, not an error condition.

Checkpoint — definition of done#

  • The agent leaves its start position, travels around the outside of the U-shaped wall, and reaches the player — the exact case that defeated the part 01 chaser.
  • An orange line with waypoint dots is visible on top of the tiles for the whole run, and it re-routes within half a second of the player moving.
  • Every waypoint dot sits in the middle of a tile, not on a tile corner.
  • Printing _grid.is_point_solid() for a cell you painted a wall on returns true after rebuild() completes.
  • Moving the level node twenty pixels to the right in the editor does not change where the path is drawn relative to the tiles.
  • Sealing the player inside a closed box makes the agent stop and stay stopped, with no error in the output panel.
  • With DIAGONAL_MODE_ALWAYS restored, you can find a place on your map where the drawn line passes through the touching corners of two wall tiles; switching to DIAGONAL_MODE_AT_LEAST_ONE_WALKABLE removes it.
  • You can explain: why marking a cell solid before calling update() has no effect, and what that implies about when solid flags need to be re-applied.

Stretch (no instructions)#

  • Let the player break a wall tile at runtime and get the grid to agree, without rebuilding the whole thing every frame.
  • Add a slow layer with a weight of 4.0 and find the exact detour length at which the search stops going around it.
  • Give the walker two speeds and drive the switch from a state machine rather than from _physics_process — state nodes is the shape that fits.
  • Smooth the path: most of the waypoints in a straight run are redundant, and dropping them changes how the agent looks at corners.

If you get stuck#

  • Agent walks straight through walls, path drawn straight through walls → update() is being called after set_point_solid(). The output panel will be full of Grid is not initialized. Call the update method. — one per marked cell. Check the order in rebuild().
  • Agent walks through walls but only in one region of the map → an is_in_boundsv() guard is skipping cells, because region came from a get_used_rect() that does not cover your wall layer. Paint floor under every wall.
  • No line drawn, agent never moves, no errors → region is still Rect2i(0, 0, 0, 0). Print _grid.region at the end of rebuild(); if it is zero-size, get_used_rect() ran on an empty layer or on the wrong export.
  • Path is a few tiny numbers near the top-left of the screen → cell_size is still Vector2(1, 1). Check that ground_layer.tile_set is actually assigned, since a null TileSet means that line never ran.
  • Waypoints sit on tile corners and the agent scrapes along walls → offset is zero, or was set before update() and then never re-applied. It belongs in the geometry block, above the update.
  • Path is drawn under the tiles → z_index on the pathfinder node is lower than the tile layers'.
  • Everything is offset by a constant number of tiles → global_position is being passed to local_to_map() somewhere instead of to_local(global_position), or the two tile layers have different transforms.
  • Agent vibrates on the spot and never advances → arrive_radius is smaller than the distance covered in one physics frame. Compare it against speed / 60.0.
  • Agent skips waypoints and cuts across wall corners → arrive_radius is larger than half a tile.
  • Agent stutters or briefly reverses twice a second → the repath is handing back a first waypoint behind the agent. Confirm _steer() uses while, not if.
  • Index error on path[0] when the target is walled off → an empty array is the documented answer for an unreachable target. Guard with is_empty() before indexing, and decide separately whether you want allow_partial_path = true.
  • Agent standing on a wall tile produces no path at all → the start cell is solid, so it is not in the graph. Snap the agent to the nearest non-solid cell before querying, or keep spawns off wall tiles.
  • Everything worked, then you widened the level and half the walls stopped blocking → region changed, so update() ran, so every solid flag reset. Re-mark after every rebuild.

Next: Part 03 — off the grid, into the mesh. Read it when your level stops being made of squares, or when the grid gets large enough that the search cost starts showing up in the profiler.