micromouse algorithm.

jonduncan

I have a boe bot with BS2, I have thinking about upgrading. I think I will to a javelin, and I assume I can use the BOE board???? But untill I get the javelin I might try and see if i can do it with BS2, but BS2 has a memory shortage I might use external memory or something. I posted another topic saying I needed more memory. But I thought about it and maybe I don't. In a micromouse maze there are 256 locations, and we know there are walls all around the outside, but we don't know where the walls are on the inside. and the robot is trying to get to the center. For more information google micromouse

I would need 256bits for vertical walls and 256 bits for horizontal walls. I thought i might need 256 bytes·for a map weight.But I was thinking and the robot only needs to know the weights of·the locations of his nieghbors. and that is only·4 bytes. but now the problem is how·do I calculate the weights of it's neighbors? sorry I probably should give more information about the map but I see some people here already know some about micromouse. I have disigned a flood fill simulation·of a micromouse robot in c. Any ideas?

maybe I will just get javelin, converting c to java would be a whole lot easier and I would have plenty of memory.·

allanlane5

Yes, the Javelin is pin compatible with the BS2, so you can put it in the BOE board no problem.

One issue you may run into is that the Javelin supports debugging on-chip, so you can't use the programming serial port as a 'real' serial port -- there's lots of debug information that shows up on that port. This may not be a problem for you, but this is the reason the Javelin board has a second serial port.

The Javelin also takes more power (current) than a BS2, so it would be good to use a 7.5 volt DC adapter with the BOE.

fzrobot

In regards to your "weight" question, you could use 4 bits to represent the current state of the robot's surroundings:

First bit: Left wall
Second bit: South wall
Third bit: North wall
Fourth bit: Right wall

Then a 0 or 1 would represetn wall or no-wall respectively.

Additionally, you might need an extra 2 bits to keep track of orientation:
00 North
01 South
10 East
11 West

Just a thought, hope it helps.

-Cisco

jonduncan

What I am trying to do is find the quickest route to the center of the maze. So the weight need more than just walls, it is also possible that the robot can go in a circle if it always turned right, because the maze has more than one path to the center. there can also be dead ends. So my algorithm would put the distance from the center on the weights, what·it could do to save memory is check the distance from center of current location and the see which location of it's neighbors is closer. But now the real problem is that when the robot finds a new wall all the weights would change. I just need to be able to find a way of calculating the distance from the center when there are walls. can we use recurtion in pbasic, probably not, and that would use way to much memory. I think the only way to do this is with the javelin or an sx or a prop. I could use a different algorithm that just doesn't go where it has b4, but this is a race to the center and those could take a long time. or maybe a combination, where it has distance from center without walls and keeps track of where it has been b4

jonduncan

Well I think I figured it out. really for what I am doing I don't need to remember the walls, thats 32bytes i don't need to remember. and I don't need to remember all the weights. I figured out a new alorithm which is very likely to use less memory, but it is possible, very unlikely, but possible to use more. well I call is the node distant method, what it will do is basically create a stack, and a node is either an intersection or a location that the robot reaches that is 16 spaces from the intersection. When it reaches a node it will store the location of the node and the distance from the previous node the location will be a byte, and the distance since it is rarely over 16 it will be a nibble , but if it goes 16 spaces without hitting an intersection it will create another node. Also it will store the directions not to go on the node, like if there is a dead end or the distance from one node to another node is shorter one way then the other. It can store those in a nibble. Worst case scenario would be if there are no walls, there will be 256 nodes, at that would be 512bytes. But the best case scenario would be if there are no intersections and it would only need 32 bytes. but none of those will happen, and the rules say there will be a wall touching every courner. So I figure it would be about 128 bytes and thats if there is an intersection every 4 locations and the bot has searched the whole maze, which is also not too likely. So I can do this on the BS2 pretty easy using the EEPROM, but I might want to uprade to the B2pe or something so i don't have to write to the EEPROM. Thanks for your help!! I tell ya how it goes