CODEWITHSUNDEEP
algorithmpath-findinga-star
user1984974
user1984974

Reputation: 129

Pathing algorithm for a continuous search space?

I'm currently making an RTS game in unity and I need a way to calculate the shortest path between two points on a continuous 2d plane where there are certain obstacles.

I have a start position, an end position, and a function that can test whether a position is valid. I need an algorithm that returns a sequence of points to move through in order to get to the destination.

Most of the pathing algorithms like A* and IDA* that I know of require discretized search spaces. I would divide the plane into a grid myself but I fear that it would result in zig zag patterns that look really unnatural when moving along the diagonal. Is there a way to alleviate this problem or a different pathing algorithm I can use? It doesn't even have to find the absolute shortest path, just a path that makes sense.

Upvotes: 1

Views: 1798

Answers (2)

Michael Zeng
Michael Zeng

Reputation: 9

You could create a zig-zaggy path then use Pure Pursuit to smooth it.

Upvotes: -3

serycjon
serycjon

Reputation: 540

One approach might be to discretize the search space by considering only points interesting for planing - points on the boundaries of the obstacles, for example only the corners of bounding boxes, and then use any of the algorithms you already know.

Another option would be to compute on a grid and then smoothen the best path found on the grid.

Upvotes: 1

Related Questions