12,395,327 members (67,559 online)
Rate this:
See more:
/* Given the following reduced micromouse maze (3x3=9 cells) stored in text file 'testin.txt':

```+-+-+-+
|6 7 8|
+-+-+ +
|3 4|5|
+ + + +
|0|1 2|
+-+-+-+```

The program opens the file, then uses getline to read a line at a time into a buffer. The elements of the buffer are moved into an array, 'mirrored', which stores the maze such that cell_0 is in the top left corner. This is done to simplify the process of translating the graphical representation to a Boolean representation of the maze's walls into the array 'MAP'. Thus, 'mirrored' becomes:

```+-+-+-+
|0|1 2|
+ + + +
|3 4|5|
+-+-+ +
|6 7 8|
+-+-+-+```

The first line '+-+-+-+' is analyzed element by element, '+' are ignored and depending on whether there is a ' ' or a '-', a '0' or '1' is written to 'MAP'. ('-' and '|' denote 'walls' and ' ' denotes the absence of a wall).

The bool array for the above maze would look like this:

The program then writes the content of the 'MAP' array to the screen.

```Map[cell][N,S,W,E bits]
-----------------------
0         0,1,1,1
1         0,1,1,0
2         0,1,0,1
3         1,0,1,0
4         1,0,0,1
5         0,0,1,1
6         1,1,1,0
7         1,1,0,0
8         1,0,0,1
-----------------------
```

The correct screen output should be:

```0         1, 0,1,1
1         1, 0,1,0
2         1, 0,0,1
3         0, 1,1,0
4         0, 1,0,1
5         0, 0,1,1
6         1, 1,1,0
7         1, 1,0,0
8         0, 1,0,1
```

For the time being, I am trying to at least get the N-bits right, but there must be a bug that I am not seeing. I believe I have excluded problems of local or global variables, which I initially thought might be causing it...

Any help from someone knowledgeable would be greatly appreciated!
*/

```#include <fstream.h>

int main()
{

const int size=3;  // Example, a standard micromouse maze is 16x16 cells...

const int rows=(2*size + 1);
const int columns=rows;
const int cells=size*size;
const int bits=4;  // North, South, West, East

char mazeFile[80]= "testin.txt";
//	char mazeCopy[80]= "testout.txt";

char buffer[columns+2];  // 2 elements added for EndOfLine
char mirrored[rows][columns];  // store contents of mazeFile such that cell_0 is at top left corner

bool MAP[cells][bits];

int m=0; int n=0;

//	Initialize all bits to 1
for (n=0; n<cells; n++){
for (m=0; m<bits; m++){
MAP[n][m]=1;
};
};

//	Initialize all bits to 1
for (n=0; n<rows; n++){
for (m=0; m<columns; m++){
mirrored[n][m]=1;
};
};

ifstream fin(mazeFile);  // open for reading
//	ofstream fout(mazeCopy);  // open for writing

int row=0; int col;  // don't confuse 'row' with 'rows'

while (row<rows)
{
fin.getline(buffer,columns+2);
//		fout << buffer << endl;
//		cout << buffer << endl;

row++;

for (col=0; col<columns; col++)
{
mirrored[rows-row][col] = buffer[col];
}

}

fin.close();
//	fout.close();  // close the file, ready for reopen

for (row=0; row<rows; row++){
for (col=0; col<columns; col++){
cout << mirrored[row][col];
}
cout<<endl;
}

//	int count=0;
row=0;
int POS=0;  // current cell POSition
int count=0;

while (row<rows)  // For standard maze, rows= 16+16+1= 33
{

if (row%2==0)  // if row is EVEN (0,2,4,6,..) - update N (and S bits)
{
for (col=1; col<(columns-1); col++)
{
if (col%2!=0)  // if Odd col (1,3,5,..) - update N (and S bits)
{
if (mirrored[row][col] == '-') {MAP[POS][0]=1;} // (and MAP[POS-3][1]=0;)
else {MAP[POS][0]=0;} // (and MAP[POS-3][1]=1;)
POS++;
}
}
POS=(POS-size); //count++;
}

else	// if row is ODD (1,3,5,..)- update W (and E bits)
{
for (col=0; col<columns; col++)
{
if (col%2==0)  //if Even col (0,2,4,6,..) - update W (and E bits)
{
if (mirrored[row][col] == '|') {MAP[POS][2]=1;} // (and MAP[POS-1][3]=0;)
else {MAP[POS][2]=0;} //(and MAP[POS-1][3]=0;)
POS++;
}
}
POS=(POS-size-1); //count++;
}

row++; count++;

//		cout << "\nRow: " << row;
//		cout << "\nCount: " << count;
//		cout << "\nPosition: " << POS << endl;

if (count!=3) {
} else {count=0; POS=POS+size;}

}

//	output MAP data to screen

for (m=0; m<cells; m++){

cout << "cell_" << m << " ";
for (n=0; n<bits; n++){
cout << MAP[m][n];
};
cout << endl;
};

cout << endl;

return 0;
}```
Posted 5-Nov-12 17:10pm
E.B.E141
Updated 8-Nov-12 0:29am
v6

