Re: [palito-dev] on simultaneous orders

[Gabriel Blum]

Hello Maylander!

Glad to hear from you, welcome to the palito project!

First of all, you should subscribe to the palito-dev mailing list
address@hidden
This reply is being cc'ed there

I'm not - yet - a developer of palito, but I'm planning to join in pretty
soon, as I'll be giving myself a break from work.

address@hidden and address@hidden are the big bosses of palito, and
there some very cool guys from around the world that also contribute to it.

All help is always welcome, and I think, for your reply, that you have solid
comp science foundations, and that will surely be helpful, even tough zed
and barrett are pretty practical guys and not keen to long theorical
discussions :-D

Let's comment your email ... [ Maylander's complete message to me is in the
end, skip to it to understand ]

> > This way is thecorrect way when server resources are limited;
> > It's a scheduling system...

> A round robin is not bad, but a weighted fair queue would be even better,

Completly agree. The unix kernel implements this, doesn't it?
Well, code it up man! ;-D

> If you cannot avaid it makeing th eweak more stronger is far better than
makeing the strong even stronger.

Very good concept and game design policy!

It's curious how the weighted fair queuing produces this 'side effect' ;-D

> You can avoid to make rules which is quite complicated to code and uses
> computing power. Simply make two rounds, in the first all unit make an
> action in the second round all weapons make a reaction. So no deadlock is
> possible its also a better solution if units have multiple weapons.. For
> the weapons you can also make a weighted queue so that the more expensive
> weapons have priority.

Good solution. It is still 'making rules', nevertheless. It's just that your
rules are simple to run, but requires two passes
I mean it is rules because you define that: all move orders will be
succesful and that you'll solve problems later,
you define that if a unit is alive at the beginning of a 'tick' then it will
fire, and other things.

It's not perfect tough, it doesn't solve the paradox, because you're just
choosing a solutino over the other: in you case, you chose
with your algorithm to allow a unit to perform action in the same tick it
dies.
Of course, you could insert a new pass:

1 - process all moving projectiles and apply damage; Also process all
'instantaneous' weapons being fired this round and apply damages
2 - for each living unit, process actions : move/turn, nanolathe,
load/unload, produce energy/metal
3 - fire weapons

What we are doing is always creating rules ;-D

I mentioned the game 'Diplomacy' which has this paradox in even more complex
and indirect ways. Well, the official diplomacy adjudicator
algorithm has 17 steps.

> > Ending this email with an interesting question: Is it possible in TOTALA
> > to
> > create a circular movement with 4 units?
> > Imagine 4 units adjacent
> > AB
> > DC
> > Can we make the circular move A move to B's position, B move to C, C->D-
> > >A

I proposed this problem for totala, cause it exists in diplomacy. That could
be solved including a 4th step
1 - process all moving projectiles and apply damage; Also process all
'instantaneous' weapons being fired this round and apply damages
2 - for each living unit, process actions : move/turn, nanolathe,
load/unload, produce energy/metal
3 - Calculate colisions between units (two units that moved to the same
space). Do_something_about_it();
4 - fire weapons

See ? ? More processing, more quality ;-D

Regards!!
Gabriel Blum
address@hidden


----- Original Message ----- 
From: "maylander_77" <address@hidden>
To: <address@hidden>
Sent: Tuesday, September 02, 2003 3:16 PM
Subject: Re: [palito-dev] on simultaneous orders


