Re: [glob2-devel] teleporters

[Kai Antweiler]

> hi list

Please wait a with the teleporters. (unless you use your second method.)
I want to revolutionize the gradient computation next month.
Last year I've planned an algorithm with Nuage.
There is a layout for this in our bugtracker.
It has some flaws, but I have a much more explicit and correct layout
somewhere in my mailbox.


> i'm digging into gradients and have some questions:
>
>
> == confusing code ==
> why are there
> updateGlobalGradientVersionSimple
> updateGlobalGradientSlow
> updateGlobalGradientVersionSimon
> updateGlobalGradientVersionKai
> when there is stated: speed 105.09% compare to simple on test
> as the best case of all?

We wanted to keep the simple version, because it is self-explanatory.
Also we wanted to used different calculations for different gradients.
The accelerations were messured, not theoretical.  They should differ
from architecture to architecture, and from map to map.
Also Simons version belongs to the most elegant solutions I have ever
seen.  I would blindly vote for it as the best part of glob2 source
code.


> it is very confusing to have some extra 300 loc and it is not comfortable to 
> hack in teleports into 4 versions of the same function.

Leave the gradientdependent implementation to me.


> if versionSimple is about as fast as the other 3 can we delete the others? 
> please don't take me wrong but a speed benefit of 5% at the cost of 4 times 
> the loc taken the speed measurement was correct i don't see the point.

The intention is to get real big maps to work smoothly where 10 or
more teams can play at the same time.
By the way.  Not the algorithms were running 5% faster.
glob2 was running 5% faster, which means that the algorithms were 10 to
15 % faster.  By the way glob2 only runs so smooth because we use outdated
gradients most of the time.

The gradient calculation is not a good place to hack in anything.
Everything has been carefully planned, theoretically proven, extensively
tested und measured.
It is one of backbones of glob2.  A bug in here leads to very
confused globs.  Trust me, I've seen some :-)
That's the reason why I don't like teleporters.
And that is also the reason why I need to implement the accelerations,
before the teleporter.  To keep things simple and testable.


> == confused leo ==
> how should i implement teleporters?

Nuage had some ideas about it.


> === gradients that hit tp put all tp to the achieved value and further 
> propagate from there ===
> *a glob walking to wheat will either hit wheat or a teleporter. tp know the 
> wheat exit gate and directly release the glob there (wait n seconds, gradient 
> drops n here)

If n is smaller than the transporter size, virtually all globs will
want to use it.  If n is bigger than 1 this will increase jams.
What shall we do, if after n timesteps there is no place for the glob to go?
Or all places it could go to are far further from the resource.  In this case
it will go into the tp again.

Tps need to check if their resource value is 254.  A resource direct
adjacent to a teleporter will lead to problems, because a glob might
want it, but there is no place to get out of the tp sometimes.
Imagine a tp that is overgrown by wood.  The gradient algorithm would
need to check, if there is a free adjacent field that is also adjacent
to this resource, otherwise use 1 as gradient value.
(0 is forbidden area, if I remember correctly.) 


> *no extra gradient needed

But all gradient calculations will suffer.


> *gradient calculation slowed down as a check has to be performed on all tp 
> until the first teleporter is hit. after that the squares of the tp are in 
> the list of the gradient and the gradient can be calculated as before.


> *the entering tp is not known until we hit it

That wouldn't matter.  The exit is important.
We calculate from source to sink.  Well, actually we don't have sinks.


> **this is bad if we want (i don't) to limit the throughput. (imagine there is 
> only one tp near wheat and all globs use tp to get there while the opponent 
> tries to rush this tp)

I do want to limit the throughput.  If we don't glob2 will become all about
teleporters.  There also big problems I refer to below.
I also would like to have teleporters for warriors only.  That is use them
on war-flag-gradient only.  This would also allow us to be more wastefull
on tp computation and thereby allow more sophisticated algorithms and
attain a better glob behaviour.


> *effectively bigger maps work with 8 bit gradients as these shortcuts put 
> remote points on the same level

I don't understand.  What do you mean?


> === gradients that hit tp put all tp to the achieved value. tps propagate 
> their own gradients ===
> *globs would have to check if they are higher on wheat-gradient or on one of 
> the (tp-gradients + the tp's wheat-value)
> *tp could accept a certain amount of globs at a time depending on the level 
> (1/s 2/s 3/s). this would lead to unwanted behaviour as globs would start 
> their journey and turn around to take the teleporter while others would 
> benefit far more from the tp ...
> *many more gradients
> *smaller change to the gradient generation

Actually no change to the gradient generation.  Or have I missed something?
This is my favorite.  Better unit control.  We could refuse globs with high
speed from using teleporters, or require some school education for using it.
This would also allow oneway teleporters.


Also your first approach will cause horrible traffic jams.
Globs are not considered in gradient calculation.  No matter how many
globs dam up in front of a transporter, even more will come.
Glob-glob collisions are eluded by premovement checks individually.


> === conclusion ===
> I prefere the first implementation as it saves on resources and will work 
> smoother i guess.
> I'd like to test another feature: global tp: one would have to build turrets 
> around the tp first and then the tp. global tps are indestructable after 
> beeing built/set up by the designer.

-- 
Kai Antweiler