Depth first search, maze solving

[barnabus]

Hi guys, I'm starting my final year project for uni (comparison of path finding algorithms for optimal maze solving). I've built the robot and experimented with variables enough to get fairly consistent, accurate movement. I'm using a 5 by 5 maze of equal gird sizes just to implement the first algorithm, depth first search. I've written the first algoritm out in probably very bad psudeo code just to get an idea of how to implement it. I'm alittle stuck on how to backtrack to the deepest node once I've hit a dead end, any thoughts? Also any thoughts in general about the way I'm going about coding the algorithm?

SET start co-ordinate AS myPos
SET goal co-ordinate AS goal
SET Direction (north, east, south, west) AS north
CREATE all movement methods //(rotate_US_left(), rotate_robot_left(), moveForward() etc etc

CREATE node object constructor (newPos, newDirection)

while(myPos != goal)
//Scan left, forward, right to determine if theirs a path(edge) to an adjacent node(vertex)
//create new node object and add to FIFO stack
//if no new paths backtrack to deepest node on stack

//scan right and compare to a pre defined distance to a wall
if (scan right > wall distance && direction = north)
{
CREATE new node object (X co-ordinate +1 + Y co-ordinate + east)
add to stack
}

elseif (scan right > wall distance && direction = east)
{
CREATE new node object (X co-ordinate + Y co-ordinate -1 + south)
add to stack
}

etc etc

scan front…

scan left…

Next move pop node object off stack

direction of travel = new direction in node object
call appropriate movement methods

update current co-ordinate with new co-ordinate in node object
same for direction

How do I backtrack?????

repeat until myPost = goal

[barnabus]

This is what I've built...





front mounted US sensor on a rotating gear.