Using PING))) to map targets and finding their center

Mightor

Hi there,

I'm trying to come up with a way to scan the front of my robot for targets and then finding their center. The reason I'm working on this is to make it possible for a mini-sumo bot to detect its opponent, calculate the angle of attack and then hit it square in the middle. Right now I'm doing all of this on my Boe-Bot seeing as I don't have a sumo bot (yet).
I used the Boe-dar as a start and started modifying the heck out of it. It divides the 128 brad area in front of it into 16 sections. The map it draws is in fact a Word sized variable in which I set the bits to 1 if an echo within 20cms was detect and 0 if this was not the case. Using DEBUG, this gives me maps like this:
0001111000000000 and 0000000000011110

Now I know how to use my human brain to find the center of these targets:
0001110000000000 <-- target size
0000100000000000 <--- center

However, I have no idea how to implement something like this on my basic stamp. It should work for targets that are an even number of bits long and odd number, e.g. 0001111000000000 = 4 bits long, and 0001110000000000 = 3 bits long. For the even ones, I don't really care if the 'middle' is calculated as a single bit that's a bit more to the right or to the left.

I am not looking for a hand-out, I wouldn't have started this project if I weren't willing to learn, but some hints would be nice [noparse]:)[/noparse]

I've attached my program so you can see what I've done so far. I realise that 20cms is not a great distance to work with for a mini-sumo, but I am testing this on my desk and it's not very big. Anything more than 20cms is going to give me a false echo.

Edit: I will only ever be tracking one single target; namely the other sumo, so no fancy multi-target tracking stuff needs to be built in.

Gr,
Mightor

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
| What the world needs is more geniuses with humility, there are so few of us left.

Post Edited (Mightor) : 7/28/2007 3:55:24 PM GMT

Mike Green

You want to find the "left" and "right" sides of the object. Eventually, you'll want to also check for noise and other (to be ignored) objects.
Basically, treat the word as a bit array (use an alias) and scan from bit 0 to bit 15. When you find the first 1 bit, save its index and then continue scanning, but for the first 0 bit after the 1 bits and save its index. Subtract the two and that gives you the width. You could check for a minimum acceptable width (like 2 or 3) and ignore narrower objects. For finding the middle, try multiplying everything by two. If Rt is the index of the first 1 bit and Lt is the index of the next 0 bit, the middle could be calculated as:
middle = ((Rt*2) - (Lt*2))/2+(Lt*2)
This would be in 1/2 step units and you could compute the positioning information from that.

Mightor

Mike,

I will have a look at that! As for using an alias, I am not sure what you mean. I am already using map.BIT0(index) to access the individual bits to draw my map. What would an alias allow me to do?

Gr,
Mightor

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
| What the world needs is more geniuses with humility, there are so few of us left.

Mightor

I have it working now. This is the output generated by the DEBUG window when I place a mug in front and to the side of the bot:

0000001111111000
0000000001000000
 left = 12
 right = 6
 Target width: 6
 Middle : 9

The first map is what the bot sees and the second one is what the program has calculated as the middle of the target. As you can see, it finds the middle just fine now. Thanks for the suggestion, Mike.

Gr,
Mightor

Find_Edges:
  state = 0
  left = 0
  right = 0
  middlemap = 0
  FOR i = 0 TO 15
    IF state = 0 AND map.BIT0(i) = 1 AND left = 0 THEN
      right = i
      state = 1
    ELSEIF state = 1 AND map.BIT0(i) = 1 AND right > 0 THEN
      left = i
    ELSE
      state = 0
    ENDIF
  NEXT
  DEBUG CRSRXY, 1, 6, ? left, CLREOL
  DEBUG CRSRXY, 1, 7, ? right, CLREOL
  DEBUG CRSRXY, 1, 8, "Target width: ", DEC left - right, CLREOL
  DEBUG CRSRXY, 1, 9, "Middle : ", DEC (left - right) / 2  + right
  IF (left - right) > 1 THEN
    middlemap.BIT0((left - right) / 2  + right) = 1
  ENDIF
  FOR i = 0 TO 15
    DEBUG CRSRXY, i, 5, DEC middlemap.BIT0(i)
  NEXT

  RETURN

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
| What the world needs is more geniuses with humility, there are so few of us left.

Mike Green

The "map.BIT0(index)" is what I had in mind. An alias is just a different way to use a name with a different type for the same variable space so you could have one name for a word and another name for an array of bits, but they'd refer to the same variable space.

Mightor

Mike,

Ah ok, I knew about the trick of using aliases to 'reuse' a var under a diff name, it is mentioned in the Boe-Bot book. I thought you had some other trick for aliasing a Word into a Bit(16) or something using a trick that I hadn't come across yet, hehe.

Gr,
Mightor

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
| What the world needs is more geniuses with humility, there are so few of us left.

Mike Green

What if you have a run of an even number of 1 bits? Are you ok with the middle location being off by 1/2 unit?

Mightor

Mike,

Yeah, it doesn't bother me at all. I'll be using the wheel encoders to check how far I've turned and they're less than 10 brads accurate anyway when doing a pivot turn. After all, this will be used to plot a collision course for my mini-sumo (that hasn't been built yet).
When I have my Propeller board I intent to make this into a SPIN program and then I will actually keep track of distance between the bot and the target at each sweep increment so I can then see how the target is turned towards me. I am assuming, of course, that my opponent will have the courtesy to stop moving while I take these measurements.
My mini-sumo will be based on the Prop ProtoBoard, this BasicStamp program is just so I can get to grips with the technique behind target acquisition.

Gr,
Mightor

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
| What the world needs is more geniuses with humility, there are so few of us left.