05 Jul, 2014, jakesmokes wrote in the 1st comment:
Votes: 0
Hello,

I was wondering if anyone could give me some insight into what is the best way to handle fair processing of turns in MUDs. Any thoughts or pointers to codebases with good implementations would be helpful.

My initial thinking is to process turns in order for all players and active NPCs. From what I am able to glean from the couple of codebases I have looked at it seems like some muds sync turns to "ticks". Which, if I am reading it right, means that turns are synced to time intervals and all participants get one turn per interval. Using a turn system seems like the most straightforward and, possibly, fair way, but I do wonder about any performance implications there. I have also been toying with the idea of giving players their own threads which could make processing in order challenging.

I have noticed that, with the few codebases I have looked at thus far, code isn't generally very well commented which makes some of this difficult to follow for people who aren't thoroughly inculcated into the ways traditional muds operate.

Any thoughts or good places to look for ideas?

Thanks (again) in advance,

David
05 Jul, 2014, Rarva.Riendf wrote in the 2nd comment:
Votes: 0
The thing is simple in diku:
all the char_list is iterated and every potential action is then process on this perticular loop (look for what happen each "pulse")

Problem with that: someone logging after another player will have his command systematically processed AFTER the other player. (you can randomize the char list or order it with some other parameter though)

Giving player their own thread ? Welcome to the multithread lock/synchro hell.
05 Jul, 2014, jakesmokes wrote in the 3rd comment:
Votes: 0
Hi,

Thanks for the response. Wouldn't the order only matter the first time through? A goes then its B's turn who will now go before A, right? Unless both players log on at the same time and were perfect in their execution of commands would it matter right? Or has this been a problem in the past.

An alternative to threading would be to use dispatch queues which handle the lock business for you. Or even assign the threads to players for read activities and handle writes through a dispatch queue.

So based on your comment, then, it sounds like the common approach is turn based?

Thanks,

David
05 Jul, 2014, Idealiad wrote in the 4th comment:
Votes: 0
Many muds use a tick, though I think the Tiny codebases (e.g. mux, mush) run on a command queue without a specific tick, and some muds (God Wars 2?) don't use turns but action points instead. So when the player has enough action points for the action it's put on a command queue, and the action fires based on some execution time.
06 Jul, 2014, Rarva.Riendf wrote in the 5th comment:
Votes: 0
>A goes then its B's turn who will now go before A, right?

No there still is a (imho) huge problem
Think an action like bash that would always suceed each round, if one player always can act before the other each round, see what happens.
06 Jul, 2014, alteraeon wrote in the 6th comment:
Votes: 0
Never use threads unless you have to. A well coded server on modern hardware should be able to handle a hundred players and ten thousand mobs at 1-5% of a single processor core in a single thread. Adding threads will needlessly complicate your project for zero net gain.

Alter Aeon MUD
http://www.alteraeon.com
06 Jul, 2014, plamzi wrote in the 7th comment:
Votes: 0
Rarva.Riendf said:
>A goes then its B's turn who will now go before A, right?

No there still is a (imho) huge problem
Think an action like bash that would always suceed each round, if one player always can act before the other each round, see what happens.


If you are looping through player input queues 10 times per second like Diku does, then the problem of privileging older connections practically goes away, even if you have split-second PvP going on all the time. Two people would have to have queued mutually cancelling actions (that would have both succeeded) all in the same 1/10th of a second for the order to matter.

If you are not processing queues so frequently, or are designing turn-based combat, then there are several pretty well-established conventions for keeping things fair, for example action-point based systems already mentioned.

If you are processing player input frequently but still sequentially, and you're still worried about fairness, one simple thing that comes to mind is to process players A-Z once, then Z-A the next round. If you're designing from the ground up, then you could just have a global command input queue where things end up in the exact order in which they were received.

People have already mentioned multi-threading. There's also the async event model under which you won't have to worry about fairness. Commands will get processed in the order received as soon as they are received, unless you artificially queue them up for synchronous / sequential processing. I'm not sure what language you're using, but I think that even in pure C this would be possible, since socket polling is asynchronous. The catch is that this would have to be baked into your design from a very early stage, and it would make even simple things considerably more complicated, as in, you'll no longer have a main loop in the conventional sense.
06 Jul, 2014, Rarva.Riendf wrote in the 8th comment:
Votes: 0
plamzi said:
> Two people would have to have queued mutually cancelling actions (that would have both succeeded) all in the same 1/10th of a second for the order to matter.


