CODEWITHSUNDEEP
carraysmaze
Schurke
Schurke

Reputation: 19

Find a Path through an physical maze in C

So we have one Robot that drives through a maze (nothing I need to worry about), writes down detected walls and ways and sends it to another robot, which shall drive straight through the maze to reach the exit.
I have already written a zigbee program to send the maze (2 dimensional array) and i guess it should work (could not test it yet since i have only one robot at home).
So My Robot gets the 2 dimensional array. For Example:

1 0 0 1 1 1 1 1 1 1
1 0 0 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 0 0 1
1 0 0 1 0 0 1 0 0 1
1 0 0 1 0 0 1 0 0 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 0 0 1

<1> symbols a wall and <0> symbols the way (it has to be 2 next to each other, since one number is equal to 10cm / 3,9 inches). And now I really have no idea how to get my robot to drive the right path.

Upvotes: 0

Views: 211

Answers (1)

einpoklum
einpoklum

Reputation: 131960

If the maze has no cycles, then all of its walls form two parallel (though contorted) lines between the entrance and the exit. Just follow one of them consistent (e.g. always take the right, and walk along the edge of the free space). This is not the optimal path, for sure - but it's pretty simple to implement.

If there are cycles you won't have it that easy. You can read up on some maze-solving algorithms on Wikipedia. One option which @nneoneo suggests is using Dijkstra's algorithm, with the "graph" having all n^2 maze squares as nodes, and edges between two adjacent empty (0) nodes. It's a bit memory-heavy, but its performance is not so bad and it's not very complicated.

More interesting reading: Look up the Greek myth of Theseus in the Labyrinth. He used a ball of yarn to track his path.

Upvotes: 2

Related Questions