[glob2-devel] Network and algorithms for the future

[MUNTEANU Olimpiu Andrei]

I think its good to make first one or two releases with cleans and 
without new network.

I think the idea of client/sever is good on the long term. There should 
be only one program, glob2, that will do the server and client part and 
this should be invisible to the user unless you want to use the 
"advanced funcionalities"...

I see two flow of information in this implementation:
   - the orders that come from the clients to the server.
   - the information to be printed who goes from the server to the client.

1) Orders from the client to the server:
    - they should use UDP for speed, but they can also use TCP for 
simplicity. Why not let the server manualy choose what is best for each 
player at the begining of the game, the same way it can choose the team 
color, depending on how good the network connection of each player is?
    - they should be sent as soon as the order is created, or even use 
partial orders for speed.

2) Information about the state of the game that comes from the server:

This is more complex because not only globules move, but the map changes 
all the time (new  resources, etc).  I think the best solution should be 
to make as much thinks possible to change automaticaly.  I think a 
single-type aproach is not good here for more reasons: people have 
various internet bandwith (some have dial-up...), hardware 
configurations, packet losts and /or ping time.

Lets see various internet conections on clients:
 c1 - very high bandwidth  (internet_over_fiber_optic  and/or  Local 
Area Network)
 c2 - "normal" broadband, but the clients are also doing P2P at the 
same time
 c3 - very low bandwith     (11kbps dial-up connection)
Lets see various internet conections on servers:
 s1 - very hight bandwith (LAN and/or fiber optic)
 s2 - broadband on the server but limited in upload and has 16 players, 
no multicast :)
 s3 - problems with firewall/NAT on the server, but good bandwith
The servers must be good computers, but the clients may have the folowig 
power:
 p1 - Very good computers
 p2 - Slow Pentium3 computers (less than 700Mhz)
 p3 - Very slow Pentium1 computers (less than 300Mhz)


Now we can identify some ways to send information from the server to the 
clients:
s1c1 - no bandwith problem.
s1c2 - the game may experience skipping only on the player with P2P
s1c3 - bandwith is very expensive on that client
s2c* - bandwith is very expensive on all clients
s3c* - bandwith depending on c

First off all, we see that the server should choose diferent badwiths 
for each client (it can choose the same also)

Finaly there are this possibilities for the clients:
 b1 -  Bandwith is very low ( less than 4kbps for a particular client = 
less than 0.5kB/s... )
 b2 -  Bandwith is normal  ( more than 22kbps for a particular client 
-  22*6=132kbps upload on the server)
 b3 -  Bandwith is very high ( more than 1Mbps for a particular client 
on LAN )

TCP b1 is ideal even for very slow computers with very slow bandwith
TCP b2 is good for broadband with computers more than 300Mhz
UDP b3 is the best  for a LAN or fiber optic


b1 (TCP):  to play b1 we nead the client to recive a snapshot (over 
TCP...) of the game at a given time.  This snapshot will be like a web 
page. He will be able to scroll around, but it will be like pause mode.  
He will be able to make orders like on a turn-based game. And even move 
flags, etc.  When he do that, he sends the comands to the server but all 
he see on the screen is completly stable.   When he has finished, he can 
push a button ro "reload" the game and to see if his orders were realy 
taken into account and what is the current state of the game, and so 
on.  Of course, pressing the button may be replaced with automatic 
refresh every a few secconds (set manualy by the client - and the server 
should have a max limit)

b2 (TCP):   If b1 is similar with a web page that reloads completly,  b2 
is more like google maps using mixed rendering (maps.google.com).  It 
will not reload the hole page but only new elements.  Since this is the 
most important mode on internet play, i have a special way to do it 
(described later on). It will adapt to the availiable bandwith.

