Shogun: Total War recently arrived on Steam, updated to fix issues with running it on modern systems. I purchased it. I had to. 

The Total War series of games have a reputation in the strategy gaming space for their bombastic, larger-than-life, but simultaneously grounded depiction of history. Mechanically, they mix sweeping turn-based strategy campaigning with real-time tactical battles between huge armies in a way which is rarely seen elsewhere, despite its great financial and critical success. Shogun was the first Total War. It's simplistic in comparison and might even seem crude next to its sequels, but to my mind it feels like a game with nothing missing, nothing much that could be improved upon beyond its badly-aged user-interface, and nothing to apologise for. A rare pure game. A rare complete game. It's confident, bold, and every Total War game since has lived in its long, dark ō-yoroi-clad shadow.

I don't really remember what age I was when I bought the Sold Out version of Shogun for a tenner from the GAME on Frederick Street in Edinburgh. Perhaps 8 or 9. (The shop isn't there anymore, but there's another just around the corner. Brick-and-mortar retail is rubbish for PC games these days anyway.) I played the shit out of it. My brother played the shit out of it. I sat over his shoulder and watched him play the shit out of it. Vice versa. It was a Good Time. It made a pretty deep impression in my mind, painting a land where honourable samurai fought in pitched battles, where ninja assassinated leaders while shinobi spied and tried to track them down. A beautiful land beset by brutal conflict. A real place and time, brought to life and made interactive. This game alone is probably a big part of why I started wanting to make games when I grew up, one of my formative games, I guess.

Point is, the second paragraph might just be nostalgia speaking. Then again, it might not be. Everything I said might actually be true. Finding out the reality is what this campaign diary is all about.

Shogun takes place in the Sengoku Jidai, or Warring States period of feudal Japanese history: a rough century-and-a-half of social upheaval and unending conflict beginning in the mid-1400s and ending around 1600AD. It's a time period which has become the backdrop for countless books, plays and films.

The game doesn't aim to be historically authentic. Instead, it takes the flavour of the history, the images it conjures in mind and feelings it generates, and pours them into the mould of a game. Stories are simplified or exploded. Ideas are picked up and run with as long as they create interesting gameplay and then, delicately, put back down. The impossibly complex graph of different factions, clans, families and individuals who vied for power and survival is boiled down to 7 playable clans which the player can take control of, who divide up the map of Japan into clear colours, leaving any remaining territory to unplayable grey-coloured rebels, ronin or Ikko-ikki. The player aims to lead their clan to power and become Shogun, the supreme military leader of Japan, by crushing their enemies underfoot and claiming control over all or most of the country.

I choose the Shimazu, who control provinces in Japan's southern island of Kyushu. Having only three neighbours and being mostly surrounded in water, their starting position is enviably defensible. They also get slightly cheaper swordsmen, and their capital province, Satsuma, has a little perk where swordsmen trained there are a bit better than those trained elsewhere, or at least begin their careers with a little bit more experience. I like swords, and although we won't get to deploy any katana wielders during the early campaign, I like to invest in the future. Also, they sport a rather striking green.

(And yes, that samurai on the left is holding an arquebus. Late-game tech in this game includes an array of gunpowder weaponry, and it's great because it's terrible.)

I control the south of Kyushu.

The Imagawa clan, an unremarkable turquoise people, control the northern territories. Needless to say, they're my first target.

I begin my campaign by trying to improve the provinces I already have while I build up more of an army. I construct watch towers in my border provinces; these act as spies into neighbouring provinces, letting me see the make up of enemy armies, and help to prevent enemy subterfuge within the province in which they're built. I also begin improving farmland, because I'll need the tax money that better farmland generates, because I'm already breaking the bank.

To make me feel even worse about my liberal spending, the game pops up a message to tell me that the Hojo clan are the most rich. Smug bastards.

In the winter of 1531 I figure I'm as ready as I'm going to be to begin a war with the Imagawa and move forces into the province of Chikuga. My daimyo (clan leader) commands an army attacking from the south, while another army invades from the east. They meet and prepare to cross the river.

And so we enter Shogun's battle mode. The Imagawa arrays itself on the other side of the river, and waits. My troops will have to cross the bridge under a hail of arrows, before charging into a wall of spears.

My own army is larger, which is good, because the only way I can hope to win is by the sheer volume of melee troops I charge across the bridge. Mine is a mixed force of bow samurai and wielders of yari (a long weapon analogous to a spear), who come in the form of well-trained samurai and troops recruited from the peasantry known as ashigaru. The samurai warriors have good morale and are better combatants than the ashigaru, but are more expensive to train and upkeep. My daimyo rides on horseback, guarded by a retinue of hard-as-nails samurai. It's too risky for him to be in the thick of the fighting, but it's useful having cavalry on the field to harass and run down enemies, even if there are only 11 of them.

