Sometimes an artist in residence program has a closing exhibition. In October 2018 I was pygame.org’s virtual artist in residence. As a kind of closing exhibition for this artist residency, I’ve put together a time-lapse video of most of my Trosnoth development during October.
If you want to actually be able to read any of the text on the screen you’ll probably need to watch it in 1080p.
Enjoy!
Reminder: in October 2018, I’m pygame.org’s artist in residence. You can ask me questions about Trosnoth, support me in my Trosnoth development, and follow this blog for articles about Trosnoth and what I’m working on.
Trosnoth is essentially a platform game. Sure, it’s not a traditional, one-player platform game where the main goal is to avoid obstacles and get to the end of the level. But it’s still a 2D side-view side-scroller with platforms and obstacles, so it counts as a platformer in my books.
Platform games have unusual physics. You might think, ‘Can’t you just use real-world physics with maybe a lower gravitational constant?’ But the answer is a resounding, ‘No’. As it turns out, it’s really hard to jump with agility between platforms or dodge bullets in mid-air in real life. The main aim of platformer physics is to feel responsive, not to be realistic.
In this article, I’ll briefly outline the steps in Trosnoth’s player physics calculations. I’ll go into some detail, but because October is nearly over and I said I’d write four blog articles this month, I’ll gloss over a few of the finer details.
An important part of game physics is calculating collisions between solid things. In the case of player movement, the important collisions to detect are between players and obstacles (walls, roofs, platforms and floors). Some games store the map as a grid of tiles, but Trosnoth’s approach is to store obstacles as polygons. Each player has an elliptical collision solid, and we calculate collisions using separating axis theorem.1
You may not think you needed to know that, but the following outline assumes you already know we’re using polygons instead of tiles.
The first step in Trosnoth’s physics calculations is to work out if the player is touching the ground. Trosnoth’s approach is to ask, ‘If the player moved downwards by a very small amount, would it hit something?’ If the answer is yes, then the player is on the ground.
Trosnoth’s approach to one-way platforms is this: if the player is pressing the down key, then one-way platforms are completely intangible to that player. So if the player would otherwise be standing on a one-way platform, but they are holding the down key, then that player is not considered to be on the ground.
The second step is to check if the player is trying to jump, or to drop from a wall or roof. These checks only apply if the player is on the ground or is hanging from a wall or roof. Dropping is quite straightforward: if the player is pressing the down key, or whichever of the left or right keys which would move the player away from the wall or roof, then the player drops.
Jumping is slightly more involved. If the player is allowed to jump and is pressing the jump key, then their vertical velocity is set to a fixed upward value. That’s the straightforward bit. But we also have two short timers that apply to jumping.
Firstly, there’s a brief window of time after a player has dropped from a roof or wall during which they are still allowed to initiate a jump. This window exists to account for cases where a player is hanging onto a wall and tries to press sideways and jump, but actually presses the sideways key just before the jump key. Without this window, the player would fall from the wall, then because they are in the air the jump key would do nothing. But this window makes the game behave as if they pressed the keys together.
Secondly, during the first few hundred milliseconds of a jump, the vertical velocity stays at a constant upward velocity unless the player releases the jump key first. This allows the player to jump to different heights depending on how long they hold the jump key for. In addition to this, when the player releases the jump key while they’re still moving upwards, their vertical velocity is set to zero. This makes the jump movement feel slightly more responsive: you let go of the jump key, and you immediately stop jumping.
Screenshot from Cosmo’s Cosmic Adventure. Source: Wikipedia
Trosnoth originally had very retro physics. Think Commander Keen or Cosmo’s Cosmic Adventure. If you were holding down the left or right keys, you moved left or right at a constant horizontal speed. More recently though, we’ve added momentum-based physics to the development branch. Here’s how it works:
Firstly, if a player grabs onto a wall or roof, their velocity is instantly set to zero. Apart from this, there are two possibilities:
If a player is on the ground, they’re either running, walking or slowing. They’re running if they’re holding down the left or right key and facing in the same direction. They’re walking if they’re holding down the left or right key and facing in the opposite direction. If they’re not holding the left or right key, the player is slowing.
When a player starts running, they have their velocity in the direction of the ground surface set to a particular minimum run speed. They then accelerate at a constant rate up to a maximum run speed. When a player is walking, they decelerate at a constant rate down to a minimum walk speed. When a player is slowing, they decelerate at the same rate, but decelerate all the way to zero.
If a player is in the air, their acceleration is determined by whether they are pressing the left or right arrow keys. But if the player is travelling faster than a certain horizontal velocity, pressing the arrow key will not accelerate them any more in the direction they are travelling. But this is not a horizontal terminal velocity: if a player is already travelling faster than that speed (e.g., after speeding themselves up with the grappling hook) then they will not automatically have their horizontal velocity capped to that value.
After horizontal acceleration is applied, gravity is applied. This is just a constant vertical acceleration, capped at a vertical terminal velocity. If the player is moving along the ground, gravity is only applied if their grappling hook is attached somewhere.
After we’ve worked out what the player’s velocity should be, we constrain that velocity to certain limits if the grappling hook is attached. In this step we basically work out how much rope is left and ensure that the player’s motion doesn’t exceed the length of the rope during this iteration.
Trosnoth’s grappling hook pulls the player in at a constant minimum rate. The player can move in more quickly than the minimum, e.g. by jumping or running towards the point where the hook is attached.
If the player’s velocity is pulling them away from the grappling hook’s pull by more than a certain amount, then the grappling hook snaps and the player is released. This check was added to make it easier to use the grappling hook to swing horizontally without having all of the player’s momentum lost by the pull of the grappling hook.
At this point, the player’s velocity has been calculated. The player’s motion for this iteration is then calculated by multiplying this velocity by the time interval, then we check if they would hit an obstacle. If so, we check if this collision qualifies as grabbing a wall.
To grab a wall, a player either needs to be pulling themselves in by grappling hook and be almost all the way in, or the collision needs to be with a vertical wall and the player needs to be pressing the direction key that would push them further into the wall. If the player has grabbed a wall, then that’s the end of their motion.
If the player has collided with an obstacle but the collision occurred within only a very tiny distance of the player’s original position, then we rerun the calculation once, but only consider the component of the player’s velocity that runs along the surface of the obstacle they collided with. We do this recalculation to avoid cases where a player is at the corner of two obstacles and we detect the wrong collision first.
If the player does collide with an obstacle and it doesn’t qualify as grabbing a wall, then we damp the component of the player’s velocity that is normal to the obstacle.
If the player started this iteration on the ground, we check if projecting a ray downwards a certain distance from the player would still collide with the ground. If so, we move the player down to on top of the ground. This is to avoid the player leaving the ground (and thereby being unable to jump) with every little bump or corner on the ground.
As a final step, if the player is holding onto a wall or roof, or they are on the ground and completely still, we look up their rough position in a database of possible stationary positions, and move them to the position in the database. This is not at all necessary for human players, but as I wrote about last week, it’s very helpful to simplify the search space for bot path-finding. And since Trosnoth aims to be scrupulously fair, we do this for human players as well as bots.
1 We calculate collisions mostly using separating axis theorem. We use slightly different calculations for one-way platforms because they aren’t complete solid polygons.
Reminder: in October 2018, I’m pygame.org’s artist in residence. You can ask me questions about Trosnoth, support me in my Trosnoth development, and follow this blog for articles about Trosnoth and what I’m working on.
Trosnoth was designed primarily as a multiplayer team game. The first playable version of Trosnoth had no computer-controlled players and nobody cared one whit.
But even in the early days of Trosnoth I remembered writing robots in C with PCRobots, and dreamt that perhaps one day we could use Trosnoth as an arena in which programmers could pit their bots against one another.
I couldn’t find any screenshots of PCRobots, but pybotwar is a modern variation on the same theme.
It turned out this dream wasn’t hard to realise. One year on Übertweak we ran an elective where camp attendees could program Trosnoth bots using the same kinds of controls that human players have: press jump key, release jump key, aim this way, pull trigger, and so on. The elective went fairly well; people coded robots that were able to kill other robots and often even kill human-controlled combatants.
But I wanted more. I wanted Trosnoth bots that could play a competitive game of Trosnoth. Bots that would capture territory, work together, and make decisions about when to attack and when to defend. In the end we achieved this, but it turned out to be a difficult endeavour.
The most difficult part of programming a competitive Trosnoth bot was path-finding. In order to capture territory, a bot needs to be able to move from its current location to the centre of the zone it wants to capture. But between those two points are all manner of obstacles and ledges. When should the bot jump? When should it release the jump key? And which way should it try to go to get around that big block in its way? These are the sorts of questions the bot needs to be taught to answer.
Now to a developer this may sound like a simple search problem: just use A* to find the shortest path and Bob’s your uncle. But there are three factors which make this more complicated for Trosnoth.
Trosnoth obstacles and ledges are vector-based not tile-based, and Trosnoth physics calculations use floating point arithmetic. This means that there are practically infinite possible ways that a bot could get between two points on a Trosnoth map. Using A* with a naïve heuristic such as euclidian distance doesn’t work so well in this case: the search would need to perform a vast number of physics calculations as it explores possibilities. In practice this kind of search can run four hours and still not arrive at the best route.
We obviously needed to reduce the number of possible paths a bot can take. So instead of calculating every possible combination of key presses at every possible instant, we simplified the problem: we started from a position where the bot is stationary, and defined a finite number of actions like ‘hold down the jump and left keys until you hit something’, or ‘drop down through the ledge you’re on then wait until you land’. This approach reduced the number of possibilities to consider, but the resulting search was still far too slow for a real-time game.
In a previous article I mentioned that Python has always been a fast enough language for Trosnoth. This is true when Trosnoth only needs to calculate one set of potential collisions per player per frame. But searching for the fastest path between points involves calculating many many sets of collisions. It involves simulating what would happen if the bot went this way or that way or did any number of other things. It involves calculating several orders of magnitude more sets of collisions than would normally happen every Trosnoth frame. Even if we’d written Trosnoth in highly optimised C, finding the path this way would be slow.
I can hear your objections. ‘Other games don’t seem to have any trouble with path-finding! And Google maps gives me directions almost instantly. It can’t be that hard!’
There are a few things going on here. Firstly, path-finding in top-down games is a somewhat easier problem. In any given room in a top-down game, the shortest path between two points is a straight line. So for these games the problem is reduced to finding the best path between rooms. But secondly, even in complicated situations like a road network, search engines such as Google maps do most of the hard work before you even tell it where you’re going to and from. Google precalculates information that will help it make rapid decisions about best routes.
So we took this approach with Trosnoth. The precalculation phase involves doing a whole load of physics calculations and storing them in a database. We only need to do this once, and the resulting database can be shipped with a distribution of Trosnoth. During a game, the bot path-finding algorithm can then look up where it would end up if it took a certain action. (Doing this necessarily involved discretising possible bot positions so that the database didn’t have to be infinitely large.) The precalculation phase also includes precalculating some heuristic information about certain points to reduce the number of options that need to be examined to find the best route1. However, in Trosnoth’s case, there was a limit to the amount of precalculation we could do.
These bots know where they’re going and how to get there.
Trosnoth maps are put together randomly, like a jigsaw puzzle2. You tell the game what size map you want, and the game follows an algorithm to piece map segments together into a complete map. This obviously limits the amount of precalculation that can be done. We could precalculate possible bot movements within a given jigsaw piece, but not across the map as a whole.
We did two things to overcome this challenge. Firstly, we precalculated possible bot movements between adjacent jigsaw pieces for every valid pair of adjacent pieces. This allowed Trosnoth bots to reliably predict where a given action would take it even when crossing segment boundaries. There are a lot of possible pairs, but it’s still a finite number so it was feasible.
Secondly, we calculated big-picture transition data for each jigsaw piece. For instance, we store information like, ‘it takes at least 37 frames to get all the way across this map segment from east to west’. This allows Trosnoth bots to make big-picture decisions about how to traverse a map before getting into the specific details. The resulting routes chosen are not necessarily the absolute fastest but they’re pretty good, and they’re quick to calculate.
In January 2016 we released Trosnoth 1.8.0 which had a practise mode with bots which could actually find their way around the map and capture zones. Not only could they capture zones, but they were quite competitive.
Of course skilled players could still beat these bots. So we gave the bots the ability to notice and avoid enemy bullets as they found their way around the map. The resulting bot was so challenging that the change log for Trosnoth 1.9.0, released in January 2017, includes the item: ‘Made the default bots easier to defeat.’
Trosnoth 1.9.0 also came with a humans vs. machines game setting. It works just the way it sounds: a team of humans can pit their skills against a team of bots. In recent games the bots seem relatively evenly balanced against a team of experienced Trosnoth players3.
We’ve had highly competitive Trosnoth bots for over 18 months now, yet I’m once again working on the bot path-finding code. Why is that?
Trosnoth has always had a retro feel to its physics: if you hold the left arrow, you move left at a constant x-velocity4. But in the development branch of Trosnoth, we’ve changed the physics to be momentum-based. This is lots of fun to play, but it breaks some of the assumptions that the previous pathfinding code used. We’ve also updated the way collision detection works, which breaks some other assumptions.
At present we get around this by keeping both the old and the new physics systems around: human players get new physics and bots get old physics. But this violates Trosnoth’s foundational principle of scrupulous fairness. So I’m currently working on reimplementing the bot path-finding code and making it less tightly coupled to the physics engine. The aim is to have highly competitive bots that move with momentum. They will be nigh unstoppable!
And that’s the deal with Trosnoth bots for now. Don’t forget to watch out for the final article in this series coming later this month.
1 When I was working out how to do this I read numerous academic papers on path-finding. There are so many interesting and ingenious path-finding shortcuts that I’d like to write more about this some time.
2 Perhaps you don’t put your jigsaw puzzles together randomly. Trosnoth does.
3 I’m of the firm opinion that if a team of humans trained together regularly and played with consistently good teamwork and communication they could defeat the bots every time. I welcome anyone who would like to put this opinion to the test.
4 Unless you’re facing backwards, in which case you move left at a slower, but still constant, x-velocity. Obviously.
Reminder: in October 2018, I’m pygame.org’s artist in residence. You can ask me questions about Trosnoth, support me in my Trosnoth development, join in online alpha testing, and follow this blog for articles about Trosnoth and what I’m working on.
In my previous article, I wrote about what makes Trosnoth Trosnoth. But what powers Trosnoth, and why did we choose those building blocks? In this article I’ll try to answer that question.
A python.
Trosnoth is a pure Python project. We do use third-party libraries that include binary components. But all of the source code of Trosnoth itself is in Python1. The Python programming language is widely used in scientific computing, education, web services and even embedded computing. And according to the 2018 Stack Overflow survey it’s the 4th most popular programming language2 after JavaScript, Java and shell script. But why choose it for a game?
In years gone by, people used to ask me, ‘Isn’t Python too slow for a game?’ Those were the days when people thought real games should be written in C or C++. But these days many games are written in interpreted languages like Java, C#, or JavaScript. So choosing Python no longer seems quite as weird. Even so, I think it’s worth pointing out that Python was never too slow to run Trosnoth. Thanks to pygame, all the graphics calculations are done by SDL. CPython3 has always been more than capable of keeping up with everything else we need to do, so we never needed to seriously consider speeding things up with PyPy or Cython.
There are three main reasons why Python was an appealing option when we started the Trosnoth project. Firstly, it’s easy to learn. We wanted to make it easy for new programmers to contribute to Trosnoth—or even to learn programming by hacking Trosnoth. Any language that was difficult to learn would make it harder from Trosnoth to be helpful for new programmers.
Secondly, Python allows rapid development. In my experience good developers can do things with Python to the same level of quality in much less time than with many other languages. (Though I do think the difference between languages by this measure has lessened somewhat over the years with the availability of free IDEs containing high quality tools.) This advantage is of great help to an open source project like Trosnoth because developers are usually writing code in their spare time. A developer doesn’t want to spend 50% of their time writing boilerplate code when they only have limited time to spend on Trosnoth.
Thirdly, Python makes it easy to write maintainable code. This is a benefit to any software project, but particularly one where developers are strapped for time. Hunting bugs is much harder when it takes several hours to understand what the code in question was trying to do in the first place.
Trosnoth runs on a Twisted main loop. That means that it uses a funny thing called cooperative multitasking. I’ve explained this in two different conference talks in the past but many developers are at least somewhat familiar with the concept from JavaScript: you start a task running (say, an AJAX request), then you provide a callback function that should be run when the task completes. In modern JavaScript, you can accomplish this by defining an async function and calling await on the task/promise. This is all cooperative multitasking because it’s the programmer, not the operating system, that decides when one task should pass control to another.
When compared with shared-memory thread-based multitasking, cooperative multitasking eliminates a whole class of synchronisation bugs. Since Trosnoth aims to be welcoming to new programmers this seemed like a good idea. Back in the days of Python 2, you needed a third-party library in order to do cooperative multitasking. Twisted was one of the prominent options, and one of our original contributors had lots of experience using Twisted. So it was an obvious choice to make.
Some twisted things.
These days, Python has built-in primitives for cooperative multitasking: async def, await, async for etc.. It also has asyncio in the standard library. If we’d started the Trosnoth project today, perhaps we would not have chosen to use Twisted. Having said that, Twisted also provides a whole raft of network protocols straight out of the box, which have proven useful at times. For instance, we can run a network-bound interactive Python REPL in a Trosnoth process using Twisted’s manhole module.
Trosnoth uses pygame for its graphics and audio. When we started working on Trosnoth, pygame and pyglet were the two main contenders for 2D Python audiovisual libraries. Pyglet was relatively young and had only a small community around it. Pygame was mature and had a large community. We chose the safe option and went with pygame. Even though development on pygame stalled from 2009 until late 2016, it continued to serve our needs.
During recent years we’ve toyed with the idea of moving Trosnoth to 2.5D graphics. That is, using a 3D game engine but keeping the gameplay all in a single 2D plane. To this end, we experimented with Panda3D. We even had a working (feature-incomplete) prototype that used the same network protocol and backend code but used Panda3D for the front-end. But sadly, when we updated our codebase to Python 3, the prototype broke. The development version of Panda3D, version 1.10, does support Python 3, but the latest stable release at time of writing does not. Until Panda3D 1.10 is released, any experimenting on this front has stalled.
The Trosnoth server has a web interface, mostly for displaying statistics from past games. When we first set up the web interface we just used twisted.web. (Yes of course Twisted comes with HTTP support built in!) But twisted.web is very rudimentary and the more information we wanted to display on the interface the more it made sense to move to a more complete web framework.
Django is a widely used and mature web framework so it was an obvious candidate: we wanted to be friendly to new programmers, and Django has lots of documentation and a supportive community. There was just one hassle: some elements of the web interface could interact with a running game. This meant that if we used Django we’d need to establish some communication between the web service and the game server. Or… we could run Django inside a Twisted main loop. This last idea sounds like it would never work. But I read a blog post explaining that actually it works pretty well, if you write code that plays nicely. Doing things this way actually made the transition to Django fairly simple. But talking about it does earn me looks of horrified admiration from certain other Python developers. (These days we actually run the web server in a separate process from the main game server, but there’s still some Twisted-y things going on in the web server.)
…well that’s what Trosnoth’s built on anyway. There are some other very interesting technical details in how Trosnoth itself works: like where we hide network lag and how bots navigate the map. But those are stories for another day.
Keep an eye out for more articles about Trosnoth here on this blog throughout October.
1 Yes, we also have HTML, CSS and JavaScript in the web interface of the Trosnoth server. But I don’t feel this invalidates my assertion.
2 If you followed the link, I’m sure you saw what I did there.
3 CPython is the reference implementation of the Python language, available from python.org.
Reminder: in October 2018, I’m pygame.org’s artist in residence. You can ask me questions about Trosnoth, support me in my Trosnoth development, join in online alpha testing, and follow this blog for articles about Trosnoth and what I’m working on.
There are so many video games out there—it’s easy to come by reasonably priced, high quality indie games in today’s market. Sure, there weren’t so many indie games back in 2006 when we started the Trosnoth project. But even so, why another game? In this article I’ll talk about why we started the Trosnoth project and a few of the things that make Trosnoth Trosnoth.
The Trosnoth project was dreamed up in a community. It was the spring of 20061 and a group of us had just finished running a fun but exhausting Christian technology camp. We were debriefing the events of camp and someone said, ‘We’ve played the same old video games on camp for years and years.’
Someone else replied, ‘Yes, but it’s really expensive to buy licenses for 60 people to all play a recent game.’
‘And we need a game that parents won’t object to their kids playing,’ interjected another person.
‘And we like our gaming sessions to teach people teamwork and strategy.’
It was at this point that I spoke up. ‘We have this argument every camp, and we still keep playing the same old games. But I’ve been thinking… since we have in this room people with many different skills in technology, couldn’t we make our own game?’
The idea intrigued everyone. A dozen people signed up to help in various ways. And so the Trosnoth project was born. We brainstormed ideas and game rules on a wiki, and finally nutted out the game in enough detail that we could start working on it.
Many of the original contributors are no longer regularly involved, because one can’t be a university student forever2. But the project continues to be integrally tied to community. When we’re considering big changes, past contributors still chip in with their ideas. And our release cycle includes getting user feedback by play-testing, sometimes online and sometimes on the very camp we originally created Trosnoth for.
Humans vs. Machines Trosnoth match, June 2018
The fact that Trosnoth was grown in community has heavily influenced the game’s design. For instance, we encourage teamwork on camp, so we developed a game that would reward teamwork. When we made design decisions for Trosnoth we kept this in mind, and the result was a game in which communication and teamwork are essential. That’s not to say that skill means nothing in Trosnoth. It helps to be good at aiming, dodging bullets, and quickly getting around the map. But if you’re playing against a team which coordinates its attacks and communicates well, your individual skill will mean very little.
This need for teamwork is mostly enforced by one game mechanic: Trosnoth is a territory control game, but you cannot capture a region of the map unless your team has more living players in the region than the defending team3. In practice this means that an unskilled player can defend a region against one attacker by staying away from them and staying alive. I’ve seen this used to effectively remove the skilled attacker from the game for as long as that attacker spends unsuccessfully trying to kill the pesky defender. But if a team works together, all it takes is a second attacker and the region is captured.
(As a developer I often test features by playing Trosnoth on my own against bots. This has taught me the really bad habit of not communicating with my team. I’ve lost a number of matches with humans as a result.)
Because of our emphasis on teamwork, Trosnoth has a game mechanic where a team cannot control two completely separate areas of the game map. This means that if the opposing team somehow manages to split your team’s territory in half, your team only maintains ownership of the larger half. The smaller half becomes neutral.
As a result of this design decision, there is a huge pay-off in trying to split your enemy’s territory. Your enemy stands to lose up to half of the area they control. The trade-off is this: in order to split your enemy’s territory you always need to leave your team’s front line, which usually exposes your own territory to being split. There are times in any Trosnoth match where there’s only a very small chance of this actually paying off. But now and again there’s a better opportunity, and you have a fraction of a second to make a choice: is it worth the risk?
Situations like this often make Trosnoth matches very intense. When someone on your team takes a risk, things can turn around very quickly, for better or for worse.
I often compare Trosnoth to a team sport. Like a sport, a Trosnoth match requires two teams of equal size, and teams have to work together in order to achieve their goal. But even in a physical sport, there are usually uncontrollable factors: the wind is blowing in a certain direction, and the sun is shining in one goalie’s eyes. We designed Trosnoth to avoid this kind of thing as much as possible. If a team wins, they can’t blame it on unfair conditions. To this end, Trosnoth generates maps which are perfectly symmetrical, and avoids randomness wherever possible.
You could think of Trosnoth as a team sport with a referee who is undeniably free of any bias.
Trosnoth is open source. As a philosophy, this encourages innovation. People can pull apart the game and experiment with any modifications they can imagine.
We’ve used the game to teach Python programming on camps. We’ll set a challenge like adding an item to the game, or writing an algorithm for a computer-controlled player, then we’ll use the process to teach programming concepts.
Because of this, we strive to keep the Trosnoth source code readable and understandable. We’ve sometimes failed at this, but it’s still always our aim.
Of course there’s much more to Trosnoth than just these five factors. But I think these five things paint a good picture of what Trosnoth’s about. It’s fast-paced and risk-filled, but also fair and team-driven. And it’s all built in community.
Watch out for more Trosnoth-related blog articles throughout this month.
1 Spring runs from September to November of course.
2 I have met people, as I’m sure you have, who try to disprove the idea that one can’t be a university student forever. None of them have yet succeeded in arriving at the ‘forever’ part.
3 There’s an upper limit to the number of players you need, but it very rarely comes into play.
