The thread thread

[oln]

I've looked through the code to get an overview of the different threads that are spawned and what they do (work in progress, missing some threads. Adding some grahpics soon):
(Referring to the threads by the name of the pthread handle variable.)

• Main thread
  
  • Handles: Rendering, gui, sound, input
  • The "main loop" is the framestarted function in ODFrameListener.
  • I think the rendering, gui and input has to be done in the main thread, especially since the ogre version in the PPA is not compiled with thread support. Not much point in putting the sound in it's own thread, though it might need a lock as it could be called from more than one thread.
• serverThread - serverSocketProcessor() in Server.cpp -
  
  • Started from: startServer() in Functions.cpp
  • Handles: Incoming connections.
  • Blocks while waiting for a new connection. Spawns a clientHandlerThread whenever a client connects.
  • Function comment:
    

    {l Code}: {l Select All Code}

    /*! \brief A thread function which runs on the server and listens for new connections from clients.
 *
 * A single instance of this thread is spawned by running the "host" command
 * from the in-game console.  The thread then binds annd listens on the
 * specified port and when clients connect a new socket, and a
 * clientHandlerThread are spawned to handle communications with that client.
 * This function currently has no way of breaking out of its primary loop, so
 * once it is started it never exits until the program is closed.
 */

• serverNotificationThread - serverNotificationProcessor() in Server.cpp
  
  • Started from: startServer() in Functions.cpp
  • Handles: Sending events (serverNotifications) to clients
  • Blocks with sem_wait() while waiting for a new item to appear in the queue.
  • Function comment:
    

    {l Code}: {l Select All Code}

    /*! \brief The thread which monitors the serverNotificationQueue for new events and informs the clients about them.
 *
 * This thread runs on the server and acts as a "consumer" on the
 * serverNotificationQueue.  It takes an event out of the queue, determines
 * which clients need to be informed about that particular event, and
 * dispacthes TCP packets to inform the clients about the new information.
 */

• creatureThread - creatureAIThread() in Server.cpp
  
  • Started from: startServer() in Functions.cpp
  • Handles: Incrementing turn, running the game logic.
  • Runs untill ODFrameListener::getThreadStopRequested() returns true.
  • Function comment:
    

    {l Code}: {l Select All Code}

    /*! \brief The thread which decides what creatures will do and carries out their actions.
 *
 * Creature AI is currently done only on an individual basis.  The creatures
 * are looped over, calling each one's doTurn method in succession.  The
 * doTurn method is responsible for deciding what action is taken by the
 * creature in the upcoming turn.  Once a course of action has been decided
 * upon the doTurn method also moves the creature, sets its animation state,
 * adjusts the creature's HP, etc.
 *
 * Since the creature AI thread runs on the server, changes to the creature's
 * state must be communicated to the some or all clients (depending on fog of
 * war, etc).  This is accomplished by building a ServerNotification request
 * and placing it in the serverNotificationQueue.  Since the
 * serverNotificationProcessor will decide which clients should know about a
 * given event, we can simply generate a notification request for any state
 * change and dump it in the queue and not worry about which clients need to
 * know about it.
 */

• creatureDoTurnThread - GameMap::creatureDoTurnThread() -> GameMap::doCreatureTurns(); in GameMap.cpp
  
  • Started from: GameMap::doTurn() in GameMap.cpp (which is again called by creatureThread)
  • Handles: Spawns threads to do the creature AI.
  • Spawned and joined each turn.
  
  
• miscUpkeepThread - GameMap::miscUpkeepThread() -> GameMap::doMiscUpkeep(); in GameMap.cpp
  
  • Started from: GameMap::doTurn() in GameMap.cpp (which is again called by creatureThread)
  • Handles:
    
    • Checks if a seat has won,
    • runs upkeep on all activeObject objects in the map.
    • Handles kobold spawning
    • Clears empty rooms from the GameMap
    • Updates mana and gold totals
    • Increment tile counts
  • Spawned and joined each turn.
