Mapping shortest route through a maze
Moderators: FourthWorld, heatherlaine, Klaus, kevinmiller, robinmiller
Mapping shortest route through a maze
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?
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?
-
- VIP Livecode Opensource Backer
- Posts: 9582
- Joined: Wed May 06, 2009 2:28 pm
- Location: New York, NY
Re: Mapping shortest route through a maze
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
Of course there must be, otherwise the solution is very simple.
Craig Newman
Re: Mapping shortest route through a maze
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
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.
Last edited by Amigatech on Mon Mar 20, 2017 10:49 pm, edited 2 times in total.
-
- Posts: 253
- Joined: Wed Aug 19, 2015 4:29 pm
Re: Mapping shortest route through a maze
You may be interested in the A* pathfinding stack available here: http://bjoernke.com/?target=games
Re: Mapping shortest route through a maze
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
Here is a stack with functional UP DOWN LEFT RIGHT buttons. I haven't tackled the auto solve yet.
- Attachments
-
- Map Directions.livecode.zip
- Functional UP DOWN LEFT & RIGHT
- (1.96 KiB) Downloaded 212 times
Re: Mapping shortest route through a maze
You might find these interesting.
https://sites.google.com/a/pgcps.org/livecode/mazes
http://livecodegamedeveloper.com/blog/2 ... ic-maze.lc
https://sites.google.com/a/pgcps.org/livecode/mazes
http://livecodegamedeveloper.com/blog/2 ... ic-maze.lc
Andy Piddock
https://livecode1001.blogspot.com Built with LiveCode
https://github.com/AndyPiddock/TinyIDE Mini IDE alternative
https://github.com/AndyPiddock/Seth Editor color theming
http://livecodeshare.runrev.com/stack/897/ LiveCode-Multi-Search
https://livecode1001.blogspot.com Built with LiveCode
https://github.com/AndyPiddock/TinyIDE Mini IDE alternative
https://github.com/AndyPiddock/Seth Editor color theming
http://livecodeshare.runrev.com/stack/897/ LiveCode-Multi-Search
Re: Mapping shortest route through a maze
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.