Re: [glob2-devel] Alleyways, and pathfinding

[Andrew Sayers]

Having thought about this for a little longer, I don't think this set of
problems is something we're going to find one single, mathematically
neat, solution for.  It's a messy problem that will need messy
heuristics to get a good solution.

I would certainly agree with Stephane's suggestion of making stationary
globs count as troughs when calculating gradients.  That would also
allow warriors crowding round an enemy building to find their way past
other warriors to their target.

Matthew's idea for one-way forbidden areas is appealing, but smacks
somewhat of micromanagement.  Also, having 8 new types of area would add
quite a bit of complexity to the UI and to path-finding.  I think it's
best left as something to look at when we're in a better position to be
doing quite high-level work, and when all the more artificially
intelligent solutions have failed.

Lokadin said:
>     1. if the shortest path from the inn to the wheat is marked as all 0's in
>        the inn to the wheat wavefront, and then the second shortest path is
>        marked as al zero's in the wheat wavefront, then it might work

It's not that simple though - there are many inns in the average town.
Globs want to go into them to deliver wheat and fruit, and to eat.
There are usually other buildings near to inns as well, making things
more complex.  If paths are reserved for specific buildings/resources,
you'd very quickly run out of paths.

And:
>     2. <snip: pheromones>

I'd have to see this in action before I could be convinced that this
solves the problems we're talking about in this thread, but I would
certainly consider it a very interesting model in general, and I'd be
interested to see what sort of behaviours it creates.

Some solutions have occurred to me that might work:

1. Workers could be allowed to harvest resources from other workers.
   Therefore, instead of bumping into each other, workers performing
   the same task could co-operate.  This has some fringe benefits:
   * Workers that go a long way to get a resource then get hungry near
     the end will sometimes have the resource they're carrying taken
     away from them before they feed.
   * it becomes possible to rob enemy globs of resources.  This might be
     a slightly useful combat tactic, and might make your globs less
     likely to walk all the way through an enemy base to collect fruit.

2. Driving on the left.  When two globs walking in opposite directions
   collide, they should negotiate so that one swerves and one carries on
   in a straight line.  The order of preference for directions to swerve
   in should be:
   * forward-left
   * left
   (* forward-right)
   (* right)
   * backward-left
   * backward-right
   They should negotiate so that (say) if one can swerve forward-left
   but the other can only swerve left, the one that can swerve in the
   more advantageous direction will swerve.
   (I'm pretty sure right and forward-right are redundant: the square to
   glob A's forward-right is the same as the square to glob B's left)
   In the long-term, I would expect this to cause globs to arrange
   themselves roughly into lanes.

3. A slightly confusing variation on Lokadin's 1st idea.
   Normally, a gradient starts at a peak and is reduced by 1 each square
   you move away from the peak.  I suggest that squares that already
   contain a glob moving away from the peak are reduced by 2 instead of
   1.  This approximates the amount of extra time it takes to cross a
   busy square.  For paths with only a few globs, or with globs moving
   in random directions, this would have little or no effect, but with
   paths with many globs moving in the same direction, it should
   encourage traffic to form into lanes.

One last thing Lokadin said:
>    btw, I am willing to do the coding or at least help a lot with it, so it's
>    not like i'm just throwing ideas that i expect other people should do :S

Great!  But if you're being brutally honest, is your interest in
experimenting with the effects of pheromones, or in solving the traffic
problem in whatever way works?  There's nothing at all wrong with
joining a project like this to explore a programming idea that interests
and excites you, but it's better that we know now rather than keep
suggesting solutions that you're not interested in.

        - Andrew