• creatureDoTurnHelperThread - GameMap::creatureDoTurnHelperThread() in GameMap.cpp
  
  • Started from: GameMap::doCreatureTurns() in GameMap.cpp (which is again called by creatureDoTurnThread)
  • Handles: Creature decisions, AI (calls Creature::doTurn) on all creatures)
  • One or more of these are spawned and joined each turn according to a parameter. (defaults to 1, according to a comment more will make it segfault currently).

[MCMic]

Great job, that should be on the wiki.

[svenskmand]

General idea
Here is my suggestion for a thread model, the basic idea is that the server keeps two game states the current and a new one which we will compute from the current. Then the new state can be computed in parallel by only reading the current game state and the updates/actions/movements performed by the players, that way there is no communication between all the threads (called Object Consumers) that compute the current game state, the game state is sent continuously to the clients when each piece of it is computed, the clients then discard their old state and use the new state.

How to store the game state
We will describe the game maps as a sequence of game objects in lexicographic order by the tiles the objects are on. So if a tile has a room, trap, trigger, door or creature on it, this will come right after the tile it is stored on in the lexicographic order, this way we can store the game state as a stream. Now we will need to store this state: tiles (their x and y position in a infinite grid and their type), rooms (the type of room, and if it stores objects like beds gold, etc.), traps (the type of trap, hit points, etc., it also stores x,y values for other traps that it triggers), triggers (the type of trigger, its hit points, and the x,y values of the traps/triggers that it triggers), doors (its type, hit points), creatures (stats like type, level, hit points, etc).

How to compute the new state from the current
To compute the new state we have a thread safe deque of game objects (tiles, rooms, traps, triggers, doors and creatures) which we want to compute a new state for. Then we have a thread (Object Consumers) for each cpu/core which then takes a object from the deque and computes its new state from it and the other objects old state. Now when all the objects have been processed they have their new state. This state, i.e. the gamemap can then be sent to the clients continously by sending each object to all clients once it has gotten its new state computed, the clients can then render (video and audio) the new state and receive input from the player. Then this input is sent to the server which then again updates the game map and sent it back to the clients, and so it continues.

Diagrams
I have attached two sequence diagrams, on for the initial thread initialization and one for the repeating loop of receiving player input from the clients, updating the game map and sending it back to the players.

[svenskmand]

I updated my last post to include, another deque for the processed objects. Each ClientConnection on the server can then run through this deque and send the elements to the clients, while the ObjectConsumers produce the elements that goes into this deque.

[oln]

I have been thinking quite a bit about the new thread model (Hopefully I have understood the idea correctly). As there are quite a lot of objects that does not often change state, we should have some way of excluding areas where nothing is happening. Spatial indexing might be useful here. Another thing is objects that interact over a larger range, causing a large number of objects having to be checked. When writing this I realised that this could be solved by having all projectiles and similar be an object, such that only objects in the nearest squares has to be checked to find the new state. (Would have to handle the high speed in some smart way.)
In any case, from what I understand, there is a tradeoff between the number of objects that has to be checked, compared to being able to check several in parallel when comparing to a traditional single-threaded model. (Svenskmands idea is sort of doing checks the opposite way of what's normal if this makes sense.) The current model has some parrallelisation, but there is a lot of locks in place which does have an impact. Additionally, most objects won't consume much cpu-time, so the scalability should give a noticeable effect when there are several cores available.
The game-state switching should also be solved in a smart way. Ideally, we don't want to construct many new objects at each frame. This could probably mostly be solved by object/memory pooling. Switching states could also be done in parallel to some extent.
Another benefit of svenskmands model, is that it should make it very easy to record games, as a result of everything being a stream.

[svenskmand]

The object creation will not be a problem as each and every object has its state two times, i.e. two copies, the current and the obsolete old one, that is currently being overwritten by the new state. So to compute the new state no new objects need to be made, unless of course something spawns in the game, like creatures in a portal, or projectiles. But existing objects will not have to be created again for the new state, they simply get their new state set and then when this has been done for all objects their old state is obsolete and can be overwritten in the next state update and so on and so forth.

Also since everything happens on a two-dimensional grid, then the visibility calculates you talk about would easily save us allot of work as each processor has easy access to the surrounding objects of the object, who's state the processor is computing on now.