> As I sow your project on TAUniverse i thought thats cool and maybe I can
> help you with some ideas I also have some Knowledge with Computerscience
> but never worked on a game. Well the problems here are general problems.
> Hopefully i could help you a bit. Please reply me if you think it was
> usefull for you.
>
> >
> >
> >
> > Cool... the server sketch looks fine; It's simple because the select()
> > synchronizes the
> > processing into frames/time slots;
> > Tough the network code is the tricky one, cause it's asynchronous.
> > I see problems in the game loop;
> > First issue) It isn't fair neither correct to process all commands from
> > player i before processing commands from player i+i; You should process
> > one
> > command per player, in a round-robin fashion until there is no more
> > commands
> > from any player OR until your time for that frame is over; This way is
> > the
> > correct way when server resources are limited; You should save the last
> > round robin position for the next tick/game loop; It's a scheduling
> > system... when you have extra time, anything works. But when you
haven't,
> > you must ensure fairness;
>
> A round robin is not bad, but a weighted fair queue would be even better,
> this means there are several priorities of the units, lets say the
> commander has the highest priority so i always can react and theres only
> one per player, were as swarm units would get the lowest priority because
> there are so many and often the cause of the lag.
> In TA it was possible to win with flashes because the EMGs caused Lag wich
> prevented the flashes from destruction, this was one of the main reaseons
> why many players used ARM as favourite, with priorities you can avoid
this.
> If the units die you should invert the priority, so the value of the unit
> is also important if the game is overloading and prevets gamers to abuse
> the lag on purpose.
>
> An example with 3 players the server can only process 12 units in a round
> 16 is the highest priority units which couldn't be processes have their
> priority increased by one. In every Round the scheduler processes one unit
> of a player in this examp,e 4 unots per player. If a unit is processed the
> priority is set back to the start value.
>
> A has  1 COMmander (16) 1 Vehicle FActory (8) and 8 FLashes (0)
> B has  1 COMmander (16) 1 Kbot FActory (8), 1 ConstuktionKbot (4)  2
Storms
> (2) and 2 AKs (0)
> C has  1 COMmander (16) 1 Aircraft FActory (9) and 2 construction Aircraft
> (5)
> the queue  looks so
>
> A COMa > FVAa1 > FLa1 > FLa2 > FLa3> FLa4 > FLa5 > FLa6 > FLa7 > FLa8 B
> COMb > KBAb1 > CKb1 > STb1 > STb2> AKb1 > AKb2
> C COMc > AFc1 > CAc1 > CAc2
>
> in the first turn the units will be processed in this order.
>
> COMa > COMb > COMc > AFc1 > KBAb1 > FVAa1 > FLa1> CKb1 > CAc1 > CAc2 >
STb1
> > FLa2
> in the second turn
> COMa > COMb > COMc > AFc1 > KBAb1 > FVAa1 > FLa3> CKb1 > CAc1 > CAc2 >
STb2
> > FLa4
> in the 3rd turn
> COMa > COMb > COMc > AFc1 > KBAb1 > FVAa1 > FLa4> CKb1 > CAc1 > CAc2 >
AKb1
> > FLa4
>
> This seems unfair for Player A because his units will be delayed more
often
> than the others, in the game it would help the weak players and make them
> stronger. If you cannot avaid it makeing th eweak more stronger is far
> better than makeing the strong even stronger.
>
>
>
> > Seconde issue) It is also important to note that player orders may
> > generate
> > conflicts if the processing is linear; Or may even generate paradoxes;.
I
> > take this from my Diplomacy experience, because it's a game that all
> > orders
> > run simultaneous;
> > I mean that the loop
> >> void game_tick() {
> >> foreach player
> >> foreach unit
> > has problems;
> > Player 0 orders
> > - Unit A: attack unit B
> > Player 1 orders
> > - Unit B, with very little health: < some order>
> > Correct "adjudication" is that BOTH unit orders should be execute,
> > because
> > they were issued simultaneously;
> > Problem: the actual game loop causes unit B do die, so he won't execute
> > his
> > orders;
> > Paradox
> > Player 0 order
> > - Unit A attack unit B
> > Player 1 order
> > - Unit B attack unit A
> > If both units are with almost zero health, both units should fire and
> > both
> > should die; Your game loop causes B to die first and A to live; The
> > paradox:
> > if both shoot and both kill each other instantaneously, both are
> > instantaneously dead and couldn't shoot the other in first place! This
> > paradox is a 2-way, but it can be n-way;
> > The same applies to movement!
> > I know this is more complicated because attacks aren't instantaneous,
but
> > anyway the problem persist: you shouldn't process the world information
> > for
> > player 0 before you do for player 1; It should be done for all players
> > simultaneously -- which is not only correct and fair, it's also cheaper;
> > The solution to the paradox involves finding conflict orders and
circular
> > references orders first and making special processing for them ( that
is,
> > applying rules ); After that, you can proccess the rest in any way;
>
> You can avoid to make rules which is quite complicated to code and uses
> computing power. Simply make two rounds, in the first all unit make an
> action in the second round all weapons make a reaction. So no deadlock is
> possible its also a better solution if units have multiple weapons.. For
> the weapons you can also make a weighted queue so that the more expensive
> weapons have priority.
>
> Example:
>
>  Player 0 orders
>  - Unit A: attack unit B
>  Player 1 orders
>  - Unit B, with very little health: < some order>
>
> Units action round:
> Unit A fires (lets say its a unguided missile).
> Unit B makes a turn.
> Weapons action round
> Weapon hits is target, but as Unit B changed the positionit only hits the
> ground
>
>  Player 0 order
>  - Unit A attack unit B
>  Player 1 order
>  - Unit B attack unit A
>
> In the first round both units fire, and the weapon is now between the
> attaker and the target.
> In the second round the weapons hit the target and cause the damage. So
its
> possible that both can kill each other without have rules.
>
> > Ending this email with an interesting question: Is it possible in TOTALA
> > to
> > create a circular movement with 4 units?
> > Imagine 4 units adjacent
> > AB
> > DC
> > Can we make the circular move A move to B's position, B move to C, C->D-
> > >A
> > ??
> > []'s
> > Gabriel
> > ----- Original Message -----
> > From: <address@hidden>
> > To: <address@hidden>
> > Sent: Friday, January 17, 2003 11:36 PM
> > Subject: [palito-dev] server sketch
> >>
> >
//------------------------------------------------------------------------ 
> >
> >
> >
> >
> > --
> > -
> >> int main(int argc, char *argv[])
> >> {
> >> print_welcome();
> >> network_init();
> >>
> >> while() {
> >> tv = wait_period;
> >> do {
> >> fd_set(rin, fileno(stdin));
> >> foreach fd_set(rin, player[i]->fd);
> >> start_select = get_ticks;
> >> if(select rin, tv) {
> >> foreach player
> >> if fd_isset(pl[i]->fd)
> >> process_command(i);
> >> if fd_isset(rin 0)
> >> process_command(0);
> >> }
> >> spent_on_select = get_ticks - start_select;
> >> tv -= spent_on_select;
> >> } while (tv>0);
> >>
> >> start_gameloop = get_ticks;
> >> game_tick();
> >> spent_on_gameloop = get_ticks - start_gameloop;
> >> wait_period = frame_period - spent_on_gameloop;
> >> }
> >>
> >> return 0;
> >> }
> >>
> >
//------------------------------------------------------------------------ 
> >
> >
> >
> >
> > --
> > -
> >> void process_command(Client *client, char *cmd)
> >> {
> >> char *tok = *cmd;
> >> switch(tok) {
> >> map;
> >> server settings;
> >> join {
> >> if(id = next_token)
> >> join as player id;
> >> else
> >> return new_player->id;
> >> }
> >> status {
> >> playerlist
> >> maplist
> >> orderlist [player] [unit]
> >> }
> >> client != NULL && command {
> >> unit = next_token(&tok);
> >> if(append|prepend|insert|delete) {
> >> if(insert|delete)
> >> order_idx = next_token;
> >> order_type = next_token(&tok);
> >> if(move|build|attack)
> >> target = next_token;
> >> else if(kill)
> >> kill();
> >> }
> >> else if(group) {
> >> group_id = next_token;
> >> group_op = next_token;
> >> units = next_tokens;
> >> }
> >> }
> >> }
> >> }
> >>
> >
//------------------------------------------------------------------------ 
> >
> >
> >
> >
> > --
> > -
> >> void game_tick()
> >> {
> >> // allocate unit slots with orders
> >> foreach player
> >> foreach unit
> >> use_slots = 0
> >>
> >> // decide what to do
> >> foreach order // inherit group?
> >> req_slots = 0
> >> "move"
> >> if too_far
> >> req_slots |= 1<<MOVE
> >> else
> >> accomplished = 1
> >> "attack"
> >> if target dead
> >> accomplished = 1
> >> break
> >>
> >> foreach weapon
> >> if used_slot & 1<<weapon_slot_id
> >> if (target_fly && weapon->is_air)
> >> || (!target_fly && !weapon->is_air)
> >> req_slots |= 1<<weapon
> >> range = weapon_range
> >> //FIXME move even if one
> >> // weapon already reaching?
> >>
> >>
> >> "build"
> >> if target_built
> >> accomplished =1
> >>
> >> req_slots |= 1<<NANO
> >> range = nano_range
> >>
> >>
> >> "follow"
> >> "guard"
> >> ...
> >>
> >> if dist_to_target > range
> >> req_slots |= 1<<MOVE
> >>
> >> if accomplished
> >> pop_order
> >> continue
> >>
> >> if req_slots & use_slots
> >> continue
> >>
> >> use_slots |= req_slots;
> >>
> >> foreach slot
> >> MOVE
> >> unit->slot[MOVE]
> >> target = order->target - range
> >> path//finding
> >>
> >> WEAPON1
> >> WEAPON2
> >> WEAPON3
> >> WEAPON4
> >> unit->slot[1<<weapon]
> >> target = order->target
> >> //allocate resources
> >> NANO
> >> unit->slot[MOVE]
> >> target = order->target - range
> >> path//finding
> >> //allocate resources
> >>
> >> end //foreach order
> >>
> >> // alocate unused slots on automatic tasks
> >> foreach slot
> >> MOVE
> >> wander around
> >> WEAPON1
> >> WEAPON2
> >> WEAPON3
> >> WEAPON4
> >> //shoot someone!
> >> //plane, trains and automobiles
> >>
> >> //allocate resources
> >> NANO
> >> //nanolate something!
> >> //patrol! get wreckage!
> >> //do something utile of your life!
> >> //FIXME make nano like a specialized weapon
> >> //  nano shoots friends and building stuff
> >>
> >> //allocate resources
> >>
> >> end //foreach slot
> >>
> >> if once_in_a_while
> >> //check communication with commander
> >>
> >> if once_in_a_while
> >> //add visual area on visualization map
> >>
> >> //FIXME visualization map is like
> >> //the commander communication check
> >> //(but to the enemy commander?)
> >>
> >> end //foreach unit
> >> end //foreach player
> >>
> >> foreach player
> >> foreach unit
> >> // finally do the physics and other shit
> >> foreach slot
> >> MOVE
> >> //change angle/speed
> >> WEAPON
> >> //spend energy/metal
> >> //aim
> >> //spawn shot
> >>
> >> if in_communication_with_commander
> >> send player unit
> >>
> >> foreach other_player
> >> if in visualization_map
> >> send other_player unit
> >>
> >> //FIXME visualization map is like
> >> //the commander communication check
> >> //(but to the enemy commander?)
> >>
> >> end //foreach unit
> >> end //foreach player
> >> }
> >>
> >
//------------------------------------------------------------------------ 
> >
> >
> >
> >
> > --
> > -
> >>
> >>
> >>
> >> _______________________________________________
> >> palito-dev mailing list
> >> address@hidden
> >> http://mail.nongnu.org/mailman/listinfo/palito-dev
> >>
> >>
> >> Esta mensagem foi verificada pelo E-mail Protegido Terra.
> >> Scan engine: VirusScan / Atualizado em 15/01/2003 / Versão: 1.3.13
> >> Proteja o seu e-mail Terra: http://www.emailprotegido.terra.com.br/
> >>
> > reply via email to
> >
>
>
>
> -- 
> Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
>
>