# Calculating a path along surfaces from point A to B?

Hello, I’m trying to find a way to calculate a path between Point A to B along the surfaces of the intruding parts such as the images below where:

Given
• Red = Point A
• Green = Point B
• Yellow = Corners the path reached in respect of the part’s size
• Pale green = calculated path from Point A to B

In some cases the algorithm works for certain rotations of the part, such as the images above, but there’s scenarios where the path fails to complete because it’s out of the part bounds in respect of the direction from point A to B:

Given
• Pink = Corner points of the closest surface
• Yellow plane = Plane the direction path should reflect off
• Red = Point A
• Green = Point B
• Pale green = Path

I’ve been stuck with this problem for a couple days now & ran through all my options; thinking that I took the wrong approach. Has anyone experimented with this type of problem, or know of a better apparoach?

I’ve attached the file of a test place with the code for some reference of what I’m currently doing
path help.rbxl (26.6 KB)

3 Likes

This looks like a really cool project. It must have taken a lot of scripting?

1 Like

I agree it is very cool it has a lot of potential.

2 Likes

Indeed! I’ve researched so many different things to get to this point, but i’ve reached a dead end fiddling with what i know

bumping for exposure reasonings…

There might be a simpler way but a [very hard] way that would be guaranteed to work would be:

1. Create a ‘Part’ union operation (not roblox’s but your own).
[Involves connecting two intersecting parts at their intersection and removes the overlap region]
Triangulate the resulting union with a triangulation algorithm.
2. First work forwards and backwards from the surface each point starts on. Work out what parts are going to be traversed and union them.
3. Look up shortest path approximation on triangulated meshes. The large union you create is your triangulated mesh. Perform that algorithm to get your final result.

An alternate (simpler) untested idea I had which might generate a path (but not the shortest):
[This will not always work when there is a “hole” in the set of parts that the path will traverse past to get from A to B. I.e. It should be topologically equivalent to a sphere/ can continuously deform shape into sphere.]

initialise a variable called currentPos to be equal to A

1. Vector project the vector (from currentPos to B or B-currentPos) onto the surface/plane that the path is currently on.
2. Move forward along the projected direction and work out where this hits an edge, and then repeat 1. for the next surface it is now on (from the position where it hits the edge) remembering to update currentPos. Be sure to raycast along that direction too in case the path hits another part before it reaches an edge of the current surface it is on.
3. If 2. results in a “ray” that starts on an edge, but moves off the square-shaped surface rather than through it, flip the direction of the projected vector 180 degrees reflect direction of projected vector in the edge currently sat on to now ensure it goes along square-shaped surface.
4. When and if you reach the surface B is on, connect the path to B for the last step.

I’m not sure if this will always work but I have a feeling it might when the path doesn’t have a “hole” it can traverse through. Sorry if what I mean by “hole” seems a bit vague. It’s just that if you imagine a hole shape constructed with parts and let point A start on a surface within the inner hole, and let point B start on an outer surface which is not within the inner hole -> path can loop forever sometimes with above algorithm.

2 Likes