[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[glob2-devel] Alleyways, and pathfinding
From: |
Andrii Zvorygin |
Subject: |
[glob2-devel] Alleyways, and pathfinding |
Date: |
Fri, 4 Nov 2005 03:13:48 -0500 |
_andrew and I (Lokadin) were discussing in IRC the problem of how the
globules have problems traveling back and forth after harvesting
resources
here is a brief definition list of terminology:
- wavefront algorithm: the
current algorithm used for path finding also refered to as "gradient
pathfinding" in this form of pathfinding we have the resource set as
255 and impassable areas as 0's then we have the squares beside the
resource 254 and decrements of one the farther you go from the
resources. The globules find their way along the resource gradient by
checking what the numbers of the squares around them are and by
followinng the highest to get to the resource the fastest
- one-lane problem: is
where there is only one path a resource. in this instance globules get
stuck tryingn to get back as globules try to go forward through the
only available path
- shortcut problem: this is
the problem where you have say two lanes beside each other, so
theoretically the globules can use one to go forward and one to go
back. however they the do not do this very efficiently and keep bumping
into each other becase one of them is usually longer then the other.
they always wish to take the shorter path though it's no faster. Thicis is a limitation of the wavefront algorithm as far as we can see.
- circuit problem: this is
the problem where you have one lane leading towards a resources and one
lane leading away, due to the fact that the shortest path is going to
be only one of the two lanes they wont even consider the second, same
problem as mentioned in the shortcut problem
we decided that there is no need to solve the one-lane problem as it
only happens due to the incompetance of the player and is more or less
easily avoidable
we realized that the main issue was the shortcut problem as if that was
fixed circuit problem should be as well or at least would be much
easier to fix
after much debate we didn't really come up with anything simple, we
looked on the web but didn't find anything obvious that could help us
with the issue
i was thinking of two possible sollutions
- 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
- another alternative is that we can change the whole alogrithm, to
maybe something like an ant colony, like getting rid of gradients we
can find the end location with A*, but as this wouldn't be efficient to
do for every glob, we can have say some ratio of globs finding it
with A*, or if they are the first they find it with A*. then when they
have actually found the route what they do is add a directional label
to every map sqaure they pass in the to wheat type and they spread a
pheramone three squares to every side of them. (btw for this algorithm
you need a few variables attached to every map square, one for amount
of pheramone, one for direction and one for type). so anyways the glob
gets to where it's going and does an A* algorithm to get back, however
in doing the calculations of how to get back it won't go in the
opposite direction of squares which have the reverse direction written
on them (of course the direction has to reach a threshold pheramone
level before it can't be disobeyed, say after 3 globs have passed in
the same direction going on that square.) pheramones degenerate slowly
every second or so btw.
If we implement this then it will also
be able to solve a number of other problems actually. for instance
explorers will be able to try and explore places with the least amount
of explored pheramone. Warriors and workers can excrete a danger
pheramone when under attack so as to warn other workers not to venture
there and to attract more Warriors.
anyways, we were wonderinng for other peopels suggestions on solutions to the problem and perhaps some comments
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 kk anyways
i have to go to sleep now as it is very late here
- [glob2-devel] Alleyways, and pathfinding,
Andrii Zvorygin <=