Pathfinding in a city builder

Help
, ,
1

Godot Version

4.2

Question

I am building a small 2D village-management game. In my design there will be a multitude of villagers assigned to particular production buildings, service buildings etc. I want to implement a pathfinding algorithm, so that the villagers will navigate around buildings and not collide with one another.

I was thinking on using the navigation layers on my tilemap, however when I have a ground tile that is passable and a building tile on top which is not, the pathing algorithm declares that tile as passable.

If I were to use the NavigationRegion/NavigationPolygon and Agents for villagers I am not sure how to change the navigable area when a building is placed. Is it possible to somehow “subtract” from a NavigationPolygon?

What is the best way to approach this subject?

2

you have to rebake the navmesh to have it consider new buildings. For big maps you probably want to do a chunk system so you dont have to rebake the whole mesh

3

Sorry, forgot to mention that it is a 2D game, from what I’m reading the Navmesh does not work in 2D

4

yes it does work in 2d. Or are you doing a sidescroller?

5

No, a top-down village manager, with a preset map size. Could you point me to a relevant resource/tutorial so I could read up more?

6

Heres one where he is NOT baking it, but doing it by hand:

Heres one with tilemaps:

and here a general demo:

all of this can be done in code obviously

1 Like
7

I followed the second tutorial, however I encounter an issue. When I set up an object with StaticBody2D parent in GUI and draw the initial navigation outline by hand, it works just fine. However, when I add a new object to the scene (also set up as a StaticBody2D with collider and set in the relevant group) and try to rebake the navigation mesh, The collision area does not change.

This is the code for the NavigationRegion2D object:

extends NavigationRegion2D


func _ready():
	var new_navigation_mesh = NavigationPolygon.new()
	var bounding_outline = PackedVector2Array([Vector2(0, 0), Vector2(0, Grid.total_map_size.y), Vector2(Grid.total_map_size.x, Grid.total_map_size.y), Vector2(Grid.total_map_size.x, 0)])
	new_navigation_mesh.add_outline(bounding_outline)
	new_navigation_mesh.make_polygons_from_outlines()
	navigation_polygon = new_navigation_mesh
	bake()

func bake():
	bake_navigation_polygon()

func _on_building_list_placed(building): ### Connects when a building is placed in the scene
	bake()

These are the parameters of the NavigationRegion:
image

8

Thi sprobably has to do with the SourceGeometryMode.
I think right now you have selected groups. Are you sure the new building is inside the “navigation” group?

9

I restarted the editor and had the same setup and now it works O.o
Thanks for all the help!
EDIT: No it doesn’t I forgot to turn off my “hacky” solution -.-

1 Like
10

Now this is getting strange.
I resorted to using NavigationMeshSourceGeometryData2D to do it step by step. With my code:

func bake():
	var source_geometry_data = NavigationMeshSourceGeometryData2D.new()
	NavigationServer2D.parse_source_geometry_data(navigation_polygon, source_geometry_data, get_node("/root/Root"))
	NavigationServer2D.bake_from_source_geometry_data(navigation_polygon, source_geometry_data)

If i look inside with:

obstructions = source_geometry_data.get_obstruction_outlines()

When buildings are placed, we have very nice obstruction outlines:
[(561, 176), (625, 176), (625, 256), (561, 256), (561, 176)]
But, the shown polygon did not change. I was at a complete loss.
HOWEVER, when I added queue_redraw() to the bake() function, the polygons got updated. I have no idea why this happens, shouldn’t the editor automatically redraw the polygons?

11

apparently it doesnt redraw when you call the bake_from_source_geometry_data

12

When you change a NavigationRegion node navigation mesh in scripts you also need to set it again in scripts to update the debug.

The debug is drawn by the NavigationRegion node and the region node is not aware what you do in scripts or with the server.

2 Likes