Turn execution

ID:151557
 
Apr 21 2010, 4:10 pm
I'm working with a turn datum right now called "battle_control" 
Battle_Control
    var
        Player_Limit
        Phase_Count

        list
            Players = new


Anyways, I want to keep everything simple with simplistic methods of keeping track (I've made numerous attempts at such a system only to confuse myself with too many variables to continue before), so procedures as simplistic and easy as adding and removing players. 
    proc
        Add_Player(mob/m)
            if(Player_Limit && !(Player_Limit < Players.len)) //if there's a limit and it has been reached
                world << "Player Limit has been reached."
                return
            Players += m

                world << "[m] [m.clan] has joined the battle"

        Remove_Player(mob/m)
            if(m in Players)
                Players -= m


Anyways, onto the main point; I'm trying to decide upon the best way for options to appear for the user, after the "next_phase" procedure is run. 
        Next_Phase()
            Phase_Count ++
            world << "Phase [Phase_Count]"
            var/list/turn_order = Find_Turn_Order(Players)

            world << "It is now [turn_order[1]]'s turn!"





proc
    Find_Turn_Order(list/players)
        var/list/turn_order = new
        var/mob/temp_lowest

        while(players.len)
            for(var/mob/m in players)
                if(!(temp_lowest) || m.delay < temp_lowest.delay)
                    temp_lowest = m

            //once the above loop is finished we have determined the lowest delay of a player.
            turn_order += temp_lowest //add the player to the list in that order
            players -= temp_lowest //remove from list to find next lowest delay... repeat.
            temp_lowest = null

        return turn_order


Is the easiest and best way to just give the determined player who was selected to have their turn next a variable such as "MyTurn = 1"? Or is there a more effective way to doing this and keeping track of it through a variable?

I was thinking maybe on "turn_phase" it could "call" a variable procedure if the mob has one, which would give access to all their "battle" and "movement" procedures (and the reason I quote these as they have more than one connotation).

What would be the easiest way to either go about one of the above ideas, or perhaps an easier method? I'm not completely familiar with how I would define these "battle" and "movement" procedures and would like some feedback. Thanks :)

P.S. If any of the code is less than efficient, or is wrong, don't hesitate to point it out.
Apr 21 2010, 5:02 pm
Store the order of the players in a list. It'll simplify it a lot!

var/list/PLAYERS=list()

mob/proc/is_my_turn()
   if(length(PLAYERS)>=1)
      if(PLAYERS[1]==src) return TRUE
   return FALSE

mob/proc/add_me()
   if(src in PLAYERS) PLAYERS.Add(src)

mob/proc/remove_me()
   if(src in PLAYERS) PLAYERS.Remove(src)

proc/next_turn()
   if(length(PLAYERS)>0)
      var/list/n = PLAYERS.Copy(2,0)
      n+=PLAYERS[1]
      PLAYERS=n
      world<<"It is now [PLAYERS[1]]'s turn!"
Apr 21 2010, 5:42 pm
In response to EGUY
Hi EGUY,

Recreating the list whenever you call next_turn() is really a very bad way to go about this. A better solution would be storing an index that indicates whose turn it is.
Apr 21 2010, 10:43 pm
In response to Seashells
While recreating the list is indeed unnecessary, cutting the first item and adding it back to the end strikes me as a nifty way to avoid index management period. Knowing that the first position is always the current player is reassuringly simple. No more incrementing list positions and checking if they're out of bounds. No more decrementing list positions based on whose turn it is when a player is removed.

Granted, I tracked indexes in my tried and true library. However, that was made with the option of reordering turns every round.
Apr 21 2010, 11:50 pm
In response to ACWraith
But aren't you over-estimating how difficult it is to work with an index? The simple calculation of <code>((turns_passed % amount_of_players) || amount_of_players)</code> allows you to figure out whose turn it currently is. Did this kind of calculation cause you trouble when working on your lib?

While I wouldn't deny the value of an organised list, I don't think it's practical to use one as the meat of the actual turn handler. Instead, because the value of such a list is more interfacial, creating a proc that returns the organised turn list seems more viable.
Apr 22 2010, 11:23 am
In response to Seashells
I don't think recreating the list is necessarily intensive, depending on how big the list is going to get. It may be overkill, but it gets the job done with little question in my mind and it's intuitive to me. If you weren't making this on a modern computer then maybe it would be something to worry about. And of course if your programming language doesn't support something like lists then the other way is the route to go in.

I'd rather manage that single list than X variables on a bunch of mobs. If a player leaves or joins, the changes to the list are rather simple and won't require back-checking the person's index variable to make sure everything is well.

Plus, you can shuffle a list or do other things with it without having to go back and retroactively adjust all the player variables. I haven't tried it myself yet but you could probably define procs for a list which simplify the actual implementation of the system as well. Not sure if this would work or not:
list/proc/bubble_sort(params)
   //yada
Apr 22 2010, 11:50 am (Edited on Apr 22 2010, 11:58 am)
In response to EGUY
Only one additional variable is necessary, and it is the one indicating the amount of turns that have passed. However, you mistaken this discussion to be about efficiency; which method is more efficient was never my point. Undoubtedly storing an integer and incrementing it is far more efficient than recreating the list, but the difference is minuscule when compared to such things as complex loops, and bothering with it would be pointless pre-optimization. The issue here is one of design.

If I find the time, I'll clarify the disadvantages that occur from using your method more thoroughly. To be brief, however: by recreating the list every time you not only lose information (for example, the original round order), but you also perform complex operations on the list when incrementing a single integer would suffice. Instead of writing:

proc/next_turn()
   if(length(PLAYERS)>0)
      var/list/n = PLAYERS.Copy(2,0)
      n+=PLAYERS[1]
      PLAYERS=n


Is it not much more ideal to write:

proc/next_turn()
   turns_passed ++


And be done with it?

Any external benefit you will get by using a recreated list as the information source of your turn-based engine is due to poor design. Ideally, the user of your system will never directly access your list at all, and so its structure won't benefit him. That said, and as I previously mentioned, there is definitely interfacial merit to having a proc that organizes the list in the way you do; but making it the source of information regarding turn order, is bad practice and should be avoided.
Apr 23 2010, 4:47 pm
In response to Seashells
But there is more to it than just,

((turns_passed % amount_of_players) || amount_of_players)

If people leave the game, the player it gives out next won't always be the correct one. Which is what people are trying to tell you.
Apr 24 2010, 4:36 am (Edited on Apr 24 2010, 5:07 am)
In response to T3h P3ngu1n
I'm somewhat embarrassed to admit I missed that part twice when responding ([edit:] apologies to AC and EGUY of course!). But yes, fair enough, if someone leaves, a little case-handling with an index offset is necessary (alternatively you could handle this by replacing the player's turn slot with 'null' and treating that slot as taken by a dummy player). That said, it's nothing complex, and I still believe the benefits of this system over the other outweigh this fact.
Apr 24 2010, 5:48 pm
In response to Seashells
Seashells wrote:
But aren't you over-estimating how difficult it is to work with an index? The simple calculation of ...