You have a command queue in most diku, so no it is not a reflex problem, you can store as many command as you wish.
And since all actions have a 'lag' limitation, you are far from having rapid fire actions.

plamzi said:
>If you are not processing queues so frequently, or are designing turn-based combat,


All games are turned based, as soon as your modus operandi is to loop through a list that is always in the same order. The fact that the turn are made in a millisecond or two hours changes nothing about it: it is a turn based game.

plamzi said:
>The catch is that this would have to be baked into your design from a very early stage, and it would make even simple things considerably more complicated, as in, you'll no longer have a main loop in the conventional sense.


That is a very big catch :) and not necessarily useful as well to address this perticular problem (you can just reorder the loop depending on thing like 'initiative', based on a dice or other parameters (a fighter swing his sword almost without thinking while a caster must have its spell casted, wave his hands or what not etc, it is called thaco if I remember correctly D&D rule)
I do not do it yet) but it is a real problem in PVP. And I am not talking 'in theory', you can experiment it first hand, when the other people always fire their actions before yours.
06 Jul, 2014, plamzi wrote in the 9th comment:
Votes: 0
Rarva.Riendf said:
plamzi said:
> Two people would have to have queued mutually cancelling actions (that would have both succeeded) all in the same 1/10th of a second for the order to matter.


You have a command queue in most diku, so no it is not a reflex problem, you can store as many command as you wish.


Yes, but the command input queue is not global. It's on the socket, and sockets' command queues get processed in order. Judging from your earlier comments, you know that's the case, so I'm not sure what point you're making here.

Rarva.Riendf said:
And since all actions have a 'lag' limitation, you are far from having rapid fire actions.


That's exactly what I meant when I said that both actions not only have to be submitted within the same 1/10th of a second, but would also have to have both succeeded. Given that most actions where speed matters would probably have some kind of cooldown, the chances for command processing order to matter would get pretty slim.


Rarva.Riendf said:
plamzi said:
>If you are not processing queues so frequently, or are designing turn-based combat,


All games are turned based, as soon as your modus operandi is to loop through a list that is always in the same order. The fact that the turn are made in a millisecond or two hours changes nothing about it: it is a turn based game.


Uhmm, yeah, but the point is that the problem is so mitigated in some games that you shouldn't need to worry about it. Of course, you're welcome to worry about slight problems, but I would not call this best practice, since by definition this would prevent you from worrying about problems that matter more.

Rarva.Riendf said:
plamzi said:
>The catch is that this would have to be baked into your design from a very early stage, and it would make even simple things considerably more complicated, as in, you'll no longer have a main loop in the conventional sense.


That is a very big catch :) and not necessarily useful as well to address this perticular problem


Most modern frameworks / platform API are designed this way, for good reasons. It solves a great number of issues having to do with concurrent usage and the added complexity is a lot less than with multi-threading.

The event-based model is actually great for something like a MUD server, and you'll just get things like "fair" command processing for free. But the biggest benefits would be in terms of never blocking the whole server until an intensive process takes place.

I'm not sure why you feel it would not address this problem because it's pretty clear that the problem will not even come up in that context, unless you go out of your way to create it.