b3 (UDP):  If the bandwith is realy no problem in term of ping but also 
bandwith then the best is to use a lite client as i see it.  It will 
recive information about what is on the region of the screen actually 
visible and a little outside.  The client will in fact use the same 
engine as in b1 case supposing the rest of the map is invisible.  This 
means the server may as well send only 5 frames every seccond but the 
client will be able to move around in as much frames per second he wants 
because the network will be a diferent thread ---- Optionaly the server 
may send from time to time the state of the map for map refresh. When 
the client scrolls outside the screen, it will see nothing untill the 
screen is refreshed, but since this happends many times on a seccond, it 
will not be a problem. 

NOTE: p3 computers will not always be able to play on b2 because they 
still nead to compute a little. On the internet they can chose b1 or b3 
on LAN.

NOTE2: the only diference between b1 and b3 is that b3 will send less 
information than b1. The implementation is however almost identical, 
excepting change from TCP to UDP. In fact, in b1 we use TCP because we 
want a full refresh.  In b3, if a frame does not come completly, then we 
can just skip it. It will not make the computer skip on the screen 
because be continue to use the last game state recived untill a new 
state will arrive.

NOTE3: on state b1 and b3,  when you give an order, the client can 
actualy put an attempt zone there (if it is a building placement) even 
if he does not know if the order was well accepted by the engine because 
he does not know the current state of the game.  In worst case, the next 
state from the engine will show that the order was refused for some 
reason.  This will make it more easy to play on b1 and more real-time on 
b3.   If you can place a building on b3, it is quite possible that it 
was placed on the server too because the badwith is very high and the 
client has almost the same vision as the client.

NOTE4:  on mode b1-b3,  the clients will do all they do now excepting 
moving globules. I mean scroll, use the menus, try to place buildings 
(we can invent a new type of building:  buildings that are going to be 
placed if the server wants,  they may be images that are a little 
transparent or more simple, special type of area - attempt area)


Mode b2:

If b1 and b2 can be obtained with the current code (they are somewhere 
between pause and play), mode b2 is more comlicated.  I think that the 
clients should also process the game a little.  This means changing a 
little more how the game engine works for b2-type clients.

For this i would sugest the introduction of information that have a TTL 
(Time To Live). This does not mean information that will expire after 
some time, but information that will alow the client to easily compute a 
few steps without any new information from the server.

For the map, the server will say that this place on the map is not free 
any more starting a number of steps later.  Not free means that the 
server intents to put there something short time after.  It may be wood, 
or anything else. Client will know long time before a new wood will be 
created. This way, when the wood neads to be created, the client will 
create it at that time without any retard even if the network is a 
little slow.

When someone puts a building, the server will announce other b2 clients 
that a building is beying put,  and only after some time it will actualy 
put the building. It is the same as with growing resources. The clients 
know before a building is beying put

Why do this?

When the player plays as client,  it has the possibility to place 
buildings.  If he place a building near wood or weat, the game must send 
the order and then wait for the response to see if the building was 
placed. This will either block the game for some time or the building 
will be placed later (the game is late). 

This new system will ensure that the place is empty. The building can be 
placed right now on the client, even if the server will consider that 
the building was placed later (it must first inform other clients that a 
building is beying placed at some time in the future).  This means there 
will be an intent to place the building, and the client will see some 
kind of building. The real placement of the building will be a little 
later, but we are sure it will happened.  On the client side, the 
building will be visible as soon as the person press the mounse button. 
If in the time between the player place the building and the time it is 
realy placed is a globule who passes, the client will place only a red 
zone exactly like he does now.  On the client, it will seem like there 
is a zero ping. Other clients and the server will see the new building 
after some time when it is finaly placed and will be informed long time 
before. Actually as soon as someone has recived the information that a 
new building is beying placed, he can print it on the screen (if there 
is no globule) so that to the user it will seem faster.

On the other hand, if at step 10000 on his computer a client places a 
buiding, at step 10016 the server knows and by the time 10039 all other 
clinets know. They know that the first client originated an order to put 
a building at step 10000.  In fact, the order was atached with some kind 
of TTL or time until real order. If TTL = 100, the building will be 
placed realy at step 10100 on all clinets at the same time. 

