Richard wanted to really go into detail about the problems and obstacles faced with the Mustering Fields implementation in the upcoming combat release.
Mustering Fields
"As Konrad mentioned in our last update, mustering fields are our solution to finding a stable spawning point for troops in the ever-changing world of Godus. In our initial implementation, troops would exit the citadel one-by-one and then get into formation at their spawn point. But how do we find a suitable spawn point?"
"The very nature of Godus makes computational geometry problems very challenging. Citadels are likely to be surrounded by lots of abodes, which means that it's difficult to find a large, empty space close by. As such, I decided to implement an algorithm that's been well-documented in acamedia to solve the largest empty sphere problem (although it's more like largest empty circle in our case, as we're only considering two dimensions)."
"The algorithm involves performing a Delaunay triangulation (computed using the Bowyer-Watson algorithm) – this provides the dual graph of a Voronoi diagram, which we can then use to find candidates for our spawning point. This implementation took me some time to pull together, but it did bring benefits. Over time, however, we started to feel that the algorithm alone couldn't quite bring us the level of robustness we wanted."
"Finding the largest empty space was great, but – again, as per the nature of Godus – it turns out that areas which are prime spaces for spawning warbands also happen to really attractive to builders looking to set-up their new home. It wasn't uncommon that we'd select a spawn point, only for an abode to be built on it before the troops could get there."
"Another problem was that, in the basic implementation of the algorithm, all obstacles (e.g. abodes, rocks) are considered as infinitely-small points. This is a fine assumption to make when all our obstacles are of roughly the same size. However, when some obstacles are much larger (for example, in the instance of citadels), this becomes highly problematic, as illustrated by the diagram."
"These challenges aren't insurmountable – I could have modified the algortihm to take account of these factors, but whenever we get to the stage that we realise that our existing solution is starting to look inappropriate for the task, we like to sit down and discuss if there's anything else we could do instead."
"Mustering fields seemed to be the answer. The player will still be able to set a rally point for their troops, but if that player elects not to or if that point becomes invalid, we know we've got an area which will always be free of obstacles and able to accommodate a war band."
"We also had some reservations about gameplay issues created by having troops spawn individually – for example, they were very easy to spawn camp if your enemy had a warband nearby."
"The settlement compression has been one of my very favourite aspects of Godus. Procedural stuff really interests me and I always found watching my abodes slide together to create a goliath settlement to be a really satisfying feeling."
"We decided that we wanted mustering fields to be an integral part of this settlement compression. Compared to the normal abodes which participate in settlement compression, the mustering fields have certain properties which mean that a lot of special rules had to be written specifically for them:"
- Mustering fields can only ever be on the ground floor.
- They can never have anything above them.
- They can never be used as the door to the settlement.
- They must be navigable to warbands.
- But they must not allow houses to be built on them (the concepts of navigability and eligbility for building are quite closely related).
- They must never be entirely surrounded by other elements of the settlement.
- They are not subdividable (other settlement elements, if they're too big to fit, will be broken down into several smaller elements – we can't do this for mustering fields).
"If you're a programmer reading this and you find yourself thinking “But that's easy – I know just how to do all that!”, you need to remember that it's not just a case of writing the functionality, but of making it work well within a very large codebase which represents several years of work and simply wasn't written with mustering fields in mind!"
"As things stand right now, we're getting closer to having a complete implementation and I'm really looking forward to when we're able to provide you with the first build of combat, so you can try it out for yourself."