Rarva.Riendf said:
(you can just reorder the loop depending on thing like 'initiative', based on a dice or other parameters but it is a real problem in PVP. And I am not talking 'in theory', you can experiment it first hand, when the other people always fire their actions before yours.


You could but those are just more mitigation techniques. Having a global command queue would solve the issue within the synchronous input processing paradigm, as I've already pointed out. Or flipping the processing order of sockets every round, which would be easier to implement in an existing codebase.
06 Jul, 2014, Rarva.Riendf wrote in the 10th comment:
Votes: 0
>Yes, but the command input queue is not global.

I do not se why it is not for you. The fact the command queue is stored in the player action queue, and that the player are stored in a ordered list, and that the action are only processed in a loop in always the same order, you could definitely make it global without changing anything.

>I'm not sure why you feel it would not address this problem because it's pretty clear that the problem will not even come up in that context, unless you go out of your way to create it.

Err I just say that using thread for that only will probably cause more problems than it solves, not that it won't solve this one.

And processing commands in the order they come is not necesserily 'fair'. I prefer to reorder the queue with some more fair parameters than your server ping.
06 Jul, 2014, plamzi wrote in the 11th comment:
Votes: 0
Rarva.Riendf said:
>Yes, but the command input queue is not global.

I do not se why it is not for you. The fact the command queue is stored in the player action queue, and that the player are stored in a ordered list, and that the action are only processed in a loop in always the same order, you could definitely make it global without changing anything.


I think you're not seeing the gotchas involved. The Diku design has a socket "input" buffer, from which a series of commands is parsed. Some commands (such as wear, remove) end up "delayed" while others (look) can be added at the top of a command queue. Aliases / multi-commands get exploded and added to a player's command queue.

When you switch to a global queue, it's not enough to just process input in the order your received it. You will also need logic that can scan for a player's latest commands vs. commands others have queued up as well as vs. the player's own queue of prior commands. You should try to do it and you'll see that it's not trivial.

One possible solution is to keep command queues on the socket, but handle player input in a global queue and attach a timestamp to each command. Then, when a round comes up, you can process commands in timestamp order instead of player order.

Rarva.Riendf said:
>I'm not sure why you feel it would not address this problem because it's pretty clear that the problem will not even come up in that context, unless you go out of your way to create it.

Err I just say that using thread for that only will probably cause more problems than it solves, not that it won't solve this one.


The async model solves a lot more problems than the challenges it creates. You just have to think in a different way from what you're accustomed to.

Rarva.Riendf said:
And processing commands in the order they come is not necesserily 'fair'. I prefer to reorder the queue with some more fair parameters than your server ping.


I'm really not sure what you mean here but I'm assuming some gameplay logic to make sure ping doesn't overtake skill. That's all fine, but your input processing model is clearly not the place for that kind of logic. How would you know who to bump up and that you won't in fact be creating a bigger problem than the one you're trying to solve?
06 Jul, 2014, Rarva.Riendf wrote in the 12th comment:
Votes: 0
>I think you're not seeing the gotchas involved. The Diku design has a socket "input" buffer, from which a series of commands is parsed. Some commands (such as wear, remove) end up "delayed" while others (look) can be added at the top of a command queue. Aliases / multi-commands get exploded and added to a player's command queue.

>When you switch to a global queue, it's not enough to just process input in the order your received it. You will also need logic that can scan for a player's latest commands vs. commands others have queued up as well as vs. the player's own queue of prior commands. You should try to do it and you'll see that it's not trivial.

I did not say it woudl be trivial to switch, but that the final result would be exactly the same.

>The async model solves a lot more problems than the challenges it creates. You just have to think in a different way from what you're accustomed to.

Multithreading cause a lots more problems for everything than it solves here. Especially on a text game.


> How would you know who to bump up and that you won't in fact be creating a bigger problem than the one you're trying to solve?

Bumping someone would depend on his class, equipement stats etc, if two people would end up equal, then their order would be randomized. it is easy enough to do, AND fair.
Basing the order of action on the time they logged (like the default 'parsing of the player list') is everything BUT fair in this concern.
For fighting mobs, it really does not matter at all as everyone is equal to them.
For pvp there is one.
06 Jul, 2014, plamzi wrote in the 13th comment:
Votes: 0
Rarva.Riendf said:
>
I did not say it woudl be trivial to switch, but that the final result would be exactly the same.


Maybe it's an ESL thing, but I think when you say "you could definitely make it global without changing anything" the implication is that the change is straightforward.

Rarva.Riendf said:
>The async model solves a lot more problems than the challenges it creates. You just have to think in a different way from what you're accustomed to.

Multithreading cause a lots more problems for everything than it solves here. Especially on a text game.


You should google async vs. multithreading because they're not at all the same thing. Your response makes me think that you don't really know how they are different.

Rarva.Riendf said:
> How would you know who to bump up and that you won't in fact be creating a bigger problem than the one you're trying to solve?

Bumping someone would depend on his class, equipement stats etc, if two people would end up equal, then their order would be randomized. it is easy enough to do, AND fair.


Well, now that you've actually said "easy", it is another case where I would actually expect it to be *NOT* easy. Are you going to evaluate relative player strength upon every player input before deciding who gets to go first? What if there are 10 people engaged in PvP? That's a whole lot of work (and overhead) to fix something that most people would not even call broken…

Rarva.Riendf said:
Basing the order of action on the time they logged (like the default 'parsing of the player list') is everything BUT fair in this concern.


Connection order is fairly random, and I think we've already agreed that it won't even make a noticeable difference in a real-time context. But once you take over who gets to go first, it's a sea change. Now, you'd better have a damned good reason for what you're doing because some players are going to be pointing fingers at you for any real or imaginary grief.
06 Jul, 2014, Rarva.Riendf wrote in the 14th comment:
Votes: 0
>You should google async vs. multithreading because they're not at all the same thing. Your response makes me think that you don't really know how they are different.

I thought you were talking about multithreading, not only doing thing asynchronous, because well, mostly everything is already done asynchronously per default in Diku.

>Are you going to evaluate relative player strength upon every player input before deciding who gets to go first? What if there are 10 people engaged in PvP? That's a whole lot of work (and overhead) to fix something that most people would not even call broken…

Why every input ? last I know player class/race/etc does not change every round, and this initiative parameter can be adjusted whenever this change, so no need to evaluate this at every input, it is done elsewhere…
And anyway, only needed to be done in the loop where you actually make the people act. And dont tell me reordering a list on a single parameter is an overhead. Quicksort is blindingly fast.

>Connection order is fairly random, and I think we've already agreed that it won't even make a noticeable difference in a real-time context.

Connection is 1 : not random (most people live in different time zone) 2: once connected, order is pretty much set once and for all till people disconnect.

> I think we've already agreed that it won't even make a noticeable difference in a real-time context.

You agreed that with yourself , there is a definitely noticeable difference , but the problem is you take a mud for a real time context game when most muds are purely turn based game. Making the turn shot in time does not change anything to this fact.
07 Jul, 2014, alteraeon wrote in the 15th comment:
Votes: 0
IMHO the easiest way to get players to execute commands in random order as you describe above is to change the 'lag_character()' function so that it randomly has a 50% chance of adding 1 extra lag to incoming values. This will occasionally delay one player slightly longer than the other.

On Alter Aeon, the fight loop runs at the slice rate, eg ~8 times per second, and there's no heartbeat based combat activity at all. This makes combat extremely async, with command parse ordering about as fair as is reasonable to implement. This is handled by keeping a list of all fighting characters and running that list to handle combat updates every slice. There's a LOT of side effects to using this approach, and it's taken a lot of years to make it work well; I would not recommend other servers attempt to switch to this model.

AA uses an async event handler system for a huge amount of stuff now, but the event handler system was definitely a tack-on module in the beginning. I'd recommend adding one and using it as new requirements come up, or as you discover performance bottlenecks.

Alter Aeon MUD
http://www.alteraeon.com
07 Jul, 2014, plamzi wrote in the 16th comment:
Votes: 0
Rarva.Riendf said:
> I think we've already agreed that it won't even make a noticeable difference in a real-time context.

You agreed that with yourself , there is a definitely noticeable difference , but the problem is you take a mud for a real time context game when most muds are purely turn based game. Making the turn shot in time does not change anything to this fact.


I have no idea what you're saying. If you have some skill like bash that succeeds 100% of the time and is implemented in a way where it's highly likely for two people to attempt it within the same "frame" even when the frame is 10xSec, *and* if instead of changing your skill implementation (which is what I would do), you would rather mess with the order in which players get to attempt the skill, it still seems like a whole lot less work to make your player list double-linked so you can traverse it A-Z, Z-A, A-Z, etc. Next in the order of labor-intensiveness would be to have a global command queue (or keep track of the time when a command was received). Logic that would require you to analyze characters' properties would be somewhere near the bottom of my own list, because it would be a lot of work that may end up doing more harm than good.

On a very fundamental level, if you are evaluating player input in any other order than the one you received it, I cannot possibly call your approach fair, and I don't think anyone could. (It's kind of like the concept behind Net Neutrality - you would be privileging packages at the low level). If you are concerned with lag introducing too many disadvantages, there are much much much more effective and "fair" ways to minimize the importance of ping in gameplay. Some of those ways already exist in your game, like queuing commands, for example. So I strongly suspect that you are overestimating the impact of the player order by degrees of magnitude.
07 Jul, 2014, jakesmokes wrote in the 17th comment:
Votes: 0
Thanks for all the input. I am having trouble with the "quote" feature, so apologies for the format of my replies.

