Optimal Chat Relay Placement

[Ruthven Ravenhurst]

I'm trying to generate a list of positions that will be the optimal placement for chat relays across my parcel. I think I have it almost there, but it's generating some vectors that seem to be too close to the previous, and either I can't figure out where to fix it, or my brain is too fried to figure it out

vector lower;
vector upper;
vector start;
key parcelid;
float offset = 14.14214;
integer dialogchan;
integer newchan()
{
    integer num = 0;
    while(num > -2000)
    {
        num = (integer)llFrand(−2147483648);
    }
    return num;
}
        
getlower()
{
    float x = start.x;
    float tempx = x;
    while(tempx > 0.0)
    {
        tempx -= 4;
        key id =llList2Key(llGetParcelDetails(<tempx,start.y,start.z>, [PARCEL_DETAILS_ID]),0);
        if(id == parcelid)x = tempx;
    }
    lower.x = x;
    float y = start.y;
    float tempy = y;
     while(tempy > 0.0)
    {
        tempy -= 4;
        key id = llList2Key(llGetParcelDetails(<start.x,tempy,start.z>, [PARCEL_DETAILS_ID]),0);
        if(id == parcelid)y = tempy;
    }
    lower.y = y;
    lower.z = start.z;
}

getupper()
{
    float x = start.x;
    float tempx = x;
    while(tempx < 256.0)
    {
        tempx += 4;
        key id =llList2Key(llGetParcelDetails(<tempx,start.y,start.z>, [PARCEL_DETAILS_ID]),0);
        if(id == parcelid)x = tempx;
    }
    upper.x = x+3.99;
    float y = start.y;
    float tempy = y;
    while(tempy < 256.0)
    {
        tempy += 4;
        key id = llList2Key(llGetParcelDetails(<start.x,tempy,start.z>, [PARCEL_DETAILS_ID]),0);
        if(id == parcelid)y = tempy;
    }
    upper.y = y+3.99;
    upper.z = start.z;
}
list placements = [];
generatelist()
{
    vector temp = first;
    @nextrow;
    while(temp.x < upper.x)
    {
        temp += <offset*2,0,0>;
        if(temp.x >= upper.x)temp.x = upper.x;
        if(onparcel(temp))
        placements += temp;
    }
    if((upper.x-temp.x) > offset)
    {
        temp = <upper.x,temp.y,temp.z>;
        if(onparcel(temp))
        placements += [temp];
    }
    if((upper.y-temp.y) > offset)
    {
        temp = <first.x,temp.y+(offset*2),temp.z>;
        if(temp.y > upper.y)temp.y = upper.y;
        if(onparcel(temp))
        placements += temp;
        jump nextrow;
    }
    @repeat;
    key last = llList2Key(llGetParcelDetails(temp,[PARCEL_DETAILS_ID]),0);
    if(last != parcelid)
    {
        temp = temp-<0.01,0.01,0>;
        placements = llDeleteSubList(placements,-1,-1);
        placements += temp;
        jump repeat;
    }
}
integer onparcel(vector vec)
{
    key last = llList2Key(llGetParcelDetails(vec,[PARCEL_DETAILS_ID]),0);
    return (last == parcelid);
}

vector first;
vector getstart(vector pos)
{
    integer x = (integer)pos.x;
    if(x < 4){ x = 2;}
    else if(x > 4){x = x-(x%4);}
    integer y = (integer)pos.y;
    if(y < 4){ y = 2;}
    else if(y > 4){y = y-(y%4);}
    return <x,y,pos.z>;
}
default
{
    state_entry()
    {
        start = getstart(llGetPos());
        parcelid=llList2Key(llGetParcelDetails(start, [PARCEL_DETAILS_ID]),0);
        getlower();
        getupper();
        llOwnerSay(llList2CSV([lower,upper]));
        first = lower + <20,0,0>*llEuler2Rot(<0,0,45>*DEG_TO_RAD);
        if(onparcel(first))
        {
            placements = [first];
            generatelist();
            llOwnerSay(llList2CSV(placements));
        }
        else
        {
            placements = [start];
        }
    }

    touch_start(integer total_number)
    {
        llSay(0, "Touched.");
    }
}

