I've been stuck on this issue for a while now, and I feel like I can ask for help now.
I basically need a search algorithm that finds the shortest path in an undirected, unweighted graph using std::map to access each Node with coordinates represented as std::pair<int,int>.
The reason I need to use std::map while a list would have made more sense is because the search algorithm is rarely used (yet essential!), and the rest of the program benefits substantially from using std::map.
the reason this problem exists:
>The full assignment is to get a robot through a maze.
>The maze is grid-like (with uniform distances in four directions)
>The starting point, exit point and maze size are unknown.
>The exit point can be detected by sensors.
>The robot can only see one space in the four cardinal directions.
My solution is to use std::map to record every 'tile' so the robot won't search for an exit where it has already searched (preventing it from running in circles). If the robot has only explored tiles around it(which is possible but rare), it uses the search algorithm to find the nearest unexplored part of the maze.
what I've done:
The whole code is finished and runs well and efficiently, the only thing missing is the search-algorithm.
I've tried using list as data-structure, as well as a hybrid between a list and a map. the resources to maintain the list part of the data-structure were too big.
I've researched a lot of algorithms, with Dijkstra's algorithm getting closest to my needs. However, it utilizes std::list and is used for weighted graphs (to be fair: all weights could be set to 1).
I've made some functions to easily access the adjacent tiles.
Can anyone help me find an effective algorithm?
NOTE: the search algorithm is implemented as a function that has complete and unobstructed access to the std::map (same class).
This post has been edited by squarepenguin: 05 January 2013 - 08:45 AM