I must admit that I'm surprised at my seeming inability to come up
with a neat, fast algorithm defined below. I've had several stabs at
it, but whatever approach I've taken so far, I'm not happy with the
efficiency and robustness of each approach. Surely AFCA can come up
with something good? Let's see.
The background is that I'm coding an object in the Second Life virtual
3D world whose MO involves being placed on the ground somewhere on the
X/Y grid of land, then exploring the ownership of (X,Y) "cells" of
land around it to find the boundaries of land consecutively owned by
the same person as the start cell. In other words, it's looking for
the largest rectangle possible which (a) contains itself and (b)
contains no cells owned by other people.
The information it has available is:
- The (X,Y) coordinates it's at.
- The maximum and minimum possible values of X and Y (actually 0-255).
- The ownership of any given (X,Y) cell.
The information needed from it:
- The (X,Y) minimum and maximum vectors; in other words, the
coordinates of the NE and SW corners of the largest rectangle of
consecutive ownership that includes its start point. In simpler
terms, the minimum and maximum values of X and Y that define the
rectangle.
Caveats:
1. The owner might not own a neat rectangle of land. For example,
they may have an L-shaped plot, in which case the solution should be
the rectangle containing the intersection plus the larger branch of
the 'L' (or one at "random" if they're identical; it doesn't matter
which).
Another example would be a sub-letting, where someone owns a large
rectangle but has sold a smaller rectangle on their land to someone
else - that smaller rectangle should not intersect with the solution.
In fact, land is parcelled in rectangles, and sometimes divided or
joined, so it's possible to end up owning a plot of any shape that can
be put together with rectangles.
2. The object may be placed anywhere - even a corner, for example.
3. It takes a significant time to query the ownership of each cell of
land, so an optimised algorithm will examine ownership as few times as
reasonably possible. However, this should not be taken to extremes -
for example, a brute force method that involved testing every single
cell on the grid should be avoided; a binary-chop method to reduce the
time taken to search in a given direction would be an unnecessary
complication, and a simpler serial search preferred.
4. If there's a balance between searching inwards from 0 and 255 and
outwards from the start position, the latter is preferred, since most
plots of land are pretty small.
5. It's possible to own an entire region, from 0 to 255 on both axes.
Finally, some context for interest's sake.
In SL, you can own or rent land, and put stuff on it - houses, plants,
rivers, whatever you want. For example, my partner and I rent between
us two different, fairly large regions which we build and maintain
between us. Mine has a kind of temperate forest/parkland theme, with
a house, hills, various trees, a small lake, a river, pathways, and so
on. Hers is a semi-desert theme, with a Moorish-style house, an
Arabian tent, an oasis, and occasional palms and other succulents.
Within regional building regulations, we could have built anything
that fit a green, rural theme (in my case) or a sandy, sparse theme
(in hers).
You can walk around these environments and simply enjoy them for their
aesthetic value, and the effect is pretty immersive.
To complement the visuals, you can make use of sounds. A waterfall,
for example, might continuously emit samples of a real-life waterfall,
centred on the fall itself - it's heard in stereo, and sound has a
source position, fading off in volume with distance from the source.
A popular device is a wildlife sound generator, which is an object
whose purpose is to play random bird song, etc, appropriate for the
time of day or night. On the forest plot, we have several of these
scattered around, since sound only carries a certain distance.
There are quite a few of these easily and cheaply available, and it's
no great feat to code your own - I have a home-made seagull sound
generator which I've placed at the seaside.
But for someone who can't code their own, and who owns a large parcel
of land, it can be expensive to buy a whole load of sound generators
sufficient to cover their land, since sound "falls off" so quickly in
SL.
So what I'm doing is coding a moving sound generator, which, when
placed on a plot, works out its boundaries and then continuously
"flies" around the available space, emitting bird noises at random as
it moves. You won't see it, it's invisible. It should never go into
land owned by someone else - that's trespassing.
It's that initial calculation of the boundaries that I'm working on
here; once it has that rectangle of consecutively-owned land worked
out, it can safely fly anywhere within the rectangle, giving it even
coverage.
--
John Hatpin
|
