Tell me more ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 1 down vote favorite

I am experimenting with the RVO2 library for collision avoidance in a 2D simulation. This library supports specifying arbitrary obstacles as a list of vertices. The obstacles must be full shapes, i.e. they must not contain holes.

I've pretty much figured out how to find the contour of a shape (using algorithms such as these), but holes are giving me trouble. Basically I need to solve the following questions:

  • How to tell if a contour is inside or outside the shape?
  • How to tell if a shape has a hole inside?
  • Once a shape has been determined to have a hole, how to segment it to form a shape without hole?

This drawing illustrates the third idea: the outer shape has been segmented so the contour is continuous, i.e. RVO2 can consider it as a shape without hole.

Outer shape has been segmented so that contour is continuous

share|improve this question
1  
Why do you need to know if obstacles have holes? If there are agents outside of the obstacle, then even if it doesn't have a hole it won't be able to enter it. If the agents are inside an obstacle, then they must be inside the "hole"... in which case it doesn't matter what the outside boundary is. – Mokosha Mar 16 at 14:21
If I don't know, then the obstacle will be considered full, and so any unit inside the hole will be considered as inside an obstacle by the collision avoidance library. This means they would not behave as intended, i.e. they'll probably just refuse to move. – Asik Mar 16 at 14:31
I believe the obstacles work like backfacing triangles... If it's inside the obstacle it won't be able to "see" the outside boundaries. I haven't tried this to see what happens... Have you tried it to see what happens? (i.e. not "probably" but "definitely" refuse to move) – Mokosha Mar 16 at 14:38
Yes, I just tested it and the behavior I described seems to be accurate... agents will not respond to boundaries of obstacles that they are currently inside of. Hence, I don't think you need to worry about the issues in this question. – Mokosha Mar 16 at 14:53

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.