 |
SteveThing
Beginner
Joined: 29 Aug 2010
Posts: 12
|
 Posted: Tue Oct 19, 2010 12:19 pm
Blind (uninformed) Maze Solving
|
So I came across a fun challenge which has proven to cause hair loss. I'm trying to write a maze solver given the following scenario:
You are dropped into a random room in a randomized maze.
You do not know the layout of the maze ahead of time.
The exit to the maze can be any room, no matter the exits available (i.e. doesn't always end at a dead-end).
All rooms are two-way exits and there are no "portals" to contend with.
I have attempted the "right-hand rule" which has proven not possible in this maze due to tricksy hobbitses. I came up with a slick method of detecting if I have reached my original position via math. I assigned a "root" even number and multiply or divide it like so:
| Code: |
(Float) Root = 100.00
Go North and root = root / 5
Go East and root = root * 2
Go South and root = root * 5
Go West and root = root / 2
|
No matter the size or shape of a loop, this will always work out that if root == 100, then you have reached your starting point. I used small prime numbers for the directions because you won't have a mathematical false positive.
Now that I have that figured out, I want to try to come up with an effective way of solving a maze using Tremaux's algorithm (most appropriate I believe) which says:
http://en.wikipedia.org/wiki/Maze_solving_algorithm:
| Quote: |
| Trémaux's algorithm, invented by M. Trémaux, is an efficient method to find the way out of a maze that requires drawing lines on the floor to mark a path, and is guaranteed to work for all mazes that have well-defined passages. A path is either unvisited, marked once or marked twice. Every time a direction is chosen it is marked by drawing a line on the floor (from junction to junction). In the beginning a random direction is chosen (if there is more than one). On arriving at a junction that has not been visited before (no other marks), pick a random direction (and mark the path). When arriving at a marked junction and if your current path is marked only once then turn around and walk back (and mark the path a second time). If this is not the case, pick the direction with the fewest marks (and mark it, as always). When you finally reach the solution, paths marked exactly once will indicate a direct way back to the start. If there is no exit, this method will take you back to the start where all paths are marked twice. In this case each path is walked down exactly twice, once in each direction. The resulting walk is called a bidirectional double-tracing. |
A visual example of this can be viewed at YouTube here: http://www.youtube.com/watch?v=6OzpKm4te-E
I just get stuck on the remembering previous paths taken part. I'll post examples of my code later. This post is to plant the seed of thought and see if anyone is interested in helping me figure this out (since apparently I am smart enough to solve a 7x7 rubix cube but too dumb to think like a rat).
Regards,
Steve |
|
|
|
|
Moo
Apprentice
Joined: 10 Apr 2009
Posts: 145
|
Posted: Tue Oct 19, 2010 1:27 pm
|
Are the rooms all "square"? So if you went east twice, north once, west twice, south once, would you definitely be back where you started?
That algorithm looks interesting. You could use the UserStr field of the mapper to store the "marks" as a stringlist. I do hope you are using the mapper. |
|
|
|
|
SteveThing
Beginner
Joined: 29 Aug 2010
Posts: 12
|
Posted: Tue Oct 19, 2010 2:41 pm
|
Yes, all rooms are square. I decided to use the math method as a challenge to myself. Either way would be fine I guess. I have been toying with the idea of using a 2D array for the maze and two global variables (x and y) to see if I have reached my original position. So many options...
Normally, I would use the mapper, but I wanted to attempt it without the mapper first (mainly because I use linux more often than windows). Besides, I have been having trouble with the room descriptions in the maze. It doesn't tell you the exits unless you specifically ask it (i.e. type exits).
So I've got a few basic aliases for rotating my character:
| Code: |
#ALIAS turn_right
{
#switch (@current_dir)
("north") {current_dir="east"}
("east") {current_dir="south"}
("south") {current_dir="west"}
("west") {current_dir="north"}
{#show {turn_right, Unknown direction: @current_dir}}
}
#ALIAS turn_left
{
#switch (@current_dir)
("north") {current_dir="west"}
("east") {current_dir="north"}
("south") {current_dir="east"}
("west") {current_dir="south"}
{#show {turn_left, Unknown direction: @current_dir}}
}
#ALIAS turn_around
{
#switch (@current_dir)
("north") {current_dir="south"}
("east") {current_dir="west"}
("south") {current_dir="north"}
("west") {current_dir="east"}
{#show {turn_around, Unknown direction: @current_dir}}
} |
I then moved on to retrieving exits, which is done via 4 triggers:
| Code: |
#trigger {It appears you can go %1 from here} {#var exits {};#additem exits %1;turn_around;#show {Hit a dead end, now heading @current_dir!}}
#trigger {It appears you can go %1 or %2 from here} {#var exits {};#additem exits %1;#additem exits %2}
#trigger {It appears you can go %1, %2, or %3 from here} {#var exits {};#additem exits %1;#additem exits %2; #additem exits %3}
#trigger {It appears you can go %1, %2, %3, or %4 from here} {#var exits {};#additem exits %1;#additem exits %2; #additem exits %3;#additem exits %4} |
In my other MUD client, I use bits, XORing, and ANDing for the exits instead of strings, but it is a bit lengthy and not relevant to CMUD. At this point I am trying to wrap my head around the Tremaux algorithm and how to begin to implement it. I'm thinking that if I reach a junction, I need to mark each exit if I have been that way already. What I would really like to do is create a 2D array of cells, where each cell contains exits, states, coords, etc. I dunno if this is possible via zScript.
Any suggestions? |
|
|
|
|
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
