Re: [glob2-devel] Globule pathfinding

[Nuage]

Hello, sorry for super-delay answer.

I read your idea. You will like to know that it was almost the same idea that
was in glob2 just before the gradient pathfinding system. One of your assumption
is that you actualy know where is the target. When you to to a building, this is
true, but when you go to a ressource, this is wrong. With this old system allot
of time where lost to scan the map to find rare ressources. In map where the
Algae was depleted or rare where suddently very slow because every simple
globule looking for algae would scan all the map. The second problem was that
players where really unhappy when globules took the wrong way, especialy at
critical things.

So I am sorry, but I won't try to implement this idea.

If you want faster game, I need speed stats for all of you, thank you.

Nuage


MOA3333 wrote:
> There are some older emails about this. I will continue my brainstorming
> on this subject. In the past emails, i thinked splitting the gradient in
> regions is good. It can help with speed, but it is both hard to code and
> with problems related to the border betwen regions.
> 
> In order to eliminate this problems, regions should take as much as
> possible the shape of obstacles. Folowing this idea, i have found that
> the best should be to eliminate completly the gradient algorithm. Each
> obstacle is a region, each region is an obstacle.
> 
> The new algorithm if it works, should be able to know a path to any
> region/obstacle, not the best, but one that is good enaught. This means
> it will at best know the average distance to the target, and it will be
> very difficult to know exactly witch building is closer.
> 
> First, the base algorithm: 
>   - identify each obstacle as a region: it must be of a single type
>   (wood, building, weet, etc) and must be continous, a single piece.
>   Each case will have a number that is the same as the region, and i
>   don't know yet if a type representing the region is useful.
>   - apply an algorithm that will compute all free spaces that are near
>   each region, at distance 1, then 2, etc,  like in the gradient system,
>   but starting with all the regions at the same time. The idea is that
>   each free case should belong to a single region, the closest, and not
>   try to cover the hole map. Finaly the hole map is covered, but each
>   case with the gradient of a single region
>   - Other diference from the gradient system, we can keep in each case
>   other informations, not only how far it is from the building. One
>   information should be in witch direction the closest region is. This
>   can be one of the 8 directions (or a more precise direction, like a
>   range of integers???)
>   - Other infomration we can keep is witch case of the region is (or was
>   when the gradient was first computed)) the closest. We can put numbers
>   on the border of each region this way, and this is important.
> 
> This algorithm is a very human one, and can replace the fact that ants
> can see. Actualy, globules can see the obstacles here. The clasical
> gradient algorithm thinks that globules should take the closest path by
> surfing on a line, taking a line.
> 
> This algorithm thinks that globules should go directly to the building
> if they are near the building. If not, the globule must avoid obstacles
> and then go to the building. To avoid obstacles, it will travel in a
> cercle around each obstacle, even if it is closer to take the corner. 
> 
> The globule must be able to do the folowing:
>   1 - go straight into the region that is the closest.
>   2 - go away from that region into the oposite direction
>   3 - go round the obstacle clockwise
>   4 - go round the obstacle reverse clockwise
> 
> For example, a travel can be the folowing staps:  3242423242421, or more
> general ([3 or 4] 2)* 1
> 
> The only problem is to decide a list of 3 and 4 to folow on the fly if
> possible...
> 
> First way, the stupid one:
>  - try to find the border of the region that is the closest to the
>  destination.
>  - go 3 or 4, depending witch is faster (we cana also consider haw large
>  the road is)
> This will be easy to implement, but it is not sure it will find a good
> path, however it will always find a path suposing we do not have a
> labyrinth.
> 
> 
> Seccond way, a better one:
>  - each region has a few neighbours. How do we know witch is the
>  neighbour? Simple: when the gradient of two regions touch each other,
>  then they are neighbours.
>  - if we put numbers on the border of the region, than every border will
>  have a neighbour and only one. (some time 2, but we ignore that for
>  now)
>  - a graph can be built, each region with his neighours and information
>  about witch part of the region is closest to that neighbour.
> Two regions that touch each other are NOT neighbours, and it is better
> to consider a region only by the border that is possible to travel
> along, not the regions that are not accesible.
>  - Now we can apply a simple A* or somethink on this graph. A* starting
>  from the destination, or even a gradient system on the graph, not on
>  the map directly.
> 
> 
> 
> Optimisation: We consider a region of more than one type. This means
> each region will realy be a region surounded by spaces. This will
> simplify the problem related to regions that touch each other. This
> means the destination will not be a region, but only the border of a
> region. Globules will travel ([3 or 4] 2)* [3 or 4 ] 1
> 
> Optimisation2: We conider a single region all part that are separated by
> a single case. Actualy this means globules will not be able to travel
> there, but this is  a good idea since this will produce congestion. It
> is up to the player to make space, especialy if bigger maps are
> possible. It will be possible in the future to implement a function (5)
> that means traversing a region, not by going round, but by going inside
> a thin hole like this. This should be however used carefuly. 
> Globules will travel (([3 or 4] 5? 2)* 1.  And the difficulty will be a
> list of 3 and 4, eventualy a 5.
> 
> This is not yet the best, but it is what i have found for now. I hope it
> is not too complicated. If you find the idea good, maybe a more simple
> solution is possible. Actualy i think the graph will not change that
> much, only localy. And the gradient we will be able to regenerate more
> localy, ond only once from time to time.
> 
> 
> 
> 
>