Category: Code

Gamification and coding

One of the big trends this decade has been gamification. By turning everyday tasks into games, the theory goes, a person’s natural competitive streak will be triggered, causing that person to put more effort into accomplishing the task, and accomplishing it well. Companies do it with their employees, web forums have begun to implement it for their users and moderators, and so on.

It was only a matter of time before someone brought it to programming. Actually, that happened years ago. Coding competitions have been around a long time, but I saw a link to CodinGame the other day, and that got me thinking.

Games people play

The idea behind gamification isn’t hard to understand. Humans are competitive by nature. We like to win, to be better than the rest. And we really like it when there’s an objective measure of just how much better we are. The Olympics weren’t that long ago, and how many of you remember watching in anticipation, staring at the world records in the corner of the screen? How often were you on the edge of your seat, waiting for the judges’ scores to pop up?

It’s not just sports, though. Most games have some element of scoring, some record of accomplishment. In Monopoly, for example, you’ve got an obvious one: the amount of money in front of you. (Unless you’re playing one of those newer versions with the credit cards, in which case, why?) In video games, tables of high scores have existed for decades, especially in arcade games. And we wanted to set those high scores so bad, because that brought a small measure of fame. Everyone could see that MHP (or whatever) was the best at that game, at least until somebody posted a better score.

Today, when we play over the Internet instead of in public, we have online leaderboards instead, but the principle is the same. It drives us to improve, to reach for that top spot. (Story time: While my brother was working at Amazon a few years ago, I spent about three hours on his XBox, playing Forza 4 and trying to set a record in one of its weekly challenges, a quarter-mile drag race. It was some of the most fun and satisfying gameplay I’ve ever had, even though I never got higher than about 26th.)

Achievements are another popular aspect of modern games, and they work the same way. As Pokemon taught us: you gotta catch ’em all! And that’s how it is with achievements. We see that list, those empty spots, and we have goals. We have something to strive for.

That’s what gamification is. It’s the transfer of that competitive urge, that desire to complete a set or simply win, to mundane work. By adding points and trophies and collectibles, we transform drudgery into entertainment. Whether at school, on the job, or in a social setting, these artificial goals effectively make us believe we’re playing a game. Games are fun, right? So if we make the boring stuff into a game, then it magically becomes fun! Well, maybe. It doesn’t always work, and it’s not for everybody.

Games without frontiers

In theory, almost anything can be gamified, but we’re talking about programming here, so let’s stick to that. How can we make writing computer programs into a game? There are a few obvious answers. One is to make a game about coding, as with else heart.break() or TIS-100. That works, but it’s very much a niche. Another option is adding subtle programming abilities into an otherwise unrelated game. Minecraft has redstone, for example, which allows you to build logic gates, the building blocks of computing, while Final Fantasy XII gave players a bit of power to program their AI-controlled party members. In those cases, however, the programming part is not the focus. It’s an aside, sometimes an unwelcome one.

True gamification of coding, as CodinGame does, is different. It’s more of a series of programming challenges, each with objective measures of success and prowess. Code has to be correct, first and foremost. It has to do what it was designed to do. It’s also good if it’s fast; given two identically correct programs, the faster one is usually considered better. Space is another factor—smaller is generally better—and you can come up with other metrics. (“Lines of code”, by the way, is not a very good one.)

Once you have a way of measuring the “score”, you’re halfway to making a game of it. Post the scores publicly, and watch as coders eagerly train at their craft for no other reason than to move up a spot or two. It’s almost like magic!

Can it work, though? I don’t know. It works for a lot of people, but not everyone. We’re not all the same. Some of us don’t have that competitive streak, or we don’t act on it. For them, gamification is a waste of time. But for the rest of the populace, it can create a reason to learn, a reason to want to learn. That’s something the world could use a lot more of, so I say it’s worth a shot.

Procedural terrain generation in 3D

I promised a look at generating 3D terrain procedurally, and now I’m delivering. This time around, we’ll look at the diamond-square algorithm, a kind of 3D extension of the midpoint displacement method we saw before.

Diamond-square is another way of generating fractal terrain, and it has been popular for a couple of decades. Old terrain generators like Terragen used it, and new programs continue to make use of this classic algorithm.

How to do it

Now, on a line segment, it’s easy to find the midpoint: just average together the ends. For a 2D plane (the source of our 3D heightmap), it’s not that much harder. But a simple midpoint displacement, as we did before, can cause severe “creasing” effects that render our terrain very unnatural, very obviously made by a computer. We don’t want that. That’s where the diamond in diamond-square comes in, as well see.

First things first, we need an array of points to represent our map. This can be as big as you like, but an array of size 2^n^+1 works best (in other words, something like 129, 257, or 1025). If you use that, then the highest index of the array will be 2^n^, and the midpoint 2^n-1^. Very easy to work with, especially once we get into the recursion. As before, we stop when we reach the bottom, which would be when we’ve run through every pixel. (If you’re paying attention, you know this makes diamond-square O(n²). Don’t worry, it’s not as bad as it seems.)

Like 2D midpoint displacement, we need a set of initial endpoints. Since we’re working with a 2D plane, we require 4 of them, one at each corner. We’ll average these together at the midpoint (the exact center of the map), and give the result a little nudge up or down, just like last time. This is the “diamond” step; if you look at the illustration on the Wikipedia page linked above, you’ll see why it’s called that.

