Part 13 Multi threading and networking.

Graftgold Memories.

My first computer was a ZX80. I ordered the kit form as I wanted to learn all about microcomputers. I assembled it and it worked first time but I was a little disappointed as it was a bit more like doing a jigsaw and required no technical knowledge. It came with a circuit diagram so I went to the library which had a good section on microelectronics. I reverse engineered the circuit and disassembled the first part of the ROM code by hand. I wanted to know how the machine worked and in particular how it was getting graphics to the screen without the graphics chip that usually accompanied the Z80 processor. I wanted to understand why the screen went blank when the program ran. I wanted to program moving graphics so I needed a way to put stuff on the screen while the program was running.

I found out how it worked but a mate gave me a copy of a Space Invaders program that had already cracked the problem. You had to run a cycle of the game then allow a timed interrupt to display the graphics. I started programming an Asteroid game and managed to get an Asteroid flying about the screen. It was at this point the ZX81 adverts appeared and I realised the ZX80 would be obsolete. I gave up at this point until I saw the first ad. for the Spectrum. This time I thought I must get one straight away and program something quickly before the machine could be superceded. I was attracted to the spectrum as I had learnt Z80 machine code and liked the fact it had colours knowing this would be very good for games. 

Deepest Blue Progress

Networking The game.

I had worked on sockets client server systems at my last job so had a good background for this technical challenge.  I was also one of the first people to work on a linked game.  The Sega handheld version of Ivan Stewarts Off Road racer was given a link game feature. Sega told me others had not succeeded in making the link game work so asked for my communication code.

My previous Sockets systems all used tcp/ip which is a connected protocol. That is the machines establish a connection which is maintained throughout the communication session. Messages are delivered in sequence and resends are automatically sent if a packet gets lost on the network. Games require the fastest transmission possible so are better catered for by using UDP.  For this you just send you messages to the other computer and usually they will be received. The loss of a packet does not caus a wait for a resend but has to be catered for. So I needed to right a robust system that could cope with missing or out of order messages.

I remember the days of PC's with dual mode processing and serial ports. When the pc changed mode it could take ages and if a message was being received you could lose all or part of it. So the comms had to cater of loss of messages. That leaves a conundrum as how do you acknowledge a message or ask for a resend if you do not know that that message will be receieved. I used a system I called the ping pong system.  Two machines send messages alternately each responding to the others message. If a reply is received then it acts as an acknowledge and the processing moves on. If a reply is not received within a specified time the message is resent.   If a machine reecieves the same message twice it reacts by sending the same anser again assuming the other machine never received it. This system used to work even with a dropout of 25% of the messages.

So I searched  the internet to research the socket routines for UDP. I soon had the low level routines written. I decided to work these into my existing communication code so it supported both protocols. I added a protocol variable to the Stream object I used to control a connection. I had to make changes to the Stream object as normally it used its own private connection for a reply. For UDP you just write out to a port telling it the destination details so in effect it shares a write stream. 

I wrote a simple client and server testbed to send text messages between them. The main issues I had were with the flow through my existing communications routines.  I wanted the preserve the individual Stream objects to handle a clients messages and m,anage it rather like a virtual connection.

Multi Threading.

While researching UDP I read some articles about multi threading games to make use of multiple processors. I thought this might be handy to make the networking run as fast as possible. The basic problem is how to get the input data from each client  to the server then back  out to all clients as soon as possible.   For the fastest system you want the client to read and send as soon as it is time to read the keys. The server should respond as soon as it has the full set and the clients need to react to the receipt of this without any delay.   I thought threading woud allow me to wait for receive events and act immediately.  So I digressed from the Comms system and thought I would write a multi threaded system as part of my game engine.

I had programmed multi threaded systems some years ago and remembered the horrible situations that can arise. Its all too easy to get everything locking up with every thread waiting for another.

I decided to write a TaskManager object to start the threads and manage several thread pools that were deicated to different classes of tasks such as physics or graphics.  Each class has a TaskList that is used by the main thread to assign tasks the the worker threads. Its a well known consumer/provider pattern. It is best to use standard design patterns for any system you write. The problems you face have all been solved by someone before. 

I was writing in plain C so needed to swot up on threading functions.   There were two main threading issues to design for.

1. Two threads must not be able to update the same data at once. You cannot just use a variable that says "in use" with multi processors.  One processor may load the variable into a register while the other writes it. You need an "atomic"   I step operation.  I chose to use EnterCriticalSection, LeaveCritical section to achieve this. These atomically use a Task list variable I called "InUse"

to lock the relevant task list while taking their task.

2. You need a mechanism to wake a thread up as quickly as possible when there is something to do.

I thought I would use the number of tasks as the driver for this. When the number increased from zero  I used SetEvent to signal there was at least one task. When a thread took the last task reverting the count to zero it used ClearEvent to keep other tasks waiting. If more than one task wakes the EnterCritical system ensures only one looks at the task list at a time. The subsequent tasks may find the count of tasks zero and just do nt do anything.  A WaitForSingleHandle  call in the threads process loop makes each thread wait until there are tasks in the list.

I wrote a simple test bed to check this all worked. It included plenty of log messages so I could work out what was happening. It adds another dimension to debugging having two threads that communicate. I had a few issues  but it turned out to be a basic problem of indexing the threads private data rather than any of the complicated stuff. Programming is often like that. You do something really whizzy and it doesn't work because of a silly mistake in the trivial code.

Testing multithreading with 1000 ships.

Programming Tip

State Programming.

Games process each object  once every game cycle then display the graphics.  The code for each object in the game has to pick up from wherever it got up to in the previous game cycle.  An object's behaviour may go though several stages. For example a grounded plane may start its engines, taxi to the runway, brake, rev its engines , take off, wheels up and fly. Each stage may involve similar or completely different processing and may carry on for many cycles.

State processing treats each distinct stage as a separate state. I use a simple switch statement to switch on state to the processing relevant to that state.  I use an enum to list out the states and give each a meaningful name.

It us useful to have a count variable as part of the objects private variables. This can be used to control the time the processing stays at any state. It is also useful to have a loop variable allowing a series of several states to repeat.  You could have a LastState variable if you want to execute a set of states like a subroutine.

You can draw out a state diagram that shows how each state can change to a different state.  Note that usually only one state usually runs in any one game cycle.  Having said that I usually have some special states that just initialise things for the following state. I leave out the break statement with a comment "falling thru" and allow the initialisation and the initialised state to run in the same cycle.

The states can be thought of as steps in a workflow or higher level program.  Thus they can have the same familiar constructs as normal programming:

Sequence.  One state merely follows another  by setting the "State" variable to the next state the next cycles processing would begin at the next state.

Loop.   One or more states are executed repeatedly. The last state in the loop has to set the State for the first. (If there is just one state it just leaves the State unchanged.) 

Decision. Any State  can have a condition that changes the State to another. State systems often break the rules of structured programming and change to any other state. This is equivalent to Spaghetti code using GOTO statements and is best avoided for reliable systems unless States are autonomous having no dependence on each other.

So it is best to structure the states just as if they were statements in  structured programming language. Follow standard rules such as only enter a construct of several states from one entrance point (use an Initialise State to contain all the necessary initialise code). Exit or loop at the end of  the set of states in the loop.  Make sure that conditions  form  if /if-else  constructs.

At Graftgold we used a macro language to implement the above but I tend to use straight C nowadays. The macro language had the advantage that it was portable between machines and could be loaded at runtime.