What's the best method to get points of change along a path?

[xg1y (safe_distance)]

Hey, so I’m currently working on dynamic generation of maps for an AI to follow, the map is generated by being randomly selecting and placing pre-built segments and had then spent a few hours fiddling around with ROBLOX’s pathfinding to realise that it’s extremely unoptimised for large quantities of AI and am now going down the path of creating points for the humanoid to :WalkTo() however, I’ve run into an issue where I’m unsure of the best method to actually generate these node/points for the humanoid to move to.

My current method essentially cycles through all path parts and produces 3 parts relative to the part’s position and size. eg; Part1.CFrame = Path.CFrame * CFrame.new(-(path.Size.X/2)-2, 5.5,0) (creation currently purely for visualization, will be only using CFrame values when its properly working)

Now this works, however due to the “pathfinding” needing to be dynamic and cater to a wide variety of paths layouts, in which some path lengths may be only a few studs wide, it causes overlap and I see the issues that may come in the future.

I was thinking of cycling through all points made and essentially “cleaning it up” by iterating through all waypoints made until a part isn’t facing the same direction as the previous part (using Vector3:Dot()) and then removing all parts in between the first and last part, but am unsure if this is the optimal way to approach this.

Ultimately, I’m at a stage where I’m unsure if my entire method is just over complicating a simple solution that I’m not seeing, so any and all help is appreciated.

Thanks, xg

[daftcube]

@xg1y

that it’s extremely unoptimised for large quantities of AI and am now going down the path of creating points for the humanoid to :WalkTo() however, I’ve run into an issue where I’m unsure of the best method to actually generate these node/points for the humanoid to move to.

Could you define “large quantities of AI?”

Generally, I wouldn’t worry about something like extra points as shown here. Each uses a negligible amount of memory. Would you be willing to share any reasons for why these extra points are problematic at scale? If you are doing something with the points that is more than creating a list of “goals” to walk towards, then there definitely is a valid reason to clean this up.

@xg1y

I was thinking of cycling through all points made and essentially “cleaning it up” by iterating through all waypoints made until a part isn’t facing the same direction as the previous part (using Vector3:Dot() ) and then removing all parts in between the first and last part, but am unsure if this is the optimal way to approach this.

Your proposed algorithm here is O(n) if implemented correctly. I can’t imagine a way to do it better, but who knows; there might be some divide-and-conquer solution. Just be sure to do this against the literal points and not parts; extra instances in the datamodel isn’t generally a good thing.

If you still don’t want the extra points: the best way to not have them points is to never generate them in the first place. You say you are dynamically generating your map – do you think you could also generate a node graph for that map and then run a pathfinding algorithm against that graph?

Hope this helps.