First of all, it looks like you completely forgot to explain the purpose of the algorithm. You need to formulate the problem first, but you started from you data presentation (pretty awkward). The problem comes first, and then its analysis.

My general note: it looks like you create artificial problems with your data presentation, to have something to bravely overcome. :-)
--SA
E.B.E 6-Nov-12 1:26am

Hello. Thanks for replying. I was just trying to be succinct ...but I see your point. I disagree with your 'general note' though. Where is the "artificial problem"? There is a real but subtle problem which becomes evident once you have understood the problem.

Here is a little background: I am simulating an algorithm that solves "micromouse" mazes (http://en.wikipedia.org/wiki/Micromouse).

I have finally completed the algorithm and it seems to work well for the one 16x16=256 maze I manually represented in a 256x4 array (actually 256x8, but 4 bits for NSWE) as part of the program.

However, I would like to test many other mazes and entering each maze manually into an array is not feasible. The mazes I would like to test are already publicly available in the above format (or similar).

The text mazes files I need to read into memory and analyze are actually 16 cells by 16 cells, but in my question I have simplified to a 3x3 maze for convenience.

The purpose of this part of the wider algorithm is to open a maze file (.txt) and to translate the graphical layout into binary data (or the integer subset 1,0 as above, which I may change to bool later on...) and for that binary data to be stored in an array for the maze solving algorithm (already completed) to try to solve.

P.s.
My difficulty at this point is not so much about the programming language, but perfecting the logic, especially without the making the code cumbersome. Ideally I would like to figure out a way of examining all rows and columns using a general method rather than having to discriminate explicitly between peripheral walls... but I am having difficulties figuring out a decent way.

Rate this:

## Solution 1

Thank you for clarification. I think your problem is some inertia of thinking which makes you using primitive arrays. Also, not solving the problem in general form from the very beginning (at least make the algorithm for arbitrary dimensions of the maze) will give you troubles later.

You need to get an array of some cells, each being a structure or class instance. The dimensions of an array should not be hard-coded but should be calculated from data. From input data, put neighbor information in each cell. It will be redundant, so what? More important, the data will be cell-centered and symmetric (all cells are equal). One way to represent members would be a list (vector or fixed-size array of 0..8 elements, some unused) of objects representing direction — this way, you would list only the directions with open path. Represent direction with the pair of signed bytes, say (-1, 1) representing WN. The maze description will become closer to the algorithm.

After that, model the mouse, history of moves, with elements of history being a pointer to the same cell. On top of it, model the algorithm of the search. And so on…

—SA
E.B.E 6-Nov-12 2:45am

My question is more precise. Furthermore, the algorithm for solving the maze is complete.

I am stuck with this detail of translating a graphical text representation to an array. When compiled and run, so far I can update the array in an incomplete manner and I have problems especially when dealing with the last row, for example.

I take your point that I could design the code to account for mazes of other dimensions. However, I would only do this once the basic logic is fixed -- my logic is missing a step or two still.

The actual maze is a standard 16x16 so writing the code for other sized mazes is not really important. I understand there is a 32x32 variant of the competition, but this does not concern me at this stage.

I can be more explicit with highlighting the problem, but if I can see the issue but cannot solve it, then how can a person that does not see the problem at all stand a chance of solving it?

Thanks for taking the time to reply anyway. If I manage to figure it out before someone else does, I will post the completed code.

My intention is to then translate the solving part of the algorithm (once I have tested it on as many maze files as possible) to assembly language so I can program a microcontroller to solve a maze...

Ah, microcontroller... and I was wondering why would see any challenge in solving the problem for a robot on desktop system. :-) Well, modeling it first is probably a good idea, and, probably reasonably, you need to take microcontroller into account from the very beginning, such things as limited resource. And I did not keep it in mind when writing the answer. Well, it wasn't clear to me. By the way, could you give me any idea on memory limitation? can a performance become a bottleneck?