After some failed attempts at skirmishing across the bridge with my archers, I simply gather up all my spearmen and rush the bridge in an attempt to overwhelm the enemy.

It works.

I lose a lot of my spearmen in the assault, but Chikuga is mine.

The Imagawa clan retaliate and strike where I'm weakest: the northern province of Buzen. I have a small force of only 120 yari samurai, but versus about 240 bow samurai I reckon I can keep a hold of the territory. 

It's a misty spring day. The valley is quiet and calm. I position my spearmen on a wooded hilltop where they will be protected from ranged attacks, and wait.

In the distance, the Imagawa forces emerge from the mist...

... but when they come within range of my spearmen, there's not much the archers can really do. They unload into the forest, firing volley after volley of arrows up the slope, but my soldiers are spread out loosely and protected by the trees. An unlucky few die, but otherwise the Imagawa arrows barely make a scratch.

Out of ammo and out of options, one of the formations of archers charges the hilltop. It's a mistake.

My soldiers drive them from the forest, but not without losses. Had the second unit of archers joined them in the assault, my men would almost certainly have been overwhelmed. Instead they hang back, using up the last of the arrows, and then press uphill themselves. My spearmen charge down from between the trees. Trying to fight up a slope, in melee combat with far superior melee combatants, the remaining Imagawa archers are slaughtered just like the others and routed from the field.

With the enemy on their back foot, I sink in the knife and march my forces into the second province on my list: Chikuzen. The small handful of battered Imagawa troops stationed there don't even attempt to defend it, and retreat.

I should wait to consolidate my hold on the provinces I own, but I can't resist the opportunity to push straight into the Imagawa stronghold of Hizen while they're weak. It might not be the soundest strategy.

My whole army marches on Hizen.

The remainder of the Imagawa army, crushed, retreats into Nagasaki castle. There's no time to wait out the siege, and there's so few soldiers left to defend the castle that an assault couldn't possibly fail.

We capture Nagasaki. It's all over for the Imagawa.

Or is it?

Having left no troops in Chikuzen to subdue the populace, a rebellion has broken out. 

Meanwhile, my campaigning left no troops in the south to repel a rebel invasion from Shikoku.

The rebel army crossed the sea from Iyo, captured the defenseless Bungo province, then moved straight on into Chikuga. 

My daimyo and his forces are surrounded, cut off from my capital in Satsuma. The only troops I have elsewhere that could relieve them are in Nagato, on my border with the Mori (red) faction, who I'm reluctant to move. Will I be able to stamp out these rebel forces and consolidate my rule of the island? Or will my forces be defeated, and my strategy be plunged into chaos? 

What a cliffhanger! 

Hopefully, I'll have part 2 up within a week.

Recently I've been thinking way too much about this stuff, so here's a full blog post about it. The aim of this post is to provide a resource other programmers can refer to whenever they have to tackle this problem. There's lots of use-cases for algorithms which generate points or vectors within the limits of a circle - a particle emitter might distribute particles over a circular area; a weapon or special ability might create explosions throughout a target zone; a shotgun's shots spread out in a cone; and so on. So how do you write a speedy, simple, understandable vector-generating function?

Depending on circumstances, you might have different requirements and want to optimise for different things:

• You probably want your points to be uniformly (evenly) distributed across the circle. To verify if an algorithm is outputting uniformly-distributed points, we check the average (mean) distance from the centre of the circle to each point. It should be about (2/3 * radius). This is because half the area of a circle is in its outer third, so when the average distance is (2/3 * radius) you know half the points are in the outer third. 
• You may want to minimise calls to the random number generator. Why? Because RNGs can be a bit crap. Certainly the C++ standard library's rand() function is. It might be bad for lots of different reasons. It might have a short period, meaning that it begins to repeat itself after a few thousand calls, which might be a big deal to you. Or it might not be very fast, which is unlikely to be impactful, but this stuff can get pretty weird.
• You might want to avoid using the square-root function. There's a discussion on stackoverflow regarding the speed of sqrt, in which someone says that it is "about 4 times slower than addition using -O2, or about 13 times slower without using -O2." Not huge in the fully-optimised case, but still big enough to add up, and you might be working on hardware where the implementation of sqrt is bad.
  
• You might want to avoid using many calls to trigonometry functions, because these might be bottlenecks in your code. Sure, you can write sin and cos functions that use a lookup table to speed things along, but maybe you don't want to have to stoop to doing all that work in what should be the age of fast processors. Again, as with rand(), these standard-library should-just-god-damn-work utilities aren't perfect.
• You want to avoid branching in performance-critical code. You can factor comparisons out using smart maths, sometimes, but that involves adding in extra code.

With these things in mind I'll discuss a handful of algorithms for generating points inside a circle.