Next comes the “square” step. We’ve got five points: 4 corners, 1 midpoint. This creates four diamonds (though we’ll sometimes have to overlap them). For each of these, we want to find the center of that, and displace it by a random amount. In coordinates, for a map of size 2n+1, our “square” center is at (n,n), and the “diamond” centers are (0,n), (2n,n), (n,0), and (n,2n).

We’ll repeat this process as long as necessary, alternating ever smaller diamonds and squares. Each time around, we’ll lower the range of our random displacement to make things smoother. At the end, we’ll have a full heightmap, with every point being at an elevation relatively close to the average of its neighbors. In other words, not too many sharp drop-offs. It looks somewhat natural, although I’ll admit that grayscale diamond-square heightmaps tend to resemble clouds to my eyes. Put them in 3D, though, and they look a lot better.

Tricks and traps

As with 2D midpoint displacement, diamond-square displacement has one major knob to tweak: smoothness. It works the same here as there: the less range given to the displacement, the smoother the resulting terrain.

But we’re working with a world now, so there’s more to it than that. One thing that most terrain generators allow is a “sea level” setting. One height is chosen as sea level, and everything below it is underwater. With a high sea level, the effect is something like an archipelago of volcanic islands sitting in an ocean. Lower values create the sense of mountains and valley lakes.

On the downside, diamond-square isn’t immune to the creasing mentioned above. The alternating diamond and square steps are meant to spread it around, but they don’t get rid of it entirely. However, a bit of post-processing can help with that, if it’s too much of a problem. (Or you can always say it’s natural, that your terrain really is sitting on a geological fault.)

The biggest disadvantage of any random displacement algorithm is its randomness, and that’s a lot harder to remove. If you’re procedurally generating terrain for a game, for example, and you use this method, you’re stuck with it. You can’t even change the RNG, because that will give a whole new set of values from the world seed. (This is not limited to purely random generation, however; any algorithm change will render old worlds obsolete. It actually happened with some early versions of Minecraft. To name one prominent example, the map used for the Achievement Hunter Let’s Play series is nearly impossible to recreate because of changes to the generator.) Your options there are limited. Either never, ever change the algorithm, or find some way to keep the old versions in the code for compatibility.

If you can live with those caveats, then procedural generation isn’t a problem. But there’s far more to it than simple randomness. In a later post, we’ll look at more predictable methods of content generation. These have the advantage that they’re easily reconstructible from a seed—as long as you use the same algorithm or sequence of them—so you still all the same benefits of procedural code. And they’re also more amenable to something other than terrain generation, as we shall see. Until then, whether you’re making maps or psychedelic images, have fun!

Software internals: floating-point

Integers are the basis for all computer calculation, but they’re not the only kind of numbers out there. Floating-point numbers are just as important when interfacing with the real world. They represent decimals, fractional quantities, anything other than simple whole numbers. But too many programmers use them without understanding them, and that tends to go horribly wrong.

First off, let’s get one link out of the way. What Every Computer Scientist Should Know About Floating-Point Arithmetic describes everything you need in more technical and precise terms than I ever could. It’s a good read, and it’s important stuff, so check it out if you want the gritty details.

Now, we’re fortunate to live in today’s world, because floating-point numbers are essentially standardized. IEEE 754 (along with some later revisions) defines a common floating-point format that’s used pretty much everywhere in modern tech. If it isn’t, then it’s still assumed to be. So we’ll base our discussion on that.

The theory

Floating-point numbers work a bit like scientific notation. In decimal, you can write something like 1.42 × 10^4^, and that’s understood to be the same as 14,200. But computers work in binary, so we need a binary form of scientific notation. In this case, for example, we can write 14,200 in binary as 11011101111000, or 1.1011101111 × 2^13^.

From there, we can create a way of packing this notation into a sequence of bits: floating-point numbers. What do we need? Well, each number can be either positive or negative, so we need some way of showing that. And we’ll have to store both the exponent (e.g, 13) and the mantissa (binary 1.101110111). The base (2, for binary) can be implied, as we know we’re working with binary. Put those three parts—mantissa, exponent, and sign—together, and you’ve got floating-point.

The practice

But it’s not as easy as that, and that’s why we have standards. First, how many bits are you going to use? Too few, and you don’t have much range. Too many, and you waste space on inconsequential fractions. However, sometimes you need those less-significant bits, so you might want to have options. Luckily, the standard gives us two main options: 32 and 64 bits. Unluckily, a lot of programming languages (like JavaScript) limit you to the latter. Some, like C, give you the choice between float and double (the latter meaning “double precision”, because that’s about what you get with more bits), but high-level programmers often don’t have that luxury. Since the “big” high-level languages tend to use 64-bit floating-point, then, we’ll look at it first.

Given our 64 bits, we need to divide them up among our three parts. The sign bit obviously only needs one, so that’s that. Of the remaining 63, the standard devotes 53 to the mantissa and 11 to the exponent. That lets us store binary exponents over 1000 and the equivalent of about 15 digits of precision. Add in a few special tricks (like denormalized numbers), and the total range runs from 10^-308^ to 10^308^. Huge. (32-bit still nets you 7 digits in a range of 10^±38^, which isn’t too shabby.)

Now, those of you better at math may have noticed a calculation error above. That’s intentional. The way IEEE 754 works, it saves a bit by a clever ruse. In decimal scientific notation, as you may know, the number to the left of the decimal point can’t be zero, and it has to be less than 10. (Otherwise, you could shift the point left or right one more spot.) The same is true for binary, but with a binary 10, i.e, 2. But there’s only one binary number that fills that role: 1. With a few exceptions, you’re always going to have the 1, so why bother putting it in?

