Pathfinding with procedural generation

Help
, , ,
1

Godot Version

4.2

Question

Many of the tutorials I have watched on pathfinding include using a navigation layer, however I do not know how to implement it with a tilemap that has been procedurally generated.

2

This involves baking the navigation mesh at runtime. A good place to start is here: Using navigation meshes — Godot Engine (stable) documentation in English

Here’s an older thread that discusses the topic:
https://www.reddit.com/r/godot/comments/jhou98/is_it_possible_to_modifyocclude_a_navigation/

Here’s another one that covers a basic implementation: Using NavigationRegion2D, NavigationPolygons, and TileMaps - #11 by oncoremarco

Basically since your tilemap is procedurally generated, the navigationmesh will have to be procedurally generated as well. A navigation mesh can be created either by baking it with the help of the NavigationServer2D, or by adding vertices and convex polygon indices arrays manually. See NavigationPolygon — Godot Engine (stable) documentation in English

I have an implementation in 3d that generates the navigationmesh from vertices and polygons. and it works.

1 Like
3

Thanks for replying. I have created a navigation mesh (I think) using the NavigationPolygon through code. Does this mean I can now follow a pathfinding tutorial and it should (hopefully) work?

4

Adding onto to this, is there any where to view the Navigation mesh in game for debugging purposes?

5

This is my current code, where a path is formed, but it goes through walls and tiles:

extends Node2D

var borders = Rect2(1, 1, 152, 82)

signal player_location(spawn_position)
@onready var tileMap = $TileMap
const Spawner = preload("res://enemy_spawner.tscn")
 
var navigation_mesh: NavigationPolygon
var region_rid: RID

func _ready():
	randomize()
	navigation_mesh = NavigationPolygon.new()
	region_rid = NavigationServer2D.region_create()
	NavigationServer2D.region_set_enabled(region_rid, true)
	NavigationServer2D.region_set_map(region_rid, get_world_2d().get_navigation_map())
	generate_level()
	NavigationServer2D.region_set_navigation_polygon(region_rid, navigation_mesh)

func generate_level():
	var walker = Walker.new(Vector2(76, 41), borders)
	var map = walker.walk(1000)
	
	for location in map:
		tileMap.erase_cell(0, location)
	
	var player_position = map.front() * 16 
	set_player_spawn(player_position)
	
	var spawner = Spawner.instantiate()
	add_child(spawner)
	spawner.position = walker.get_end_room().position * 16
	
	walker.queue_free()
		
	var used_tiles = tileMap.get_used_cells(0)
	for tile in used_tiles:
		tileMap.erase_cell(0, tile)
		
	setup_navigation_mesh(map)
	
	tileMap.set_cells_terrain_connect(0, used_tiles, 0, 0)
	
	
func setup_navigation_mesh(map):
	# Create navigation mesh vertices based on the walker path
	var vertices := PackedVector2Array()
	var indices := PackedInt32Array()
	var tile_indices := []
	# Generate vertices from the procedural map data
	var index = 0
	for location in map:
		var position = location * 16  # Assuming tile size is 16x16
		
		var top_left = position
		var top_right = position + Vector2(16, 0)
		var bottom_left = position + Vector2(0, 16)
		var bottom_right = position + Vector2(16, 16)
		
		vertices.append(top_left)
		vertices.append(top_right)
		vertices.append(bottom_right)
		vertices.append(bottom_left)
		
		tile_indices.append(index)
		tile_indices.append(index + 1)
		tile_indices.append(index + 2)   
		tile_indices.append(index + 3)
		
		index += 4  # Move index forward by 4 for the next tile
		
		
		#vertices.append(position)
		#indices.append(index)
		#index += 1
	
	# Set the vertices for the navigation mesh
	navigation_mesh.vertices = vertices
	navigation_mesh.add_polygon(tile_indices)

	# Set the navigation region with the created navigation mesh
	NavigationServer2D.region_set_navigation_polygon(region_rid, navigation_mesh)



func reload_level():
	get_tree().reload_current_scene()

func _input(event):
	if event.is_action_pressed("ui_accept"):
		reload_level()

func set_player_spawn(spawn_position : Vector2):
	emit_signal("player_location", spawn_