Terrain Path With A* Pathfinding

Help and Feedback Scripting Support
,
#1
  1. I want to make a tower defense game where the enemies pathfind along a terrain path using A*. Something like what crazyman32 does in this video:

ROBLOX Terrain Path With Pathfinding

  1. What is the issue? I don’t actually know how to do the A* pathfinding. I am new to A* pathfinding and I havent found any roblox tutorials or sample scripts to help me out. Any sample scripts or links to tutorials would be greatly appreciated.

  2. I have tried using Region3 read voxels to find the terrain voxels of the right material but I don’t know how to do any of the A* stuff or where to start.

local region = Region3.new(Vector3.new(0,0,0), Vector3.new(512,1,512)) -- The region in workspace that is being scanned
region = region:ExpandToGrid(4) -- Expanding the region be voxel sized
--game.Workspace.Terrain:FillRegion(region, 4, Enum.Material.Brick)

local material, occupancy = game.Workspace.Terrain:ReadVoxels(region, 4) -- Reading the terrain voxels
local size = material.Size
local nodes = {} -- The table of terrain nodes for A* pathfinding?
for x = 1, size.X do -- Loop through X,Y,Z Directions for terrain stuff
	for y = 1, size.Y do 
		for z = 1, size.Z do
			if material[x][y][z] == Enum.Material.WoodPlanks then
				-- A* stuff?
				print("Material at (", x, y, z, "): ", material[x][y][z])
				print("Occupancy at (", x, y, z, "): ", occupancy[x][y][z])
--				table.insert(nodes, Something?)
				wait() 
			end
		end
	end
end
2 Likes
#2

Why you not try to see how A* actually work normally, then convert it in Lua? Here is a good Link: Introduction to the A* Algorithm

I hope it can help you @TSevik.

1 Like
#3

There aren’t many examples on the devforum of A* code wise but it’s pretty self explanatory ( as far the base/normal version goes, path-finding and A* can go way more in depth), there is pseudo code on Wikipedia (there actually used to be an article on the dev hub at some point too), but the main idea of A* is to find the shortest path from A to B while still being efficient, which Dijkstra algorithm was not (but it was sometimes more accurate) . In A* there is a closed and open set/table. The open set is the table that contains all the nodes (positions) that need to be evaluated next, that need to be checked to see if they are next best candidate in the path. Where-as the Closed set is almost the opposite its the set or table of nodes that we don’t need to visit or look at, or the nodes we have already visited.

A* also has heuristics and something often recalled as the f-score and G-score, the f score is calculated every step in the algorithm, it’s how the next node is chosen, and is calculated by Fscore = Gscore + heuristic , where G-score is the distance from start and the node and the heuristic (which can be more in-depth) is often just the distance from A-B. Starting at A For each Node, A* looks at it’s neighboring nodes adds them to the open set, checks to see which one is next best candidate by finding the node with the lowest F-Score in the open set then removing that node from the open set then adding it to the closed set, then it goes to that node and check it’s neighbors and so on and so forth until there are no more nodes left in the open-set. Assuming that each node kept reference of the node before it (the node it came from) and once everything is completed, (if it does, and it’s not un-solvable) nodes are retraced/traversed back to the start node by using those cached references giving you a path from A-B. That’s just the quick run down of the algorithm if you haven’t already i would highly recommend looking at the pseudo code on the Wikipedia Page. There also should be some lua-based examples of A-Star. i also have an old-ish example of A-star:

https://github.com/Jaycbee/A-Star

Here is the roblox implementation of the same thing above:
https://www.roblox.com/games/4292307301/A-Star-Pathfinding

Also Here is a very good series i’m going to recommend that be easily implemented to lua and to 3d:

This is also a good “visualization video” to start with :

if you need any help with the algorithm i would gladly help!

Now as far as terrain and A* my best guess is that Crazyman is using node based A* and is doing something similar to what you have in your code example and checking voxels and creating nodes at their positions or he could be generating a grid that are initially defined as “walls” and checking the nearest nodes to the voxels and setting them to a non-wall if that makes sense. Or even he could just be placing the nodes as the red thing is dragged around, in that case reading voxels isn’t, needed at all really. But Another thing you can do is just ask him right?
cc @Crazyman32

And you know what if i have time i might make a quick example, maybe…

10 Likes
Custom Pathfinding Just Isn't Working
Pathfinding Help Needed (NPCs getting Stuck)
#4

Look at this page:

It explains in detail what and how A* works as well as how to implement it in your code.

I would also recommend looking at Dijkstra algorithm.

4 Likes
#5

Thanks for all the great resources everyone! Also I don’t think that I can just ask crazyman32 to open source something he made ~5 years ago just for me.

2 Likes
#6

Maybe not open source but it doesn’t hurt to ask for input !

2 Likes
#7

Do Roblox Pathfinding system was based on a A* algorithm?

#8

If I remember correctly yes, it uses some version/type of A*, someone might have to back me up on that claim though. This post/thread talks a little about the current pathfinding service, not really about the algorithm behind it and it’s a bit old but idk it might be of some use.

1 Like