How to make a directed graph?

I'm working on an robot that would be able to navigate through a maze, avoid obstacles and identify some of the objects in it. I have a monochromatic bitmap of the maze, that is supposed to be used in the robot navigation.

Up till now, I have converted/read the bitmap image of the maze into a 2D array of bits. However, now I need guidance on how to use that array to plan the path for the robot. I would appreciate if you could share any links as well, because I am new to all this stuff (I am just a 1st year BS electrical engineering student) and would be happy to have a more detailed explanation.

If you need me to elaborate on anything kindly say so.

I would be grateful!

Here's the image of the maze. This is just a sample image; the robot should be able to work with any maze (image) with similar dimensions. And you are welcome!

Thank you Chuck!

UPDATE Heres the code for sub2ind in c++. Kindly see if the output is correct:-

ofstream subtoind;
subtoind.open("sub2ind.txt");

int sub2ind = { 0 };
int ind2subROW = { 0 };
int ind2subCOL = { 0 };
int linearIndex=0;
j = 0;
z = 0;

for (j = 1; j <= 64; j++)
{
for (z = 1; z <= 96; z++)
{
linearIndex = z + (j - 1) * 96;
sub2ind[z-1][j-1] = linearIndex-1;
//ind2subROW[linearIndex-1] = j-1;
//ind2subCOL[linearIndex-1] = z-1;
}
}
for (j = 0; j < 96; j++)
{
subtoind << endl; //correction
cout << endl;

for (z = 0; z < 64; z++)
{
subtoind << sub2ind[j][z] << " ";
}
}
subtoind.close();

Heres the Link to the output file. https://drive.google.com/file/d/0BwUKS98DxycUSk5Fbnk1dDJnQ00/view?usp=sharing

• Glad I could help. If my answer gave you the information you were looking for, please accept it. Thanks! – Chuck Jun 7 '15 at 23:43
• Could your remove the output from the question body and maybe link to an output file instead? It's not going to format correctly as your matrix is 64 elements wide - it won't fit on a page. This means that your output just looks like a bunch of garbled numbers. – Chuck Jun 15 '15 at 14:10
• I have provided the link to the output file. – Muhammad Faique Shakeel Jun 15 '15 at 15:07
• I added a line to your code. I think all you need is what I've added; an endline character to force a wrap at the end of each row. When you use this, open it in Notepad and go to Format -> Word wrap and ensure that word wrap is not selected. This should cause line breaks to happen only when you've specified (at the end of each row), so column 1 should be numbered 1-> 96, column 2 97->192, etc. I can't force an edit, but I think you should be able to see/accept it. – Chuck Jun 15 '15 at 15:44
• @Chuck I have fixed the code. The output is correct now. Thanks – Muhammad Faique Shakeel Jun 15 '15 at 16:41

Use the bits in your array to create a connectivity map, assign distances between points (but it sounds like the map is uniformly sampled), then implement some version of Dykstra's algoritm.

The map you have can be parsed to see which non-wall tiles have neighbors. Use this, with a regular numbering scheme, to establish the connectivity graph. Each location on your map will have a distance associated with each neighbor. Dykstra uses the map and distances to find the shortest path from one point to another. One output is total distance, another output is a list of way points to get from A to B. The way points will be a list of every neighbor along the path, then all you have to do is get the car to move from one point to another.

:EDIT:

I started this as a comment, but it's too long and this is really more information on the answer, so I put it here.

Matlab has a neat trick where you can access values of a matrix with only one number (called linear indexing) instead of the usual row/col argument. Your map will be an arbitrary size, like the 64x96 you mention. In it you have a 1 if the craft is allowed there (is a path) and a 0 of the craft is not allowed there (is a wall).

So you should be able to display your map matrix, which again is of arbitrary size, and see all of the paths and walls.

Now to create to connectivity map (the directed graph, or digraph), you want to cycle through all of the points in your map and see which neighbors are adjacent. Note that the linear indexing I linked to shows that Matlab indexes increasing from the top of col1 to the bottom of col1, then top of col2, etc. Linear indexing is great because it gives each location on your map one number with which to refer to that position.

Let's assume your map has N locations, where N is the length x width of your map (N = 64x96 = 6144 in your example). Now your digraph matrix should be NxN, because you're looking for a relationship between any one location on your map and any other location. Let's name your digraph "Digraph" for simplicity.

This setup means that you should be able to call digraph(a,b) and get a value of 1 if $a$ and $b$ are connected and 0 if they are not, where again $a$ and $b$ are linear indices that refer to one location on your arbitrary map.

So, for some implementable Matlab code (writing this on the fly on my phone, so please forgive any errors):