The problem with this “implied” 1 comes when you have the one number that has no 1 anywhere in it. That, of course, is 0. But it’s okay, because the standard simply makes 0, well, 0. Exponent zero, mantissa zero. Sign…well, that’s different. Standard floating-point representation has two zeroes: negative and positive. They’re treated as equal essentially everywhere, but they do differ in that one sign bit.

The IEEE standard also does an odd thing with its exponents. Except for the case of a literal 0, every exponent is biased. For 64-bit numbers, the number 1023 is added to the exponent, so a number like 2.5 (binary 10.1 or 1.01 × 2^1^) would be stored as if it were 1.01 × 2^1024^. Why? Because it makes sorting and comparison easier, or so they claim.

In the rare event that you go outside the range, you get to infinity. Like zero, we’ve got two forms of that, one for either sign, but they’re considered nearly the same.

And then there’s NaN. This is a special value used mainly to make programmers scream, but it also represents invalid results like dividing by zero or taking the square root of a negative number. NaN is special in that it’s a whole class of values (anything with all bits in the exponent field set to 1), but they’re completely different. NaN equals nothing, not even another NaN. It’s a null value and an error code at the same time, which is where things inevitably go wrong.

Care and feeding

NaN, though, is only one of the pitfalls of using floating-point. You also have to watch out for infinities, since they don’t play nice with finite numbers. Also, unless you have a really good reason for doing so (such as being John Carmack), you probably don’t want to mess with the bits themselves.

More important than knowing how to use floating-point numbers is when to use them. Or, rather, when not to. They do give you precision, often more than you need, but sometimes that’s not enough. Take the classic example of 1/3. In decimal, it’s an endless string of 3s. Binary changes that to a repeating pattern of 01, but the principle is the same. No matter how many digits or bits you’ve got, you’re never getting to the end. So the simple code 1.0 / 3.0 will never give you exactly 1/3. It can’t. The same goes for any other fraction whose denominator isn’t exactly a power of two. So, if you need exact representation of an arbitrary rational number, floating-point won’t help you.

For 1/100, it’s no different, and that’s why floating-point isn’t a great idea for money, either. Sure, for most simple purposes, it’s close enough, but those tiny errors do add up, especially when multiplication and division get involved. If you’re serious about your money, you won’t be storing how much you have in a floating-point number. Instead, you’ll likely want a decimal type, something a lot of business-oriented languages offer.

In the general case, however, floating-point is the solution. You just have to know its limitations.

Procedural midpoint displacement

So I’ve been talking in the abstract about procedural generation. Now, let’s get to something solid. In this post, we’ll look at one of the most basic methods of “terrain” generation out there. (I use the scare quotes here for a very good reason, as you’ll soon see.) The technique is called midpoint displacement, and it’s a fairly simple method that can give sensible results…if you know how to use it.

The easiest way to demonstrate the algorithm is in two dimensions. That’s for a couple of reasons. First, lines are easier to visualize than planes in a medium like this. Two, heightmaps take longer to construct, and they’re harder to tweak. So instead of making actual terrain (i.e., an area of simulated land), we’ll make a line-art representation. Think of it as a cross section if you like, or the beginnings of a 2D scroller’s background.

Onto the algorithm itself. You start with a blank surface (a straight, horizontal line, in our case). Take the midpoint of that surface and move it up or down by a small, random amount. Now you’ll have two lines meeting at an angle. That might not look very terrain-like, but, at this stage, it’s not supposed to. The trick with midpoint displacement is that it’s recursive. For each of these line segments, do the same thing as before: move the midpoint by a random amount. Keep going as long as you want, either until you’re bumping up against resolution limits or you reach some predefined level of detail.

The end result is an increasingly “fractalized” line that begins to look less artificial and more like something that could come from natural processes of erosion and the like. The more subdivisions you do, the smoother the finished product will look, like so:

midpoint-displace

The above image shows midpoint displacement, with an increasing number of subdivisions. At the top, we have 1, going up to 10 at the bottom. (Note that these are separately generated images.) By the bottom, we’re starting to see something that doesn’t look too bad. You can go farther in your own code; I used Inkscape just for illustration, and 10 is the highest setting it has.

Using your imagination, you might be able to see how this could be interpreted as terrain. It’s a very rugged terrain, though, and that comes from the other tweakable parameter. Remember how I told you, at each step, to move the midpoint a little in either direction? Well, how far you move it determines how rough the generated terrain becomes. This is the smoothness factor.

In general, midpoint displacement works best if you decrease the range of movement at each subdivision. Otherwise, you get wild swings that don’t look at all natural. The “default” assumption is that each step has half the range as the one before it, but changing the smoothness affects this; smoother generation requires smaller variation.

Interactive tools to visualize midpoint displacement aren’t hard to find, and code samples are almost as easy, so we’ll leave off here for now. Later, we’ll look at expanding this idea to a three-dimensional world, where we can truly see the effect of terrain generation.

On procedural generation

One of my favorite uses of code is to create things. It always has been. When I was young, I was fascinated by fractals and terrain generators and the like. The whole idea of making the code to make something else always appealed to me. Now, as it turns out, the rest of the world has come to the same conclusion.

