Data structure to store a robot map

Question

I'm studying robotics at the university and I have to implement on my own SLAM algorithm. To do it I will use ROS, Gazebo and C++.

I have a doubt about what data structure I have to use to store the map (and what I'm going to store it, but this is another story).

I have thought to represent the map as a 2D grid and robot's start location is (0,0). Each cell of the grid will be 1x1 meters. I will use a laser to know where are the obstacles. Using current robot's location, I will set to 1 on all the cells that represent an obstacle. For example, it laser detects an obstacle at 2 meters in front of the robot, I will set to 1 the cell at (0,2).

Using a vector, or a 2D matrix, here is a problem, because, vector and matrices indices start at 0, and there could be more room behind the robot to map. And that room will have an obstacle at (-1,-3).

On this data structure, I will need to store the cells that have an obstacle and the cells that I know they are free.

Which kind of data structure will I have to use?

Answer 1

I recommend you use the Gridcell data structure to start. It is designed for storing grid information in a 1d array. You will just need to create algorithms to store data in the array and retrieve data in the array properly.

https://docs.ros.org/kinetic/api/nav_msgs/html/msg/GridCells.html

Then, when you want to display data, you use Markers in a marker array.

from visualization_msgs.msg import Marker, MarkerArray

This link documents more about this message type

https://wiki.ros.org/visualization_msgs