Page 1 of 1

Mapping shortest route through a maze

Posted: Fri Mar 17, 2017 1:40 pm
by Amigatech
I was wondering if anyone has done this already, or would like to "play" for a bit.

If I have a maze (like a company cubicle farm) and I know that Sarah sits in a cube waaay over there, behind the potted tree, and I have a known "you are here" arrow showing the starting point (which can be moved anywhere), I want an algo to plot the most efficient route to travel to Sarah's desk. A polygon of 90 degree turns would be generated to display the route.

So the maze would be on a card with "groups" to represent cubicles. Inside each group would be objects that represent the desk, chair, cabinet, etc., and an outer wall with entry an point set with a specific attribute to aid the mapping algorithm. Everything should be considered solid except the designated entry points.

Thoughts or suggestions? Have any of you already done something similar?

Re: Mapping shortest route through a maze

Posted: Fri Mar 17, 2017 3:21 pm
by dunbarx
I assume there are obstacles in the maze that require one to turn away from either a horizontal or vertical direction that moves one absolutely closer to the goal.

Of course there must be, otherwise the solution is very simple.

Craig Newman

Re: Mapping shortest route through a maze

Posted: Fri Mar 17, 2017 4:24 pm
by Amigatech
Yes, I'm thinking of something like the maps at the mall. You are here, and if I want to go to a specific store, what is my best route to go there? All lines, boxes, etc. are obstacles. So after bouncing off of everything and figuring out the many optional paths, I want to see which path is shorter.

Re: Mapping shortest route through a maze

Posted: Fri Mar 17, 2017 10:20 pm
by Amigatech
Here's a file we can play with using a super simple maze. I'll make more complex ones to test any offered solutions. Put your code in the "Auto Solve" button.

Re: Mapping shortest route through a maze

Posted: Fri Mar 17, 2017 10:24 pm
by ClipArtGuy
You may be interested in the A* pathfinding stack available here: http://bjoernke.com/?target=games

Re: Mapping shortest route through a maze

Posted: Sat Mar 18, 2017 5:44 pm
by Amigatech
That stack gives me some ideas, but unfortunately the stack doesn't work, at least in 8.1.2.

Re: Mapping shortest route through a maze

Posted: Mon Mar 20, 2017 10:51 pm
by Amigatech
Here is a stack with functional UP DOWN LEFT RIGHT buttons. I haven't tackled the auto solve yet.

Re: Mapping shortest route through a maze

Posted: Tue Mar 21, 2017 5:44 pm
by AndyP

Re: Mapping shortest route through a maze

Posted: Tue Mar 21, 2017 7:09 pm
by Amigatech
Thank you, Andy. Those maze game concepts are helpful in understanding the constraints of keeping the ball inside its boundaries. Navigation is still manually left up to the player. I want the computer to be my "player", and to solve the maze. Making some progress toward that end, I think.