Procedural generation is all the rage in games these days. Minecraft, of course, has made a killing off of creating worlds from nothing. No Man’s Sky may have flopped, but you can’t fault its ambition: not only was it supposed to have procedurally-generated worlds, but a whole galaxy full of aliens, quests, and, well, content. That last part didn’t happen, but not because of impossibility. The list goes on—and back, as Elite, with its eight galaxies full of procedural star systems, is about as old as I am.

Terrain

Procedural terrain is probably the most widely known form of generation. Even if you’ve never played with TerraGen or something like that, you’ve probably played or seen a game that used procedural heightmaps. (Or voxels, like Minecraft.) Making terrain from code is embarrassingly easy, and I intend to do a post in the near future about it.

From the initial generation, you can add in lots of little extras. Multiple passes, possibly using different algorithms or parameters, give a more lifelike world. Tweaking, say, the sea level changes your jagged mountain range into an archipelago. You can go even further, adding in simulated plate tectonics or volcanic deposition or coastline erosion. There really are no boundaries, but realism takes some work.

Textures and models

Most 3D modeling software will give you an option to make “procedural” textures. These can be cool and trippy, especially those based on noise functions, but it’s very difficult to use them to make something realistic. That doesn’t stop them from being useful for other things; a noise bump map might be more interesting than a noise texture, but the principle is the same.

Going one step up—to actual procedural models—is…not trivial. The “creature generators” as in No Man’s Sky or Spore are severely limited in what they can do. That’s because making models is hard work already. Leaving the job in the hands of an algorithm is asking for disaster. You’re usually better off doing as they do, taking a “base” and altering it algorithmically, but in known ways.

Sound

Procedural sound effects and music interest me a lot. I like music, I like code. It seems only natural to want to combine the two. And there are procedural audio packages out there. Making them sound melodic is like getting a procedural model to work, but for your ears instead of your eyes. It’s far from easy. And most procedural music tends to sound either very loopy and repetitive, or utterly listless. The generating algorithms we use aren’t really suited for musical structure.

Story

Now here’s an intriguing notion: what if algorithms could write a story for us? Creating something coherent is at the high end of the difficulty curve, but that hasn’t stopped some from trying. There’s even a NaNoWriMo-like contest for it.

On a smaller scale, games have been making side quests and algorithmic NPCs for years. That part isn’t solved, but it isn’t hard. (For some reason, Fallout 4 got a lot of press for its “radiant quests” in 2015, like it was something new. Though those are, I think, more random than procedural…) Like modeling, the easiest method is to fill in parts of a pre-arranged skeleton, a bit like Mad Libs.

Anything else

Really, there’s no limit to what can be made through procedural generation. That’s probably why I like it so much. From a small starting seed and a collection of algorithms, amazing things can be brought forth. In an age of multi-gigabyte games full of motion-captured animation, professional voice talent, and real-world scenery, it’s a refreshing change to make something beautiful out of a few letters and numbers.

On visual programming

With the recent release of Godot 2.1, the engine’s developers broke the news of a project coming to a future version: a visual scripting system. That’s nothing new, even in the world of game development. Unreal came out with Blueprints a while back, and even Godot already used something similar for its shaders. Elsewhere, “visual programming” has its proponents and detractors, and I’m going to throw in my two cents.

Seeing is believing

In theory, visual programming is the greatest revolution in coding since functions. It’s supposed to deliver all the benefits of writing programs to those who don’t want to, well, write. The practice has its origins in flowcharts, which are graphical representations of algorithms. Computer scientists got to thinking, “Okay, so we can make algorithms like this, so why not whole applications?” It’s only been fairly recently that computers have been able to fulfill this desire, but visual programming languages are now springing up everywhere.

The idea is deceptive in its simplicity. Instead of laboriously typing out function declarations and loop bodies, you drag and drop boxes (or other shapes), connecting them to show the flow of logic through your program. The output of one function can be “wired” to another’s input, for example. The benefits are obvious. Forget about syntax errors. Never worry about type mismatches again. Code can truly become art. With the name of this site, you’d think I could get behind that.

It does work, I’ll give you that. MIT’s Scratch is used by tens of thousands of programmers, young and old alike. Through its ingenious “building block” system, where the “boxes” are shaped like pieces in a jigsaw puzzle, you never have to worry about putting the wrong peg into the wrong hole. For children who barely understand how a computer works—or, in extreme cases, may not know how to read yet—it’s a great help. There’s a reason why it’s been copied and cloned to no end. It even makes coding fun.

What can’t be unseen

The downsides to visual programming, however, are not fun at all. Ask anyone who’s ever suffered through LabVIEW (I’ve read enough horror stories to keep me away from it forever). Yes, the boxes and blocks are cute, but complex logic is bad enough when it’s in linear, written form. Converted to a more visual format, you see a literal interpretation of the term “spaghetti code”. Imagine how hard it was to write. Now imagine how hard it would be to maintain.

Second, visual programming interfaces have often suffered from a lack of operations. If you wanted to do something that there isn’t a block for, you were most likely out of luck. Today, it’s not so bad. Unreal’s Blueprints, for example, gives you about 95% of the functionality of C++, and Godot’s variation purports to do the same.

But some things just don’t fit. Composition, an important part of programming, is really, really hard to get right visually. Functional styles look like tangled messes. Numerics and statistics are better served in a linear form, where they’re close to the mathematics they’re implementing.

The verdict