Simple calculations are nice, but less flexible. Imagine index-tracking players A, B, and C. It's player C's turn, and player B drops from the game. This is a simple scenario which can be handled somewhat simply, but it can be more severe and this illustrates the main point that with index-tracking, you are tasked with the responsibility of actually tracking your index. This has the potential to become tedious and error-prone.

A solid plan for turn-based systems is to put all of the players into a queue data structure. To advance turns, you simply have to pop() the front of the queue and then push() it to the back. This is effectively what ACWraith described, but using a more general data structure making it more reusable.

Here's a basic /Queue datum which could be used for this:
Queue   // personally I prefer lowercase names, but consistency insists...
    var/list/m_data
    
    proc
        Push(x)
            if(!m_data)
                m_data = list(x)
            else
                m_data += x
        
        Pop()   // runtime error if list is empty
            ASSERT(m_data)
            . = m_data[1]
            if(m_data.len == 1)  // free list object if empty
                m_data = null
            else
                m_data.Cut(1,2)
                
        Peek()  // runtime error if list is empty
            ASSERT(m_data)
            return m_data[1]
                
        Size()
            return (m_data ? m_data.len : 0)
            
        Empty()
            return !m_data
            
        Remove(x)   // not a true queue operation but helps for Remove_Player()
            if(x in m_data)
                m_data -= x
                if(!m_data.len)
                    m_data = null
                return TRUE     // removed
            else
                return FALSE    // couldn't remove


