Optimal scan strategy

Further to some discussion elsewhere I wonder if anyone has managed to come up with a provably optimal strategy for scanning an area for all objects/avs? (Avs is probably more useful, but objects is more general, since whatever works for objects will work for avs with a quick change in the llSensor call) Assume that the sensor range of 100m is far enough and the problem is the 16 object top limit, and that the goal is the lowest number of sensor calls.

It's clear that there's no way of doing it with a static list of points, since for any such list you can arrange a "cloud" of 16 objects around each of those points, and then any object that is not in one of the "clouds" cannot be detected.

An early guess was that, if the sensor detects 16 objects, it could then move around their convex hull, but this causes a problem if those 16 objects are very close together, since an object that's further out could get missed again.

This is guesswork, I've not actually tried it, but I'd look at working out the centre of the cloud (just average their x, y, z positions, finally a use for the llListStatistics call!), and calculating the vector from the current position and moving to there +50m further along that line. If you match the cloud again you can be moderately sure there's nothing else in range, but I'm not 100% - it seems way too simple somehow.

Interesting idea but I see a problem The problem is if the cloud is too close.. if you have a situation like this:

<object> spaaaaaaaaace <sensor> <cloud>

Then the sensor will pick up the cloud, but when it moves 50m towards the cloud, it's moving away from the non-cloud object.

Apart from memory issues, you could use any number of standard maze-following algorithms. If you detect 16 objects, cut your sensor range to less than the range to the furthest object, then do a recursive space-filling scan with that range. Something like...

sensor(integer n)
{
    if(n <= 15)
    {
        // do your work with the objects you found.
        //...
        // find the next place to work...
        new_pos = ZERO_VECTOR;
        while(!new_pos)
        {
            new_pos = next_location(current_pos, current_bounding_box, current_range);
            if(!new_pos) // finished scanning the current bounding box
            {
                if(llGetListLength(bounding_box_stack) < 4) return; // no more work

                current_bounding_box = llList2List(bounding_box_stack, 0, 1);
                current_pos = llList2Vector(bounding_box_stack, 2);
                current_range = llList2Float(bounidng_box_stack, 3);
                bounding_box_stack = llList2List(bounding_box_stack, 4, -1);
            }
        }
        current_pos = new_pos;
        llSetPos(current_pos);
        llSensor(...);
        return;
    }
    bounding_box_stack = current_bounding_box + [ current_pos, current_range ]
        + bounding-box_stack;
    current_bounding_box = [
        current_pos - <current_range,current_range,current_range>,
        current_pos + <current_range,current_range,current_range> ];
    current_range = llVecMag(current_pos - llDetectedPos(15);
    llSensor(...);
}

Let me preface this by saying that I know next to nothing about sensors.

It might be overkill, but send out two new sensors, one in each direction?

Don't forget that the easiest thing to manipulate in a sensor call is the solid angle that you are scanning. I would suggest beginning by halving the solid angle of the sensor call to create a narrower 'beam' whenever more than 16 hits are recorded and then continuing to subdivide as required. Assuming all your targets are inside a 96m sphere, I believe that this comes close to an optimal search.

[edit] Actually, this would be optimal if the sensor call allowed you to specify arc seperately in two planes so that your beam shape was something other than a cone. Since you can't (you can only specify the solid angle around the forward axis), any arc other than PI or PI/2 will result in beams that overlap. It will still work, but it wont be a perfect binary search, since you will have to overlap beams to get complete coverage and throw away objects that appear in multiple beams. Ah well.

I saw a script a while back that operated kind of like Jamie suggests. It scanned a small angle, rotated the prim, then scanned the same angle again ... repeat until you've scanned the whole sphere. I can't find the script right now, and I don't know if it worked, but it sounded like a reasonable approach.

That sort of approach will divide the search down into a known number of sensor calls - if (for example) you divided the total sphere into 100 rotated positions, it would ALWAYS take 100 scans.

The scan / divide / scan approach completes in ONE scan, if there are less than 16 hits. There are 31 hits scattered equally around you it (might) complete in two scans and certainly completes in 4. Since you stop subdividing any given beam when the number of hits goes below 16, you never waste time rescanning where it is not necessary.

Also... dividing the scan into a set number of steps will fall apart if more than 16 hits are clustered into one of your beams - you would need some sort of strategy (like division) to rescan that area anyway.