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

[MUNTEANU Olimpiu Andrei]

I wrote network for the future in a email recently, witch is not very 
important for now since we will not change the network for some time.

This will be about algorithms.

I thought a lot about how to make the game faster.  I feel there are a 
few possiblities:
    - improve the current gradients:  this is what people try to do, 
witch is difficult. Actualy since the map changes all the time, any 2D 
algorithm like gradients will not work fast (1D like paths or pheromons 
will work fast but we are not sure they will work at all in this type of 
game scenario)
    - make a new system
    - change the game scenario so that it can use more simple 
algorithms: this will produce other game, and some people do like this 
gameplay scenario.

So i guess making a new system is the most important to focus on. We 
have 1D algorithms, and i thinked about a path-based combined with local 
gradients. This will work on huga maps for long distance paths. But it 
is extremy difficult to implement and will work only for games where 
globules work in a small place and then travel to other small places and 
the path is very long between this two regions, some 512/512 maps for 
example (if you want details about how to implement i can give them to you)

Other solution, pheromons, well this is comlicated, and they nead to be 
combined with other systems. Actualy pheromons could show when globules 
travel a lot in one direction and avoid other globules to travel on the 
oposite direction and so we can solve the problems af globules blockes 
in a 1 cell space.  This is only an improve in how globules move, but 
will not make the game faster... 

If you have other 1D algorithms, you can tell about them. Now i will try 
to describe only 2D algorithms.

Actualy, whatever the system used, it is better to combine two or more 
algorithms. a local algorithm that will do work on the map and a seccond 
algorithm that will do work on the result of the first algorithm.  All 
2D algorithms that are fast must be composed of two or more algorithms, 
one on top of the other, and the base one should be 2D  (the seccodn one 
could be whatever)

One solution is to split the map in regions. Mark each case with the 
number of the region. Regions may have various shapes and size depending 
on how the map is.  From time to tima all shapes can be regenerated to 
work better if the map has changed a lot. Well,  each region will have 
gradients on how to reach the regions that are near it if it is possible 
to reach them. Then a seccond algorithm will show the path to a specific 
region using a gradient algorithms or A* in the graph of regions.

However this is still difficult to implement (tel me if you want to know 
more about how this can be implememnted). But i think that the limited 
number of developpers will like first to try a simplified version:  all 
regions are 32*32 fixed squares. (32*32 is the optimal i think)

Then a 1024*1024 will have 32*32 regions each od them will have 32*32 
cases. (optimal for this map)

16*16 woulg go optimal  with 256*256 maps, but i think 256*256 is not 
big enaught and 16*16 is not big enaught neather (not for the same 
reason, lol).


this means computing a local gradient and a global gradient takes the 
same time (32*32 for example on a 1024*1024 map)

this will not produce optimal path for long distance, only for short 
distance....

If the building is in the same region as the globule, than the local 
gradient will be used.

If the globule is in other region, it will use the global gradient to 
know what is the next region it should go in order to get closer, and 
then will use the local gradient of the region it is to know how to go 
to the next region.

This means every building will have local/global gradients of only 32*32 
max each, very fast to compute.

But each region will have a gradient (in this simplified case of square 
region) of how to go from each of the 4 neighbours to the other, this 
means 4*4 gradients (8*8 if we compute the corners, when they are free). 

if we have 8*8 regions on a 256*256 map, there are 8*8*4*4 gradients to 
compute =256*32=4000

You said computing the local gradient is about 100 times faster. this 
means the system should be "only" 40 times slower than computing a 
single global gradient on a 256*256 map.  On a 1025/1025 map it will be 
maybe even faster than computing a global gradient.

Eventualy we can use 16*16 for 256*256 maps and 32*32 for bigger maps.

Well thi si not all, because we will not compute all the 4000+ 
transitional gradients at each clock. We will compute them at demand, 
this is only if the globule cannot folow a certain path.

Also from time  to time, we can compute a single region or a single 
transitional gradient of a single region each time (this is very very 
fast) in order to take in account not only blocking paths but also new 
paths that may have apeared.


Final notes:
-  if we use square regions, say if we do not have a road from region3 
to region 4, it is extremly not probable that we have a path very fast 
because we are speaking about wide regions.
-  but if we use rezgions with custom shape and size, we can optimize it 
so that the transitional gradients will not change almost never.  This 
means we will only compute tham on demand from a globule. 

And when i say not change i mean i fit says there is a path from region 
3 to region4 then there is a path, even if the old path is not actualy 
the optimal or even good now (if it is not good, we can recomute a new 
one, but this will not change the fact that there IS a path from region3 
to region4).


CONCLUSION:

  - shaped regions are better for both CPU and how globules find the 
best path, but i think we can test the square shape idea first, much 
easier to implement because we have 32*32 regions instead of a complex 
graph.

So what do you think about implementing the 32*32 square regions idea?