Mapping shortest route through a maze

Anything beyond the basics in using the LiveCode language. Share your handlers, functions and magic here.

Moderators: FourthWorld, heatherlaine, Klaus, kevinmiller, robinmiller

Post Reply
Amigatech
Posts: 18
Joined: Mon Jan 18, 2010 12:55 am

Mapping shortest route through a maze

Post by Amigatech » Fri Mar 17, 2017 1:40 pm

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?

dunbarx
VIP Livecode Opensource Backer
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

Post by dunbarx » Fri Mar 17, 2017 3:21 pm

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

Amigatech
Posts: 18
Joined: Mon Jan 18, 2010 12:55 am

Re: Mapping shortest route through a maze

Post by Amigatech » Fri Mar 17, 2017 4:24 pm

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.

Amigatech
Posts: 18
Joined: Mon Jan 18, 2010 12:55 am

Re: Mapping shortest route through a maze

Post by Amigatech » Fri Mar 17, 2017 10:20 pm

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.

ClipArtGuy
Posts: 253
Joined: Wed Aug 19, 2015 4:29 pm

Re: Mapping shortest route through a maze

Post by ClipArtGuy » Fri Mar 17, 2017 10:24 pm

You may be interested in the A* pathfinding stack available here: http://bjoernke.com/?target=games

Amigatech
Posts: 18
Joined: Mon Jan 18, 2010 12:55 am

Re: Mapping shortest route through a maze

Post by Amigatech » Sat Mar 18, 2017 5:44 pm

That stack gives me some ideas, but unfortunately the stack doesn't work, at least in 8.1.2.

Amigatech
Posts: 18
Joined: Mon Jan 18, 2010 12:55 am

Re: Mapping shortest route through a maze

Post by Amigatech » Mon Mar 20, 2017 10:51 pm

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

AndyP
Posts: 614
Joined: Wed Aug 27, 2008 12:57 pm
Location: Seeheim, Germany (ex UK)
Contact:

Re: Mapping shortest route through a maze

Post by AndyP » Tue Mar 21, 2017 5:44 pm

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

Amigatech
Posts: 18
Joined: Mon Jan 18, 2010 12:55 am

Re: Mapping shortest route through a maze

Post by Amigatech » Tue Mar 21, 2017 7:09 pm

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.

Post Reply

Return to “Talking LiveCode”