Flying bird pathfinding

I want to make a flying bird that follows the player. Simple enough.
The problem is, because my game is procedurally generated, the bird need to be able to pathfind. Simple. I’ll use PathfindingService. Because my bird needs to be able to fly, PathfindingService won’t work in my case because I don’t think it supports flying characters. What could I do to get the bird to properly pathfind?

I have tried using PathfindingService, but it gives me the no path found error because the destination is in the air. I tried implementing my own pathfinding but I can’t seem to get the A* algorithm to work. I was able to check if a position in 3d space can be occupied by the bird, by checking if the closest distance to any surface is greater than my bird’s size. That’s as far as I got. Any help on the A* solution would be appreciated.

TL;DR How do I make a pathfinder for flying characters?

(And, if anyone is wondering, I’m using my alt because my little sister set my main’s age to 6 years old and Roblox won’t change it no matter how many support emails I send.)

2 Likes

Never really worked with A* myself but maybe you could try to set up a grid of pathfinding nodes in your world and then treat every node that can’t fit your bird at its position as untraversable. Then treat adjacent nodes as being connected by paths. From there you should be able to implement A* based on one of the many tutorials such as this one online. Don’t count on this being a perfect solution though as I’m not very experienced with custom pathfinding myself.

You can either use A* or dijkstra. I’ve used dijkstra in the past within roblox.

Here is a video: https://www.youtube.com/watch?v=EFg3u_E6eHU

I’ve got this from Github GitHub - matthewdeguzman/Maze-Generator-and-Path-Finder: Roblox game that generates random mazes from a given size and solves them using either a breadth-first search or Dijkstra's algorithm, I will place the code below:

local Dijkstra = {}

-- Gets services
local ReplicatedStorage = game:GetService("ReplicatedStorage")
local RunService = game:GetService("RunService")

-- gets values
local values = ReplicatedStorage:WaitForChild("Values")
local clear = values:WaitForChild("Clear")
local finishClear = values:WaitForChild("FinishClear")

-- gets module scripts
local guiScripts = require(ReplicatedStorage:FindFirstChild("GUIScripts"))
local helper = require(ReplicatedStorage:WaitForChild("Helper"))

