Re: [glob2-devel] globules algorithms for the future (long)

[MUNTEANU Olimpiu Andrei]

Nuage wrote:

> Thanks for sharing the idea.
>
> I have not been able yet to design an algorithm able to update local gradient
> areas inside a global one, which guarantee consistancy and would be faster than
> updating the global one. The first problem are the tricky conditions at each
> border of the local gradients, and the "warping" conditions at the global 
> gradient.
> Do you already have an idea how to solve it ?
>
>  
Actualy, the local gradients are not part of the global gradient.

It is like a gradient capable of working only on a 32*32 mini-map. This 
will include gradients for: goind to find resources, goind to ay 
building that may be inside the 32*32 mini-map.

And also with 4 more gradients (sorry, i said 4*4 in the last mail, but 
actualy you only nead 4 gradients, but you do nead 4*3 global informations)

The 4 gradients will show how to go to the edge of the mini-map.  Now, 
if a globule want to go to a building that is not inside the 32*32 
minimap. Lets say the building is in region5 and the globule in 
region9.  There is no gradient that shos how to move inside region9 
excepting the gradient that show how to move from region9 to the right edge.

*********************************
*          **          * *          **         *
*  R1    **  R2    * *  R3    **  R4 *
*          **          * *          **         *
*********************************
*          **          **          **  end *
*  R8    **  R7   * *  R6  **  R5    *
*          **          * *         **          *
*********************************
*  start**          * *          **         *
*  R9    **  R10 * *  R11  **  R12*
*          **          * *          **         *
*********************************
*          **          **          **          *
*  R13 **  R14  * *  R15 **  R16 *
*          **          * *         **          *
*********************************


Lets say there si no way to go  from R10->R11, and there is no way R7->R6.
Other paths are valid.

In this case the trajectory will be R9-R8-R1-R2-R3-R6-R5   or  
R9-R10-R7-R2-R3-R6-R5  or  R9-R8-R7-R2-R3-R6-R5 or whatever similar.

We can count moving from one region to th other as constant or we can 
make statistics and put a coeficient on each ttrajectory.

Of course, moving R9-R8-R1-R2-R3-R4-R5 is slower than 
R9-R8-R7-R2-R3-R6-R5 practicaly, but the gain in distance is not huge 
when compared with the hole distance. At most 10% of the traject or 20% 
in general (there are exceptions).

Lats now take a globule that want to go from R9 to R7.  Possible paths 
are R9-R8-R7  and R9-R10-R7.

Lets say going to the border from R9 to R8 and R10 takes the same time.  
Also going from the border of R7 to the building.  Lets look at "from R9 
to R7 inside the R8 region"  and "from R9 to R7 inside the R10 region"

Lets say R8 is like this:
E is the entrance and X the exit.

                    ****
         *****   ****
           **      ****
    *******         X
   ***************
  ***************
                  *****
**********E *****


And R10:
****X  ***********
****    ***********
****   ************
E                      ***
***                    ***
*******             ****
**********   *******
*******************



In this case, going from E to X  inside R10 is faster than inside R8


But again, this is more in a labyrinth situation, or this game does not 
have many labyrinths.

We can choose R9-R8-R7 with no problem.  Of course, it will not be the 
shortest path, but at least, in practical situation it will be a path 
that is at most 50% longer, maybe only 10% or 20% in most cases.  Of 
course we can also place more information about the R8--->R7 usual path 
so that we can try to reduce this anomalies, but this is optional.

A building will be close if it is in the same region, even if there is 
an other building next to the border. Only if there is no building in 
this region we will search in the global gradient froma  building that 
may be in some other region.



The global gradient is a gradient between regions. Actualy it i more 
than a usual gradient, because you must know if there is a path from one 
edge of the region to some other edge, while in simple gradients you 
must only know if the case is free or not.

So global gradient do not know the shortest path.  Do not confuse with 
global gradient in the current implementation, where it is about a 
gradient between every case, while here it is a gradient betwen regions 
only.


A building that is on the border could have more then one local 
gradient, one for each region.  A single global gradient is enaught however.


Each region will work as an independent minimap, so there is no such 
problem as the  border, because after the border there is a new mini-map 
with a diferent gradient. 

I used to play a game when i was little, where you must draw a complex 
image, and you have the original image with a grid.  The only think you 
have to do is to draw each of the grids as if they were diferent images, 
and finaly you will have the hole image much faster than if you would 
have tryed to draw it on the full paper.  It works for children because 
they have few CPU (lol) to process the hole image as a hole, but they 
can process each case of the grid.


Finaly:

I would like to correct the time Actualy creating a single local 
gradient for each region takes as much time as computing a "traditional" 
global gradient.  In this case we have 4 gradients for each local 
gradient.  So computing all the transitional gradients will take exactly 
like 4 "traditional" global gradients. Since we comute only a few of 
them each time, it will take far less CPU i think.  Also even gradients 
about resources wil be computed only when neaded  and only in the region 
where they are neaded or between regions ("new global gradient").