For my Network Programming coursework I took a shot at making multiplayer Asteroids. By focusing on the networking rather than gameplay side of things I managed to get an A, but I left the game in a pretty unfinished state, which is why it looks so bad. I've been meaning to come back to it since December, because what I've got is a pretty good base on which to build a full game, and explore more network programming things along the way. Here's an overview.

Libraries

Given the choice to use any combination of libraries or engines I wanted, I naturally opted for just using SFML for everything, which provides a module for networking on top of all the other things it does. SFML is great - if you're a budding game programmer who knows a bit of C++ and you want to test your skills or just make something quick without worrying about anything terribly low-level it's a great option, provided you're on Windows or Linux. The networking module has its misgivings but simplifies a lot of the busywork involved in creating/managing sockets and connections, which was all I needed. I was trying to learn network programming, not master its intricacies. With SFML's networking classes I could have the mental benefits of cleaner, less dense code without having to write my own wrapper for WinSock, the socket library we used in the labs (and in so doing tie myself to Windows).

Network Architecture

There's a bunch of pretty big questions you have to ask when you sit down to design a networked game. How do you arrange the different machines in a network? What route does information take to get around? How do game worlds running on different machines remain in sync with each other?

Different network architectures exist, most of which fit into existing patterns or models. In the Client-Server model the network consists of a bunch of client machines connected to a single server machine. All communication goes via the server, and the server controls what happens when clients' worlds get out of sync. The Client-Server model is generally preferred by games, but sometimes they have to settle for Peer-to-Peer architectures. In the Peer-to-Peer model every network member is connected to every other network member. There's no central hub. There's no definitive version of the game world, and the different machines have to sort it out between themselves when there are inconsistencies between their different versions.

I chose to use a Client-Server Hybrid model in which one of the members of the network acts as both a client and a server. This is a pretty common pattern in game networking. The special machine is called the 'host' of the game. For my lightweight game I couldn't imagine a case where users would want to set up a powerful dedicated server - there just isn't that much data to crunch. 

All instances of the game - client or host - run their own basic simulation of the game in motion, aiming to run at 30 steps per second. On the clients' versions of the simulation, game entities' positions are updated each frame by their velocity, and input is handled for the local player's ship, but not much else. Only on the host is collision detection done and resolved, meaning that the host says whether an asteroid hit a player and no awkward situations arise with ambiguity.

Information Transmission

Information for which ordering is vital is sent over TCP using non-blocking sockets. For example, when an asteroid gets destroyed it's pretty much impossible for the separate game worlds to keep running correctly and in sync unless they are all immediately informed of the event. It's even more crucial that they find out about the event before another asteroid gets blown up - real headaches will occur if they don't thanks to the way I chose to manage game entities.

To find out if an event has happened, sockets are polled once per update loop (so as many times as possible per second) and if something has arrived on the socket it is immediately acted upon. I could have used a socket selector to do this without any busywaiting, but I had difficulty getting SFML's sf::SocketSelector class to work, and even when it did kind of work it was actually less time-consuming to just poll each and every socket.

When an object's velocity changes, the new velocity is sent over TCP. Each client controls the velocity of only a single object - their player's ship - while the host controls the velocity of everything else. Asteroids don't change velocity during their lifetime after creation and player ships don't feel the effects of drag. Everything follows a linear path apart from player ships, which can accelerate unpredictably. Velocity-change events don't represent a huge amount of network traffic, as such, so they shouldn't gum up the works, but it is important that the server finds out about a player's decision to accelerate as soon as possible so it can pass that information on to other players

Other less critical data (such as the positions of objects) is sent over UDP. The periodic position updates help a great deal in keeping things in sync, but it doesn't matter if they arrive out of order, late or at all, because the network messages all have timestamps.

Course Correction

If a position update for an object arrives from the server and it's wildly different from the client's version of the object's position, some correction is needed. In this case there are two options: we can simply set the position, or we linearly interpolate to the position based on the time difference between when the message was sent and when it was received. The first option causes perceivable jerkiness which makes the game difficult to play and painful to look at, but the second smooths things out pretty nicely, bringing objects back into line. 

More advanced course correction methods (using lerping when correcting the velocities of objects, for example) could be used but the game doesn't really call for them. 

For testing how the application responded to latency, packet loss and other fun things I used clumsy. It made me sad to see how badly the game responded to adverse network conditions, but it helped me get an understanding of where I needed to strengthen the code to handle such conditions.

Looking Back

I learnt quite a lot from building my network game in this way. My big takeaways from the project were:

