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 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 commentsbtw, 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 mailing list [email protected] http://lists.nongnu.org/mailman/listinfo/glob2-devel
