Re: [glob2-devel] Alleyways, and pathfinding

[Andrii Zvorygin]

On 11/4/05, address@hidden <address@hidden> wrote:

Hio,

I agree with your analysis and also agree that the solution would be to
take the globules into acount to compute the gradient. I've a very simple
idea and would like your opinion: a simple trick could be that units
blocked for a long time mark the case they are on as obstacle. Then, if
gradient is recomputed often enough, too crowded paths will not be used.

well we were actually thinking that sorry forgot to add it in, but there is a problem with blocking paths off if say if it's a small map and you can't space buldings far enough apart to not cause congestion.

another issue is of course, say that you do have a large enough map and maybe many alleways, they will still get congested, even if they are farther away, so those will be blocked off... and before you know it you won't have any routes left to get to the resource or object

though theoretically you can say time out obstacles but they would just get recongested..

We could also keep the two maps, so that if there is no other way units
still try to use the crowded ones and that units in crowded area could
still use the other map to get out of them. The unit marking case could
also mark up to a certain distance, and we can even imagine units that
forward mark of congestions. I haven't thought enough if this idea is
equivalent to the pheromones in the end.

sorry i'm just a little confused as to the above here,  :| from what i understand

1.  we have two maps
2. if units can't get to resource any other way then they will use the congested ones
   
3. units will use a different map to get away from the resources
4. by marking to a certain distance do you mean to say we shall reduce the gradient value?

though I highly doubt I understood you correctly so please excuse me,
i believe this opinion was voiced as well in our discussions

basically what we were saying in the discussion is that
(note: a wavefront is the gradient path)

• since there are two wavefronts (one to wheat, and one to inn once resources are gathered)
• congestion of workers in the "to wheat wavefront" shall lower the path value in the "to inn wavefront",
• that way workers shall not go through the congested parts as they will have a lower path value

There are two main issues we found with this approach,

the first being the definition of congestion, as in how will we identify where globules are congested?
while theoretically globules are going one way, and other globules are going another way, when they are actually congested, due to collision algorithms that tell them to try to by pass to the right or left they aren't really facing any particular way and just spin around.
though this is theoretically fixable say if we get the globules to go in one direction "as in to inn" and only turn if there is indeed space for them to move into another direction

the second issue is that even with markers in place, unless they are 0's in which case the wavefront shall simply bypass the 0's the globules won't see points lowererd marker places until they hit them, at which point they will get rather confused as they are looking for a path that is one less then their current position and they just really wouldn't go anywhere. unless it is on the lower marked path

if they are 0's i guess there wouldn't be much of a problem except that you would need to have them fade with time as occasionally your routes do change as primary resources change locations. with this comes the problem that after a while recongestion occurs as the congestion markers have to be re established

Steph



_______________________________________________
glob2-devel mailing list
address@hidden
http://lists.nongnu.org/mailman/listinfo/glob2-devel

anyways, though this problem and perhaps every other one we come across
can probably be fixed in some way using the gradient system. 

However there will be a lot of coding and thinking that will have to be
done. There are no current ways in which all these problems can really
be solved, no RTS to date that i know of compares to Glob2 in the
capabilities of their AI and no one has really made any algorithms to
support anything like that.

So that is why I was thinking that we could follow nature's example
with ants, as well they get around just fine. There are many problems
that we could solve using the pheramone system a few of them are like I
illustrated above.

The problem of course is that we are trying to make glob2 stable and
not go off on random tangents and Ideas. Afterall what we have no works
after a fashion. Like we really couldn't afford to lose the time, or
the user base we have already accumulated. Like how about all those
people that feel more at home with the gradient system or what not?

So what I was actually thinking, if we make it a little more object
oriented, or seperate the classes a little more (pathfinding is
curently housed in Map.cpp) then we could develop different Unit Ai's
on the side just like we have various Computer AI's. Afterall that is
the glob2 strength, UnitAI. We should really capitalize on that.

In any case, my point being is that we can keep the gradient system for
the moment as it does work. And we can develop the pheramone system
allowing the user to switch between the two.

I was actually thinking that what we can do if we split up AI's we can
also add in an AI that is more like say one of the "normal" RTS's as in
allowing the user to control which units do what, and which units go
where, for all them starcraft fans. While units will still go and feed
themselves what occupations they have and say what warriors work at
what flags will be up to the user. (path finding will probably still
have to be fixed though)

Sincerly, Lokadin