search

maxwellreynolds / Maze

Solves user-uploaded maze images
36 stars 17 forks source link

Decrease Path "Jaggedness" #19

Open a1ward opened 2 years ago

a1ward commented 2 years ago

Hello! I just wanted to say that this is a really cool implementation of maze solving.

One thing I was wondering, is whether or not you had an idea of how the code could be modified to force the output "path" to have less jagged segments. Or at least is there a reason why the script chooses a jagged path over an identical in length more straight path?

I've attached a picture here from one of your example maze solves, where the red path near the finish should be identical in length to the path that was found by the solver. Can you think of any ways to find a "least turns" path?

Picture1

maxwellreynolds commented 2 years ago

To get a smooth line as in your example, there might be a small distance penalty for making a "turn". This could be kept track of separately, or a more hacky way would be to change "get distance" to consider the parent of the vertex in question and add a small penalty (<< 1) if a turn is made.

Changing get_neighbors to allow diagonals (with a distance of sqrt(2) rather than 1 via Pythagorean theorem) may also make the graph appear smoother

a1ward commented 2 years ago

Hello!

Thank you so much for taking time to respond. What you mentioned about a turn penalty makes perfect sense actually. Since I'm not interested in the shortest path (which would of course happen if I implemented "hypotenuse" capabilities), and more interested in decreasing "turns", I will look into what you mentioned for the parent of the vertex, and see what results I can get.