[glob2-devel] Gradients (again)

[Andrew Sayers]

For those that don't already know, Globs find their way around the world
by means of gradients.  We discussed it on the ML a few months ago.  The
thread is archived online at:
        http://lists.gnu.org/archive/html/glob2-devel/2005-07/msg00014.html

This post discusses one of the main problems with the current system
(globs going at different speeds along land vs. water) and suggests
possible solution(s).

To outline the problem, the current gradient implementation considers
two distinct cases: globs that are completely unable to swim, and globs
that are considered to swim equally as well as they walk.  Since most
globs swim more slowly than they walk (and in principle could walk more
slowly than they swim), this leads to sub-optimal behaviour.  For
example, a glob will happily swim slowly across an ocean, when there is
a land route right next to them.

The gradient system doesn't suggest any simple solution to this problem
- in fact, the problem is a lot harder than it first appears.  I've made
an example case demonstrating the complexity of path-finding here:
        
ftp://ftp.ysagoon.com/ftp/pub/anonymous/screenshots/path-finding-small.png
(The glob isn't as easy to see as I would like - he's standing between
the two bodies of water)

In this example, the patch of wheat to the south of the worker is
closer than the one to the north.  If he can't swim at all, he is forced
to go to the patch of wheat in the north.  If he can swim slowly, he
should go to the patch of wheat in the south.  If he can swim
significantly better than he can walk, he should go north.

I can't see an easy solution to this problem.  We can't have each glob
find its own path, because the processor time would be prohibitive.
We can't use a dozen different paths with large or floating-point values
for gradients because the memory *and* processor time would be
prohibitive.

One hackish solution would fix the worst symptom of the problem -
that slow-swimming globs ignore nearby land routes (and vice versa).
A "land/sea gradient" would point towards land squares (when on the sea)
or sea squares (when on the land).  Then, when a glob is following a
gradient and has a choice of uphill directions to go, he can take the
direction that gets him closer to the land (or keeps him on land).

A more radical solution has just occurred to me, which I think I rather
like.  What is the gameplay advantage of water?  Certainly it makes life
more interesting when it takes a long time to get to your opponent, but
I think the complexity of building a swimming pool, upgrading it,
repairing it, running globs through it and so on is not worth the
hassle in practice.

How about we fix the speed globs swim at half the speed they walk?  Then
we could make the gradient for moving across land squares 2 and water
squares 1.  Since we'd have half as many grids of elevations to deal
with, we could make each elevation a 16 bit value instead of an 8 bit
one without using any more memory.  That would mean globs could find
peaks up to about 65,536 squares away across the water or 32,768 squares
across land.  In principle, this means it could take longer to calculate
each grid, but maps 256x256 and smaller would only notice in rare cases,
and it wouldn't be that hard to split the workload over two or more
ticks (which would cause the occasional hiccup, but nothing hugely
serious).  This is a big change, but would be easier to implement, and
goes right along with what I'm working on in the map rewrite at the
minute, so now's the time to decide.

        - Andrew