Distribute objects on a navmesh

Gokudomatic

Hello,I'm facing quite a tricky problem. I have a Navigation node with a Gridmap that contains a navmesh. My goal is to drop randomly spatial nodes (typically characters as rigidbody) all over the map, but not above the void (otherwise they fall). It must be on the ground of the gridmap.To do that, I created a node around which a random position is calculated within a given radius. Then I call [code]get_closest_point(random_point)[/code] of the Navigation node and I put my npc to this place.It does work well, but it causes a problem in some cases. All random points that are outside the navmesh will have a closest point at a border of the navmesh. And since the navmesh is made from a gridmap, there is no distance between the real border of the map and the border of the navmesh. And when the gridmap is designed to have walls all around the map, like in this screenshot:[img width=750 height=478]http://pix.toile-libre.org/upload/original/1469137014.png[/img]then the closest point of a point of the map would be right inside a wall. If you look at this image of a view from above: [url=http://pix.toile-libre.org/?img=1469137504.png][img width=361 height=360]http://pix.toile-libre.org/upload/img/1469137504.png[/img][/url]You see:[list type=decimal][li]The point generated randomly[/li][li]The closest point in the navmesh, where the npc rigidbody will be created.[/li][li]The point of the rigid body pushed by the wall (in red) thanks to the physics engine[/li][/list]And then the rigidbody falls from the map. I want to prevent that and be sure it will be dropped somewhere on a safe ground of the gridmap.I also tried to avoid the problem by comparing the position of the random point and the closest point, and if it's too far, calculate another random position. That does quite the trick but there are still some cases where the random point is exactly at the border of the navmesh, making then the rigidbody being pushed outside the map.And I can't use a cheap trick like killing all rigidbodies that fall too far away from the map. Some of those npc rigidbodies have the ability to float and they don't fall.Truly, I have no idea for the moment how to solve this problem. Does anyone have a suggestion?

Berfandil

Given, that there is much more "good" area than "bad" ("good" is the place when it is ok to place a character, and bad is eg. inside a wall), You could do the following:1.) Generate a random place.2.) Check whether the line on the given place, parallel with the Y axis intersects a "good" or "bad" place.3.) If it intersects a "good" place, You can spawn your character, but if it is a "bad" place, then goto "1.)"Also, You can then check the distance of the nearest edge with the function You made, and if it is less then the radius of the character, then it is fully ok, to spawn it.Or at least this is how I'd get started.

Gokudomatic

Good idea, Berfandil. By using a vertical ligne and check the intersecting points with the navmesh instead of searching the closest point to the navmesh, I'd be sure the point is really inside the navmesh (no error margin). Yet that won't fix the problem with the points that happen to be very close to the walls (often inside the walls since they're overlapping a bit with the navmesh.For that problem, I thought about 2 solutions:1) since it's a gridmap, I can assume there is a center point of each cell of the gridmap. I simply have to round mathematically my random position to snap it to the grid. Also, it would tell me if one cell is already occupied and so avoid two npc being at the same place. And since it's random, the fact that the npc look like distributed in a grid doesn't really matter.2) check the area around the random point (only 4 directions would be enough). If they're all in the navmesh, I can assume there's no wall around. It won't cover every case, making it still a bit unpredictable, and that require more cpu.

Gokudomatic

The method get_closest_point_to_segment was alas not helpful. It still gives a coordinate even if the segment is not intersecting with the navmesh.However, by rounding the coordinates to the grid (in my case, multiple of 4) and by checking that the place wasn't already occupied, there was no more out of bound npc.

Berfandil

You could also check the distrance between the wall and the npc and if it is less than a given amount, then you don't accept that random position either.But it sound good that You found a solution. :)

Gokudomatic

Checking the distance between the wall and the npc is not as easy as it sounds. That would require to create a raycast and make it scan in every direction. And for each scan, I have to wait the next frame. Or, I create as many raycasts as there are direction to check. Or maybe I can use an area and a sphere of a given radius(might be a better idea than the raycast).Anyway, the problem is that it requires at one frame to do the checking. And considering I have maybe 50 or 100 npc to drop, it might need quite a lot of frames, or a lot of resources if I do it all at once.But thanks for your help.

Sammy

Preproces the navgrid, produce a 2d array of points(cells, say each point is at 10x10 intervals), good points and bad. Good points are on the navgrid, bad not. You can do a bounds check(sphere check) to make sure the points are away from the edge of the navgrid. Use these points to drop npcs, as a point is used up, mark it as such so it won't be used again. Possibly use a 1d list of good XY points to speed this up.All of this can be stored in a data file as long as your map is not procedural. A higher resolution would mask the existence of the 2d grid too.

Gokudomatic

Thanks, Sammy. Yet, I do have some maps that aren't gridmaps but conventional meshes made in blender. I try to keep the possibility to use this kind of map. Therefore I can't preprocess the map in a virtual array.