-- Begins Dijkstra's algorithm
-- grid: adjacency list of every wall and path block
-- start: starting position
-- endPos: end position
function Dijkstra.solve(grid, start, endPos, size)
	
	-- removes any pathblocks if they previously existed
	helper.removePaths()
	
	-- creates a new model to hold the pathblocks
	local pathBlocks = Instance.new("Model")
	pathBlocks.Name = "PathBlocks"
	pathBlocks.Parent = workspace
	 
	-- Constant to simulate an infinite value
	local inf = 10000000
	
	-- table that contains the visited path blocks
	local vis = {}
	
	-- table that holds the shortest distance from the starting point to every path block
	local dist = {}
	
	-- table the holds the current path
	local prev = {}
	
	-- Initializes an indexed priority queue 
	local ipq = require(game:GetService("ReplicatedStorage"):FindFirstChild("IndexedPriorityQueue"))
	local queue = ipq.new(#grid)
	queue:initialize()
	
	-- Initializes all of the tables with default values
	for i = 1, #grid do
		table.insert(vis, false)
		table.insert(dist, inf)
		table.insert(prev, 0)
	end
	
	-- Initializes the distance from the starting node to be 0 and places it in the queue
	dist[start] = 0
	queue:insert(start, dist[start])
	
	-- Begin's pathfinding andd the timer
	guiScripts.activateTimer()
	while not queue:isEmpty() do
		
		-- Remove the pair with the smallest value from the queue
		-- and assign variables to the key and the distance
		local pair = queue:poll()
		local index = pair[1]
		local distance = pair[2]
		-- set visited to true since we are now on the path block
		vis[index] = true
		
		-- If we've already found a better distance to the current path block
		-- than the one that has been retrieved, we continue because it does not
		-- hold the shortest path
		if dist[index] < distance then
			continue
		end
		
		-- we place a block down based on the index of the wall to 
		-- show we are exploring the path
		-- this can be removed if you want to remove visualization
		helper.placeBlock(index,size)
		
		-- looks at all of the connected path blocks to the current path block
		-- and determines if their distances can be improved
		for i, value in ipairs(grid[index]) do
			
			-- If we've already visited the neighbor than we're assuming
			-- we've already found a better path and we finish the iteration
			if vis[value] then continue end
			
			-- retrive the new distance by adding the edge cost (will always be 1 because
			-- this is an unweighted graph)
			local newDist = dist[index] + 1
			
			-- if the new distance is shorter than the previous distance
			-- we will update it
			if newDist < dist[value] then
				
				prev[value] = index -- update prev to hold the shortest pathblock
				dist[value] = newDist -- update dist to hold the shortest distance
				
				-- if the path block hasn't been explored yet, then we will be 
				-- placing it in the queue
				-- else we will be updating the distance of the path
				if not queue:contains(value) then queue:insert(value, newDist)
				else queue:decreaseKey(value, newDist) end
				
				-- Runservice wait to get shorter wait time
				RunService.Heartbeat:Wait()
			end
			
		end
		
		-- If we've reached the end position than we can break out of the loop
		-- because we've found the shortest path to the end position
		if index == endPos then 
			-- ends the timer because we've found the end
			guiScripts.stopTimer()
			
			-- updates dijkstra's solve time
			guiScripts.updateTime("Dijkstra")
			break 
		end
		
		-- if we want to clear the maze then we stop the timer and exit the script
		if clear.Value then
			finishClear.Value = true
			return
		end
		
	end
	
	-- Creates a path table that will be one plus the size of the shortest distance
	-- and fills it with a default value
	-- the variable at is the path block which connects to the end
	local at = prev[endPos]
	local i = dist[endPos] - 1
	local path = table.create(dist[endPos]-1, -1)
	helper.drawPath(i, prev[endPos], prev, table.create(i,-1),size)
end

return Dijkstra

Helper.lua

local helper = {}


-- Helper helper functions -- 
-- These functions were made helper functions because i needed to call them
-- within the module scripts and module scripts can't require them selves

-- given the placement number of a block and the size of the maze, it returns
-- the column and row number it was placed in
local function _unbox(position, d)
	local a = {}
	table.insert(a, math.ceil(position / d))
	a[2] = position - (a[1] - 1) * d
	return a
end

-- Given the x and z position of a block, it returns the x y and z coordinates
-- based on the size of the block
local function _getPos(x, y, z)
	return {(x-1)*4, y, (z-1)*4}
end

-- opposite of the unbox function, given the row and column number of the block
-- it returns the placement number of the block given the maze's size
local function _box(y, x, size)
	return x+(y-1)*size
end

-- Given a posiiton and size of the maze, it places a pathblock
function _placeBlock(position, d)
	-- receives it's position
	local pos = _unbox(position, d)
	
	-- Creates part and places it in pathblock model
	local part = Instance.new("Part")
	part.Color = Color3.fromRGB(159, 161, 172)
	part.Anchored = true
	part.Size = Vector3.new(4,2,4)
	part.Material = Enum.Material.Neon
	part.Position = Vector3.new((pos[1]-1)*4, 4, (pos[2]-1)*4)
	part.Parent = workspace:FindFirstChild("PathBlocks")
end

-- Functions
function helper.unbox(position, d)
	return _unbox(position, d)
end

function helper.getPos(x, y, z)
	return _getPos(x, y, z)
end

function helper.box(y, x, size)
	return _box(y, x, size)
end


function helper.placeBlock(position, d)
	_placeBlock(position, d)
end

-- Creates a block given certain perameters
function helper.createBlock(name, sz, mat, brkClr, pos, par)
	local part = Instance.new("Part")
	local p = _getPos(pos[1],pos[2],pos[3])
	part.Name = tostring(name)
	part.Size = Vector3.new(sz[1],sz[2],sz[3])
	part.Material = mat
	part.Color = Color3.fromRGB(brkClr[1],brkClr[2],brkClr[3])
	part.Position = Vector3.new(p[1],p[2],p[3])
	part.Anchored = true
	part.Parent = par
end

-- Draws the path of the solved maze
-- i: the number of blocks needed to be placed
-- at: the placement number of the block that needs to be placed
-- prev: a table that holds the paths of how to get to certain blocks from the starting posiiton
-- size: size of the maze
function helper.drawPath(i, at, prev, path, size)
	
	-- Gets the runservice of the game and the pathblocks model
	local RunService = game:GetService("RunService")
	local ReplicatedStorage = game:GetService("ReplicatedStorage")
	
	local values = ReplicatedStorage:FindFirstChild("Values")
	local clear = values:FindFirstChild("Clear")
	
	local finishClear = values:FindFirstChild("FinishClear")
	local pathBlocks =  workspace:FindFirstChild("PathBlocks")
	
	-- reconstructs the path by continuously updating the connected paths
	-- until at is equal to zero, which means that we've found the beginning
	-- because we set it's path to be 0
	while i >= 1 do
		path[i] = at
		at = prev[at]
		-- stops early so it doesn't place a block on the start
		if prev[at] == 0 then
			break 
		end
		i -= 1
	end

	-- get's the model we created called path blocks and clears all of it's children
	pathBlocks:ClearAllChildren()

	-- we then traverse the path and place a block on every path block we traverse
	-- to outline the shortest path
	for i, v in ipairs(path) do
		
		-- If the user has decided to clear the maze, then we stop the function
		if clear.Value then
			finishClear.Value = true
			return
		end
		_placeBlock(v,size)
		-- optional wait that can be removed 
		RunService.Heartbeat:Wait()
	end

	-- once we've finished constructing the path, we turn it blue to indicate that
	-- we've finished
	for i, v in ipairs(pathBlocks:GetChildren()) do
		v.Color = Color3.fromRGB(82, 124, 174)
	end
	
end

-- Destroys a path if it exists
function helper.removePaths()
	local path = workspace:FindFirstChild("PathBlocks")
	if path ~= nil then path:Destroy() end
end




return helper

A* Is deceivingly simple. From the outside looking in it seems impossible but once you understand a few rules it actually becomes very easy to implement.

This video by Sebastian Lague is how i learnt it, and it should be easy to apply this to a 3d axis for your flying bird :slight_smile:

1 Like

I wasn’t responding to you. 30char

Yes, A* would work too I agree.