# Built-In Digital Map for Robot Driving

So, I'm creating this project for school. It's a simple robot with Arduino MEGA 2560 and basically, I create a digital map, feed it into the Arduino program and then the robot can drive. However, I've run into some problems while trying to implement my idea. Parsing errors mostly. And I want to know if there is another and different approach.

So, basically at the moment, this is how my digital map works:

Using C# and Visual Studio IDE I've created a program with which I can create the map. Basically, I create connections(lines/roads) and the connection has a starting and end point, a median point and a label(what it is). So, each connection info token is something like this:

```"Connection[x1: 0, y1: 0|x2: 13, y2: 0|xm: 6.5, ym: 0|label: Nothing]" ``` `"Connection[x1: 13, y1: 0|x2: 13, y2: 28|xm: 13, ym: 14|label: library]"`

Now, I have figured out a way to import this information into Arduino, and I've stored the information into a class object I created. Now, the difficulty I'm experiencing is how am I going to drive the robot from one point to another, store the robot's position and go to any point in the map when asked to.

Edit:

As for the implementation and storage of the map, it's like this:

So, I have a class Vertex. It basically the equivalent of a point and store (x, y) values.

``````class Vertex {
public:
int x;
int y;

Vertex(int _x, int _y) {
x = _x;
y = _y;
}
};
``````

Then there's the connection class. It stores the starting vertex, the end vertex, the median vertex and the label(string). It's like this:

``````class Connection {
Vertex v1();
Vertex v2();
Vertex median();
String label;

public:
Connection(Vertex _v1, Vertex _v2, Vertex _median, String _label) {
v1() =  Vertex(_v1.x, _v1.y);
v2() =  Vertex(_v2.x, _v2.y);
median() = Vertex(_median.x, _median.y);
String label = _label;
}
};
``````

And, finally, there's the map class where the user passes in the info tokens produced by my map creating application made in Visual Studio and it works like this:

``````#include "Connection.h"

class Map {
public:
Map(string infoTokens[]) {
//I import the info tokens here.
}

void drawMap(MCUFRIEND_kbv tft, String ) {
//This is a totally different function, it is just for drawing the map
on top of the TFT screen that I have on my robot.
}

void driveTo(Vertex rP, String destinationLabel) {
//This is where I drive my robot when the user requests to go to a
destination and provides the label.
}
};
``````

As for the importing of the info tokens(the map information) I just do some `String Manipulation` on, for example, this `"Connection[x1: 0, y1: 0|x2: 13, y2: 0|xm: 6.5, ym: 0|label: Nothing]"` and get back all the info in the required data types. As for the importing it doesn't really change anything because I have tested my function(not present here) a lot of times and it works brilliantly. My question is how to use that information to hopefully drive the robot.

• Do you want to command the robo "go to position 6, 3" or "got to library" (last one is using the label instead of the physical location)? – chrisl Apr 30 at 14:10
• And do you want the shortest connection to the target through your street net? – chrisl Apr 30 at 14:11
• I want it to command using 'go to position 6,3' as it would be more useful. And yeah implementing the shortest distance possible would be a great idea. – Gaurav Mall Apr 30 at 14:44
• Can you please show the implementation of your class object, so that we can see, how the data is stored? – chrisl Apr 30 at 16:45
• Added the information you requested. Hopefully, it is what you need and can give me a solution. Thanks! – Gaurav Mall Apr 30 at 18:22

You were able to create a custom data structure from your string, but it seems, that the connections, that are stored in the `Map` class, are not connected. So the map does not really represent the structure of the "street" net. I would propose a different approach:

Instead of defining connections you can define the nodes of your net (where 2 or more streets meet). For each node you save the position (x, y) (or an instance of your vertex class), a label (like "library") and an array of pointers to other node objects. In code this may look like this (I left the methods out):

``````class Node {
Vertex pos;
char label[25];
Node *connections[6];
}
``````

Excursion: If you don't know, what pointers are in C/C++, here a short introduction. You should definitely read more about it on the web.

A pointer variable contains the address of another variable in the RAM. You can change this address and let the pointer point to another variable. A variable is marked as pointer with a `*` at the declaration. You can get the address of a variable (to set the pointer to this variable) through the `&` operator: `pointer = &variable` . If you dereference a pointer (by writing a `*` before the pointer name), you can work with the value, that the pointer points to. Each pointer variable has a type. It is the type of the object, that it points to. The pointer declaration `int *var` let's `var` point to `int` variables. If the type is a `class` or `struct` and you want to access members of the target (where it points to), you can use the shortened version `pointer->member`.

You define each node and add pointers to other nodes to represent connections. To traverse through the map, you need a start node. You save the address of the current node in a pointer. Then you can use it to access the connections of the current node. To actually go to the next node, you would set your pointer to the value saved in one of the `connections` elements, because that are pointers to the connected nodes.

The robot can then be moved along the straight lines between 2 nodes. When you want to also have non-straight, you can also do that by defining a middle point. You just to define the geometrical form, that the line should take.

The `Map` class can contain an array of `Nodes`. You can loop through all nodes in the array, if you need to, or you can traverse through the net by using the pointers.

The actual algorithm to find the path with the smallest travel distance is a big out of scope here. Doing that efficiently can be a complex task. You can research these algorithms on the web. The easiest way is to test all different paths in your program (without actually moving the robot), save the needed distance for each path and then choose the path based on that. You would need to write a termination condition, so that no connected will be taken twice on the same path (which would mean some kind of loop). Also keep in mind, that this will need more and more computation time, as your net grows. If it stays small and you don't need very fast computation, it might stay sufficient. If your implementation is recursive, you also have to consider, that each recursion takes up memory on the stack. You don't want to get out of memory.

Speaking of memory: In your implementation you use `String` for the label and you might want to use dynamic memory allocation for your map. That is not a good idea, because it can make swiss cheese out of your heap memory (heap fragmentation). It is better to define a fixed array, that can hold the maximal number of elements (as I have done with the connection of a node). The not needed elements can be set to something meaningless (for the connections you can use the null pointer and for unused nodes simply only null pointer connections).

• Oh, thank you so much. Exactly what I needed. I was stuck with trying to implement the idea based solely on coordinates and ended with nothing. This was exactly the solution I was looking for. Thank you! – Gaurav Mall Apr 30 at 20:09