Finding open space reliably

[animats]

Here's a surprisingly difficult problem - determining whether a volume in SL doesn't have anything in it. I'm doing path planning and need to know that.

Out in the open, this is easy. Use llCastRay pointed downward and see that the first hit is the ground or a walkable surface. Indoors, though, it's hard.

What llCastRay tells you is the first face of an object hit in the direction of the ray cast. If the ray cast starts inside an object, you don't detect that object. So if you ray cast from an arbitrary point, you can get a "no hits" result if the start of the ray cast is inside an object. The bigger the obstacle, the more likely you won't detect it.

If you ray cast from known open space, you can reliably detect an object. So a chain of ray casts from a known good location can check that a path is clear. When an obstruction is found, though, it's hard to find the far side of the obstruction. Ray-casting in the backwards direction from past the obstacle only works if you know how far is "past". And just because you hit an object doesn't mean you're outside it. If it's convex, you can hit it anyway. Big problem with mesh buildings.

llSensor doesn't help. That just senses the root location of an object, not its surface.

Volume detect only works for moving objects, and you have to start from clear space.

Reading object bounding boxes isn't helpful inside mesh buildings - you just get the entire building.

Am I missing some simple trick, or is this going to take a lot of ray-casting and bookkeeping?

 

[Rolig Loon]

That's a tricky problem. I suppose the answer depends on what level of detail you want to know.

24 minutes ago, animats said:

llSensor doesn't help. That just senses the root location of an object, not its surface.

llSensor would be my first inclination but you are right. It won't tell you where the surface of the object is.  However, if you check llDetectedPos() and llVecDist() and compare results with llCastRay(), you ought to be able to tell whether you are inside something and where you are relative to its center.  You at least have a rough idea of which way is "out". 

 

 

[Wulfie Reanimator]

Raycast will be your only friend here, but what I suggest is that you add a higher number of collisions to the ray, then cast the same ray from the opposite direction. This will give you a kind of a "cross-section" of surfaces (which you could combine into a strided list) and you can assume anything between those values is solid material.

// Surfaces from A to B:
[ <1,0,0>, <1.5,0,0>, <3,0,0> ]

// Surfaces from B to A:
[ <2.8,0,0>, <1.4,0,0> ]

// Combined list:
[ <1,0,0>, <1.4,0,0>, <1.5,0,0>, <2.8,0,0>, <3,0,0> ]

According to the combined list, <0,0,0> (ray origin) to <1,0,0> is open space. <1,0,0> to <1.4,0,0> is solid. <1.4,0,0> to <1.5,0,0> is open, and so on.

You could further clean this up by considering the first detected surfaces of the same UUID from both directions as one solid block of impassable terrain, but it wouldn't work very well with large encompassing objects like the house itself.

Edited July 14, 2019 by Wulfie Reanimator

[animats]

29 minutes ago, Rolig Loon said:

You at least have a rough idea of which way is "out". 

Not that helpful. I'm writing my own pathfinding system.

New pathfinding system.

• First, it generates a path with llGetStaticPath. That's the straight green and red sections here. (Those colored lines are temporary prims; after about a minute they disappear, but they're around long enough for debugging and screenshots.)  LlGetStaticPath will go around static obstacles and only put paths on walkable surfaces. It doesn't notice anything not in the static navmesh, and has no concept of vertical clearance, so it will go under tables and such.
• Then it scans forward and backwards from each llGetStaticPath waypoint, using llCastRay to detect obstacles. The red section has an obstacle.
• Then it runs a maze solver, which uses a grid of cells and works around moderate-sized obstacles, to get past the red section. Doing the whole path with a maze solver in LSL is too slow, but using one to get around obstacles works. Those are the yellow lines.
• Then there's some cleanup; shortcuts are tried and used to make the path not so rectangular.

For this to work, the llGetStaticPath waypoints have to be in open space. Otherwise, the endpoints for the maze solver won't be clear and there's no way to get a valid path.

Here's a hard case. Here's a path around a corner. LlGetStaticPath did that by itself. Then the path was checked with llCastRay calls,  to catch any above-ground obstructions. Works fine.  The translucent circles are LlGetStaticPath waypoints.

But if there's an obstacle right at that corner, on top of a waypoint, it will fail. The maze solver needs free space on either side of the obstruction. If a waypoint is obstructed, I need to search along the path for open space for the start and end points. That's where finding open space reliably gets hard.

[animats]

8 minutes ago, Wulfie Reanimator said:

Raycast will be your only friend here, but what I suggest is that you add a higher number of collisions to the ray, then cast the same ray from the opposite direction. This will give you a kind of a "cross-section" of surfaces (which you could combine into a strided list) and you can assume anything between those values is solid material.

Already doing that. That's what produced the red section in my picture above. Works fine as long as the ray cast is started outside the obstacle. It's hard to guarantee that. Especially inside buildings.

[animats]

Here's a scan in both directions. This is vertical, in both directions.

Ray cast in arrow dir from <195.04470, 16.08895, 35.56000> to  <195.04470, 16.08895, 25.56000>
 Hit #0: <195.04470, 16.08895, 35.31000> Walkable rug
 Hit #1: <195.04470, 16.08895, 35.25266> Opulent Garage
 Hit #2: <195.04470, 16.08895, 35.15000> Stone floor
 Hit #3: <195.04470, 16.08895, 33.88510> Ground
Upward ray cast from <195.04470, 16.08895, 0.00000> to  <195.04470, 16.08895, 35.56000>
 Hit #0: <195.04470, 16.08895, 33.65000> Stone floor
 Hit #1: <195.04470, 16.08895, 33.88510> Ground
 Hit #2: <195.04470, 16.08895, 35.11000> Walkable rug
 Hit #3: <195.04470, 16.08895, 35.15014> Opulent Garage
 Hit #4: <195.04470, 16.08895, 35.30999> Cast ray tester 0.3

Cast ray tester.

Going downward, there's a rug, the floor of "Opulent Garage", a stone ground slab, and Linden ground. The floor of "Opulent Garage" is thin (0.102m). The "walkable rug", added for pathfinding purposes, is 0.200 thick, because pathfinding does not reliably recognize walkables less than 0.200m thick. So here, the floor of "Opulent Garage" is totally inside the "Walkable rug". Which is why the cast ray hits "Walkable rug" before "Opulent Garage" in both directions.

Similarly, "Stone floor" penetrates into Linden ground, so it gets detected before the ground surface in the upward scan.

This gives a sense of why scanning in both directions is ambiguous.