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…