• Higher simulation steps-per-second meant high latency caused bigger problems. I was originally running the game at 60 timesteps per second, and the drop to 30 made the game handle higher levels of network lag so much more gracefully. I didn't get around to making up for the timestep deficiency, but I could do it by rendering objects ahead of where they actually are between steps based on their velocity, which would produce a smoother-looking game, I could also figure out a way to vary the timestep dynamically based on network conditions, but that sounds tricky to get right.
• High-magnitude accelerations are unkind. If an object's velocity is changing in a big way it becomes easier and easier for versions of the game world to become out of sync when network conditions aren't ideal. It's therefore in the interest of the programmer that game object's accelerations be clamped within some limits.
• The game world wraps around, so that if an object moves off the right edge of the screen it reappears on the left. This plus linear interpolation of positions equals weird bugs where objects quickly fly across the screen, which sucks. 

I left the project with some problems still needing to be fixed:

• I left an annoying bug - when an asteroid gets destroyed, the newly-created ones on the client can end up slightly behind their host counterparts. This could be fixed by sending periodic position updates from the host to clients for asteroids, not just players, although this would of course increase network traffic by a substantial amount.
• There also seem to be issues which I forgot about with connecting more than one client to the host. As in, it's impossible for multiple clients to connect to the host. So I need to fix that.

Looking Forward

• Fix a bunch of bugs and issues and smooth out the code.
• Internet multiplayer. How hard can it be?
• Implement the gameplay, putting art in in the process.
• Get local mutliplayer working.

In the future I'm hoping to find time to do a blog post discussing the system I used for managing game entities, which was pretty nifty, but I seem to be pretty busy this summer with things.

At some point over the last few days I looked at a list of maths topics that I have to study next year at university and I thought I might not have such a heavy workload when the time comes if I put some time over the summer into figuring them out. I find the best way to learn maths is to write code that involves it.

This is true of pretty much anything, really. Learning how a system works? Program it. Tinker with it. It’s the difference between looking at diagrams about how to tie your laces and actually practising with your hands.

Bézier curves are a nifty way of representing curves. This website is a fantastic overview of them and their surrounding topics, and I highly recommend it if you want to learn more, because this is just a write-up of an afternoon coding project I undertook recently and isn't going to go into anywhere near as much detail. (Moreover, that site has interactive diagrams and curves, which I don’t know how to do yet. Soon, though. Soon.)

They’re not very intimidating things, really - just polynomials manipulated by a set of ‘control points’. Look:

Here is a very simple Bézier curve with only 3 control points: the start (bottom left), the end (top right), and one in between (correct, it is indeed in the bottom right). As you can see, the curve bends towards the middle control point.

All Bézier curves are like this, having a start point, an end point, and bunch of points in between. If you were to draw lines sequentially joining up all the control points, the curve would fit within the shape formed by those lines.

So how does all this work? How do we get the x and y values of the curve at some distance along the curve?

You know how to do linear interpolation, right? It's basically just that. But not linear. So instead of this:

// 0 <= t <= 1
Vector2f Lerp(Vector2f start, Vector2f end, float t) {
        return start + (end - start) * t;
}

... we throw in more maths, so that in the end we have something looking like this:

Vector2f BezierCurve::GetValueAt(const float t) const {
        int order = m_control_points.size() - 1;

        Vector2f sum;

        for (int i = 0; i <= order; i++) {
                sum += m_control_points[i] * Binomial(order, i) * 
                        pow((1.f - t), (order - i)) * pow(t, i);
        }

        return sum;
}

(I'd write a nicely-formatted mathematical formula version for this here to make this section clearer if I could figure out a good way to do it with Weebly. Might come back for that.)

Simply put, for each control point, we warp the curve by a certain amount. The 'order' of the curve is equal to its number of control points minus one. A curve with only 2 control points isn't much of a curve at all - it's a straight line, of order 1, it is linear. With 3 control points we get an order 2 (quadratic) curve. With 4 we get an order 3 (cubic) curve. And so on. 

At each iteration, before we add in the control point's position to the sum, we multiply it by the binomial coefficient for the order of the curve and the current term we're on, i. This is done by just looking up the value in Pascal's triangle at (order, i). After that we multiply by the polynomial section of the formula, (1 - t)^(order-i) * t^i, and we're ready to move on to the next iteration.

To render the curve it is split up into segments, with higher numbers of segments producing smoother curves:

The demo program I wrote lets the user create any 2-dimensional curve they want by adding and rearranging control points. 

Controls:

• Left click: place a new control point. The new point becomes the second point in the curve's list of points.
• Left click and hold over an existing point moves the point around.
• H: hide or reveal the text.
• Up arrow, down arrow: increase or decrease the number of segments.
• R: reset the curve. Removes all the control points.

You can download a (hopefully functional) copy of this very simple program below. Enjoy!

As usual, I used SFML for the window management, input handling and graphics. The code sections of this blog were formatted by hilite.me, a sick little HTML generator.

If you're lucky, I'll share the source code later once I've done some tidying on it and probably added one or two features.