Find and draw shortest route around a mesh collider

Question

Hi,

I couldn't find any code example for the following problem. I really hope someone could help. I want to let player draw a path (the black line in the example image). Then I want to render the shortest possible route (green line). The drawing can start and end anywhere but the route should always start from the players position (blue dot in the image) and go around the grey areas.

My current functions for drawing the line are like below (following a tutorial) but then I released my incompetence :)

alt text

     void ResetLine ()
     {
         lineRenderer.positionCount = 0;
         targetPos = 0;
     }
     void CreateLine()
     {
         fingerPositions.Clear();
         fingerPositions.Add(Camera.main.ScreenToWorldPoint(Input.mousePosition));
         fingerPositions.Add(Camera.main.ScreenToWorldPoint(Input.mousePosition));
         lineRenderer.SetPosition(0, fingerPositions[0]);
         lineRenderer.SetPosition(1, fingerPositions[1]);
     }
     void UpdateLine(Vector2 newFingerPosition)
     {   
         fingerPositions.Add(newFingerPosition);
         lineRenderer.positionCount++;
         lineRenderer.SetPosition(lineRenderer.positionCount - 1, newFingerPosition);
     }

Answer 1

Best Answer

Answer by Llama_w_2Ls · Feb 22, 2021 at 10:21 AM

You could try a pathfinding algorithm. They calculate all possible routes from one point to another that don't cross paths with any walls/obstacles and return the shortest path. You can try the A* pathfinding algorithm, from the asset store, which uses a grid to do this. Or you could implement it yourself, if you're up for the challenge. @w-harri

Add comment · Show 1 · Share

w-harri · Feb 22, 2021 at 07:12 PM 0

Share

Thanks! That seems like a good direction to go.

Answer 2

Answer by Bunny83 · Feb 22, 2021 at 10:33 AM

Well your problem is very vague. The initial problem seems to be you want to get a player from A to B. What if there's no colliders in the way? so you could fly / walk / move in a straight line. You usually want to do the mesh "hugging" when there's an obstacle in the direct line of sight. So once you reach the bottom most point on the first mesh you get a direct line of sight to the target so what on earth would cause your player to take that detour you drawn? Based on what decision? What if there are 10 other colliders? Does the player have to visit all of them? As I said the initial problem is not clear at all. Also you said the shortest path. However you drawn a hugging path which naturally is longer on any concave mesh.

Finally the most important question: Is this a 2d problem or 3d problem? In 3d it becomes much more difficult and my first questions get even more degrees of freedom. So your exact wanted behaviour has to be narrowed down first. Note that getting pathfinding right is a quite tough topic.

Add comment · Show 1 · Share

w-harri · Feb 22, 2021 at 03:13 PM 0

Share

Thanks for the clarifying questions. I try to make more sense:

It's a 2D problem
First the player draws a route (with mouse or finger) that they would like to move the blue dot.
So the initial input for the final route would be the line that the players draws. The first target is the starting point of that line. If the starting point cannot be reached due an obstacle it should find the shortest possible route to go as close as possible to that point.
The route should be calculated after the player has finished drawing the line (=lifts the mouse button or the finger).
The final route (green line) can't go through the obstacles (grey areas in the picture).
The final target (=where player stops drawing) should be reached with $$anonymous$$imum distance while still following the drawn line as closely as possible (as long as the the line isn't inside the obstacle).

I hope this clarifies. Thanks for the answer!

Find and draw shortest route around a mesh collider

2 Replies

Your answer

Follow this Question

Related Questions