I’m not saying visual programming is useless. It’s not. There are cases where it’s a wonderful thing. It’s great for education, and it’s suited to illustrating the way an algorithm works, something that often gets lost in the noise of code. But it needs to be used sparingly. I wouldn’t write an operating system or device driver in Scratch, even if I could. (You can’t, by the way.)

In truth, the visual “style” doesn’t appeal to me. That’s a personal opinion. Your mileage may vary. When I’m learning something new, it’s certainly a big help, but we have to take the training wheels off eventually. Right now, that’s how I see a visual scripting system. For a new programmer, sure, give it a try. You might love it.

But you probably won’t. After a while, you’ll start bumping into the limitations. You’ll have webs of logic that make spiders jealous, or customized blocks that look like something by Escher. Stay simple, and you might keep your sanity—as much as any programmer has, anyway. But we’re not artists. Not in that way, at least. Code can be beautiful without being graphical.

Let’s end threads

Today’s computers almost all have multiple cores. I don’t even think you can buy a single-core processor anymore, at least not one meant for a desktop. More cores means more things can run at once, as we know, and there are two ways we can take advantage of that. One is easy: run more programs. In a multi-core system, you can have one core running the program you’re using right now, another running a background task, and two more ready in case you need them. And that’s great, although you do have the problem of only one set of memory, one hard drive, etc. You can’t really parallelize those.

The second option uses the additional cores to run different parts of a single application. Threads are the usual way of doing this, though they’ve been around far longer than multi-core processors. They’re more of a general concurrency framework. Put a long-running section of code in its own thread, and the OS will make sure it runs. It won’t block the rest of the program. And that’s great, too. Anything that lets us fully utilize this amazing hardware we have is a good thing, right?

Well, no. Threads are undoubtedly useful. We really couldn’t make modern software without them. But I would argue that we, as higher-level programmers, don’t need them. For an application developer, the very existence of threads should be an implementation detail in the same vein as small string optimizations or reference counting. Here’s why I think this.

Threads are low-level

The thread is a low-level construct. That cannot be denied. It’s closer to the operating system layer than the application layer. If you’re working at those lower levels, then that’s what you want, but most developers aren’t doing that. In a general desktop program or mobile app, threads aren’t abstract enough.

To put it another way: C++ bears the brunt of coders’ ire at its “manual” memory management. Unlike C# or Java, a C++ programmer does need to understand the lifecycle of data, when it is constructed and destructed, what happens when it changes hands. But few complain about keeping track of a thread’s lifecycle, which is essentially the same problem.

Manual threading is error-prone

This comes from threads being low-level because, as any programmer will tell you, the lower you are in the “stack”, the more likely you’ll unwittingly create bugs. And there might not be any bigger source of bugs in multithreaded applications than in the threading itself.

Especially in C++, but by no means unheard of in higher-level languages, threading leads to all sorts of undefined or ill-defined behavior, race conditions, and seemingly random bugginess. Because threads are scheduled by the OS, they’re out of your control. You don’t know what’s executing when. End a thread too early, for example, and your main program could try reading data that’s no longer there. And that can be awfully hard to detect with a debugger, since the very act of running something in debug mode will change the timing, the scheduling.

Sharing state sucks

In an ideal situation, one that the FP types tell us we should all strive for, one section of code won’t depend on any state from any other. If that’s the case, then you’ll never have a problem with memory accesses between threads, because there won’t be any.

We code in the real world, however, and the pure-functional approach simply does not work everywhere. But the alternative—accessing data living in one thread from another—is a minefield full of semaphores and mutexes and the like. It’s so bad that processors have implemented “atomic” memory access instructions just for this purpose, but they’re no magic bullet.

Once again, this is a function of threads being “primitive”. They’re manually operated, with all the baggage that entails. In fact, just about every problem with threads boils down to that same thing. So then the question becomes: can we fix it?

A better way

Absolutely. Some programming languages are already doing this, offering a full set of async utilities. Generally, these are higher-level functions, objects, and libraries that hide the workhorse threads behind abstractions. That is, of course, a very good thing for those of us using that higher level, those who don’t want to be bogged down in the minutiae of threading.

The details differ between languages, but the usual idea is that a program will want to run some sort of a “task” in the background, possibly providing data to it at initialization, or perhaps later, and receiving other data as a result. In other words, an async task is little more than a function that just happens to run on a different thread, but we don’t have to care about that last part. And that is the key. We don’t want to worry about how a thread is run, when it returns, and so on. All we care about is that it does what we ask it to, or else it lets us know that it can’t.

This async style can cover most of the other thread-based problems, too. Async tasks only run what they’re asked, they end when they’re done, and they give us ways (e.g., futures) to wait for their results before we try to use them. They take care of the entire lifecycle of threading, which we can then treat as a black box. Sharing memory is a bit harder, as we still need to guard against race conditions, but it can mostly be automated with atomic access controls.

A message-passing system like Scala and Erlang use can even go beyond this, effectively isolating the different tasks to an extent resembling that of the pure-FP style. But even in, say, C++, we can get rid of most direct uses of threads, just like C++11 removed most of the need for raw pointers.

On the application level, in 2016, there’s no reason a programmer should have to worry about manual memory allocation, so why should we worry about manual thread allocation? There are better ways for both. Let’s use them.

Software internals: associative arrays and hashing

We’ve already seen a couple of options for storing sequences of data in this series. Early on, we looked at your basic array, for example, and then we later studied linked lists. Both of those are good, solid data structures. Linear arrays are fast and cheap; linked lists are great for storing an arbitrary amount of data for easy retrieval. There’s a reason these two form the backbone of programming.

