Trosnoth Development Priority: Simple Server Deployment

Earlier this year, a volunteer on Übertweak tried to use Trosnoth on camp, but couldn’t work out how to run and configure a Trosnoth server. In the current version of Trosnoth, the server is not shipped in any easy-to-use bundle; instead, you must run the Trosnoth server from the source code. This effectively means that you need an expert present to run a Trosnoth server. If the person on camp with the motivation to run Trosnoth does not have the required expertise, it doesn’t work.

I consider this to be a major failure in Trosnoth. Trosnoth was created many years ago for use on Übertweak. If it can’t be easily used on camp, this is a problem.

Over the weekend, we released Trosnoth 1.13.0. This was a huge milestone, incorporating many months of work and completely overhauling some Trosnoth internals.

In January, I listed some upcoming Trosnoth development priorities, and said that I hadn’t yet decided on the importance of each priority. That has now changed. Now that version 1.13.0 is released, all other development priorities are on hold until we’ve fixed this shortcoming. The aim of the next release is to make it really easy to install, configure and run your own Trosnoth server, so that people can play Trosnoth at LANs or on camps without any specific technical knowledge.

Posted in short | Tagged , , | Leave a comment

Trosnoth in 2018 and Beyond

The past year has been a good year for Trosnoth. Over this time, we have:

  • migrated Trosnoth to Python 3
  • made several UI improvements, including adding indicator lights around orbs, showing the short names of friendly players on the minimap, and adding a respawn gauge to all ghosts
  • adjusted the costs of items based on observed usage
  • added a way for players to select their preferred scenario for the next match, along with a bunch of new scenarios including Elephant King, Orb Chase and Cat Among Pigeons
  • updated the server to keep track of some statistics across multiple matches in a tournament
  • made huge improvements to the momentum-based physics that was released in late 2017: we overhauled the collision detection to use separating axis theorem which eliminates the possibility of falling through walls; we also made improvements to how grappling hook works (these are yet to be released)
  • as part of the grappling hook changes, given players the ability to hold on to roof surfaces, and shoot while holding onto walls and roof
  • made bots feel a bit more fair—they have a short simulated reaction time, but they’re still a challenge to defeat
  • fixed a bunch of bugs
  • made other minor changes and improvements in response to player feedback
  • made fair progress towards bots using the updated momentum-based physics

Trosnoth League

In 2018 a small number of players formed a Trosnoth League. Once a month we scheduled time to play Trosnoth competitively online. The internet causes some frustrations that aren’t experienced on a LAN (chiefly of the, ‘I hit you on my screen!’ variety). But our experiences showed us that internet Trosnoth is still a lot of fun!

One of the fun things we did during Trosnoth League was to play Human vs. Machines matches. These matches were often very tense matches. Over the course of the year, 8 HvM matches were won by the humans, compared to 6 won by machines.

Trosnoth League also provided regular opportunity for player feedback—we often played with an alpha or beta Trosnoth version and solicited feedback. This resulted in us fixing a number of minor annoyances for players, and adding a number of low-effort medium-payoff features to the game. For instance, we added a visual indicator for ninjas to see how close they can get to enemy orbs before being seen, and we made it possible to remap the right mouse button (previously only keyboard keys could be remapped).

If you’re interested in joining in Trosnoth League in 2019, please fill out this survey, and also send an email to the trosnoth-players Google group to ask us how to join in.

Project Participation

In 2017, three people contributed code to Trosnoth. In 2018, there was only me. This 67% drop isn’t a concern in itself, but it does serve to illustrate how the project operates at the moment: I’m the main code contributor, and other contributors offer a bit of code every so often as they’re motivated an able. Maybe this is ok for a working game like Trosnoth, but I’d still love more regular contributors. We’ve actually never been great at attracting new coders to Trosnoth. Almost all of the occasional contributors were contributors 8 to 10 years ago when the project was still getting off the ground. If you’re a coder and you’re interested in helping out with Trosnoth, please get in touch! I’ll be as helpful and encouraging as I can!

The previous paragraph may sound like doom and gloom, but having no new coders doesn’t mean I’m the only one involved in the project. Trosnoth League has been a great source of ideas and suggestions, and has also resulted in one or two people contributing to future artwork and design of Trosnoth, which I find exciting! And there are still 5–10 people who help me decide on project priorities when I do spend time on Trosnoth.

