PAKit: Pathfinding Algorithms Toolkit

PAKit is a high-performance, context-aware navigation framework for Godot 4.x. It enables NPCs to navigate dynamic, destructible, or procedurally generated tile-based worlds using multiple search strategies.

Implementation Guide

1. The Global Core (PAKitCore)

Place a PAKitCore node in your main world scene. This node manages the mathematical grid and world-level path costs.

• Setup: Assign your TileMapLayer to the Tilemap property in the Inspector.
• Initialization: If your map is procedural or changes size, call:

pakit_core.initialize(my_tilemap_layer)
pakit_core.update_region(Rect2i(start_x, start_y, width, height))

• Main Weight APIs:

pakit_core.update_cell_weight(coords, 1.0)
pakit_core.update_layer_cell_weight(&"lava", coords, 10.0)

2. The Agent Controller (PAKitNavigator)

Add a PAKitNavigator node as a child of your NPC.

• Targeting: To move the NPC, simply call:

navigator.set_target(player.global_position)

• Movement API: Connect to the navigator's main signals to drive character logic:

var ai_direction := Vector2.ZERO

func _on_movement_requested(direction: Vector2):
	# direction is an offset to the next waypoint (not normalized speed)
	ai_direction = direction

func _physics_process(delta: float) -> void:
	var deadzone := 8.0

	if ai_direction.x > deadzone:
		velocity.x = speed
	elif ai_direction.x < -deadzone:
		velocity.x = -speed
	else:
		velocity.x = move_toward(velocity.x, 0.0, speed * delta)

	# Optional: jump when next waypoint is clearly above
	if ai_direction.y < -24.0 and is_on_floor():
		jump()

	move_and_slide()

func _on_target_reached():
	ai_direction = Vector2.ZERO

• Layer Preference (per NPC):

navigator.set_layer_importance(&"lava", 2.0)
navigator.set_layer_importance(&"safe_floor", 0.5)

3. Making the World Dynamic

To make the AI avoid obstacles or prefer specific paths, update tile weights whenever the world changes:

# When a tile is destroyed (e.g., mining)
pakit_core.update_cell_weight(coords, 1.0) # 1.0 is the cost of empty air

# When a tile is created (e.g., building)
pakit_core.update_cell_weight(coords, 10.0) # High cost makes AI avoid it

For layer-specific behavior shared by all agents, update named layers:

# Mark dangerous cells as expensive in a specific layer
pakit_core.update_layer_cell_weight(&"lava", coords, 12.0)

Note: Navigators recalculate paths continuously (based on path_refresh_time) and react to weight updates without extra manual refresh calls.

---

Configuration

Property	Description
path_refresh_time	Frequency (seconds) to update the path for moving targets.
algorithm_selection_mode	Set to FIXED, RANDOM, or CONTEXT (distance-based).
default_algorithm	Algorithm used when selection mode is FIXED.
debug_tile_costs	Visualizes the weight of tiles.
stuck_detection_enabled	Enables stuck detection and recovery logic.

Add Your Own Algorithm

If you want to add a new search algorithm (for example BFS, IDA*, JPS, or a custom variant), extend the addon in these steps.

1. Add the Enum Value

In PAKitAlgorithms, add your new value to the algorithm enum.

Also update these helper maps/functions so UI/debug remains correct:

• algorithm_color
• to_name()
• get_default_list() (optional, if you want it included by default)

2. Implement the Search Function

In PAKitSearch, add a new method such as:

func find_path_bfs(start_grid: Vector2i, end_grid: Vector2i, layer_profile: Dictionary = {}, grid: AStarGrid2D = null, max_up_tiles: int = -1) -> PackedVector2Array:
	# implement your algorithm here
	return PackedVector2Array()

Recommended: reuse existing helpers to keep behavior consistent with the rest of the addon:

• get_neighbors(...)
• get_step_cost(...)
• reconstruct_grid_path(...)
• grid_path_to_world_path(...)

3. Wire It in the Core Dispatcher

In PAKitCore.generate_path(...), add a new match case that calls your method:

PAKitAlgorithms.algorithm.BFS:
	result_path = searcher.find_path_bfs(start_grid, end_grid, layer_profile, astar_grid, max_up_tiles)

4. Make It Available in Navigator Selection

No extra code is needed in PAKitNavigator if it already uses the algorithm enum. Your new value will be selectable through:

• default_algorithm
• random_algorithms
• PAKitAlgorithmContext resources

5. Optional: Extend Context Heuristics

If you use selection_mode.CONTEXT, you can update PAKitAlgorithms.choose_by_context(...) so your new algorithm can be picked automatically for specific distance/target patterns.

6. Validate

After adding the algorithm:

• Run a scene with algorithm_selection_mode = FIXED and your new algorithm selected.
• Enable debug path color to confirm the selected algorithm path is used.
• Test with max_up_tiles enabled to ensure climbing constraints still behave as expected.

Add Your Own Heuristic

If you want to add a new heuristic (for example Chebyshev, Octile, or a custom risk-biased estimate), extend the addon in these steps.

1. Add the Enum Value

In PAKitAlgorithms, add your new value to the heuristic enum.

Also update these helper functions so inspector/debug names remain clear:

• to_heuristic_name()
• get_default_heuristic_mode() (optional)

2. Implement the Heuristic Formula

In PAKitAlgorithms.estimate_heuristic(...), add a new match branch for your enum value.

Example:

heuristic.CHEBYSHEV:
	return max(dx, dy)

Keep in mind:

• If you want A* to remain optimal, use an admissible heuristic.
• If you intentionally want faster but less optimal routes, allow an aggressive estimate (similar to weighted modes).

3. Ensure the Searcher Uses It

PAKitSearch already routes heuristic evaluation through:

• set_heuristic_settings(...)
• heuristic_distance(...)
• PAKitAlgorithms.estimate_heuristic(...)

So if your formula only needs (a, b, mode, weight), no extra wiring is needed.

4. Expose It in Context/Navigator (If Needed)

The following fields are already exported and will include your new enum value automatically:

• PAKitNavigator.default_heuristic_mode
• PAKitAlgorithmContext.heuristic_mode

If your heuristic needs extra tuning values beyond heuristic_weight, add new exported fields and pass them through the same flow used by selected_heuristic_mode and selected_heuristic_weight.

5. Validate Behavior

After adding the heuristic:

• Set algorithm_selection_mode = FIXED and force ASTAR.
• Compare path result and timing against MANHATTAN and ZERO on the same target pairs.
• Test at least one short path and one long path scenario.
• If the path shape does not change, verify whether your map has a unique optimal route (this is normal).