I’m trying to pick good locations for spawning enemies in my 3D game, and one of the things that would be very neat is generating spawn locations that are on an existing pathfinding graph.
Practically speaking, my level is “mostly rectangle-ish”, so I understand I could just do rejection sampling and generate a point in the level bounding box, and reject those that aren’t on the graph, which should generate a valid position in 1/P(fill) iterations, e.g. for a bounding box that’s 10% full it’d just take 10 attempts to generate a point.
I’ll probably start with this anyway, but I’m wondering if there are any other approaches that might be better? I do plan on scaling up my level to weirder shapes, so it might end up being a bit annoying when lots of spawn positions are generated. Probably still fine, but still, I wonder if there’s an easy way to generate positions that are already constrained to the graph?
In this instance I’m using a recast graph.