- I like the idea of reversing the order of players processed. That would be trivial to do and makes a lot of sense.

- In answer to planzi's question, I a coding in ObjectiveC. So, I could do what you were suggesting about eliminating the game loop by using dispatch queues that trigger off of socket input. I am probably at a stage where it wouldn't be to costly to convert, but I am thinking that, given what I am reading in this thread, that I should be okay if sample frequently and reverse order. One concern (which I haven't had a problem with yet) is what to do if processing an NPC turns out to be costly in terms of time and holds up processing.

- I don't plan on using threads directly. I am thinking, really, about using dispatch queues for certain functions which might take time away from processing player input / responses. Even with dispatch queues your code has to be "thread-safe" but if you are careful with the organization its actually not too big of a deal. An example might be using a queue for managing light in locations (there's that example again :-)). It could watch all the players / NPCs movement with light sources and adjust light levels in rooms without burdening the main thread as players move and calculate light levels. I have ideas for partitioning the workload using (probably serial) dispatch queues to lighten the load on the main thread. I do a fair amount of threaded work for my "real" job so I am not all that worried about it. Tools for debugging threads are pretty awesome these days.

Thanks for all the excellent discussion. I still have some more reading in the thread to do :-)

David
08 Jul, 2014, plamzi wrote in the 18th comment:
Votes: 0
jakesmokes said:
I a coding in ObjectiveC. So, I could do what you were suggesting about eliminating the game loop by using dispatch queues that trigger off of socket input. I am probably at a stage where it wouldn't be to costly to convert, but I am thinking that, given what I am reading in this thread, that I should be okay if sample frequently and reverse order. One concern (which I haven't had a problem with yet) is what to do if processing an NPC turns out to be costly in terms of time and holds up processing.