This it the list of positions it's outputting, with the near doubles colored red:

<14.142137, 14.142137, 21.405308>, <42.426418, 14.142137, 21.405308>, <70.710701, 14.142137, 21.405308>,

<98.994980, 14.142137, 21.405308>, <127.279259, 14.142137, 21.405308>, <127.989998, 14.142137, 21.405308>,

<14.142137, 42.426418, 21.405308>, <42.426418, 42.426418, 21.405308>, <70.710701, 42.426418, 21.405308>,

<98.994980, 42.426418, 21.405308>, <127.279259, 42.426418, 21.405308>, <127.989998, 42.426418, 21.405308>,

<14.142137, 63.990002, 21.405308>, <42.426418, 63.990002, 21.405308>, <70.710701, 63.990002, 21.405308>, <123.999146, 60.000671, 21.405308>

[ellestones]

the loops like 'while(tempx > 0.0)' don't break

 

as an aside. To avoid the catatonic state in the newchan function then can consider:

newchan = (integer)llFrand(-2147481648) - 2000;

 

[Ruthven Ravenhurst]

7 hours ago, ellestones said:

the loops like 'while(tempx > 0.0)' don't break

 

as an aside. To avoid the catatonic state in the newchan function then can consider:

newchan = (integer)llFrand(-2147481648) - 2000;

 

That's the while loop is in the function to get the lower corner of the parcel. That's not the problem.

[ellestones]

ok

i tend to get itchy fingers when I see this kinda problem. Write some code itchy. But I try to resist as best I can

so lets state the problem.  What is the optimal number of devices to place on a rectangular plane so that the plane is fully covered?

we start with Pythagoras. A device has a radius of say 20 meters, diameter 40 meters. Pythagoras tells us that each device is 28.28 meters apart. sqrt(40 * 40 / 2)

next we get the length and width of the plane.
divide the length by 28.28 to get the number of rows;
divide the width by 28.28 to get the number of columns;
offset the position of the first row to be as equidistant from the edge as the last row
offset the position of the first column to be as equidistant from the edge as the last column

plot the drop positions. Something like:

for (x = firstrow; x <= lastrow; x += 28.28)
{
  for (y = firstcolumn; y <= lastcolumn; y += 28.28)
  {
     ... rez device at x y ...
  }
} 

the other thing to consider is device overlap (circle vs square). In each device check that the origin of the chat is within the square. Something like:

if ((origin.x >= (pos.x - 14.14)) && 
    (origin.x <= (pos.x + 14.14)) &&
    (origin.y >= (pos.y - 14.14)) && 
    (origin.y <= pos.y + 14.14))
{
   ... then ok ...
};

 

Edited June 15, 2018 by ellestones
last column, width, consider, equidistant

[Ruthven Ravenhurst]

Thanks, I'll try this next time I'm in world.

I already got the actual relays, and they take care of checking which is the closest relay to the chatter, and then checks the list of avatars on the parcel and only repeats to the ones that aren't within 20m of the chatter. It's one of the ones in the Library, but I modified it a bit to check if the avatar it's repeating to is within 20m of a relay, instead of some distance from the center of the relays

[Ruthven Ravenhurst]

Ah, but the biggest problem is, my parcel on the X axis is 128m, so 128/28.28 is roughly 4.5. And the Y axis is 64m, and 64/28.28 is roughly 2.26. That half or quarter bit either won't have a relay, or I need it to calculate to place the last column and row on that edge

Alost, the first row and column needs to be <14.14,14.14,0> from the lower origin, or it will miss that corner

Edited June 16, 2018 by Ruthven Willenov

[Ruthven Ravenhurst]