Suppose that client2 has placed there a building also, at time 9990.  
client does not know at  step 10000 when he creates the order. In this 
case, it does not mather who placed first the building.  In fact,  at 
time 10090 there should be a new building and at time 10100 there should 
be a new building at the same place.

The server will take the first order he recives, even if it is the 10000 
order whitch is older than 9990.  He will then say to everyone that a 
new building is beying put at 10100.  Later,  about time 1030, the 
server recives the order to put a building at time 10090. He wil not 
have time to cancel the first order because the second order was 
initiated earlier. He will say to client2 that the order was canceled.  
This does not affect client2 at all because the building was not placed.

What will see clinet2:  first he will see the building on the screen (if 
there is no globule who is going to pass there soon). Then he will see 
the building dissapearing.  In fact, he is sure to recive the cancel 
order in time because if he is more than 90 steps late he will wayt.  
the client will try to wayt for confirmation of all orders before the 
TTL of the order expires.  Then the client will recive that it was 
canceled. In fact it will first recive the new order before reciving 
information about his order.   In this case he will execute the new 
order because it hapened at time 1090.  At time 1099 it will wayt and 
finaly recive information about his order that was canceled.

However, this are very rare.  It may happend some time.  But for 
example, the TTL for growing resources may be initiated 400 steps before 
it hapends.  This way, each client will have the information enaught 
time so that each TTL of each building be 100.   This means that no 
construction order will be canceled because of a growing resource.  It 
must happend only because of new buildings (not for globules because in 
case there is a globule it will just turn into restricted area, and the 
order will not be canceled)


What happends with globules?

Since globules move a lot, it is difficult to know what their position 
will be after 100 or 200 steps without very fast computer (even then, 
each order recived will completly change everything).

If the TTL for placing buildings is 100,  in order for globules to move 
around the same way on all computers, it is important to make all 
computations on globules at a time that is less important.  For example, 
the TTL for  globules may be only 50.  Actualy for globules it is more 
complicated since they move.  There must be a TTL  minimum, for example 
40 and it means  that if the client is not able to know where the 
globule will move in the next 40 steps, it will wait for the server.  
There should also be a max. This means that the server will try to send 
to the client information maximum this amount, let's say 80 but it may 
usualy be more like 99 or 100 (= the TTL of orders) in order to have 
more steps cached.

Actualy we can see there are priorities:
 - growing resources, very high TTL
 - orders of any kind even settings at right of the screen, less
 - moving globules, from some min to the TTL of orders in best of cases.

This system will actualy alow the game to know for this three type of 
moves what will hapened long before it hapends.

What is the benefit of this?

Actualy, from all this, the most important and the one that requires the 
most bandwith and computer power is by far the moving of globules. 
Actualy other will also benefit, but the most will go to the moving of 
globules.

Lets take the example before.  Suppose that all numbers are exactly the 
same.  From all that TTL numbers, there is one, a single one, that is 
realy important. It is the minimum TTL about moving globules.  In the 
example it was 40 (this way, if the network is slow a little bit, the 
normal is 99, and 99-40=59 steps where there is plenty of time for the 
information to come in order for the client to know it at least 40 steps 
faster) . Actualy, the server should send this information even more 
offten than every 59 steps because of the ping of the network, lets say 
every 30 steps.

