Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

micromouse: PLEASE HELP A MOUSE FIND ITS WAY HOME!!!

2 views

Skip to first unread message

vince

unread,

Apr 21, 2008, 1:20:36 PM4/21/08

Is anyone here interested in micromouse, problems of logic or
programming? (The principles behind micromouse maze solving are fairly
simple so I have decided to leave that to you and the search engines to
save space here)

If you have no idea what this is all about and would like to know more,
this link shows a micromouse in action (cool!)
http://www.youtube.com/watch?v=_L9rkLAskWU

I have designed some code in C to solve a standard micromouse maze using
my own algorithm. The code is functional, it works as predicted and
there are no known bugs. The source code is very explicit since it will
eventually be translated into assembly language.

In order to prevent the mouse from "looping" or circling a region
indefinately, code was introduced to recognise "dead-ends".

In the simplest case, the mouse enters a cell through its only point of
entry/exit. In leaving the cell, it recognises that it is a dead-end and
so it blocks further access to the cell by writing a "virtual" wall to
memory.

My algorithm/logic fails when there is a "loop" within a dead-end
region. The result in some cases is that the mouse raises virtual walls
and progressively closes itself into an increasingly smaller region
until it is blocked and cannot search the maze any further.

PLEASE HELP A MOUSE FIND ITS WAY HOME!!!

The following is an output of my program. The first layout is the
physical maze, which the mouse must explore. The second layout is a map
in the mouses memory which is updated as the mouse searches the maze.
The list shows the mouse's stepwise moves numerically. The South-West
corner (start) of the maze is cell 0, the South-East corner is 15, the
cell North of 0 is cell 16 and so on. The four centre-most cells
(target) are 135, 136, 119 and 120. As can be seen by the list, the
mouse ends up closing itself within a region comprised of cells 137,
121, 122, 138 and 154.

Moves=150

16 32 33 34 35 36 52 53 69 85 101 100 99 83 67 68 84 68 67 51 50 66 82
66 65 81 97 113 129 145 129 113 97 81 65 49 48 64 80 96 112 128 144 160
161 177 193 209 225 224 240 241 242 243 244 245 246 247 248 249 250 251
252 236 235 236 237 238 222 206 190 174 173 189 205 221 220 219 218 217
216 215 214 213 212 211 210 194 195 179 163 164 180 196 180 164 148 132
116 117 133 149 165 181 197 198 199 200 201 202 203 187 171 170 169 168
167 151 152 153 137 121 122 138 154 138 122 121 137 121 122 138 154 138
122 121 137 121 122 138 154 138

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | |
+ +--+--+--+--+--+--+--+--+--+--+--+ +--+--+--+
| | | | | | | | | | | | | |
+ + +--+--+--+--+--+--+--+--+--+--+--+--+ +--+
| | | | | |
+--+ + +--+--+--+--+--+--+--+--+--+--+ + +--+
| | | | | | | | | |
+--+ + + +--+ +--+--+--+--+--+ +--+ + +--+
| | | | | | | | | | | | | | | | |
+--+ +--+ +--+ +--+--+--+--+--+ +--+ + +--+
| | | | | | | | |
+ +--+--+ + + +--+ +--+--+ +--+--+ +--+--+
| | | | | | | | | | | | | | |
+ +--+--+--+ + +--+--+--+ +--+--+--+--+--+--+
| | | | | | | | | | | | | | | | |
+ +--+--+--+ + +--+--+--+ + +--+--+--+--+--+
| | | | | | | | | | | | | |
+ +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | |
+ +--+--+ +--+ +--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | |
+ +--+--+ +--+ +--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | |
+ + + + +--+ +--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | |
+--+--+--+--+ +--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | |
+ +--+--+ +--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | |
+ +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
Press any key to continue

Vince.

In order to prevent the mouse from "looping" or circling a region
indefinately, code was introduced to recognise "dead-ends".

PLEASE HELP A MOUSE FIND ITS WAY HOME!!!

