Has anyone got any suggestions on how to improve my collision detection algo?


    Feb 06 2008 | 10:03 pm
    max v2;
    Currently I'm going by the top left, top right, bottom left and bottom right pixel on the the square ball and telling the counter to change direction should any of those areas come into contact with the area the shape is in.
    This however, doesn't work very well?!
    Does any one have any ideas on how it could work, and is there a much better way of doing it than this?
    Thanks,
    Rhys

    • Feb 06 2008 | 10:32 pm
      maybe you would be interested in checking katsuhiro chiba's "ref matrix" patch, it might give a couple of ideas :)
    • Feb 07 2008 | 12:40 am
      That's an excellent patch, thanks karrrlo!
      I was thinking along similar lines only I didn't want to be limited to just squares, and I would like to avoid using grid patterns, if possible.
      The LCD object seems perfect as it allows for user created sprites and therefore the user's imagination, to run riot.
      I think the collision detection on that must be done by on a pixel by pixel basis though?
      The algo I came up with and thought would work, unfortunately has various oddities and kinks that come with it...
      Any other thoughts anyone?
      Rhys
    • Feb 07 2008 | 3:29 am
    • Feb 07 2008 | 9:57 am
      Derek:
      you patch seems interesting but there miss some abstractions,
      which i couldn't find on maxobjects...
      Could you send them along, or give a link to get them?
      Rhys:
      there have been some posts on this forum on this topic,
      you could check them.
      a few ideas on how to get collision done:
      1) you will need to have speed stored at some point,
      It helps for making objects evolution controlled by speed.
      Namely : new_position = position + current_speed.
      Check "advanced navigation" patch for a nice exemple
      on how to do it with jit.matrix... (however you could do
      with matrixes)
      2) in your collision patch, check estimated next position to know if you
      encounter an obstacle
      and correct speed accordingly... this part may be tricky, you will find
      literrature on the net
      on algorithms to achieve this
      for exemple :
      3) Take into account all simplication you can get from a simple
      geometry. (hint: very important point!!)
      4) get some coffee and a sheet of paper for drawing these trigonometric
      formulas back into mind.
      It took me almost a week to get something clean and efficient.
      I developped it for someone else and cannot post it for licence reason,
      sorry, but I hope the lines above will help you get started.
      ... vincent
      www.pucemuse.com
      www.mazirkat.org/vincent/
      Derek Franz a écrit :
      > psst! hey buddy,over here. its a collision detection algo for any two
      > lines in 2d space, it requires peter elsea;s l== and position by
      > James McCartney...its hot, i use it whenever I can
      >
      > max v2;
      > #N vpatcher 130 129 774 594;
      > #P window setfont "Sans Serif" 9.;
      > #P window linecount 1;
      > #P newex 274 290 60 196617 _ paintoval;
      > #P newex 276 268 27 196617 l;
      > #P flonum 229 210 57 9 0 0 0 3 0 0 0 221 221 221 222 222 222 0 0 0;
      > #P newex 227 165 66 196617 pack 0 0 0 0;
      > #P newex 90 400 32 196617 sel 1;
      > #P newex 76 352 105 196617 pack 0 0 0 0 0 0 0 0;
      > #P newex 419 30 94 196617 bgcolor 30 240 23;
      > #P message 356 33 59 196617 multitetris;
      > #P window linecount 3;
      > #P message 327 86 85 196617 A = y2-y1 B = x1-x2 C = A*x1+B*y1;
      > #P window linecount 1;
      > #P message 497 228 79 196617 return bang if ||;
      > #P message 218 400 102 196617 return bangig collide;
      > #P message 356 52 203 196617 collision detechtion between 2linesegments;
      > #P button 73 424 15 0;
      > #P newex 76 374 97 196617 l== 1 1 1 1 1 1 1 1;
      > #P newex 239 324 27 196617 >=;
      > #P newex 268 324 27 196617 > #P newex 178 324 27 196617 >=;
      > #P newex 207 324 27 196617 > #P newex 58 328 27 196617 >=;
      > #P newex 148 325 27 196617 > #P newex 87 325 27 196617 >=;
      > #P newex 116 326 27 196617 > #P newex 197 269 76 196617 unpack 0 0 0 0;
      > #P newex 91 269 76 196617 unpack 0 0 0 0;
      > #P message 162 303 154 196617 min (y1 , y2) ≤ x ≤ max(y1 , y2);
      > #P message 10 302 162 196617 min (x1 , x2) ≤ x ≤ max(x1 , x2);
      > #P button 477 227 15 0;
      > #P newex 479 206 32 196617 sel 0;
      > #N vpatcher 143 219 676 650;
      > #P outlet 353 238 15 0;
      > #P window setfont "Sans Serif" 9.;
      > #P window linecount 0;
      > #P newex 354 209 66 196617 pack 0 0 0 0;
      > #P newex 370 131 53 196617 maximum;
      > #P newex 357 109 50 196617 minimum;
      > #P newex 324 132 53 196617 maximum;
      > #P newex 295 110 50 196617 minimum;
      > #P window linecount 3;
      > #P message 208 147 85 196617 A = y2-y1 B = x1-x2 C = A*x1+B*y1;
      > #P outlet 131 219 15 0;
      > #P outlet 232 217 15 0;
      > #P outlet 33 204 15 0;
      > #P window linecount 1;
      > #P newex 156 150 27 196617 *;
      > #P newex 127 186 27 196617 +;
      > #P newex 86 153 27 196617 *;
      > #P newex 152 111 27 196617 -;
      > #P newex 143 76 67 196617 unpack 0 0 0;
      > #P newex 61 83 40 196617 unpack;
      > #P newex 155 50 72 196617 position 0 2 1;
      > #P newex 82 50 63 196617 position 3 1;
      > #P newex 65 113 27 196617 -;
      > #P inlet 121 23 15 0;
      > #P connect 1 0 10 0;
      > #P connect 2 0 4 0;
      > #P connect 4 0 1 0;
      > #P connect 0 0 2 0;
      > #P connect 4 1 1 1;
      > #P connect 1 0 7 0;
      > #P connect 5 0 7 1;
      > #P connect 7 0 8 0;
      > #P connect 8 0 12 0;
      > #P connect 3 0 5 0;
      > #P connect 9 0 8 1;
      > #P connect 5 0 6 0;
      > #P connect 0 0 3 0;
      > #P connect 6 0 9 0;
      > #P connect 5 1 6 1;
      > #P connect 5 2 9 1;
      > #P connect 6 0 11 0;
      > #P connect 2 0 14 0;
      > #P connect 2 0 15 0;
      > #P connect 18 0 19 0;
      > #P connect 14 0 18 0;
      > #P connect 3 0 16 0;
      > #P connect 3 0 17 0;
      > #P connect 15 0 18 1;
      > #P connect 16 0 18 2;
      > #P connect 17 0 18 3;
      > #P pop;
      > #P newobj 171 131 64 196617 p abc;
      > #P button 84 90 15 0;
      > #P newex 147 105 27 196617 llist;
      > #P number 162 24 35 9 0 0 0 3 0 0 0 221 221 221 222 222 222 0 0 0;
      > #P number 187 44 35 9 0 0 0 3 0 0 0 221 221 221 222 222 222 0 0 0;
      > #P number 219 25 35 9 0 0 0 3 0 0 0 221 221 221 222 222 222 0 0 0;
      > #P number 228 45 35 9 0 0 0 3 0 0 0 221 221 221 222 222 222 0 0 0;
      > #P newex 189 68 61 196617 pak 0 0 0 0;
      > #P newex 85 106 27 196617 llist;
      > #P number 59 35 35 9 0 0 0 3 0 0 0 221 221 221 222 222 222 0 0 0;
      > #P number 89 50 35 9 0 0 0 3 0 0 0 221 221 221 222 222 222 0 0 0;
      > #P number 107 28 35 9 0 0 0 3 0 0 0 221 221 221 222 222 222 0 0 0;
      > #P number 140 48 35 9 0 0 0 3 0 0 0 221 221 221 222 222 222 0 0 0;
      > #P newex 86 68 61 196617 pak 0 0 0 0;
      > #P newex 335 130 72 196617 _ linesegment;
      > #P message 318 119 33 196617 clear;
      > #P user lcd 317 252 264 194 1 1 0 0 0;
      > #N vpatcher 407 227 826 536;
      > #P outlet 252 229 15 0;
      > #P window setfont "Sans Serif" 9.;
      > #P window linecount 0;
      > #P newex 257 180 66 196617 pack 0 0 0 0;
      > #P window linecount 1;
      > #P newex 352 125 53 196617 maximum;
      > #P newex 327 100 50 196617 minimum;
      > #P newex 277 125 53 196617 maximum;
      > #P window linecount 0;
      > #P newex 247 101 50 196617 minimum;
      > #P window linecount 3;
      > #P message 223 47 85 196617 A = y2-y1 B = x1-x2 C = A*x1+B*y1;
      > #P outlet 8 239 15 0;
      > #P outlet 166 219 15 0;
      > #P outlet 78 203 15 0;
      > #P window linecount 1;
      > #P newex 154 146 27 196617 *;
      > #P newex 17 191 27 196617 +;
      > #P newex 11 145 27 196617 *;
      > #P newex 38 114 27 196617 -;
      > #P newex 53 84 40 196617 unpack;
      > #P newex 123 89 67 196617 unpack 0 0 0;
      > #P newex 49 53 63 196617 position 3 1;
      > #P newex 140 51 72 196617 position 0 2 1;
      > #P newex 137 114 27 196617 -;
      > #P inlet 82 30 15 0;
      > #P connect 8 0 12 0;
      > #P connect 6 0 7 0;
      > #P connect 7 0 8 0;
      > #P connect 4 0 7 1;
      > #P connect 9 0 8 1;
      > #P connect 5 0 6 0;
      > #P connect 0 0 3 0;
      > #P connect 3 0 5 0;
      > #P connect 5 1 6 1;
      > #P connect 6 0 10 0;
      > #P connect 2 0 4 0;
      > #P connect 4 0 1 0;
      > #P connect 0 0 2 0;
      > #P connect 4 1 1 1;
      > #P connect 1 0 9 0;
      > #P connect 1 0 11 0;
      > #P connect 4 2 9 1;
      > #P connect 3 0 14 0;
      > #P connect 18 0 19 0;
      > #P connect 14 0 18 0;
      > #P connect 15 0 18 1;
      > #P connect 3 0 15 0;
      > #P connect 16 0 18 2;
      > #P connect 17 0 18 3;
      > #P connect 2 0 16 0;
      > #P connect 2 0 17 0;
      > #P pop;
      > #P newobj 91 132 67 196617 p abc;
      > #N vpatcher 20 74 620 474;
      > #P window setfont "Sans Serif" 9.;
      > #P newex 144 64 76 196617 unpack 0 0 0 0;
      > #P newex 86 50 27 196617 *;
      > #P newex 59 75 27 196617 -;
      > #P newex 50 51 27 196617 *;
      > #P inlet 166 29 15 0;
      > #P outlet 59 97 15 0;
      > #P connect 5 0 2 0;
      > #P connect 2 0 3 0;
      > #P connect 3 0 0 0;
      > #P connect 5 1 2 1;
      > #P connect 4 0 3 1;
      > #P connect 5 2 4 0;
      > #P connect 5 3 4 1;
      > #P connect 1 0 5 0;
      > #P pop;
      > #P newobj 227 185 57 196617 p parrellel;
      > #N vpatcher 20 74 620 474;
      > #P window setfont "Sans Serif" 9.;
      > #P newex 59 124 91 196617 append 40 30 233;
      > #P newex 57 97 74 196617 ladd -3 -3 3 3;
      > #P newex 52 50 48 196617 pack 0 0;
      > #P newex 50 72 39 196617 dupe 2;
      > #P inlet 52 30 15 0;
      > #P inlet 90 30 15 0;
      > #P outlet 64 170 15 0;
      > #P connect 4 0 3 0;
      > #P connect 2 0 4 0;
      > #P connect 3 0 5 0;
      > #P connect 5 0 6 0;
      > #P connect 6 0 0 0;
      > #P connect 1 0 4 1;
      > #P pop;
      > #P newobj 219 238 63 196617 p drawpoint;
      > #P window linecount 3;
      > #P message 293 209 176 196617 else{ double x = (B2*C1 - B1*C2)/det
      > double y = (A1*C2 - A2*C1)/det };
      > #P message 302 163 156 196617 double det = A1*B2 - A2*B1 if(det == 0){
      > //Lines are parallel };
      > #P window linecount 1;
      > #P newex 174 214 27 196617 / 0.;
      > #P newex 189 165 27 196617 *;
      > #P newex 170 189 27 196617 !-;
      > #P newex 161 166 27 196617 *;
      > #P newex 96 217 27 196617 / 0.;
      > #P newex 83 166 27 196617 *;
      > #P newex 97 191 27 196617 -;
      > #P newex 115 165 27 196617 *;
      > #P connect 3 0 39 0;
      > #P connect 53 0 45 0;
      > #P connect 34 2 39 1;
      > #P connect 39 0 52 0;
      > #P connect 52 0 44 0;
      > #P hidden connect 12 0 2 0;
      > #P connect 22 0 28 0;
      > #P connect 16 0 28 0;
      > #P connect 28 0 21 0;
      > #P connect 20 0 16 0;
      > #P connect 7 0 37 0;
      > #P connect 37 0 52 1;
      > #P connect 44 0 53 0;
      > #P connect 21 0 12 0;
      > #P hidden connect 12 3 34 0;
      > #P connect 1 0 3 0;
      > #P connect 2 0 1 0;
      > #P connect 29 2 2 1;
      > #P connect 16 0 21 1;
      > #P connect 36 0 52 2;
      > #P connect 19 0 16 1;
      > #P connect 34 0 37 1;
      > #P connect 11 0 3 1;
      > #P connect 0 0 1 1;
      > #P hidden connect 12 2 0 0;
      > #P connect 38 0 52 3;
      > #P connect 7 0 36 0;
      > #P connect 18 0 16 2;
      > #P connect 41 0 52 4;
      > #P connect 29 1 0 1;
      > #P connect 34 1 36 1;
      > #P connect 17 0 16 3;
      > #P connect 40 0 52 5;
      > #P connect 28 0 27 0;
      > #P connect 3 0 38 0;
      > #P connect 43 0 52 6;
      > #P hidden connect 12 0 4 0;
      > #P connect 22 0 27 1;
      > #P connect 34 3 38 1;
      > #P connect 42 0 52 7;
      > #P connect 4 0 5 0;
      > #P connect 27 0 29 0;
      > #P connect 5 0 7 0;
      > #P connect 29 0 4 1;
      > #P connect 7 0 41 0;
      > #P connect 6 0 5 1;
      > #P connect 26 0 22 0;
      > #P hidden connect 12 1 6 0;
      > #P connect 11 0 7 1;
      > #P fasten 35 0 41 1 200 296;
      > #P connect 29 3 35 0;
      > #P connect 25 0 22 1;
      > #P connect 29 1 6 1;
      > #P connect 7 0 40 0;
      > #P connect 3 0 10 0;
      > #P connect 24 0 22 2;
      > #P connect 35 1 40 1;
      > #P hidden connect 12 1 54 0;
      > #P connect 54 0 11 0;
      > #P connect 11 0 55 0;
      > #P connect 3 0 43 0;
      > #P connect 23 0 22 3;
      > #P connect 29 2 54 1;
      > #P connect 35 2 43 1;
      > #P hidden connect 12 2 54 2;
      > #P connect 3 0 42 0;
      > #P connect 7 0 10 1;
      > #P connect 56 0 57 0;
      > #P connect 45 0 56 0;
      > #P connect 29 0 54 3;
      > #P connect 35 3 42 1;
      > #P connect 10 0 56 1;
      > #P connect 57 0 13 0;
      > #P connect 15 0 13 0;
      > #P connect 14 0 13 0;
      > #P connect 28 0 14 0;
      > #P connect 21 0 15 0;
      > #P connect 27 0 15 0;
      > #P connect 30 0 31 0;
      > #P connect 11 0 30 0;
      > #P pop;
      >
      >
      > On 2/6/08, Rhys Perkins wrote:
      >
      >> That's an excellent patch, thanks karrrlo!
      >>
      >> I was thinking along similar lines only I didn't want to be limited to just
      >> squares, and I would like to avoid using grid patterns, if possible.
      >>
      >> The LCD object seems perfect as it allows for user created sprites and
      >> therefore the user's imagination, to run riot.
      >>
      >> I think the collision detection on that must be done by on a pixel by pixel
      >> basis though?
      >>
      >> The algo I came up with and thought would work, unfortunately has various
      >> oddities and kinks that come with it...
      >>
      >> Any other thoughts anyone?
      >>
      >> Rhys
      >>
      >>
      >
      >
      >
      >
    • Feb 07 2008 | 8:33 pm
    • Feb 07 2008 | 10:42 pm
      Thanks for the info guys. I figured out a dead easy way of doing it now you told me that I had to stop the counter before changing the ball direction.
      The websites were very enlightening! Thanks very much for all your help.
      Rhys
    • Feb 07 2008 | 11:17 pm
      so, what does it look like now? got the patch to pass along?
      feeble minds wanna know
      ron
      Rhys Perkins wrote:
      Thanks for the info guys. I figured out a dead easy way of doing it now you told me that I had to stop the counter before changing the ball direction.
      The websites were very enlightening! Thanks very much for all your help.
      Rhys
    • Feb 08 2008 | 5:53 pm
      I can upload a video of what I have got so far (without sound as I can't find a screen capture program for mac with sound)
      I also can't upload the patch until it is done as it is part of a bigger project to be marked by my uni.
      Come summer time if people are still interested then I can upload it.
      Thanks,
      Rhys
    • Feb 08 2008 | 7:51 pm
      proprietary hogwash
      On 2/8/08, Rhys Perkins wrote:
      >
      > I can upload a video of what I have got so far (without sound as I can't
      > find a screen capture program for mac with sound)
      >
      > I also can't upload the patch until it is done as it is part of a bigger
      > project to be marked by my uni.
      >
      > Come summer time if people are still interested then I can upload it.
      >
      > Thanks,
      >
      > Rhys
      >
    • Feb 09 2008 | 12:40 am
      Not really. I'm just being cautious.
      I wrote it using all the standard max objects which are coded by people other than myself, along with some personal thought and development/manipulation of these objects.
      I can't claim ownership for this but I would rather release a more complete version after I have handed it in.
      Seeing as you asked so nicely though:
      The collision detection is done by this expression:
      if $i1 = $i2 && $i3 = $i4 then bang
      where:
      $i1 is the x co-ordinate of the moving ball on the LCD object
      $i2 is the x co-ordinate of the shape it collides with
      $i3 is the y co-ordinate of the moving ball
      $i4 is the y co-ordinate of the shape it collides with
      If the ball comes into contact with the shape then a bang is sent out (at which point the ball will rebound in the opposite direction)
      $i1 to ($i1+15) and $i3 to ($i3+15) means that the ball is 15 x 15
      $i2 to ($i2+30) and $i4 to ($i4+30) means that the ball is 30 x 30
      Hope that helps,
      Rhys
    • Feb 09 2008 | 12:44 am
      Sorry that should read the shape is 30x30 not the ball for the second one.
      $i2 to ($i2+30) and $i4 to ($i4+30) means that the shape is 30 x 30