Solve a maze using multicores?
- by acidzombie24
This question is messy, i dont need a working solution, i need some psuedo code.
How would i solve this maze? This is a homework question. I have to get from point green to red. At every fork i need to 'spawn a thread' and go that direction. I need to figure out how to get to red but i am unsure how to avoid paths i already have taken (finishing with any path is ok, i am just not allowed to go in circles).
Heres an example of my problem, i start by moving down and i see a fork so one goes right and one goes down (or this thread can take it, it doesnt matter). Now lets ignore the rest of the forks and say the one going right hits the wall, goes down, hits the wall and goes left, then goes up. The other thread goes down, hits the wall then goes all the way right. The bottom path has been taken twice, by starting at different sides.
How do i mark this path has been taken? Do i need a lock? Is this the only way? Is there a lockless solution?
Implementation wise i was thinking i could have the maze something like this. I dont like the solution because there is a LOT of locking (assuming i lock before each read and write of the haveTraverse member). I dont need to use the MazeSegment class below, i just wrote it up as an example. I am allowed to construct the maze however i want. I was thinking maybe the solution requires no connecting paths and thats hassling me. Maybe i could split the map up instead of using the format below (which is easy to read and understand). But if i knew how to split it up i would know how to walk it thus the problem.
How do i walk this maze efficiently?
The only hint i receive was dont try to conserve memory by reusing it, make copies. However that was related to a problem with ordering a list and i dont think the hint was a hint for this.
class MazeSegment
{
enum Direction { up, down, left, right}
List<Pair<Direction, MazeSegment*>> ConnectingPaths;
int line_length;
bool haveTraverse;
}
MazeSegment root;
class MazeSegment
{
enum Direction { up, down, left, right}
List<Pair<Direction, MazeSegment*>> ConnectingPaths;
bool haveTraverse;
}
void WalkPath(MazeSegment segment)
{
if(segment.haveTraverse) return;
segment.haveTraverse = true;
foreach(var v in segment)
{
if(v.haveTraverse == false)
spawn_thread(v);
}
}
WalkPath(root);