Then you can rewrite the /Battle_Control datum like so:
Battle_Control
    var
        Phase_Count
        Player_Limit
        Queue
            Player_Queue = new
    
    proc
        Add_Player(mob/m)
            if(Player_Limit && Player_Limit>=Player_Queue.Size())
                world << "Player Limit has been reached."
            else
                Player_Queue.Push(m)
                world << "[m.name] [m.clan] has joined the battle"
                
        Remove_Player(mob/m)
            return Player_Queue.Remove(m)
            
        Next_Phase()
            if(Player_Queue.Size() > 1)
                var/mob/m = Player_Queue.Pop()
                Player_Queue.Push(m)
                
                ++Phase_Count
                world << "Phase [Phase_Count]"
                
                m = Player_Queue.Peek() // I like to re-use variables
                world << "It is now [m.name]'s turn!"


It is worth noting that a common goal of object-oriented programming is code-reuse, so you needn't make a new /Queue datum every time you have a use for a queue data structure. Unknown Person has a library, upContainers, which contains an implementation of a /Queue datum, as well as several other generic containers.
Apr 24 2010, 7:36 pm
In response to Kuraudo
I would change your Push code.

If x is a list it has a different behavior depending on whether or not m_data was null at the beginning.

    proc
        Push(x)
            if(!m_data)
                m_data = list()
             m_data += x


That could work, but just depends on how you want to manage putting a list in it.
Apr 25 2010, 5:53 am (Edited on Apr 25 2010, 6:05 am)
In response to Kuraudo
I share your opinion about indexing in general, but not in this particular case. As we are talking about a turn-based system, we are talking about maintaining a turn progression dictated by a "player bank", from which we select the appropriate player depending on certain variables. As far as I can see, the only added complexity with using an index is some simple case-handling in the event a player leaves. This can be handled effectively, and the error-proneness is only seemingly present.

But, a queue system has several cons that you did not account for.

To begin with, the flow of the battle in general is more difficult to predict and manipulate with a queue, being a linear data structure. You cannot use it alone to easily predict the turn order (because you cannot check members in the middle of the queue), nor influence it.

Also a primary concern is that, with a queue-based system, information such as the actual round order (that is, whose turn opens the around, whose turn ends it, etc.) is not a given, and must be kept for reference. This becomes a bigger problem when it needs to be updated, and also interpreted by, and synchronized with the queue.