If you're using Objective-C sockets, you would be receiving notifications when a socket receives data. At that point, the natural thing to do would be for your processing method to handle the input. The less natural thing to do would be to stick this input into something and wait for a global input processing pulse to come by. If you do that, you'd be effectively trying to recreate a main loop inside your code that the framework itself has already abstracted away for you. You would be depriving yourself of one of the big benefits of the event-based model: high responsiveness to concurrent requests in a single thread.

Rather than try to recreate a Diku model, you could take full advantage of what has been given to you. You don't have to have a global input processing pulse, or a global combat pulse for that matter. Instead, socket input can be handled in the order it arrives, and each entity engaged in combat can have its own interval pulse for automatic attack attempts. Even though your hardware is likely more than capable of handling 10 fps for at least several hundred players, abandoning global pulses is going to make your game feel snappy and much more natural.

If you design your storage vs. in-memory data logic well, you will not need to use dispatch queues to handle the most frequent commands / actions a player may perform. Your code will know enough about current entity properties to handle any combat or common item manipulation event without having to call a database etc. After handling a state change, you could sometimes fire off an async save to persistent storage.
08 Jul, 2014, quixadhal wrote in the 19th comment:
Votes: 0
The important thing to remember, if you use a fully event driven system like planzi is describing, is that you have to carefully specify how frequently a given command can be used by a given player. That is, once they do a kick, or a sword swing, there should be some amount of time that passes before they can do another one. There might be global delays based on the type of action performed… if you just did a sword swing, you probably aren't physically ready to do a kick instantly.

This now matters, because without such delays, the player with the lowest latency connection will always win, since they can spam attacks. Resource costs won't help here, because they can still likely do enough damage quickly enough to overwhelm the slower connection player and keep the advantage, even as they wait for resources to regenerate.

The one good thing the Diku loop did was prevent this from happening. You could type as much as you wanted, but you'd only get one command per main loop round, at most. And at 100ms per loop, that was usually slow enough to counter most latency issues.

I'm not saying event-driven isn't a good idea, but you do have to consider this if you plan to have players from all over the globe, and using both fast fiber and slow cellular connections.
08 Jul, 2014, plamzi wrote in the 20th comment:
Votes: 0
quixadhal said:
This now matters, because without such delays, the player with the lowest latency connection will always win, since they can spam attacks…

The one good thing the Diku loop did was prevent this from happening. You could type as much as you wanted, but you'd only get one command per main loop round, at most. And at 100ms per loop, that was usually slow enough to counter most latency issues.


Evaluating input at the time it was received doesn't mean you can't, or shouldn't, have a command queue. It's the command queue + wait timers in Diku that minimizes the effects of lag during battle. If you don't have queues and wait timers, the up-to-100ms delay is not going to save anyone who is lagged.

In an event-based model, you can let all non-delayed commands simply execute (without waiting for the next loop), while those who run on a timer can be queued up. The important difference is that the wait timer will be individual, and so the person who performed a combat action first, and whose combat action is capable of firing first, will win out. That's the most fair you're going to get. It is only if you artificially delay and store input for a global pass that you set yourself up for the problem that the OP is worried about.
0.0/40