I always welcome new contributors to Trosnoth, but right at the moment we don’t have any regular contributors with particular expertise in game graphics, and it would also be really cool to have someone who could put together video tutorials or a Let’s Play. Please get in touch if you’d like to be involved! You can connect with us on the trosnoth-dev Google Group.

Trosnoth repository history over the past 5 years (number of commits)

Releases and Artist in Residence Grant

2018 saw three Trosnoth releases in January, April and May. This means that there has been no new release in over six months. The man thing that’s been holding up the release of Trosnoth 1.13.0 is the bot pathfinding: I’d like the bots and humans to be using the same physics, but that can’t happen until the pathfinding is working. I keep thinking that I’ve almost finished updating the pathfinding code only to find that there’s more to do.

One huge motivator to work on the bot pathfinding was when I was named as the Pygame Artist in Residence in October. During October I wrote a bunch of Trosnoth-related blog posts, but I also spent significant time working on bot pathfinding. (I did a time-lapse video of my work too!)

The Artist in Residence program also came with a small grant of money. I spent some of it obtaining a Windows code signing certificate and related hardware, so future releases of Trosnoth should actually be signed!

What Next: Server Deployment, New Levels, Chrome, and Synchronisation

Once I finally finish the bot path-finding, there are a few different ideas that I’d like to work on. I haven’t yet prioritised these, so I can’t tell you which one is coming soon. But here are four things somewhere in the pipeline at present:

  1. Simpler server deployment: I want to make it really easy to install, configure and run your own Trosnoth server, so that people can play Trosnoth at LANs even without specific technical knowledge.
  2. New levels: And not just new levels, but a restructure of how levels work so that there are coherent rooms such as a control centre, cargo bay, living quarters, recreation areas, and so on.
  3. HTML and CSS UI elements: I’d like to experiment with using Chromium Embedded Framework for some Trosnoth UI elements. This wouldn’t be used to render the game itself, but for menus and some parts of the heads-up display. One potential advantage of this approach is that it allows people who know HTML and CSS to tweak the UI without forcing them to learn how Python and pygame work. This also might simplify things if we ever move to using Panda3D for rendering: the HTML/CSS parts wouldn’t need to be rewritten to make the shift.
  4. Speed/smoothness/synchronisation improvements: At the moment Trosnoth has a very workable process for synchronising the game state between the server and clients. But I’d like to generalise what Trosnoth does into a separate library. This will allow for more automated testing of the synchronisation code, and more consistency and robustness. This will also make it easier to reason about the code when making improvements to how the game handles internet latency smoothly.

With the current level of time I spend on Trosnoth, I don’t expect to complete more than one (or at most two) of these four things in 2019, but that gives you an idea of where things are heading at the moment.


Posted in long | Tagged , , , , , | Comments Off on Trosnoth in 2018 and Beyond

Timelapse Trosnoth Development Video

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!

 

Posted in short | Tagged , , , , , , , , | Comments Off on Timelapse Trosnoth Development Video

Platformer Physics and Trosnoth

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.

Intro to platformer physics

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.

How Trosnoth calculates collisions

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.

Step 1: is the player on the ground?

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.

Side note: one-way platforms

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.

Step 2: jumping and dropping

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

Step 3: acceleration

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:

Moving along the ground

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.

Moving through the air

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.

Step 4: grappling hook

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.

Step 5: actually applying the velocity

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.

Step 6: adhering to the ground

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.

Step 7: discretisation

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.


Notes

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.

 

Posted in long | Tagged , , , , | Comments Off on Platformer Physics and Trosnoth

Path-finding in a Tiled Trosnoth Map

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.

Dreaming of robots

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.

Bots fighting each other in pybotwar arena

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.

Troubles with robots

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.

Factor 1: Infinite search space

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.

Factor 2: Physics calculations are slow

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.

Picture of 2 Trosnoth bots showing path-finding debugging information

These bots know where they’re going and how to get there.

Factor 3: Dynamic map generation

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.

The result

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.

What I’m working on now

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.


Notes

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.

Posted in long | Tagged , , , , , , | Comments Off on Path-finding in a Tiled Trosnoth Map