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

Article View: uk.tech.robotics

Article #1

From: vince
Date: Mon, 21 Apr 2008 17:20

242 lines
12950 bytes

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.


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)

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 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.

Technical Details

Message-ID: <E14Pj.21251$B83.10134@newsfe3-gui.ntli.net>

Path:

arc1-ca.pugleaf.net!g2news1.google.com!news1.google.com!border1.nntp.dca.giganews.com!border2.nntp.dca.giganews.com!nntp.giganews.com!bigfeed3.bellsouth.net!news.bellsouth.net!news-in.ntli.net!newsrout1-win.ntli.net!ntli.net!news.highwinds-media.com!newspeer1-win.ntli.net!newsfe3-gui.ntli.net.POSTED!53ab2750!not-for-mail

Show Full Headers

Complete Article Headers

X-Google-Thread: 10352b,e669ba7b7106895f,start
X-Google-Thread: f6d13,e669ba7b7106895f,start
X-Google-Thread: 1100c6,e669ba7b7106895f,start
X-Google-Thread: 102569,e669ba7b7106895f,start
X-Google-Attributes: gid10352b,gidf6d13,gid1100c6,gid102569,domainid0,public,usenet
X-Google-Language: ENGLISH,ASCII-7-bit
Path: arc1-ca.pugleaf.net!g2news1.google.com!news1.google.com!border1.nntp.dca.giganews.com!border2.nntp.dca.giganews.com!nntp.giganews.com!bigfeed3.bellsouth.net!news.bellsouth.net!news-in.ntli.net!newsrout1-win.ntli.net!ntli.net!news.highwinds-media.com!newspeer1-win.ntli.net!newsfe3-gui.ntli.net.POSTED!53ab2750!not-for-mail
From: vince <tell.l8er@you.com>
User-Agent: Thunderbird 2.0.0.12 (Windows/20080213)
MIME-Version: 1.0
Newsgroups: uk.tech.robotics,uk.tech.misc,uklinux.help.newbies,england.chat
Subject: micromouse: PLEASE HELP A MOUSE FIND ITS WAY HOME!!!
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Lines: 242
Message-ID: <E14Pj.21251$B83.10134@newsfe3-gui.ntli.net>
Date: Mon, 21 Apr 2008 17:20:36 GMT
NNTP-Posting-Host: 80.0.96.84
X-Complaints-To: http://netreport.virginmedia.com
X-Trace: newsfe3-gui.ntli.net 1208798436 80.0.96.84 (Mon, 21 Apr 2008 18:20:36 BST)
NNTP-Posting-Date: Mon, 21 Apr 2008 18:20:36 BST
Organization: ntl Cablemodem News Service
X-Original-Bytes: 12610