A* pathfinding over procedural terrain in Godot: Vega de Poniente, the vineyard town

Leave Brumacosta heading west and follow the meadow for 490 m, and you reach Vega de Poniente: an arch with the town's name in orange, houses with reddish roofs, Gael at the post office and, behind the town, a vineyard. It has four rows of vines with purple bunches, wired between posts, and next to them a wine press with three barrels. Dalia, the winegrower, says her grapes taste "salty" because they grow in the sea wind. Olmo, who runs the press, reassures you that the way back follows the meadow, with no forest or water to cross.

That last line isn't flavour text. It's exactly what I asked the algorithm that drew the road to do.

How it's built

Where to put the town. Before building anything I sampled the island every 32 m, looking for spots that were flat, dry and more than 170 m from the existing mods. Vega de Poniente ended up at (−352, 448). This is its configuration for the shared builder (it's the only town with a 50 m clearing):

village = Village.new({
	"name": "VEGA DE PONIENTE", "center": CENTER, "yaw": YAW,
	"houses": [Vector3(-18, 0, -14), Vector3(16, 0, -16), Vector3(-19, 0, 3), Vector3(20, 0, 2), Vector3(-16, 0, 20), Vector3(17, 0, 19)],
	"plaster": [Color("d8c49a"), Color("c7b7a2")], "roofs": [Color("a0613f"), Color("7a5a4a")],
	"markets": [[Vector2(8, -3), Color("b5692f")], [Vector2(-8, -3), Color("6f8f3a")]],
	"landmark": "vineyard", "landmark_at": Vector2(0, -38), "name_color": COLOR, "radius": 50.0,
})

Where the road goes. That's where A* comes in. Gotic doesn't store its island: the height at any point is computed from fixed-seed noise (Island.height_at). On top of that function I laid a grid of 4 m cells and ran A* with three rules:

• water is forbidden;
• each step costs more the steeper it is;
• forest also adds cost, so the road goes around it when it can.

Searching a road of several hundred metres this way takes seconds, which is not something you can do while the game boots, let alone on a phone. So I ran it outside the game and saved the result as a constant in the mod: 25 world points, from Brumacosta's arch to Vega de Poniente's. Since the terrain comes from a fixed seed, those points stay valid as long as the island doesn't change. If it ever does, the road test will catch it: it walks every stretch metre by metre and fails if it touches water or if a slope goes beyond what the character can climb.

All the game has left to do is draw it. WorldArt.road turns the points into a strip of dirt that hugs the ground, split into 110 m meshes so distant stretches aren't drawn. On PC, building a town takes about 50 ms and its road between 46 and 104 ms.

The result is a gentle walk: the steepest part of the Poniente road has a slope of 0.09, while the character can climb up to 0.305. And the road turned out to be useful for more than this town. When the farm arrived, its 239 m branch road joined it (maximum slope 0.11, no forest).

The recipe for adding another town is now written down: copy a town's folder, change its centre, rotation, dictionary and road, and let the test tell you whether it crosses water or an impossible slope.

Still unverified

The A* ran outside the game and its script isn't in the repository: what remains are its points and the test that keeps an eye on them. If I change the island, I'll have to write it again. FPS with all four towns on a phone hasn't been measured, because the phone was locked when the APK was installed. This screenshot cost 329 draw calls and about 166,000 triangles on PC.