How to make sure multiple bezier curves don't cross each other?

I was trying to create bots for my scene who walk around in scene randomly within the rectangular plane. So I was trying to generate bezier curve using multiple random points within the boundary and make each bot follow the one of the bezier curves

This is how it looks

but as you can see in the video many lines are crossing and overlapping each other and models are passing through each other and I wanna avoid that, so is there a way that I can make sure no line overlap another? Another approach comes in my mind is set up the ray casting for each bot and slow them down or reverse their movement when other bot is crossing or walking in opposite direction as them but again ray casting will hit a performance a lot and I might be using more bots in future

ray casting will hit a performance a lot

You wouldn’t have to use full raycasting here - a 2D solution would be enough with each person represented by a point or a circle. When the points get close to another point, register a collision.

3 Likes

considering if I represent the model with circle, still i’ll have to loop through all the circles for each circle on each frame, that still costly isn’t it? Like If i have 10 models, ill have to check each of them against other remaining 9 models, right?

You can can calculate how costly quite easily:

  • first model check against the other n-1 models
  • 2nd model check against n-2 models
  • 2nd last model check against 1 other models
  • last model check against nothing (all possible collisions checked)

That’s (n-1) + (n-2) + ... + 2 + 1 + 0 = n(n-1)/2.

So for n=10 you’d need to do 45 checks each frame.
For 20, it’s 190 checks.
For 500 50, it’s 1225 checks.

It grows quickly - it won’t work for thousands of objects. But it looks like you’ll just have 10 or twenty people walking around, in which case it should be fine.

A speed up would be to divide the room into a grid (or something fancier like a quadtree), track which grid area a point is in, then only check it against other points in the same area. But I wouldn’t bother with that unless you have performance issues.

EDIT: actually that quadtree repo has a cool demo that probably does what you want - you could use this instead of making your own version:

https://timohausmann.github.io/quadtree-js/many.html

3 Likes

That’s (n-1) + (n-2) + ... + 2 + 1 + 0 = n(n-1)/2 .

So for n=10 you’d need to do 45 checks each frame.
For 20, it’s 190 checks.
For 500, it’s 1225 checks.

The formula is correct, the last number not quite:

for 500, it’s 124750 checks …

This is btw the same formula which gives you the number of “clinks”, if “n” people are clinking glasses with each other.

3 Likes

missing collision against rectangular plane.

n*3.5 + n**2/2;

2 Likes

Yeah, thats right, will have to check. Its weird I did not see any example of such case where people made a bots in scene, my first thought was to try some steering behavior or something lol, anyway will have to try this collision detection. Thanks for reply, that was really helpful. :slight_smile:

wow, that’s weirdly interesting XD

which rectangular plane? Sorry did not understand that, also can you please explain that equation?

If I may jump in, starting with looeee’s verbal description …

… you could sketch the result (“thumbs up”) from left to right in a grid pattern like this, for a sample number of six (6):

Note that the grid has dimensions of n=6 columns and (n-1) rows. Clearly, the number of cells is n * (n-1).
Also note, that there’s an equal number of skulls and thumbs-ups.

Since you’re only interested in the cells having the thumbs-up symbol, that’s the lower-left half of the rectangle, hence n*(n-1)/2

2 Likes

Wow, that explaination fits perfectly into ‘explain me like I’m 5’ category. Thanks :slight_smile:

1 Like

Sorry, typo. I meant for 50, not 500.