[glob2-devel] Alleyways, and pathfinding

[Andrii Zvorygin]

_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

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
2. 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