Finding shortest path between two points

**PetrHoracek** · 09-04-2019, 05:38 AM

Hey, so I'm working on a simulation project and I've encountered an obstacle.

Here's a representation of the problem:

Výstřižek.PNG

I want to find a path from A to C (or C to A, doesn't really matter), that's as short as possible. The W's represent walls, that cannot be crossed. Also, the path can't be diagonal, only ortogonal.
I've been trying to come up with a solution, but no luck so far.

Is this even possible to do?

Thanks for any advice. Have a nice day.
Petr

**WideBoyDixon** · 09-04-2019, 06:26 AM

I wrote an exhaustive recursive function to find the shortest path:

Please Login or Register  to view this content.

See attached. If you want to see it in action, comment out the line which turns off screen updating.

WBD

**sintek** · 09-04-2019, 06:32 AM

This is going to be an interesting one...Wanna see how this plays out...
Does the letter W always represent a brick in a wall...Is the markers always A and C or are other letters in the alphabet used...
How must the path be displayed...Interior cell color changes...step by step cell reference etc etc

**PetrHoracek** · 09-04-2019, 06:38 AM

Wow, thanks a lot. I will look into it. Much appreciated!

**PetrHoracek** · 09-04-2019, 06:49 AM

Hey, yeah, the W is like a brick, impassable. Letters A and C are just an example, it could be any letter.

Regarding how the path is going to be displayed and the other things... I really don't know either. I am just assisting the main programmer who works on this project, as a summer job before school starts. He basically just told me he wants to find a shortest path between two cells and that's it. I'll probably tell you more when i see him again.

**sintek** · 09-05-2019, 04:18 AM

Just for the fun of it...Would fall apart if the maze was more elaborate though...

Please Login or Register  to view this content.

Just for interest sake...I have attached a file I found on the net...
The left area [A:L] allows you to enter 1 into a cell to create an amazing elaborate maze...
The right area [O:Y] depicts the path...