HOME | DD
TGFWritter — Project Maze Part 2
Published: 2012-04-17 12:48:35 +0000 UTC; Views: 1240; Favourites: 3; Downloads: 17
Redirect to original
Description
That's right, my project is related to mazes.However, there's but one little problem. Guess what the program's supposed to do?
Make it? No
Solve it.
And I'm the schmuck that got stuck with doing it (we drew a lottery).
Supposedly, we've got to make the program capable of solving a maze in less than 2 minutes with the timer set at 50hz. Or in other words, 50 moves per seconds (every move being one of the squares, and reaching a dead end automatically sends you back to the last "option" rather than forcing you to backtrack)
However, we must also make the maze so that a normal person will take 2 hours at the very least (in fewer words, the teacher have their own program that simulates how long it'd take a human to solve it).
But I still get my revenge on my teamates, because they're the ones that'll be testing the program, and since I'm using Paint to do this, the "white" and "black" on the image you're looking at is actually 20 different "whites" and "blacks" (at least in the computer's point of view). So they'll have to deal with a way to solve that on their own (cuz I'm stuck doing the maze).
Part 1 [link]
Part 3 [link]
Related content
Comments: 6
What language are you writing this in?
And that sounds like fun. -tries to imagine how I would program such a program-
👍: 0 ⏩: 1
We use Eclipse (java). Teacher gave us a pre-prepared program that allows us to read an image... pixel by pixel (that's why it's so small).
I made some modifications so it would consider one "step" to be 4 pixels instead and from there on I was pushed onto "making maze" duty (it's four pixels since the tiny squares on the image are 3x3 pixels, and have a single pixel separating it from the squares around it).
The tough part will be making the program understand where the "walls" are at since, as I said on the comments, though we might see one "Black", the computer recognizes it as 20 or so different kinds... stupid Paint.
Well, once that problem's solved, I already more or less drew a general sketch as to how the program should work (I'm better at drawing general concepts than using all the specific language to make a program out of it). A first sweep of the program will make it go through every nook and cranny on the maze and create a "Tree" made out of nodes, where each node represents 3x3 pixel square in the maze, and from which you pretty much have up to three decisions to make: -Go straight -Take Left or -Take Right.
Of course, you can't put a "Go left" branch where it's just a straight line, and a dead end is a dead end (still have to program that into the program though).
Once that's done (I'm guessing it'll take a minute or two to make the digital "Map") we run our "Maze solver" at 50hz and see how long it takes... hopefully, we won't need to remake the Solver too many times.
👍: 0 ⏩: 0
Oh yeah. I think I had to do something similar using recursion. Just be careful with the stack - super easy to blow it.
👍: 0 ⏩: 1
We're using trees (Not sure if that's how to say it in English)
Basically we treat the "Entrance" as the Root node and from there on every decision turns into a "branch" one of which leads to the final node... it's a two part program since the 1st "reads" the labyrinth and the second solves it
👍: 0 ⏩: 1