nRows = size(Map,1);
nCols = size(Map,2);
mapSize = size(Map);
N = numel(Map);
Digraph = zeros(N, N);

for i = 1:nRows
for j = 1:nCols
currentPos = sub2ind(mapSize,i,j);
% left neighbor, if it exists
if (j-1)> 0
destPos = sub2ind (mapSize,i,j-1);
Digraph(currentPos,destPos) = Map(currentPos)*Map(destPos);
end
% right neighbor, if it exists
if (j+1)<=nCols
destPos = sub2ind (mapSize,i,j+1);
Digraph(currentPos,destPos) = Map(currentPos)*Map(destPos);
end
% top neighbor, if it exists
if (i-1)> 0
destPos = sub2ind (mapSize,i-1,j);
Digraph(currentPos,destPos) = Map(currentPos)*Map(destPos);
end
% bottom neighbor, if it exists
if (i+1)<=nRows
destPos = sub2ind (mapSize,i+1,j);
Digraph(currentPos,destPos) = Map(currentPos)*Map(destPos);
end
end
end

A couple things to note here - 1. This populates the digraph with zeros for every entry of Digraph(a,a). This is a matter of preference, but if you prefer you can set all of those entries to 1 (showing that $a$ is connected to itself) with the command Digraph = Digraph + eye(N);

1. If you use 1's and 0's in your map, then Map (currentPos)*Map (destPos) is either 1 if both entries are 1 or 0 if either entry is a 0. That is, it doesn't matter which is the wall, you equally can't move from wall to path or path to wall.

2. If you just use a regular map you should get a symmetric matrix. The nice thing about a Digraph is that it doesn't need to be symmetric. That is, you could have wormholes/tunnels/portals/chutes and ladders where one point on the map is connected to some remote point on the map.

3. Further, these tunnels can be bi-directional (two way), or they can be uni-durectional. That is, Digraph(a,b) could be 1 (path exists) where Digraph(b,a) is zero (path does not exist).

4. If there are such tunnels, you need to add them by hand after the script above runs.

5. Just like sub2ind gives you the linear index given conventional subscripts, ind2sub gives you subscripts given the linear index.

6. Finally, as a note, the Dykstra algorithm should give you a series of way points, but these will all be in linear index form. This is why I point out the ind2sub function above.

Hope this helps. Please feel free to comment if you have any more questions.

:EDIT EDIT: Linear indexing is just a way to refer to a matrix location with one value. You can brew your own as follows (again in Matlab form not c++, though they are similar):

nRows = size(matrixToBeIndexed,1);
nCols = size(matrixToBeIndexed,2);
N = numel(matrixToBeIndexed);
sub2ind = zeros(nRows,nCols);
ind2subROW = zeros(1,N);
ind2subCOL = zeros(1,N);

for i = 1:nCols
for j = 1:nRows
linearIndex = j + (i-1)*nRows;
sub2ind(j,i) = linearIndex;
ind2subROW(linearIndex) = j;
ind2subCOL(linearIndex) = i;
end
end

In this way you can pass subscripts to sub2ind, now a matrix instead of a function, and get the linear index, and you can pass a linear index to the pair of ind2sub functions to get subscripts. How you want to implement ind2sub is up to you; I would personally use an Nx2 matrix but I wrote it as two separate vectors for clarity.

Hope this helps!

• How can I make a connectivity map. Any link you can share, perhaps?? – Muhammad Faique Shakeel Jun 11 '15 at 14:16
• Sure! Here's a link to how to make the connectivity map (a directed graph), and then here's a link that actually gives some sample code to implement the Dykstra's algorithm. – Chuck Jun 11 '15 at 14:43
• As a side comment, I had to do this problem once before for a robotics class. A neat trick is that most languages will evaluate if X to be false if X is zero and true if X is anything other than 0. This means that you can replace the directed graph (1's show connections between adjacent locations) with a weighted directed graph, where the values in the matrix represent the "cost" of getting from one point to the adjacent point. You can still use "if X(1,2)" to see if 1 and 2 are adjacent, then use the value of X(1,2) as the weight/cost in the algorithm. – Chuck Jun 11 '15 at 14:52
• Thank you! I need some more help from you. Sorry to bother you again again. Chuck how will I know the number of vertices of the connectivity map if my 2D array of bits is of the size 64x96? And will start making the adjacency matrix from the starting point of the maze?? – Muhammad Faique Shakeel Jun 13 '15 at 6:35
• @Muhammad - see the edit in my answer. Too much content to put in a comment here. – Chuck Jun 13 '15 at 16:23