Let me illustrate how this can become a problem. As this is a battle system, it is not perpetual. Therefore, the round order is potentially more dynamic than with, say, a roguelike world-wide turn handler (in the case of a roguelike, by the way, I would prefer a priority queue-based implementation). That is to say, at a certain point in time the battle system's designer might wish to allow for turn-order altering events. I don't want this to become a "what-if" discussion, but I mention this point because it seems entirely likely, given the context, that the OP might eventually want to do something like this with his system (if he doesn't already).

If the designer wishes to simply skip some turns, the operation is different in both cases. With an index it is particularly simple: incrementing it would work. But when using a queue, he would have to restructure the queue in a manner similar to the "next turn" method a specifiedf amount of times until the appropriate order is received, while avoiding actually calling the "next turn" proc. A bigger problem arises when he wishes to manually change the round order (such as making the round opener, the third player to play). To do this using queues, he would need, aside from the queue, a reference to the actual round order, in order to restructure the queue according to it. Come the additional complexity I mentioned before, and with it the tediousness and error-proneness that we wanted to avoid. Using an index, because we are only restructuring, he could directly change the round order and be done with it.

My post is already quite longer than I intended it to be, so I'll cut short here. I suppose my intent in this response was to show that an index system is not as inflexible as it seems, and that the proposed queue system is not as flexible either. As with most anything, the famous aphorism "use the right tool for the right job" applies. There are instances in which a queue is preferable to indexing, and in others it is the reverse. I think this case is of the latter.
Apr 25 2010, 11:11 am
In response to Seashells
Seashells wrote:
But, a queue system has several cons that you did not account for.

You cannot use it alone to easily predict the turn order (because you cannot check members in the middle of the queue), nor influence it.

Sure I did, I just did not explicitly account for it. One of the things about DM is that data-hiding is impossible; there is no "private" and "public" specifier for member variables. At any time, you could use the m_data variable to directly reference the queue structure's elements. While this removes the elegance of the general queue system, it does not degrade to being any worse than the index-based system you favor. As for the index: that is accounted for in the /Battle_Control datum as the Phase_Count variable (which should, likely, be initialized to 0).

The key thing here is that you only degrade to list/index operations in a small minority of cases, while operating with a higher-level queue for the majority. The more time spent operating on high-level data types, the less time spent risking calculation errors or for accounting for all of the "what-if" risks that index-based systems would impose.

If the designer wishes to simply skip some turns, the operation is different in both cases. With an index it is particularly simple: incrementing it would work. But when using a queue, he would have to restructure the queue in a manner similar to the "next turn" method a specifiedf amount of times until the appropriate order is received, while avoiding actually calling the "next turn" proc.

Huh? To skip a turn all you would have to do is push(pop()) again. This would be as simple as giving players a "skip" var and a small amount of skip-handling in the "next turn" proc. Some pseudocode for everything:
   push(pop())   // advance to next player
   var/mob/next = peek()   // next player
   while(next.skip)
      --next.skip
      push(pop())
      next = peek()

This logic isn't much different from if you were using an index:
   ++index
   var/mob/next = list[index]
   while(next.skip)
      --next.skip
      ++index
      next = list[index]
So I don't see your point.

As for all of your talk about "round opener" and "round ender," I think it's a bit nonsensical. In most cases, there is little concept of a "round;" you're just taking turns. If you do have to track the round opener, all you need is a variable reference in the /Battle_Control datum to it. To change the opener, all you have to do is change the reference. If you need to traverse the queue structure, as I mentioned before, you can always access m_data as if it were a simple list and index setup. You can find the index of the opener with a simple Find() call and do simple arithmetic from there to re-assign it. If you wanted to make the opener the nth person in the round:
   var/index = battlecontrol.m_data.Find(opener)
   index -= (n-1)
   while(index <= 0)
      index += battlecontrol.m_data.len
   opener = battlecontrol.m_data[index]

In either system, you always have to account for scenarios that affect your system's integrity. I personally find that the queue system is more elegant and robust, for a small trade-off in terms of memory use and some negligible operations.
Apr 25 2010, 11:19 am
In response to T3h P3ngu1n
T3h P3ngu1n wrote:
If x is a list it has a different behavior depending on whether or not m_data was null at the beginning.

That is a good point, and is rooted in one of DM's peculiarities that I have never agreed with.

For the record, I don't so much agree with your solution:
but just depends on how you want to manage putting a list in it.

---because I believe that trying to push a /list into a container should put the list within the container, rather than append each of its contents. As a fix to my original oversight, I would rewrite it as such:
        Push(x)
            if(!m_data)
                m_data = list(x)
            else
                m_data[++m_data.len] = x
Apr 25 2010, 1:14 pm (Edited on Apr 25 2010, 1:28 pm)
In response to Kuraudo
My criticism was levelled at the queue implementation. A queue is a well-known data structure, and its common implementations do not allow checking the "m_data"'s equivalent's contents. When you talk about accessing the queue's contents you are treating the queue in a different sense, which my response did not account for. The sense you refer to it in is actually pretty much what EGUY had in mind. That said, I'll clarify some things:

You slightly misunderstood the way I talked about turn skipping. If, truly, each member of the turn list had a "skip" variable that determined whether its turn should be skipped, then the implementation would've been roughly the same. I was speaking about such a situation as say, a player using an ability that skips three turns forward, in which case what you would have to do with an index implementation is much simpler.

As for the round system, you are right that I am assuming there are actual "rounds". If they do not exist in this system, some of my criticism here admittedly does not apply. However, if they do, the code you gave for altering the round order is much more complex than simply restructuring the round list. Reordering it around the opener alone might be feasible, but say if you wanted, in addition, to switch the fifth and sixth player's turn, using the commonly-accepted queue system, you would've had more trouble (this argument is somewhat less applicable if you can access m_data directly, but remember I was arguing against the "closed" queue).

You wrote:
While this removes the elegance of the general queue system, it does not degrade to being any worse than the index-based system you favor.

But I disagree. Exactly because of this, your implementation is less preferable to the index one, which I find more elegant in light of the points I mentioned.

I don't think that, in a turn based system, the aforementioned operations are a minority; depending on the usage, you may very well want to do things such as these very often, and in that case, the index implementation eases things. There are likely other things that it makes more difficult, and feel free to point them out; if the likeliness of them happening in a battle system is similar or larger than that of the issues I mentioned regarding queues, then I might very well change my mind and favour the "queue" implementation as well.

But after all, I think that at around this level, elegance is subjective, and arguing about it is pointless when discussing which system is superior to the other. After reconsidering things, I realized that, in my initial response I was very much against your and EGUY's kind of preferred implementation. Now: I still favour indexing, but not so much, and after hearing some arguments for the other implementation I am tempted to use it instead, if I ever need a turn-based system handler.

It's getting quite late, so I'll end my response here. I'll check this post again around tomorrow to see if you responded.


Apr 26 2010, 9:50 am
Okay, so I pretty much don't understand what anyone has said below.


So just really wondering about this part:

-quote- "Anyways, onto the main point; I'm trying to decide upon the best way for options to appear for the user, after the "next_phase" procedure is run. "
Apr 26 2010, 11:53 am
In response to Speedro
Speedro wrote:
Okay, so I pretty much don't understand what anyone has said below.


So just really wondering about this part:

-quote- "Anyways, onto the main point; I'm trying to decide upon the best way for options to appear for the user, after the "next_phase" procedure is run. "

Well are we talking user interface or behind the scenes stuff?
Apr 26 2010, 3:04 pm
In response to EGUY
Generally interface.

I was currently thinking just on screen buttons that you couldn't click unless it your "my turn" variable was 1. Same for movement with arrow keys.

And does a "my turn" variable seem like a good idea? Then the player just clicks the "end turn" button on their screen, which changes their "my turn" variable to 0, then how would I specifically send this information to the datum to call Next_Phase()? The only way I know right now is for each mob to have their own variable. So here's an example: 
mob
    NPC
        verb
            fight()
                set src in view(1)
                var/Battle_Control/BC = new
                BC.Add_Player(src)
                BC.Add_Player(usr)
                BC.Next_Phase()
                
                //And then this is what I mean below:
                src.battle_datum = BC
                usr.battle_datum = BC
                
mob
    var
        Battle_Control/battle_datum
    verb
        end_turn()
            if(battle_datum)
                battle_datum.Next_Phase()


Is this the best way to approach controlling the datum outside of itself?
May 6 2010, 4:38 pm
In response to Speedro
Yes? :O
May 8 2010, 12:59 am
Um, forgive me for this suggestion, perhaps, while i'm getting pretty experienced with programming for byond, i'm still not uh... top notch.

I was making a Turn-Based RPG Framework, with AI, Parties, ect.

When I made the combat itself, I made a list of all participants. I then used the Index of the list as the turn number.

On top of that, I had lists of all enemies, all party members, and so on, for attacks that hit all, and such.

Edit:
My Demo or whatever doesn't including people being added midbattle.

Of course, you could have a party var on the party leader (or just the battle control), and then when someone gets added, add them to the list inside the next_Phase proc, or someplace else that gets called a lot.

Edit:
Looking more at this, you may want to ignore my post, as, my Turn-Based RPG is all one proc, for combat. I wasn't paying attention to the whole post, I apologize