They do have their downsides, however. Linear arrays and lists both suffer from a problem with indexing. See, a piece of data in an array is accessed by its index, a number you have to keep track of if you ever want to see that data again. With linked lists, thanks to their dynamic structure, you don’t even get that. Finding a value in a list, if you don’t already know what you’re looking for, is practically impossible.

By association

What we need is a structure that gives us the flexibility of a list but the indexing capabilities of an array. Oh, and can we have an array whose indexes are keys we decide, instead of just numbers? Sure, and I bet you want a pony, too. But seriously, we can do this. In fact, your programming language of choice most likely already does it, and you just never knew. JavaScript calls them “objects”, Python “dictionaries”, C++ “maps”, but computer science generally refers to this structure as the associative array. “Associative”, because it associates one value with another. “Array” tells you that it functions more like a linear array, in terms of accessing data, than a list. But instead of computer-assigned numbers, the indexes for an associative array can be just about anything: integers (of your choosing), strings, even whole objects.

The main component of an associative array is the “mapping” between keys (the indices used to access the data) and the values (the actual data you’re storing in the array). One simple way to create this mapping is by making a list of key-value pairs, like so:

class AssociativeArray {
    constructor() {
        // Pairs are objects with 2 attributes
        // k: key, v: value
        this.pairs = []
    }

    get(key) {
        let value = null;
        for (let p of this.pairs) {
            if (p.k === key) {
                value = p.v;
                break;
            }
        }

        return value;
    }

    insert(key, value) {
        if (!this.get(key)) {
            // Add value if key not already present
            this.pairs.push({k: key, v: value});
        } else {
            // *Update* value if key present
            this.pairs = this.pairs.map(
                p => (p.k === key) ?
                    {k: key, v: value} :
                    p
            );
        }
    }

    remove(key) {
        this.pairs = this.pairs.filter(p => (p.k !== key));
    }
}

(Note that I’m being all fancy and using ES6, or ES2015 if you prefer. I’ve also cheated a bit and used builtin Array functions for some operations. That also has the dubious benefit of making the whole thing look more FP-friendly.)

This does work. We could create a new instance of our AssociativeArray class, call it a, and add values to it like this: a.insert("foo", 42). Retrieving them is as easy as a.get("foo"), with a null result meaning no key was found. (If you want to store null values, you’d have to change this to throw an exception or something, which is probably better in the long run, anyway.)

The problem is, it’s not very fast. Our simple associative array is nothing more than a glorified linked list that just so happens to store two values at each node instead of one. For small amounts of data, that’s perfectly fine. If we need to store a lot of information and look it up later, then this naive approach won’t work. We can do better, but it’ll take some thought.

Making a hash of things

What if, instead of directly using the key value, we computed another value from it and used that instead? That might sound silly at first, but think about it. The problem with arbitrary keys is that they’re, well, arbitrary. We have no control over what crazy ideas users will come up with. But if we could create an easy-to-use number from a key, that effectively transforms our associative array into something closer to the familiar linear array.

That’s the thinking behind the hash table, one of the more popular “back ends” for associative arrays. Using a special function (the hash function), the table computes a simple number (the hash value or just hash) from the key. The hash function is chosen so that its output isn’t entirely predictable—though, of course, the same input will always return the same hash—which distributes the possible hash values in a random-looking fashion.

Hashes are usually the size of an integer, such as 32 or 64 bits. Obviously, using these directly is not an option for any realistic array, so some sacrifices have to be made. Most hash tables take a hybrid array/list approach. The hash “space” is divided into a number of buckets, chosen based on needs of space and processor time. Each bucket is a list (possibly even something like what we wrote above), and which bucket a value is placed in is determined by its hash. One easy option here is a simple modulus operation: a hash table with 256 buckets, for instance, would put a key-value pair into the bucket corresponding to the last byte (hash % 256) of its hash.

In code, we might end up with something like this:

class HashTable {
    constructor() {
        this._numBuckets = 256;
        this._buckets = new Array(this._numBuckets);
        this._buckets.fill([]);
    }

    _findInBucket(key, bucket) {
        // Returns element index of pair with specified key
        return this._buckets.findIndex(p => (p.k === key));
    }

    _update(key, value, bucket) {
        for (let i = 0; i < this._buckets[bucket].length; i++) {
            if (this._buckets[bucket][i] === key) {
                this._buckets[bucket][i].v = value;
                break;
            }
        }
    }

    set(key, value) {
        let h = hashCode(key);
        let bucket = h % this._numBuckets;
        let posInBucket = this._findInBucket(key, bucket);

        if (posInBucket === -1) {
            // Not in table, insert
            this._buckets[bucket].push({k: key, v: value});
        } else {
            // Already in table, update
            this._update(key, value, bucket);
        }
    }

    get(key) {
        let h = hashCode(key);
        let bucket = this._buckets[h % this._numBuckets];
        let index = this._findInBucket(key, bucket);

        if (index > -1) {
            return bucket[index].v;
        } else {
            // Key not found
            return null;
        }
    }
}

The function

This code won’t run. That’s not because it’s badly-written. (No, it’s totally because of that, but that’s not the point.) We’ve got an undeclared function stopping us: hashCode(). I’ve saved it for last, as it’s both the hardest and the most important part of a hash table.

