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

Mapping shortest route through a maze

Postby 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?
Amigatech
 
Posts: 17
Joined: Mon Jan 18, 2010 12:55 am

Re: Mapping shortest route through a maze

Postby 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
dunbarx
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
 
Posts: 4643
Joined: Wed May 06, 2009 2:28 pm
Location: New York, NY

Re: Mapping shortest route through a maze

Postby 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: 17
Joined: Mon Jan 18, 2010 12:55 am

Re: Mapping shortest route through a maze

Postby 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.
Amigatech
 
Posts: 17
Joined: Mon Jan 18, 2010 12:55 am

Re: Mapping shortest route through a maze

Postby ClipArtGuy » Fri Mar 17, 2017 10:24 pm

You may be interested in the A* pathfinding stack available here: http://bjoernke.com/?target=games
ClipArtGuy
 
Posts: 79
Joined: Wed Aug 19, 2015 4:29 pm

Re: Mapping shortest route through a maze

Postby 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: 17
Joined: Mon Jan 18, 2010 12:55 am

Re: Mapping shortest route through a maze

Postby 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 17 times
Amigatech
 
Posts: 17
Joined: Mon Jan 18, 2010 12:55 am

Re: Mapping shortest route through a maze

Postby AndyP » Tue Mar 21, 2017 5:44 pm

Andy Piddock

http://2108.co.uk/tinyide/ - TinyIDE gives you more space to develop your ideas

http://2108.co.uk/script-editor-themer/ Script Editor Themer - Your code has never looked so good

My software never has bugs. It just develops random features
AndyP
 
Posts: 276
Joined: Wed Aug 27, 2008 12:57 pm
Location: Seeheim, Germany (ex UK)

Re: Mapping shortest route through a maze

Postby 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.
Amigatech
 
Posts: 17
Joined: Mon Jan 18, 2010 12:55 am


Return to Talking LiveCode

Who is online

Users browsing this forum: No registered users and 4 guests