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

[MUNTEANU Olimpiu Andrei]

If i think better, i guess there is a new problem:

If  there are two entrances to region1, but only one of them can take t 
region2


     **
      **
    ****        X
     ****
    *****   
  E1***   E2


Then, globules enetring in E1  will not find the path to X.

This means we must create regions that are not split in two parts, or 
that are a single space as much as possible.


This is not possible with square regions, only with regions with shape.


Then the only technical problem is how to reshape a region very fast.  
Actualy lets say a region is next to other region

Region1 is only empty, region2 is only wood.   When a wood disapear,  
region1 should expand one case and region2 should become smaller.   
Actualy i think we can expand the gradient if the region becomes bigger, 
but we must recompute it on the entire region if the region becomes 
smaller (actualy we can recompute on demand.

Anyway, it is not as simple since it may happend that a region is split 
in two. In this case we must create two new regions. 


Before coding anythink, a good thinking is neaded, and maybe a 
pseudo-code. If not, we will have lot of bugs.

Some questions: sould each case belong to a single region, or should we 
alow cases to belong to multiple regions?  iI think to a single region 
is enaught.

Then each case wil have a pointer to the region it belongs. Also a 
variable list of gradients. We cannot atach the gradient to the 
building/resource/region because the region is not square.


A region should have:
     - a list of neighbours.
     -  for each neighbour, a list of cases of contact, it means cases 
that are at the border with that neighbour.
     - for each neighbour, a list of the other neighbours with some 
information, like "is there is a path and eventualy what is the average 
distance (can be computed in many ways)"
    


How to compute regions?  One way:

First compute regions with rsources. Choose a resource and take all the 
region where the resource is as a hole.
Do this for every resource type and every resource location.

Then make a region for each building. Each building should belong to a 
region  that is only the size of the building.

Then choose a grass case.  Then make an algorithm (maybe A*) with a max 
iteration, fro example 16 cases. This will produce somethink about 32*32 
id the region is square.

Actualy, free space cannot be into a single region like resorces, so we 
try to create more than one.

Once finished, choose a water, and do the same, create regions in the water.



This wil produce:
     - regions for each resource type and each location
     - regions with only grass
      - regions ith only water
     - regions with only one building.


It should be possible to split a grass region in two regions if the 
region is practicaly splited in two by other region (lets say a region 
composed by wood that has grown too big)

A region must be continous and composed by a single type 
grass/water/wood/weat, etc

This means that wen a globule entgers a region, it is sure she will be 
able to join any other neighbour region.