The following is an output of my program. The first layout is the
physical maze, which the mouse must explore. The second layout is a map
in the mouses memory which is updated as the mouse searches the maze.
The list shows the mouse's moves numerically. The South-West Corner of
the maze is cell 0, the South-East corner is 15, the cell North of 0 is
cell 16 and so on. As can be seen by the list, the mouse ends up closing
itself within a region comprised of cells 137, 121, 122, 138 and 154.

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| |
+ +--+--+--+--+--+--+--+--+--+--+--+ +--+ +--+
| | | |
+ + + +--+--+--+--+--+--+--+ +--+--+--+ + +
| | | | | |
+ + + +--+--+--+--+--+--+--+--+--+--+ + + +
| | | | | | | | |
+ + + + + + +--+--+--+--+--+ + + + + +
| | | | | | | | | | | |
+ + + + + + + + +--+--+ + + + + + +
| | | | | | |
+ +--+ + + + + + +--+--+ +--+--+ +--+ +
| | | | | | | | | | | |
+ + + + + + + +--+--+ + + +--+--+ + +
| | | | | | | | | | | | | | |
+ + + + + + + + + + + + + + + + +
| | | | | | | | | | |
+ + + +--+--+--+ +--+ +--+--+ + + + +--+
| | | | | | | | | |
+ + +--+ +--+ + +--+--+--+ + + +--+ + +
| | | | | | | | |
+ + + + + + +--+ +--+ +--+--+--+ + + +
| | | | | | | |
+ + + + +--+ +--+--+ +--+ +--+--+--+--+ +
| | | | | | |
+--+--+--+--+ +--+--+ +--+--+--+--+--+ +--+ +
| | | |
+ +--+--+ +--+ +--+--+ +--+--+ +--+--+ + +
| | | | |
+ + +--+--+--+--+--+ + +--+--+--+--+--+--+ +
| | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
Moves=150
16 32 33 34 35 36 52 53 69 85 101 100 99 83 67 68 84 68 67 51 50 66 82
66 65 81
97 113 129 145 129 113 97 81 65 49 48 64 80 96 112 128 144 160 161 177
193 209
225 224 240 241 242 243 244 245 246 247 248 249 250 251 252 236 235 236
237 238
222 206 190 174 173 189 205 221 220 219 218 217 216 215 214 213 212 211
210 194
195 179 163 164 180 196 180 164 148 132 116 117 133 149 165 181 197 198
199 200
201 202 203 187 171 170 169 168 167 151 152 153 137 121 122 138 154 138
122 121
137 121 122 138 154 138 122 121 137 121 122 138 154 138
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | |
+ +--+--+--+--+--+--+--+--+--+--+--+ +--+--+--+
| | | | | | | | | | | | | |
+ + +--+--+--+--+--+--+--+--+--+--+--+--+ +--+
| | | | | |
+--+ + +--+--+--+--+--+--+--+--+--+--+ + +--+
| | | | | | | | | |
+--+ + + +--+ +--+--+--+--+--+ +--+ + +--+
| | | | | | | | | | | | | | | | |
+--+ +--+ +--+ +--+--+--+--+--+ +--+ + +--+
| | | | | | | | |
+ +--+--+ + + +--+ +--+--+ +--+--+ +--+--+
| | | | | | | | | | | | | | |
+ +--+--+--+ + +--+--+--+ +--+--+--+--+--+--+
| | | | | | | | | | | | | | | | |
+ +--+--+--+ + +--+--+--+ + +--+--+--+--+--+
| | | | | | | | | | | | | |
+ +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | |
+ +--+--+ +--+ +--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | |
+ +--+--+ +--+ +--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | |
+ + + + +--+ +--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | |
+--+--+--+--+ +--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | |
+ +--+--+ +--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | |
+ +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
Press any key to continue

Vince.

vince

unread,

Apr 22, 2008, 11:01:31 PM4/22/08

The code contained a bug, which has now been corrected (so my reasoning
was correct after all!) The code is, therefore, complete and has both
"search mode" and "run mode" functionality. The algorithm has not been
designed to find the optimum solution, but a solution which removes
"loops" and "dead-ends" and finds as "direct" as possible a path from
the start to the centre. However, I plan to add an additional layer of
code at a later date to this effect. I will now direct my efforts to
converting the code from C to ASM. If anyone is genuinely interested in
sharing this project and has some experience with ASM (or later on with
the hardware side), then I would be interested in hearing from you,
especially if you have experience with event/interrupt driven code, task
scheduling and complex conditional statements in ASM. Please post a
message in this thread and I will get back to you as soon as possible...

