How is this pathfinding system made?

Help and Feedback Scripting Support
#21

I think you can just use pathfinding without the person moving.

1 Like
#22

Can you tell us the context of what your trying to do? it may help us find easier solutions

#23

I’m just trying to implement a unique pathfinding system into my future games,
better than a beam or something lol.

#24

I’m unsure if it is custom or not–if the path is only constrained to a specific place on the ground, it might be.

In terms of if it’s possible to implement, the answer is absolutely. I implemented A* not too long ago (even though it was a bit rough, in terms of organization). If you search for ‘A* pathfinding’ or ‘Custom pathfinding system’ on the dev forum there should a quite a bit of posts and topics about it.

Also pinging, @IdiomicLanguage, as he’s making a pathfinding system, that might improve on some of Roblox’s current pathfinding shortcomings.

1 Like
#25

I will now risk brain damage by trying to edit the pathfinding system lol

#26

I never heard about A* considering it’s my first time doing a “custom pathfinding”, although do you think i can replicate this pathfinding system in a simpler way, this is confusing me

#27

If the grid is unweighted, you can simply perform a Breadth-First Search starting from your start location. It’s very simple:

function findShortestPath(src, dest)
	local queue = {src}
	local visited = {[src] = true}
	local parent = {}
	
	while #queue > 0 do
		local node = table.remove(queue, 1)

		if node == dest then break end

		for _, neighbor in ipairs(node.neighbors) do
			if not neighbor.isObstructed then
				-- you can have another separate routine updating this property
				if not visited[neighbor] then
					visited[neighbor] = true
					parent[neighbor] = node
					
					table.insert(queue, neighbor)
				end
			end
		end
	end
	
	if parent[dest] then
		-- if destination has a parent, there exists a path from start to finish
		
		local path = {}
		local temp = dest
		
		while temp do
			table.insert(path, temp)
			temp = parent[temp]
		end
		
		-- list of nodes from destination to source (start)
		return path
	end
end

It may also help to familiarize yourself with some of the basics of Graph Theory.

5 Likes
#28

Breadth First Search is like Binary Heap Right?

#29

Yes, you can use a breadth first search (BFS) or Dijkstra’s algorithm. BFS is the simplest.

Here is a copy of a place I implemented A* in for another pathfinding question a couple years ago. I tested the differences in performance between an ordered linked list, an ordered array, and a binary heap for the queue.

Here is the video of it working: Roblox Custom Pathfinder - YouTube

My question is, why limit yourself to a grid? I’m writing a pathfinder right now on a navigation mesh, but if you give me a suitable reason I’ll make it editable to run on a customizable grid when required. If you’re interested in seeing the current progress or supporting it, you can join the community here

Best wishes!

3 Likes
#30

Any way to make this system skip over diagonal grid spots?