Introduction
As a member of UCL AI Society's developer team (part of the committee), I've been looking into new and varied events that the society could offer. I was inspired by an induction event that professor Mark Handley ran for students on their first day of UCL. The idea was that the professor ran a server on their local computer running a multiplayer instance of pacman and then us students were provided some starter python code which handled the connection logic and let us write code in a single function to control the pacman. We were provided a limit view around ourselves so that we had to be strategic with our limited knowledge of the game board.
The induction event was really fun and a great ice breaker event and when I joined the AI society I realised that this would be the perfect event to run. It would hopefully bring together people who were interested in AI and expose them to the society. I realised that I would need to make some significant changes from Mark's original design:
- We expected up to around 20 people and having them all on the same game board would be chaos. So we needed support for putting people onto dynamically created game boards as they became full.
- Due to COVID this was a remote event. This meant that we couldn't just put up a projector with the game state on the server inside the room (we could screenshare but this would require that I run the server on my local computer which may be difficult with people remotely connecting to my internet). This meant I had to design a front-end UI with a Websocket server feeding the user's the state of the game.
- Since we wanted to run this event relatively soon I only had a few weeks to prepare (in between studies) - although I had been playing around with this idea for some time before the code was very limited and there was no server logic, it was only slightly better than starting from scratch. Due to these strict time requirements it was really important that in the event of a server crash (which was likely on the short notice) no-one's high score would be loss. This is why I synchronise the high score with a Postgresql database every single tick so that as soon as a crash happens the high score is saved. This also allowed me to use queries to find the top 10 players for the leaderboard very easily (I was considering using some kind of priority queue but it would risk becoming de-synchronised with the database and would require too much engineering work to be worth the optimisation).
- There needed to be authentication for the users. Since this event was entirely remote I didn't want people to spoof being someone else. The solution was to store a randomly generated code alongside a username and require them to be submitted as the first message in the TCP connection before the user was spawned.
Implementation
When I had previously done multiplayer games with a rust server, I had used actix-web. This works great for purely HTTP servers but what I was doing was far more complex. I needed both a Websocket server (for game UI and leaderboard) and a separate raw TCP socket server for interacting with the user's agents (AI bots programmed in the python scripts). With these requirements (as well as wanting an excuse to learn it) I chose to use tokio which is the lower level future library that hyper is built on which in turn is what actix-web is built on. I really loved getting into the gritty details with tokio and how it interacts with rust's polling futures.
I decided to use react and redux for the front-end since I'd done a lot of projects with them before.
I first implemented the game model which allowed me to call simple methods such as saying that a player wants to play a certain action and then the game will simulate all the logic within the tick. It would also let me view the game state each tick ready to send it to the clients. I created a GameManager that would accept new players automatically creating new game boards as needed and routing the actions to the correct board. I then created a TCP server that would accept incoming connections, authenticate them and then forward their commands to the game manager and handle the out going game state to each of the clients.
There was a lot of complicated state management involved here. Sockets were identified using sequential ids (with auto-filling lower ids when they became free due to a disconnection). I had to be very careful since when a connection is first initiated it is moved into an unauthenticated bucket and once authentication is received I have to wait for the game to spawn the player in and assign them a new ID and the move the connect to a new bucket. In between these states a disconnection might happen or a player may accidentally send two authentication messages (which could trigger spawning the player twice leading to an invalid state). All of these issues were largely mitigated by separating connections to different buckets and considering what was allowed to be multi-threaded and what wasn't, despite this there were still some complex bugs around disconnection that led to some issues that I had to fix.
Once it was possible to connect using a python script to the server and play your bot it was time to focus on the game UI. I used redux to manage the state of the application as it received messages from the websocket. It would then create as many Game components as necessary which would each render using a canvas the current game state. I also created a Leaderboard component to show the high scores of the best 10 players. Each game also had it's own leaderboard that showed the lives scores for each player.
When writing the server code to send the game state I was originally planning on simply using serde to derive the serialisation into JSON. I knew this wasn't a great solution but I thought that under the time constraints it would be fine but then I did some medium-worst case analysis on the bit rate required. I realised the with the string keys and the overhead that JSON adds it was going to be too large to be reliable. This is why I came up with a custom string encoding and a delta system to only send the changes from the last tick. I had originally budgeted around 100kb/s per user per game for medium-worst case but I ended up managing to get it under 1kb/s per user per game which I felt very happy about. There was a lot of complicated code to generated a list of deltas for each of the different events (e.g. entity_moved or food_spawned ) and it under covered a bug in the model. I knew that it was important that entities were simulated in a certain order so that when the AI would make a move it would be able to reliably know where the other entities in it's vision would be at the end of the tick and the delta code used the assumption that it was correct. It turned out the order was completely wrong in the model which was causing some difficult to debug issues in the UI and it took me a long time to realise the issue was with the model.
The end result was a great event with around 20 participants many of whom were very new to the society. We gave the winner a £20 gift voucher for Amazon. Most people who attended seemed to want another event like this to be run again which sparked a few ideas with the society so watch this space.
Source code
The code is available at https://github.com/louisdewar/pacman_tournament. It's poorly documented and some of the code is pretty rough but this was the consequence of the time constraint. The bulk of the interesting server code is inside the tournament folder.
Highlights
Fortunately I made some recordings during the event of the web view and I'll be adding them soon.
