- Home /
Start/End zigzag coverage region algorithm
I've spent a few days wackin my head on this problem and cant figure it out.
I've been trying to create an algorithm that I give a start/end and it would figure out a zigzag formation in a grid like the one in the image.
I've search around to see if I could find this/similar algorithm that creates this formation in other languages, but sadly I haven't been able to find anything.
I would be very grateful if someone can help or even point me in a direction that I can research more into this problem, thanks in advance.
Answer by Bunny83 · 2 days ago
I don't think it's possible to have such an algorithm that only has local awareness because you can always end up in situations you can't escape. Also there are naturally certain situations where it is impossible to fill the whole space without overlap. Just think about a "room" that has only one entrance that is 1 tile wide. So you can enter the room but never exit again since there's no room for it. As soon as you have 2 such situations it's impossible to fill both rooms as you would need to end in such a room.
So it's not really clear what your goal is. If it's just about pathfinding, such a path would be the lease efficient path. To me it makes not much sense why your path would turn at certain points considering starting at S. For example why does your line turn to the right after 5 steps? The line from above does not yet exist, So it's an arbitrary choice which is not really based on any logics here. So if you want a certain behaviour you have to be more specific. Just running randomly around has to potential to get stuck so you would need to back track and retry. A full analysis of the map before starting is probably too complicated.
Your answer
Follow this Question
Related Questions
how do I add abilities(Scripts/GameObjects) to my path finding agent 1 Answer
How can I get my pathfinding algorithm to know that it cant go through certain sides of tiles 1 Answer
A* Pathfinding, destroying a path once it has reached its end 0 Answers
Delete Astar Path gride graph around a particular Object 1 Answer
Find the closest point of an Invalid or Partial path 0 Answers