1
$\begingroup$

I'm working on an robot that would be able to navigate through a maze, avoid obstacles and identify some of the objects (Boxes in which it has to pot the balls) 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. Right now I am writing a code that should convert the 2D array (that represents the maze) into a connectivity map so that I could apply a path planning algorithm on it. Mr. @Chuck has helped me by providing a code in MATLAB. i have converted that code into C++, however the code isn't providing the right output. Kindly see the code and tell me what I am doing wrong.

I am sharing the link to the 2D array that has been made, the MATLAB code, and my code in C++ to convert the array into a connectivity map.

Link to the 2D array:-

https://drive.google.com/file/d/0BwUKS98DxycUZDZwTVYzY0lueFU/view?usp=sharing

MATLAB CODE:-

Map = load(map.mat);
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

Code in C++:-

int **digraph = NULL;
digraph = new int *[6144];

for (int i = 0; i < 6144; i++)
{
    digraph[i] = new int[6144];
}

for (j = 0; j < 96; j++)
{
    for (z = 0; z < 64; z++)
    {
        currentPos = sub2ind[j][z];
        digraph[currentPos][currentPos] = 0; //------NEW ADDITION-----------

    if ((z - 1) >= 0)
        {
            destPos = sub2ind[j][z - 1];
            digraph[currentPos][destPos] = bitarray[j][z] * bitarray[j][z - 1];
        }

    if ((z + 1) < 64)
        {
            destPos = sub2ind[j][z + 1];
            digraph[currentPos][destPos] = bitarray[j][z] * bitarray[j][z + 1];
        }

    if ((j - 1) >= 0)
        {
            destPos = sub2ind[j - 1][z];
            digraph[currentPos][destPos] = bitarray[j][z] * bitarray[j - 1][z];
        }

    if ((j + 1) < 96)
        {
            destPos = sub2ind[j + 1][z];
            digraph[currentPos][destPos] = bitarray[j][z] * bitarray[j + 1][z];
        }
    }

}

ofstream connectivityMap;
connectivityMap.open("diGraph.txt");

for (int l = 0; j < 100; l++) // printing only 100 elements
{
    for (int k = 0; k < 100; k++)
    {
        connectivityMap << digraph[l][k] << " ";
    }
}
$\endgroup$
  • $\begingroup$ For any future visitors, here's the link to the first portion of this problem - how do I plan a path through a maze. $\endgroup$ – Chuck Jun 16 '15 at 13:53
  • $\begingroup$ This is going to give you a graph with sooooo many 0's in it. It's such a waste of space and consequently has bad effects on the performance as well. Your original bitmap itself is the best representation of the graph. Can't you modify the algorithm you want to use to use the bitmap directly instead of an adjacency matrix? $\endgroup$ – Shahbaz Jun 27 '15 at 13:42
  • $\begingroup$ @Shahbaz I wasn't able to do so. I mean what should be the number of vertices if I use the original bitmap array? I couldn't figure it out. Should I share the code for dijsktra I am using now, and you tell me if I can modify the algorithm? $\endgroup$ – Muhammad Faique Shakeel Jun 27 '15 at 13:46
  • $\begingroup$ I don't have access to a desktop for a while, so I can't write up an answer. That specific question (Dijkstra on a bitmap) is fit for stackoverflow.com and is most likely already answered. Each pixel is a vertex by the way, which can have up to 4 neighbors; its surrounding pixels. $\endgroup$ – Shahbaz Jun 28 '15 at 0:07
  • $\begingroup$ @Shahbaz I can wait for your answer. However ill search it tomorrow on stackoverflow and let you know if I find an answer. Otherwise, Ill be glad to have your answer. $\endgroup$ – Muhammad Faique Shakeel Jun 28 '15 at 17:06
1
$\begingroup$

What is the problem you're having with the file?

The only two things I notice off the bat are that you aren't outputting an endline character between rows on your output stream and that it looks like you're initializing the digraph variable in an odd manner. As I mentioned previously, it's been a long time since I've used c++, but could you not just call int digraph[6144][6144] = {0};?

For the endline character,

for (int l = 0; j < 300; l++) // printing only 300 elements
{
    for (int k = 0; k < 300; k++)
    {
        connectivityMap << digraph[l][k] << " ";
    }
//End the line when you're done outputting rows
connectivityMap << endl;
}

Lastly, note that you're only outputting the first 300 columns of the first 300 rows - you're looking at the upper left 300x300 portion of the digraph. digraph[a][b] will equal 1 if a and b are connected; as you have a straightforward map this means it will equal 1 if they are neighbors and neither is a wall.

:EDIT:

I think I see most of the problems you're having with this.

  1. Here is the map image I made from your map text file. Note that you have a lot of pixels in the map, but it's really a low-resolution map that has been blown up.

map

  1. Here is a map image I made that is functionally equivalent but much smaller in resolution. Instead of having 6144 points, the small map has 84. I'm not sure how the black squares with the white 'X's should be treated, so I counted them as walls, though I think it would probably make more sense if they were paths and your start/end position. You should replace the 0's with 1's in those locations if this is the case.

small map

  1. You are getting entries on the diagonal in your digraph because your map is very basic. Point 1 connects to point 2, point 2 to 3, then 3 to 4, etc., so you wind up with 1's (path exists) on the diagonals. Matlab has a function called imwrite that you can use to generate images from matrices; I used this function to generate the digraph images below.

Small Digraph Large Digraph

Aside from the scale, the small digraph and large digraph have the same data regarding path connectivity. If you want to avoid keeping such a large, sparse matrix (it's all zeros on the upper/lower triangles because you don't have any paths from start to the middle of the map or start to finish!) then you can check out some of the other methods of map representation in this document on creating directed graphs.

Lastly, here's a link to the Matlab script I wrote to generate the images and digraphs.

$\endgroup$
  • $\begingroup$ The reason I am not simply calling int digraph[6144][6144] = {0}; is because the array size is too big. Even my core i5 laptop with 6GB Ram isn't able to dedicate that much memory to the program this way. Thats why I am using dynamic allocation to make the array. Chuck why do we need to initialize the digraph array to zeros? I haven't initialized it here and so in the output I get many -842150451 values apart from 0s (because I added a new line in the code please see; otherwise only got 1s and -842150451s) and 1s. -842150451 means that no value was allocated. $\endgroup$ – Muhammad Faique Shakeel Jun 22 '15 at 10:53
  • $\begingroup$ Ofcourse, there is no problem if I initialize the array to 0's, and I do get a digraph with 1s and 0s. But why do we need to initialize the array and why isn't every element of digraph allocated a 1 or 0 when those for loops run? Thanks $\endgroup$ – Muhammad Faique Shakeel Jun 22 '15 at 10:53
  • $\begingroup$ Heres the link to the output file. This I have onlu outputted first 100 rows and columns. link $\endgroup$ – Muhammad Faique Shakeel Jun 22 '15 at 11:00
  • $\begingroup$ if I initialize the digraph array to zeros all the -842150451s are replaced by 0s in the output.... $\endgroup$ – Muhammad Faique Shakeel Jun 22 '15 at 11:01
  • $\begingroup$ In your C++ conversion, you call digraph = new int *[6144];, then just below that you have a for loop where you declare digraph[i] = new int [6144];. Now, as mentioned, I am on the low end of C++ literacy, but it looks like your initial declaration creates digraph as a pointer (with the * notation), then, for each pointer in your pointer array, you assign it a row of integers? I'm not sure why you're not just declaring this as a two-dimensional int array. I don't know what you get by having pointers on one dimension. $\endgroup$ – Chuck Jun 22 '15 at 12:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.