Getting a gateway between two parts

Help and Feedback Scripting Support
1

Hey dev forum!

I’ve been trying to implement a Navigation system for a horde of zombies (may zombies
moving and interacting with each other) and I’ve divided the complex geometry of the map into smaller zones or nodes which can easily be navigated. I’ve used parts to denote these zones. But when it comes to move between these zones I’ve been facing a problem of how to obtain a suitable gateway between them.

Let me illustrate my point.

Untitled121_20250528045659
Untitled121_20250528045659100×100 368 Bytes

Now here the purple rectangle could be represented as a top-down view of the zones as I was describing. They have a position and size in the 3D workspace. Now taking 2 parts, we always assume they have surface contact with eachother and now we want to find a gateway. The green dots represent a point in 3D space and as you observe they appear at the ends where 2 parts stop making surface contract and thus creating a small gate of sorts. Finding these points are my ultimate objective.

So far I’ve been pondering solutions with trying different mathematical approaches. But I’ve yet to come to a clearer implimentation, so that’s why I’m here. I hope you can help me find a good solution.

Thanks!

2

Assume rectangles never intersect, only touch. When they do touch, it will always between a left side and a right side, or a top side and a bottom side.
Make two lists of all rectangles, one sorted by left side X coordinate, the other by right side X coordinate. Look for matches between the sets (its faster if they’re sorted), these edges have the potential to contain a gateway. Now you just need to check if those edges overlap, by checking their two other Y axis coordinates.
That gives you all the vertical gateways, do the same thing with the axes flipped to get the horizontal ones.