Now I understand your problem a bit better, but I have an impression that you limit yourself by the idea of changing or adding only a small piece of the code, the one which is not yes ready, assuming that "everything is working". This is something I doubt about. The good code is not written like this. In real life, such code is written be re-writing it all from scratch. Ideally, no more than two or three times, but it depends. By some reason, rewriting code became considered a big sin and strongly opposed by all kind of managers (I hope you don't have them), but this is because people only pretend they write the code only once, but in fact they "improve" it forever.

So, let me look at it a bit more. If I have any good idea, I'll tell you, but if you say in advance that you will keep some part of your code just because it "already works", my interest to your little problem would drop to zero, sorry. This is not just my style. After all, it's clear in advance that this problem is solvable; and your existing code is not so good to take it this serious. I believe you can solve your problem anyway, because there is nothing special about it and because you have enough knowledge and skills.

--SA
E.B.E 6-Nov-12 12:25pm

Hello.

My code was all designed from scratch. I developed the decision/solving part around an actual competition maze (which I mapped directly into a 256x8 array in the program). This took a little while to perfect, but eventually I managed to solve the given 16x16 maze in the program.

My algorithm, at least for the one maze I designed it around, does solve the maze correctly. It is not perfect because it does not (yet) calculate the 'best' solution. But I am leaving that for a later version.

I designed a little routine to display the solution to a screen. My algorithm definitely solves the one maze I tested it on, and I am confident enough about the solving part to now test it on other mazes.

The main algorithm is huge and unfriendly (designed to be as close to primitive ASM as possible, without becoming totally unreadable, to me ...someone else would probably find it impossible to follow without a manual).

...........So, here is the precise isolated problem I am asking for help with:
---
designing a piece of code that will interpret an ASCII representation and correctly update an array.
---

The code included above works to a point, but the logic of it needs refining. I may be able to figure it out eventually, but I have been struggling with this bit for a while.

Since you asked (I really don't want to confuse the problem too much though), the microcontroller will need one 8-bit word for each cell. 16x16=256 registers. For each register, 4 bits contain wall information (the map), N-S-W-E bits; the other 4 bits include information about whether or how the cell was accessed/left (so a path is gradually formed). Once I have proved that the solving logic works with other mazes, I will have the task of converting to ASM.

Yes, I understand all you say. And thank you about the information on the processor. This is really limiting, but what's the RAM size you can use? Or nothing? :-)
--SA
E.B.E 6-Nov-12 13:36pm

Well, some people have used 16-bit/32-bit processors for the micromouse competition. I believe top designers like Ng Beng and Dave Otten have.

However, these guys use giros and accelerometers and have designed devices much more advanced than what I am aiming for at the moment.

Earlier designs were based around 8-bit chips, which is what I intend to design around. At the moment I am considering using a PIC.

http://www.microchip.com/wwwproducts/Devices.aspx?dDocName=en010242

The one I am considering (I may need to upgrade if I find it too limiting) is 368 bytes -- enough for the 256 register map and then general purpose registers...

Interesting. So I did not get it: what, no RAM at all?! 256 registers are used instead of RAM? Well, that's tough, and challenging... :-)
--SA
E.B.E 6-Nov-12 13:56pm

368 bytes of RAM on-chip. Each RAM byte is 8-bits wide. (I should not have called the RAM addresses 'registers'...)

So the ASM program will be written in the 14KB flashable program memory and the array of maze cells will take up 256 RAM bytes.

Some of the remaining RAM bytes will be used to store variables such as the current cell position, orientation, and any other variable that might be needed.

There is also 256 EEPROM bytes, which I might use to store addition information about the 256 cells in RAM...

P.s. It is all tough and challenging. The biggest issue I see is with the 8 level stack, which the 'if-else' decision tree will need in its entirety...

Yes, got it. I was just asking for the confirmation, in some disbelieve. Well, the minimum CPU I used (on the level of CPU programming, registers, and ASM, too) was Intel 8086/8088, 640K RAM address space by 64K segments, actual RAM size vary... :-)
--SA
E.B.E 6-Nov-12 14:42pm

I suppose the closest thing to programming these simple MCUs was C64 or Amiga(Motorola6800) programming, but that was a little before my time.

The good thing about MCUs is they are cheap and can drive sensors or read sensors via on-chip peripherals, like analog-to-digital converters... Being simpler, they are probably easier to master as well.

Understood. However "simpler" does not mean easier to master, not always.
--SA
E.B.E 6-Nov-12 17:58pm

The PIC uses reduced instruction set code (RISC), with just over 30 mnemonics to learn. This makes learning the language easier, but probably means that a complex routine will require more lines of code and more clock cycles.
It would be interesting to design a circuit around an Intel CPU, but that would be overkill and I suspect it is not allowed by the rules.
...Anyway, thanks for the discussion. I will have another look at the issue I am having on my own and see if I can figure it out. The devil is in the detail, as they say. I will probably then be back posting questions under ASM!

Remembering even the IE64 instructions is not a big problem (understanding of all of the architecture starting from i386 is pretty complex though), after all, the reference can be handy, but using a limited repertoire is more difficult... Intel CPU for a robot? I don't know; I work a lot with control systems, industrial/scientific, where the cost of one such CPU, especially older or, would not count, but I understand the huge market difference. Anyway, they are getting pretty cheap, so, if the rules are ever changing, they will inevitably migrate two more powerful CPUs...
--SA
E.B.E 8-Nov-12 5:53am

I have modified the code to allow for different sized mazes, and to simplify the translation from ASCII to Boolean I have introduced a bit of code that mirrors the read file into an array. However, I can't seem to find the bug that is causing erroneous output for the N-bits (the other bits need some work still). Any ideas what I am doing wrong? For a while I thought that my compiler might be treating some variables as local instead of global, but that does not seem to be the issue.
E.B.E 8-Nov-12 16:47pm

I think I have narrowed down the problem to the POS variable.

For maze size=3:

For 'even' rows (0,2,4,6) the POS is incremented 3 times to POS=3 because the columns of interest are 3 in total (columns 1,3,5).

For 'odd' rows (1,3,5) the POS incremented 4 times to POS=4 because the columns of interest are 4 in total (columns 1,2,4,6).

Each row of cells is defined by 3 rows/lines of chars from the 'mirrored' array.

So, for the first row of cells: POS starts at 0; it is incremented by 3 (for the first line); it is incremented by 4 (for the second line); it is incremented by 3 (third line).

Once a line has been processed, POS must be reset to the first cell (cell 0) of the cell row (row 0) of interest, in order to continue updating the correct cell in the Boolean 'MAP' array.

Once a whole row of cells (which involves 3 lines) has been processed, POS must be set to the first cell in the next row line. And the above discussion applies over again, but with reference to POS=3 instead of POS=0.

...So, POS becomes 3, then 6 (for maze size=3).

Somewhere there is a bug with POS though as it should never exceed 4 positions from the first cell of any cell row. It should never exceed 10 (the last cell row), ...but somehow it does.
E.B.E 8-Nov-12 17:21pm

I seem to have corrected the error. Program updates N,S,W,E bits of 'MAP' correctly, ...except for E-bit of final cell. For anyone that was interested, I will post a succinct version of the solution once I have figured out this final issue.

Great. It would make an interesting article, but not forget to prepare interesting photographs. Let's close it for now. Thank you for interesting information on the project.
--SA

Top Experts
Last 24hrsThis month
 OriginalGriff 215 Jochen Arndt 130 Richard MacCutchan 90 Richard Deeming 80 khaled Ezzat 70
 OriginalGriff 5,998 Karthik Bangalore 2,382 ppolymorphe 2,350 F-ES Sitecore 1,877 Richard MacCutchan 1,707