P=0, start search mode...

167 151 152 153 137 121 122 138 154 138 122 121 137 153 152 151 167 183
182 166 150 134 118 102 103 104 120

P=120, end search mode...

Output register contents to screen...

cell PASSED WALLS
---- -------- --------
0 0 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1
3 1 1 1 1 1 1 1 1
4 1 1 1 1 1 1 1 1
5 1 1 1 1 1 1 1 1
6 1 1 1 1 1 1 1 1
7 1 1 1 1 1 1 1 1
8 1 1 1 1 1 1 1 1
9 1 1 1 1 1 1 1 1
10 1 1 1 1 1 1 1 1
11 1 1 1 1 1 1 1 1
12 1 1 1 1 1 1 1 1
13 1 1 1 1 1 1 1 1
14 1 1 1 1 1 1 1 1
15 1 1 1 1 1 1 1 1
16 0 1 1 0 0 1 1 0
17 1 1 1 1 1 1 1 1
18 1 1 1 1 1 1 1 1
19 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1
21 1 1 1 1 1 1 1 1
22 1 1 1 1 1 1 1 1
23 1 1 1 1 1 1 1 1
24 1 1 1 1 1 1 1 1
25 1 1 1 1 1 1 1 1
26 1 1 1 1 1 1 1 1
27 1 1 1 1 1 1 1 1
28 1 1 1 1 1 1 1 1
29 1 1 1 1 1 1 1 1
30 1 1 1 1 1 1 1 1
31 1 1 1 1 1 1 1 1
32 1 1 0 0 1 1 0 0
33 1 0 0 1 1 0 0 1
34 1 0 0 1 1 0 0 1
35 1 0 0 1 1 0 0 0
36 0 0 1 1 0 0 0 1
37 1 1 1 1 1 1 1 1
38 1 1 1 1 1 1 1 1
39 1 1 1 1 1 1 1 1
40 1 1 1 1 1 1 1 1
41 1 1 1 1 1 1 1 1
42 1 1 1 1 1 1 1 1
43 1 1 1 1 1 1 1 1
44 1 1 1 1 1 1 1 1
45 1 1 1 1 1 1 1 1
46 1 1 1 1 1 1 1 1
47 1 1 1 1 1 1 1 1
48 0 1 0 1 0 1 0 1
49 0 0 1 1 0 0 1 1
50 0 1 0 1 0 1 0 1
51 0 0 1 1 0 0 1 1
52 1 1 0 0 1 1 0 0
53 0 0 1 1 0 0 1 1
54 1 1 1 1 1 1 1 1
55 1 1 1 1 1 1 1 1
56 1 1 1 1 1 1 1 1
57 1 1 1 1 1 1 1 1
58 1 1 1 1 1 1 1 1
59 1 1 1 1 1 1 1 1
60 1 1 1 1 1 1 1 1
61 1 1 1 1 1 1 1 1
62 1 1 1 1 1 1 1 1
63 1 1 1 1 1 1 1 1
64 0 1 1 0 0 1 1 0
65 1 1 0 0 1 1 0 0
66 1 0 1 0 1 0 1 0
67 0 1 1 0 0 1 1 0
68 1 1 1 1 1 1 1 1
69 0 1 1 0 0 1 1 0
70 1 1 1 1 1 1 1 1
71 1 1 1 1 1 1 1 1
72 1 1 1 1 1 1 1 1
73 1 1 1 1 1 1 1 1
74 1 1 1 1 1 1 1 1
75 1 1 1 1 1 1 1 1
76 1 1 1 1 1 1 1 1
77 1 1 1 1 1 1 1 1
78 1 1 1 1 1 1 1 1
79 1 1 1 1 1 1 1 1
80 0 1 1 0 0 1 1 0
81 1 1 1 1 1 1 1 1
82 1 1 1 1 1 1 1 1
83 0 1 1 0 0 1 1 0
84 1 1 1 1 1 1 1 1
85 0 1 1 0 0 1 1 0
86 1 1 1 1 1 1 1 1
87 1 1 1 1 1 1 1 1
88 1 1 1 1 1 1 1 1
89 1 1 1 1 1 1 1 1
90 1 1 1 1 1 1 1 1
91 1 1 1 1 1 1 1 1
92 1 1 1 1 1 1 1 1
93 1 1 1 1 1 1 1 1
94 1 1 1 1 1 1 1 1
95 1 1 1 1 1 1 1 1
96 0 1 1 0 0 1 1 0
97 1 1 1 1 1 1 1 1
98 1 1 1 1 1 1 1 1
99 1 1 0 0 1 1 0 0
100 1 0 0 1 1 0 0 1
101 1 0 1 0 1 0 1 0
102 0 1 0 1 0 1 0 0
103 1 0 0 1 1 0 0 1
104 0 0 1 1 0 0 0 1
105 1 1 1 1 1 1 1 1
106 1 1 1 1 1 1 1 1
107 1 1 1 1 1 1 1 1
108 1 1 1 1 1 1 1 1
109 1 1 1 1 1 1 1 1
110 1 1 1 1 1 1 1 1
111 1 1 1 1 1 1 1 1
112 0 1 1 0 0 1 1 0
113 1 1 1 1 1 1 1 1
114 1 1 1 1 1 1 1 1
115 1 1 1 1 1 1 1 1
116 0 1 0 1 0 0 0 1
117 0 0 1 1 0 0 1 1
118 0 1 1 0 0 1 1 0
119 1 1 1 1 1 1 1 1
120 1 1 1 0 1 1 1 1
121 1 1 1 1 1 1 1 1
122 1 1 1 1 1 1 1 1
123 1 1 1 1 1 1 1 1
124 1 1 1 1 1 1 1 1
125 1 1 1 1 1 1 1 1
126 1 1 1 1 1 1 1 1
127 1 1 1 1 1 1 1 1
128 0 1 1 0 0 1 1 0
129 1 1 1 1 1 1 1 1
130 1 1 1 1 1 1 1 1
131 1 1 1 1 1 1 1 1
132 0 1 1 0 0 1 1 0
133 0 1 1 0 0 1 1 0
134 0 1 1 0 0 1 1 0
135 1 1 1 1 1 1 1 1
136 1 1 1 1 1 1 1 1
137 1 1 1 1 1 1 1 1
138 1 1 1 1 1 1 1 1
139 1 1 1 1 1 1 1 1
140 1 1 1 1 1 1 1 1
141 1 1 1 1 1 1 1 1
142 1 1 1 1 1 1 1 1
143 1 1 1 1 1 1 1 1
144 0 1 1 0 0 1 1 0
145 1 1 1 1 1 1 1 1
146 1 1 1 1 1 1 1 1
147 1 1 1 1 1 1 1 1
148 0 1 1 0 0 1 1 0
149 0 1 1 0 0 1 1 0
150 0 1 1 0 0 1 1 0
151 1 1 1 1 1 1 1 1
152 1 1 1 1 1 1 1 1
153 1 1 1 1 1 1 1 1
154 1 1 1 1 1 1 1 1
155 1 1 1 1 1 1 1 1
156 1 1 1 1 1 1 1 1
157 1 1 1 1 1 1 1 1
158 1 1 1 1 1 1 1 1
159 1 1 1 1 1 1 1 1
160 1 1 0 0 0 1 0 0
161 0 0 1 1 0 0 1 1
162 1 1 1 1 1 1 1 1
163 0 1 0 1 0 0 0 0
164 1 0 1 0 1 0 1 0
165 0 1 1 0 0 1 1 0
166 0 1 1 0 0 1 1 0
167 0 1 0 1 0 1 0 1
168 1 0 0 1 1 0 0 1
169 1 0 0 1 1 0 0 1
170 1 0 0 1 0 0 0 1
171 0 0 1 1 0 0 0 1
172 1 1 1 1 1 1 1 1
173 0 1 0 1 0 1 0 0
174 0 0 1 1 0 0 1 1
175 1 1 1 1 1 1 1 1
176 1 1 1 1 1 1 1 1
177 0 1 1 0 0 1 1 0
178 1 1 1 1 1 1 1 1
179 0 1 1 0 0 1 1 0
180 1 1 1 1 1 1 1 1
181 0 1 1 0 0 1 1 0
182 1 1 0 0 1 1 0 0
183 1 0 1 0 1 0 0 0
184 1 1 1 1 1 1 1 1
185 1 1 1 1 1 1 1 1
186 1 1 1 1 1 1 1 1
187 0 1 1 0 0 1 1 0
188 1 1 1 1 1 1 1 1
189 0 1 1 0 0 1 1 0
190 0 1 1 0 0 1 0 0
191 1 1 1 1 1 1 1 1
192 1 1 1 1 1 1 1 1
193 0 1 1 0 0 1 1 0
194 0 1 0 1 0 1 0 0
195 1 0 1 0 1 0 1 0
196 1 1 1 1 1 1 1 1
197 1 1 0 0 1 1 0 0
198 1 0 0 1 1 0 0 1
199 1 0 0 1 1 0 0 1
200 1 0 0 1 1 0 0 1
201 1 0 0 1 1 0 0 1
202 1 0 0 1 1 0 0 1
203 1 0 1 0 1 0 0 0
204 1 1 1 1 1 1 1 1
205 0 1 1 0 0 1 1 0
206 0 1 1 0 0 1 1 0
207 1 1 1 1 1 1 1 1
208 1 1 1 1 1 1 1 1
209 0 1 1 0 0 1 1 0
210 1 1 0 0 0 1 0 0
211 1 0 0 1 1 0 0 1
212 1 0 0 1 1 0 0 1
213 1 0 0 1 1 0 0 1
214 1 0 0 1 1 0 0 1
215 1 0 0 1 1 0 0 1
216 1 0 0 1 1 0 0 1
217 1 0 0 1 1 0 0 1
218 1 0 0 1 0 0 0 1
219 1 0 0 1 1 0 0 1
220 1 0 0 1 1 0 0 1
221 1 0 1 0 1 0 1 0
222 0 1 1 0 0 1 1 0
223 1 1 1 1 1 1 1 1
224 0 1 0 1 0 1 0 0
225 1 0 1 0 1 0 1 0
226 1 1 1 1 1 1 1 1
227 1 1 1 1 1 1 1 1
228 1 1 1 1 1 1 1 1
229 1 1 1 1 1 1 1 1
230 1 1 1 1 1 1 1 1
231 1 1 1 1 1 1 1 1
232 1 1 1 1 1 1 1 1
233 1 1 1 1 1 1 1 1
234 1 1 1 1 1 1 1 1
235 1 1 1 1 1 1 1 1
236 0 1 0 1 0 1 0 1
237 1 0 0 1 1 0 0 1
238 1 0 1 0 0 0 0 0
239 1 1 1 1 1 1 1 1
240 1 1 0 0 1 1 0 0
241 1 0 0 1 1 0 0 1
242 1 0 0 1 1 0 0 1
243 1 0 0 1 1 0 0 1
244 1 0 0 1 1 0 0 1
245 1 0 0 1 1 0 0 1
246 1 0 0 1 1 0 0 1
247 1 0 0 1 1 0 0 1
248 1 0 0 1 1 0 0 1
249 1 0 0 1 1 0 0 1
250 1 0 0 1 1 0 0 1
251 1 0 0 1 1 0 0 1
252 1 0 1 0 1 0 0 0
253 1 1 1 1 1 1 1 1
254 1 1 1 1 1 1 1 1
255 1 1 1 1 1 1 1 1

P=120, start run mode...

104 103 102 118 134 150 166 182 183 167 168 169 170 171 187 203 202 201
200 199 198 197 181 165 149 133 117 116 132 148 164 163 179 195 194 210
211 212 213 214 215 216 217 218 219 220 221 205 189 173 174 190 206 222
238 237 236 252 251 250 249 248 247 246 245 244 243 242 241 240 224 225
209 193 177 161 160 144 128 112 96 80 64 48 49 65 66 50 51 67 83 99 100
101 85 69 53 52 36 35 34 33 32 16 0

P=0, end run mode...

0 new messages