A good hash function needs to give us a wide range of values, distributed with little correlation to its input values so as to reduce collisions, or inputs leading to the same hash. For a specific input, it also has to return the same value every time. That means no randomness, but the output needs to “look” random, in that it’s uniformly distributed. With a hash function that does this, the buckets will remain fairly empty; optimally, they’d each only have one entry. The worst-case scenario, on the other hand, puts everything into a single bucket, creating an overly complex linked list with lots of useless overhead.

There are a lot of pre-written hash functions out there, each with its own advantages and disadvantages. Some are general-purpose, while others are specialized for a particular type of data. Rather than walk you through making your own (which is probably a bad idea, for the same reason that making your own RNG is), I’ll let you find one that works for you. Your programming language may already have one: C++, for one, has std::hash.

Incidentally, you may have already seen hash functions “in the wild”. They’re fairly common even outside the world of associative arrays. MD5 and SHA-256, among others, are used as quick checksums for file downloads, as the uniform distribution principle of hashing causes small changes in a key to radically alter the final hash value. It’s also big (and bad) news when collisions are found with a new hash algorithm; very recently—I can’t find the article, or I’d link it here—developers started warning about trusting the “short” hashes used by Git to mark commits, tags, and authors. These are only 32 bits long, instead of the usual 256, so collisions are a lot more likely, and it’s not too hard to pad out a malicious file with enough garbage to give it the same short hash as, say, the latest Linux kernel.

Summing up

Hash tables aren’t the only way to implement associative arrays. For some cases, they’re nowhere near the best. But they do fill the general role of being good enough most of the time. Computing hash codes is the most time-consuming part, with handling collisions and overfull buckets following after that. Unfortunately for higher-level programmers, you don’t have a lot of control over any of these aspects, so optimizing for them is difficult. However, you rarely have to, as the library writers have done most of that work for you. But that’s what this series is about. You may never need to peer into the inner workings of an associative array, but now you’ve got an idea of what you’d find down there.

Godot Engine 2.1

So a new version of one of my favorite game engines came out recently, and I’m just now taking a look at it. (Actually, I’m writing this on the 11th.) If you’ll recall from a couple of months ago, I tried making a game in Godot 2.0, but I couldn’t continue due to an illness. Now, with a new version out, I think I might try again soon. But first, let’s look at what’s in store, and let’s see if Godot is still worthy of the title of Best Free Game Engine.

Asset sharing

Unity’s absolute best feature is the Asset Store. There’s no question about that. It’s got everything you need, and it’s almost possible to make a game just by downloading graphics, sound effects, and pre-written code from there. And other engines (Unreal, etc.) are starting to jump on the same bandwagon.

With version 2.1, Godot can now say it’s joining the ranks. There’s a new Asset Library accessible within the editor, and it’ll eventually work the same as any other. Right now, it’s pretty bare, but I have no doubt it’ll grow as time goes on.

Better plugins

Godot’s editor has a lot of features, but it doesn’t do everything. Developers have always been able to add functionality with plugins (mainly through using the tool keyword in Godot scripts), but 2.1 brings a whole new EditorPlugin API, meaning that these tools can integrate better with the rest of the editor. They can also work with the Asset Library.

The API, like the Asset Library, is a work in progress, so it doesn’t have all the features yet. But give it time.

Editor improvements

If you don’t speak English, Godot 2.1 helps by supporting full internationalization of the interface. Along with that, the developers have added full support for actual fonts, instead of the whole “import TTF to textures” process we used to have to do. This also opens up the possibility of customizing the editor’s fonts, their colors and sizes. And it’s a small step from there to full-on theming, so that’s in, too.

Another nicety is custom keybindings, and that solves one of my bigger gripes. Not that I couldn’t change the bindings, mind you; I rarely do that in programming apps, if only because it makes tutorials harder to follow. No, now I can actually see what the default bindings are. Godot’s documentation was severely lacking in that area, but giving me the option to change now also brings the ability to discover, and that’s always a good thing.

They’ve also added some drag-and-drop stuff that I’ll probably never use, along with context menus, which I certainly will. And then there’s the usual improvements to the script editor, which are necessary when you’re using your own scripting language. (More on that later.)

Animation

Animation in Godot confused me. It must have confused a lot of other people, too, because one of the big new additions is a simpler way of using the AnimatedSprite node for, well, animation. You know, the thing it’s made for. No longer do you have to create an AnimationPlayer and all that, when all you really want to do is say, “Hey, play this one little animation, okay?”

The verdict

The official announcement (linked above) has a few other additions, like new features for live reloading. They’ve also got a link to the full changelog, if you like reading. But I’m content with what I’ve seen so far. Godot is still good, and it looks like it’s only getting better—maybe.

What does the future hold? Well, according to the developers, the next version is 2.2, due by the end of the year. (Yeah, right!) That one’s the first true “feature” release, and what features it’ll have. Do you hate Python? My brother does, so he’s happy to hear that Godot will soon give you not one, but two new options for scripting. One is a “visual” design system like Unreal’s Blueprints, a style that I’ll be writing about soon. The other is massive in its importance: C#. Yep, the same language Unity uses. If that takes off, then look out.

Beyond that, things get murky. They claim they’re already starting on Godot 3.0, and it’ll come out early next year. As it’s centerpiece, it’ll have an entirely new renderer, probably based on Vulkan. And that might be a problem. But I’ll wait and see. Godot is too good to abandon, but I hope it doesn’t abandon me on the road to better things.