here we go, i figured out how to make it add that last row and/or column if the upper edges are less than 28.28 but more than 14.14 from the previous row/column. Edited above Thank you @ellestones for the solution for the initial row and column generation

Edit to Add: It doesn't let me edit the old post, i guess if it's more than a day old?

script below. Works how I want it (other than the additional commands for actually making it do the work. But that's just tedious listen event with if tests

vector lower;
vector upper;
vector start;
key parcelid;
float offset = 14.14214;
integer dialogchan;
integer newchan()
{
    integer num = 0;
    while(num > -2000)
    {
        num = (integer)llFrand(−2147483648);
    }
    return num;
}
        
getlower()
{
    float x = start.x;
    float tempx = x;
    while(tempx > 0.0)
    {
        tempx -= 4;
        key id =llList2Key(llGetParcelDetails(<tempx,start.y,start.z>, [PARCEL_DETAILS_ID]),0);
        if(id == parcelid)x = tempx;
    }
    lower.x = x;
    float y = start.y;
    float tempy = y;
     while(tempy > 0.0)
    {
        tempy -= 4;
        key id = llList2Key(llGetParcelDetails(<start.x,tempy,start.z>, [PARCEL_DETAILS_ID]),0);
        if(id == parcelid)y = tempy;
    }
    lower.y = y;
    lower.z = start.z;
}

getupper()
{
    float x = start.x;
    float tempx = x;
    while(tempx < 256.0)
    {
        tempx += 4;
        key id =llList2Key(llGetParcelDetails(<tempx,start.y,start.z>, [PARCEL_DETAILS_ID]),0);
        if(id == parcelid)x = tempx;
    }
    upper.x = x+3.99;
    float y = start.y;
    float tempy = y;
    while(tempy < 256.0)
    {
        tempy += 4;
        key id = llList2Key(llGetParcelDetails(<start.x,tempy,start.z>, [PARCEL_DETAILS_ID]),0);
        if(id == parcelid)y = tempy;
    }
    upper.y = y+3.99;
    upper.z = start.z;
}
list placements = [];
generatelist()
{
    vector temp = first;
    integer columns = (integer)((upper.x-lower.x)/28.28);
    integer rows = (integer)((upper.y-lower.y)/28.28);
    float firstcolumn = (upper.x-(columns*28.28))/2;
    float firstrow = (upper.y-(rows*28.28))/2;
    float x;
    float y;
    llOwnerSay("First Round");
    for(x = firstcolumn; x <= upper.x; x += 28.28)
    {
        for(y = firstrow;y <= upper.y;y+= 28.28)
        {
            temp = <x,y,lower.z>;
            placements += [temp];
        }
    }
}
integer onparcel(vector vec)
{
    key last = llList2Key(llGetParcelDetails(vec,[PARCEL_DETAILS_ID]),0);
    return (last == parcelid);
}

vector first;
vector getstart(vector pos)
{
    integer x = (integer)pos.x;
    if(x < 4){ x = 2;}
    else if(x > 4){x = x-(x%4);}
    integer y = (integer)pos.y;
    if(y < 4){ y = 2;}
    else if(y > 4){y = y-(y%4);}
    return <x,y,pos.z>;
}
default
{
    state_entry()
    {
        start = getstart(llGetPos());
        parcelid=llList2Key(llGetParcelDetails(start, [PARCEL_DETAILS_ID]),0);
        getlower();
        getupper();
        llOwnerSay(llList2CSV([lower,upper]));
        first = lower + <20,0,0>*llEuler2Rot(<0,0,45>*DEG_TO_RAD);
        if(onparcel(first))
        {
            //placements = [first];
            generatelist();
            llOwnerSay(llList2CSV(placements));
        }
        else
        {
            placements = [start];
        }
        dialogchan = newchan();
    }

    touch_start(integer total_number)
    {
        key id = llDetectedKey(0);
        if(id == llGetOwner())
        {
            llDialog(id,"Choose an option",["Rez","Reset","Update","Relay Chan","Clear","Show","Hide","Intersect"],dialogchan);
        }
    }
}

 

Edited June 16, 2018 by Ruthven Willenov
updated function for generating placement list

[ellestones]

calculating the offset. As a exercise we look at a full region. 256x256 meters.

256 / 28.28 = 9.05

9 * 28.28 = 254.52

we are short by 1.48 meters. so we need a 10x10 grid

we divide 1.48 by 2 to get our start position

1.48 / 2 = 0.74;

plotting this:

0.74, 29.02, 57.3, 85.58, 113.86, 142.14, 170.42, 198.7, 226.98, 255.26

check:

256 - 255.26 = 0.74

for other size planes the algorithm is the same. In the 128x64 case:

128 / 28.28 = 4.53

4 * 28.28 = 113.12

128 - 113.12 = 14.88

14.88 / 2 = 7.44

the other axis:

64 / 28.28 =

and so on

[Ruthven Ravenhurst]

3 minutes ago, ellestones said:

calculating the offset. As a exercise we look at a full region. 256x256 meters.

256 / 28.28 = 9.05

9 * 28.28 = 254.52

we are short by 1.48 meters. so we need a 10x10 grid

we divide 1.48 by 2 to get our start position

1.48 / 2 = 0.74;

plotting this:

0.74, 29.02, 57.3, 85.58, 113.86, 142.14, 170.42, 198.7, 226.98, 255.26

check:

256 - 255.26 = 0.74

for other size planes the algorithm is the same. In the 128x64 case:

128 / 28.28 = 4.53

4 * 28.28 = 113.12

128 - 113.12 = 14.88

14.88 / 2 = 7.44

the other axis:

64 / 28.28 =

and so on

Oh ok, i see now. Let me try that

[Ruthven Ravenhurst]

Perfect, thank you again @ellestones, edited above

Edited June 16, 2018 by Ruthven Willenov

[ellestones]

i would like to come back to the 2 things I mentioned earlier, as a general discussion about algorithmic Big O time

this one:

integer newchan()
{
    integer num = 0;
    while(num > -2000)
    {
        num = (integer)llFrand(-2147483648);
    }
    return num;
}

there is a catatonic state here. The 'while' loop will never exit should 'llFrand' always return a value in [-1999..-0]

how likely is this?  2000/2147483648 * 2000/2147483648 * 2000/2147483648 * ... infinity

pretty small but the possibility remains. This kinda function is of the class O(INF) time. I am guilty of writing this kinda code myself sometimes also

to eliminate this possibility and also have the function execute in O(1) time ( O(1) time being optimal in this case) then example:

integer newchan()
{
   return (integer)llFrand(-2147481648) - 2000;
}

example of a more generalised O(1) function to fetch a random channel within a range

integer rnd_range(integer start, integer end)
{
   return (integer)llFrand(1 + end - start) + start;
}

channel = rnd_range(2000, 2147483647);  // positive n
channel = -rnd_range(2000, 2147483647);  // negative n

the other is this one for edge detection

float y = start.y;
float tempy = y;
while(tempy > 0.0)
{
   tempy -= 4;
   key id = llList2Key(llGetParcelDetails(<start.x,tempy,start.z>, [PARCEL_DETAILS_ID]),0);
   if(id == parcelid)y = tempy;
}
lower.y = y;

this is a O(N) time algorithm. The optimal in this case is O(log N) time

a O(log N) time algorithm stops when the target is found. Example:

vector p = start;          
while ((p.y >= 0.0) && (parcelid == llList2Key(llGetParcelDetails(p, [PARCEL_DETAILS_ID]), 0)))
{
   p.y -= 4.0;
}      
lower.y = (float)((integer)(p.y + 4.0) / 4 * 4);
// lower.y is in [0, 4, 8, 12, 16, ... etc]

more info about O() time algorithms here: https://en.wikipedia.org/wiki/Big_O_notation