Re: One for the programmers or maths/logic geeks

In article <68v7q8F2s69q1U1@[EMAIL PROTECTED]
>,
Greg Goss  <gossg@[EMAIL PROTECTED]
> wrote:
> xhoster@[EMAIL PROTECTED]
 wrote:
> 
> >Snidely <Snidely.too@[EMAIL PROTECTED]
> wrote:
> >> On May 11, 2:52 pm, xhos...@[EMAIL PROTECTED]
 wrote:
> >> > How im****tant is the even coverage?  I'd be tempted to just make it
fly
> >> > around at pseudo-random (or maybe depth-first systematically),
checking
> >> > each non-checked square before entering it and remembering the
result
> >> > for future use. That way it would cover all accessible land
regardless
> >> > of the shape, although perhaps not evenly.
> >>
> >> I'd be tempted to just set it up as a random walk, choosing dir->next
> >> if dir-Owner !match.  And let it wind its own way through the plot,
> >> rather than manually moving it.  You only have to have it move one
> >> square at a time at some arbitrary interval ~= len(birdsong).  And
why
> >> bother remembering?
> >
> >Because he said checking is slow, so why do it gratuitously?
> 
> The app would keep its own internal check function that would
> gradually learn all the Yesses and Nos.  So the function would
> gradually speed up over time.

How about something like this:
(This assumes it starts at (0.0) and the world goes to (+/- 255, +/-
255)
Check the owner of (0,0).  Store it.
steplength=128
Check owner****p of here+steplength northward
  Same owner?
    Assume every cell along the way has the same owner.
  Different owner?
    Divide steplength by 2 and try again.

(Do this until you can take a step and have it be the same owner.)

move northward by steplength

OK, now see how far you can go northward before you hit the next owner's
plot of land.  You know you can't go another steplength because you've
already checked and found it belongs to someone else.    So start
with steplength/2 and go down.

When you've gone as far as you can northward, maybe use an
edge-following algorithm to find the land boundaries?

This does fail if you own two discontiguous plots, or maybe if the plot
is non-convex, or if another player's land is completely surrounded by
your own (like Lesotho in South Africa).

-- 
-eben     QebWenE01R@[EMAIL PROTECTED]
     royalty.mine.nu:81

Only two things are infinite, the universe and human stupidity,
    and I'm not sure about the former." -- Albert Einstein