First glance: C++17, part 3

It’s not all good in C++ land. Over the past two posts, we’ve seen some of the great new features being added in next year’s update to the standard, but there are a few things that just didn’t make the cut. For some, that might be good. For others, it’s a shame.

Concepts

Concepts have been a hot topic among C++ insiders for over a decade. At their core, they’re a kind of addition to the template system that would allow a programmer to specify that a template parameter must meet certain conditions. For example, a parameter must be a type that is comparable or iterable, because the function of the template depends on such behaviors.

The STL already uses concepts behind the scenes, but only as a prosaic description; adding support for them to the language proper has been a goal that keeps receding into the future, like strong AI or fusion power. Some had hoped they’d be ready for C++11, but that obviously didn’t happen. A few held out for C++14, but that came and went, too. And now C++17 has shattered the concept dream yet again. Mostly, that’s because nobody can quite agree on what they should look like and how they should work under the hood. As integral as they will be, these are no small disagreements.

Modules

Most “modern” languages have some sort of module system. In Python, for instance, you can say import numpy, and then NumPy is right there, ready to be used. Java, C#, JavaScript, and many others have similar functionality, often with near-identical syntax.

But C++ doesn’t. It inherited C’s “module” system: header files and the #include directive. But #include relies on the preprocessor, and a lot of people don’t like that. They want something better, not because it’s the hip thing to do, but because it has legitimate benefits over the older method. (Basically, if the C preprocessor would just go away, everyone would be a lot better off. Alas, there are technical reasons why it can’t…yet.)

Modules were to be something like in other languages. The reason they haven’t made the cut for C++17 is because there are two main proposals, neither truly compatible with the other, but both with their supporters. It’s almost a partisan thing, except that the C++ Standards Committee is far more professional than Congress. But until they get their differences sorted out, modules are off the table, and the preprocessor lives (or limps) on.

Coroutines and future.then

These fit together a bit, because they both tie in with the increased focus on concurrency. With multicore systems everywhere, threading and IPC are both more and less important than ever. A system with multiple cores can run more than one bit of code at a time, and that can give us a tremendous boost in speed. But that’s at the cost of increased complexity, as anyone who’s ever tried programming a threaded application can tell you.

C++, since its 2011 Great Leap Forward, has support for concurrency. And, as usual, it gives you more than one way to do it. You have the traditional thread-based approach in std::thread, mutex, etc., but then there’s also the fancier asynchronous set of promise, future, and async.

One thing C++ doesn’t have, however, is the coroutine. A function can’t just pause in the middle and resume where it left off, as done by Python’s yield keyword. But that doesn’t mean there aren’t proposals. Yet again, it’s the case that two varieties exist, and we’re waiting for a consensus. Maybe in 2020.

Related to coroutines is the continuation, something familiar to programmers of Lisp and Scheme. The C++ way to support these is with future.then(), a method on a std::future object that invokes a given function once the future is “ready”, i.e., when it’s done doing whatever it had been created to do. More calls to then() can then (sorry!) be added, creating a whole chain of actions that are done sequentially yet asynchronously.

Why didn’t then() make it? It’s a little hard to say, but it seems that the prevailing opinion is that it needs to be added in the company of other concurrency-related features, possibly including coroutines or Microsoft’s await.

Unified call syntax

From what I’ve read, this one might be the most controversial addition to C++, so it’s no surprise that it was passed over for inclusion in C++17. Right now, there are two ways to call a function in the language. If it’s a free function or some callable object, you write something like f(a, b, c), just like you always have. But member functions are different. With them, the syntax is o.f(a, b, c) for references, o->f(a, b, c) for pointers. But that makes it hard to write generic code that doesn’t care about this distinction.

One option is to extend the member function syntax so that o.f() can fall back on f(o) if the object o doesn’t have a method f. The converse is to let f(o) instead try to call o.f().

The latter form is more familiar to C++ coders. It’s basically how Modern C++’s std::begin and end work. The former, however, is a close match to how languages like Python define methods. Problem is, the two are mutually incompatible, so we have to pick one if we want a unified call syntax.

But do we? The arguments against both proposals make some good points. Either option will make parsing (both by the compiler and in the programmer’s head) much more complex. Argument-dependent lookup is already a difficult problem; this only makes it worse. And the more I think about it, the less I’m sure that we need it.

Reflection

This, on the other hand, would be a godsend. Reflection in Java and C# lets you peer into an object at run-time, dynamically accessing its methods and generally poking around. In C++, that’s pretty much impossible. Thanks to templates, copy elision, proxy classes, binders, and a host of other things, run-time reflection simply cannot be done. That’s unfortunate, but it’s the price we pay for the unrivaled speed and power of a native language.

We could, however, get reflection in the compile-time stage. That’s not beyond the realm of possibility, and it’s far from useless, thanks to template metaprogramming. So a few people have submitted proposals to add compile-time reflection capabilities to C++. None of them made the cut for C++17, though. Granted, they’re still in the early stages, and there are a lot of wrinkles that need ironing out. Well, they’ve got three (or maybe just two) years to do it, so here’s hoping.

And that’s all

C++17 may not be as earth-shattering as C++11 was, but it is a major update to the world’s biggest programming language. (Biggest in sheer size and scope, mind you, not in usage.) And with the new, faster release schedule, it sets the stage for an exciting future. Of course, we’ll have to wait for “C++Next” to see how that holds up, but we’re off to a great start.