[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [glob2-devel] Alleyways, and pathfinding
From: |
Andrew Sayers |
Subject: |
Re: [glob2-devel] Alleyways, and pathfinding |
Date: |
Sat, 5 Nov 2005 03:23:28 +0000 |
User-agent: |
Mutt/1.5.11 |
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