This too numbers (40 = min TTL and 30= how offten the info is sent are 
very important.  They should be as big as possible. The first number 
means how many steps further the client know about globules. The second 
number is how many information the server will send. Because the server 
may send this information from time to time only in order to save bandwith.

For this to work, it means that the server will not send the position of 
globules at each step. Rather it will send only information that will 
alow the clinets to easily (so that it works on lsov computers) compute 
the path of globules.

This means that the bandwith used to send this information is 
proportional with the number of globules only, and not with the number 
of steps.  It means that if the server send information, let's say every 
30 (or 130) steps, then the information sent in the first case is as big 
as the one sent in the seccond. This means that the server may 
auto-adjust this settings for best performance. If the bandwith is not 
enaught, increase this. If the bandwith is enaught but the client 
computers are slow to compute so many steps it may send information 
every 5 or 10 steps witch is much easyer to compute by the client.

However, while the client will only use very simple  algorithms to find 
the path, the server must always compute everything using more complex 
algorithms.  This means the server will realy require fast computers 
(more than 1Gh or even more than 3Ghz in there are many players or 
globules or the map big)

The client should use algorithms that do not change depending on the 
size of the map, not on the number of players,  not on the number of 
globules that are visible on the sscreen, but on the total number of 
globules and maybe also depending on how little or big the min TTL for 
globules is.

NOTE1:  there are some special events for globules like fighting or 
harvesting or building. This may be transmited each time since the 
client will only compute simple paths for the globules.

Until here was the simple part. More difficult is this algorithm.  
Actualy i don't have the response to the question "what is the best algo 
with this proprieties on the clinet side and that will be also easy to 
implement on the server side?"

Tmin=40 is TTL min for globules;  T=30 is how offten the information is 
transmited;

On the server:
   - first send the information about where each globule is at a given time
   - then try to move one single globule to the destination for  30 steps:
          - if the globule is has not arrived at destination after 30 
steps, note his position on the map;
          - if the globule is at destination at time 30 do the same
          - if the globule has arived at destination before, then mark 
the destination point and then mark the action and then continue with 
the path to the next destination until the step 30
   -  when moving the globule mark on each case the number of the state 
when the globule passed
   - then compute this for other globules so that they do not croos in 
the same place
   - now you know where each globule will be in 30 steps and all the 
places where the globule did something more than just move.  You will 
note all this infomation and send it to the clients
  
On the client:
   -  the client is at step 10000.  He knows how to move the globule 
until step 10045.  Right now he recives information about the next 30 
moves.
   - using this information he will be capable of computing all moves 
up to step 10045+30=10075.

The principle is that it is much easyer to compute a path that is at 
most 30 cases long than a path atat is maybe much longer. This means the 
cline t  should not be a strong computer.  Also it will save bandwith 
since the client will recive information about where globules are 30 
time less (or whatever this variable is).

----------------

This first algorithm, i am not sure how to implement it exactly yet 
(maybe someone else know).  I am not evens ure if it is easy to 
implement. However there are other algorithms:

The pheromone algo is GREAT.  Why?  It is perfect for this situation.  
Imagine the server compute all A*  algorithms and then put here and 
there pheromones.  One thing somoene should understand is that globules 
do not nead to find the shortest path. Most of the time they don't even 
know how to work because of congestion and other problems related to the 
free cells changing all the time.

So, when the server has computed pheromones, he will set for them an 
activation time and an TTL.  At step 10000, the server computes the new 
pheromones.  They will be activated at step 99. The clients will recive 
them as soon as possible (max at step 10060 if the min TTL for globules 
is 40). Begining with step 10000, the pheromones begin to work for, lets 
say, 1000 or 2000 or 3000 steps. Actualy, if they don't work, the server 
can cancel them with 99 steps of grace. If not, they can even be 
extended before they expire even for more time.

What does this mean? if pheromoes are realy good,  they will have a 
longer and longer TTL, maybe up to 10000 (why not?).  This means the 
network traffic is VERY thin.

It's great. No traffic.  And computing the path using pheromoes is very 
easy for the clients.

Only the server will have to compute A* algorithms.


-----------

By the way,  areas that will force globules to go into one direction are 
a very good idea.  This will alow to eliminate congestion easily, and i 
think it should be implemented also here.


------

Thats it.  It is easyer to say it in english than in C language. But 
anyway. I hope it will help people because i am not sure i will have 
time right now to go into the code (one day maybe...).


Also, i think there should be a concrete specification of the algorithm 
to sove other problems i did not thinked about yet. If you want to 
comment and even to propose other algorithms using the b2 network 
structure  that are very low on network  and at the same time consume 
very few CPU resources on the client side.


IMPORTANT:
 As i said, there are other things to do for the next version, and this 
should be done if people are ready.  It may take a loooong time to code 
it right.