Godot 3 Infinite Tilemap Chunked World Generation with O(n) Clearance-Based Pathfinding (AA*)

.World.gd

extends Node2D

export var __CHUNK_SIZE = Vector2(32, 32)
export var __SIMPLEX: OpenSimplexNoise = OpenSimplexNoise.new()
var __tile_weight = {}
	
#
# World Generation
#

func __world_global_to_chunk (pos):
	pos = $TileMap.world_to_map(pos)
	pos += __CHUNK_SIZE / 2
	pos /= __CHUNK_SIZE
	return pos.floor()

func __world_chunk_to_map (pos):
	pos *= __CHUNK_SIZE
	pos -= __CHUNK_SIZE / 2
	return pos

func __world_chunk_exists (chunk_pos):
	return AL_Utils.TilemapHasCell($TileMap, __world_chunk_to_map(chunk_pos))

func __world_update_tile_navigation (pos):
	__tile_weight[pos] = 1
	var check = pos + Vector2(-1, -1)
	if __tile_weight.has(check):
		var new_weight = __tile_weight[check]
		var max_ofs = new_weight
		for ofs in range(1, new_weight + 1):
			if not __tile_weight.has(pos - Vector2(ofs, 0)):
				max_ofs = ofs - 1
				break
			if not __tile_weight.has(pos - Vector2(0, ofs)):
				max_ofs = ofs - 1
				break
		__tile_weight[pos] += max_ofs

func __world_update_chunk_navigation (chunk_pos):
	var map_pos = __world_chunk_to_map(chunk_pos)
	for x in range(map_pos.x, map_pos.x + __CHUNK_SIZE.x):
		for y in range(map_pos.y, map_pos.y + __CHUNK_SIZE.y):
			var pos = Vector2(x, y)
			if __tile_weight.has(pos):
				__world_update_tile_navigation(pos)

func __world_generate_chunk (chunk_pos):
	# chunk already generated
	if __world_chunk_exists(chunk_pos):
		return
		
	randomize()
	
	var map_pos = __world_chunk_to_map(chunk_pos)
	for x in range(map_pos.x, map_pos.x + __CHUNK_SIZE.x):
		for y in range(map_pos.y, map_pos.y + __CHUNK_SIZE.y):
			var pos = Vector2(x, y)
			var noise = __SIMPLEX.get_noise_2d(x, y)
			
			var is_water = (noise < 0.01)
			var is_sand  = (noise < 0.05)
			var is_traversable = (not is_water)

			if is_water:
				AL_Utils.TilemapSetRandomCell($TileMap, pos, "water_1", "water_2")
			elif is_sand:
				AL_Utils.TilemapSetRandomCell($TileMap, pos, "sand_1", "sand_2")
			else:
				AL_Utils.TilemapSetRandomCell($TileMap, pos, "grass_1", "grass_2")
					
			if is_traversable:
				__world_update_tile_navigation(pos)
					
	var chunk_pos_down = chunk_pos + Vector2.DOWN
	var chunk_pos_right = chunk_pos + Vector2.RIGHT
						
	if __world_chunk_exists(chunk_pos_down):
		__world_update_chunk_navigation(chunk_pos_down)
	if __world_chunk_exists(chunk_pos_right):
		__world_update_chunk_navigation(chunk_pos_right)
						
func _ready ():
	randomize()
	__SIMPLEX.seed = randi()
	for x in [-1,0,1]:
		for y in [-1,0,1]:
			__world_generate_chunk(Vector2(x, y))

AL_Utils.gd

#
# AutoLoad
#

extends Node

func TilemapHasCell (tilemap, pos):
	return tilemap.get_cellv(pos) >= 0

func TilemapSetCell (tilemap, pos, tile_name):
	tilemap.set_cellv(pos, tilemap.tile_set.find_tile_by_name(tile_name))
	
func TilemapSetRandomCell (tilemap, pos, tile_name_1, tile_name_2):
	randomize()
	if randf() < 0.5 : TilemapSetCell(tilemap, pos, tile_name_1)
	else             : TilemapSetCell(tilemap, pos, tile_name_2)

More info: https://harablog.wordpress.com/2009/01/29/clearance-based-pathfinding/
Archived mirror: https://web.archive.org/web/20210914022339/https://harablog.wordpress.com/2009/01/29/clearance-based-pathfinding/