Indeed, I got that now. Mufin, what progress?

Ok, well, I have some code now, and it isn't pretty, or yet functional, but I think I've made enough progress to post it.

As of now, the theoretical process is that it will go from each intersection, then go from each possible exit from that point, until it hits a dead end or another intersection. If it hit a dead end, it's supposed to reverse it's trail, then use the same "path following" code (pi/7 or pi/14 as Ans then recalling the program) however with an added parameter (pi/14) that has it delete each cell as it leaves it, then redisplays that cell as empty. After that, it returns to searching for more exits from the first intersection.

If from the first intersection, it finds another intersection, then it'll begin to search from each of that intersection's exits. If it finds the first intersection from that exit, then it will compare the distances it recorded for both the times it went down the paths between the intersections, then delete the longer path.

Yes I realize that this system is flawed: going from intersection A to B, using path 1, then reusing path 1 to go from intersection B to A, would in theory have the program delete path 1, essentially having the program delete most all paths that exist. However, since for some reason it doesn't delete any paths at all, this can't happen. I'm going to prevent this soon by having the program lay "bread crumbs" using a second matrix the same size as the first. Then with that, it will turn the current position it's at from 0 to 1, so it knows where it has been, then prevent itself from going where it has been before.

Anyways, that's all the code I have so far. Here's a pastebin. I was using Merth's TokenIDE and using tabs, so here's your heads up.

PseudoProgrammer, I did notice a problem with your little program, as it only gets rid of dead ends, as Kerm has pointed out, and decided to show you a more visual example of how that can be both useful, and also not so useful.

Before, I go on, I want to be sure you know I think it is a great little method, and have intentions to probably use it in the end product of my program, but it isn't a maze solver by itself.

Here's my given maze as is pictured by the calculator. With this maze, I made it so the entrance and exits that lead outside the maze, for added assurance it won't delete those squares.

I'd say it's a fair sized, simple maze, that unfortunately your solver would have trouble solving.

Here is the end result after running it through your solver.


Now, there are pro's and con's with this, I find. The bad thing is that by itself, it would be impossible to solve anything with any sort of loop, which happens quite often in mazes. The good thing, is that it can easily and quickly look over the entire maze, making it a good tool to be used with the proper other tools.

Of course with your permission, I was hoping to use your code you provided, to make my solver faster, or at least use an easier to implement method for tracking and eliminating dead ends. My plan was that when it finds one intersection and two intersection loops, it will turn on one pixel, so it fakes being two dead ends, so your code will eliminate the unnecessary paths.

I'm not sure if my code would be faster properly working without your code, or with your code, but I find your code would be a good, easy way to get rid of dead ends, until I get my code working properly without, then I can compare.

Now, I'm going to head back to work on trying to figure out what's wrong with my code as is at the moment.

My code was kind of designed as a joke actually, and it's horribly inefficient. But as to the loops within mazes, my code assumes the mazes are what's known as perfect mazes, where there is only one solution (no loops). Here is code (that I also have still not tested, just thinking it up off hand) that should be significantly quicker. You can change the values of the For() loops depending on the size of the maze, but it will function perfectly on full screen regardless. Note that if you do change the values you also need to adjust the values of the pixel tests and whatnot in the second half of the code (the 94s and whatnot).


Code:


EDIT: Look into Ant Colony Optimization.

Yeah, I did something like that already, except I added another double nested for loop using opposite directions, then nested the whole thing in a Repeat, so it'll stop the search when goes through a full cycle without modifying any pixels.

And sure, I'll look into that, thanks for the tip.

A minor point: I've actually seen very few mazes where a loop is included; maybe that's just me. With the simplified maze after Pseudo's solver, though, if you found all more-than-two-path intersections (ie, intersections), you could trace each way from each intersection, figure out the duplicate paths, keep only the shortest, and then juts string them together into your solution.

The MineCraft server I frequent uses mazes as a prerequisite for actually "joining the server" (being granted builder permissions) and loops are very often used to give the impression that the maze is larger than it really is. I've found mazes designed for a top-down view of it don't really have many loops, because loops are fairly easy to spot. However inside the maze, they're significantly harder to detect, unless you know what you're doing. Nonetheless, I'd still like it to be completely able to solve any and all mazes, with or without loops, so some code for detecting and eliminating loops will be needed.

Also Kerm, haha yes, I'm already working on doing that. That was what I meant by "one intersection and two intersection loops." I meant loops that will go straight back to where you last turned, or "loops" that are more literally edges that go to and from the same points.

If I can't get this loop detection/elimination part of the code working soon, then I'm going to work on it later. I'm excited to try and implement these shortest path algorithms, and see them go.

Out of curiosity, in the Minecraft example, how do you prevent users from just griefing the maze by constructing walls or destroying pieces of it?

Kerm: Admins and what have you of servers can make certain areas of the server unchangeable.

That makes perfect sense, that's more or less what I was assuming. So, shall we return to our regularly-scheduled maze discussion?

Well, I found out that the reason my method wasn't deleting dead end paths, was because of the While loop that was running the "path following" method I made. So instead of worrying about it being a single program, for now I've made it a four program, set, although I'm not sure I need the fourth.

The new main program is prgmMAZE, and it uses it's methods prgmMAZE1 for following paths, and recording their distance, where they came from, where they ended, and what exactly is the reason they ended their path following (dead end or a new intersection).

prgmMAZE2 is the path deleting method. It will go to a new cell down the path, delete the old, then redisplay the old as an empty block, and repeat. After all this, it calls prgmMAZE3, which is the one I'm not sure I'm going to need, as this is the only time as of yet that it is called.

prgmMAZE3 makes sure that a given cell in the maze (given using coordinates E,F) will match with it's surroundings, given it has a surrounding (edge of the maze), for when the path deleting method deletes paths, it deletes it's footprints, not tidy up where it is now. Without it, it would lead the program into dead cells of value 0.

Anyways, I also realized that without an intersection "check" sort of code, it always uses the same given intersection coordinates. I added a few lines so that it now checks to be sure a coordinate used, is still an intersection before assuming it is. If it isn't, then it takes those coordinates out of the list. Because of this, I had to start working on given coordinates for source and destination, because otherwise (using my given maze) it would run the quite likely chance that it would delete the cells that are the source and destination, which would be unacceptable, imho at least.

I'm currently working on getting it so it won't have to worry about paths that lead out of the maze boundaries for certain situations, having it use designated source and destination coordinates, prevent it from ever deleting source or destination cells, and a few other things.

And lastly, here's the current code as detoken-ized by TokenIDE:

Code:


May edit this post later today/tomorrow, I'm posting this before starting my day's work on it, so things may change by the time I decide to hit the sack.

Out of boredom, and while trying to figure out some errors I'm running into (for some reason, it tries to navigate through dead cells, then gets an invalid dim error with the current maze) I made some code that used something between Pseudo's code, and between mine.

It finds a dead end, then follows the dead end to an intersection, so I think it's much more efficient.

In my experience, it only needs to do one look over before it has eliminated all the paths it can, so this code only does one check over the whole maze:

Code:


Just in case you're wondering, C needs to be stored to E before it's modified, otherwise in some cases (going around corners coming from either above or below, to either side) it will move twice in one iteration of the path following code.

After realizing what caused the error that made me add that, I had to slap myself, because this is at least the fourth time I've run into this sort of problem with path following code. XD

Tomorrow I'm spending the whole day babysitting, so if I get a free moment or two (I'm bringing a few movies, and their parents said they'd give us a pass so they can go to some jungle gym thing nearby, so I'll get some time there), I'll be spending it working on my maze program.