Category Archives: games design

#Gamification, #StackOverflow: How they create new sites from the community while blocking spam

If you’re not a StackOverflow user …

  • It’s rapidly become the go-to place for answers to precise technical questions
  • It has a bold, “points-based reputation controls everything”, moderation system (e.g. get upvoted enough and you become a moderator – there is no human intervention!)
  • It worked so well they expanded to infinitely many clone sites, for any topic you can think of, collectively termed “StackExchange”
  • …and the process for creating a new clone is itself points-based (not human moderated)

Historically this kind of setup has been a recipe for disaster – too easily gamed (taken advantage of), both by selfish users and purely malicious griefers. SO has had, and still has, many problems – some of the design choices that worked early on caused more problems than they solved as it scaled up in size. But overall it worked, and continues to work, very well.

The main site is easy to understand – by the time you’ve earned 10,000 reputation you are probably so enmeshed in the community it’s probably safe to give you moderator tools. (Note “probably” – it causes serious damage in a large minority of cases, but overall it works well, and it’s very cheap. This generally means no corporate sponsors/advertisers/subscriptions are needed)

But the process for creating new sites is less obvious, more convoluted, and – for the brand – potentially a lot more dangerous. I’m involved in two sites going through the process right now, and it’s interesting to compare them.

Site creation overview

  1. A special site – Area51 – allows you to create new sites, with this FAQ
  2. Your new site goes into phase 1: “Definition”
  3. If it passes, it goes to phase 2: “Commitment”
  4. Once it’s live, it’s monitored for a while, and if the site was a bad idea / disaster / failure, it gets shutdown
  5. If it passes the probationary period, the site is live

SO is worried about a bunch of things. From game-design and community-management perspective, I’d expect them to focus on e.g.

  • Will anyone use the site? (ask questions)
  • Are there any experts around to answer the questions?
  • Is the community large enough to be self-sustaining?

“Definition”

This checks the first worry – will anyone ask any questions?

To prove this programmatically, they force you to ask 40 “Good” questions.

To determine if a question is good, it has to receive 10 more upvotes than downvotes. This is arbitrary, but it means e.g. 10 different people felt it was a good question, and no-one thought it bad (or more for both sides, so long as there’s 10 more up than down votes).

Riiight … so you write 40 questions, get 9 friends to upvote all of them, and away you go … right? Easily gamed/abused.

Wrong. Area51 uses a modified version of SO’s voting. Each user is limited to asking 5 questions – which is fair and harsh. Fair because: if there’s really a community ready to go, it will have questions from many people (at least 8 people will have to pose good questions to get the 40 needed). Harsh because: most people will struggle to think up more than 1 or 2 good questions.

Still easily gameable, but now enough to dissuade idle / bored people.

Similarly each user can only upvote 5 questions. Choosing to up/downvote is very easy, so this isn’t “harsh” at all. It’s (almost) equally gameable: other users (anyone, anywhere) can register and counter-game by downvoting bad questions, forcing the collaborators to work harder.

Sadly, this scheme has a non-obvious element – the need to get 40 questions to 10 upvotes – that MOST users fail to understand, and SO has done nothing to fix. On SO.com, more upvotes is always better; on Area51 the 11th upvote (and all afterwards) are not only worthless, but actively delay the proposal because they squander upvotes that the user could have used on other questions.

So, for instance, the Computer Science Educators proposal was popular but spent many months failing to pass this phase because people arrived, upvoted the top questions, felt they’d helped … and left. Because of the design-flaw, not only were they “not helping” but the surge of high voted questions above the fold encouraged the next wave of newcomers to do the same. #facepalm.

By comparison, the IMHO less valuable Microbit proposal, for a politically driven educational tool that distracts from CS education, appears to have been supported by people with better understanding of the rules, and got through much more quickly. I don’t mind a microbit SE site, but … not if something so niche and political gets through at the cost of the CS Educators site (because it diverts attention away).

Solution: SO should change Area51’s visual design so that any question with 11 or more upvotes is displayed as “accepted” instead of a number, and the total number for each question is shown in smaller type somewhere else on the page.

“Commitment”

Guarding against the second concern is phase 2. With 80 people signed up as “committed” to microbit, and only 65 “committed” to CS Educators, microbit has now overtaken the older proposal. Right? Wrong.

Microbit proposal CS Educators proposal
Screen Shot 2016-10-05 at 12.33.01 Screen Shot 2016-10-05 at 12.32.53

Clicking the link at bottom right of each info panel shows that SO has a different approach at this stage. They use not one but three measurements to pass – it’s got harder.

Microbit would be winning here, except … SO judges you on the weakest link in the chain. And two of the three criteria are biased against people who don’t use SO much:

Microbit proposal CS Educators proposal

Screen Shot 2016-10-05 at 12.06.03

Screen Shot 2016-10-05 at 12.05.59

Measure 1: Total number of committers

Raw score of “how many people have clicked a button to say they believe this is a good site worth adding to the web”. Very much in the vein of SO.

EXCEPT: I see no “anti-commitment”; true SO ideals would suggest that we have a way to say “no, I don’t think this deserves a site” – and have it cost you some of your positive influence on committing to sites you do like. This is the essence of what made SO successful, and it’s intriguing that they’ve dropped it here.

I suspect (guess) that the relative infrequency of people proposing/committing to new sites (a few a year) vs voting/asking/answering SO questions (hundreds a year) means that the danger of people putting in negative votes at no effective personal cost was considered too likely. Or the cost to individuals of gaining enough positive commitments to “earn” the right to anti-commit was too high.

Measure 2: Require committers with > 200 reputation elsewhere

This is the classic gating strategy SO doubled-down on when they became too successful / too big: a requirement for minimum amount of positive reputation before enabling basic features that spammers tried to (Ab)use.

Earning 200 rep on “any” site is much too easy, and I think they’ve made a mistake here. It ought to be something like “earn 200 rep on 2 different sites, or 500 rep on one site”. I say this because over time SO rep has continual inflation problems, just like real-world currencies in live economies. A 200 rep barrier on one site is no barrier to people gaming the system – there are now so many obscure SE sites that it’s easy to find a gameable one. But finding multiple gameable ones would be substantially harder.

Measure 3: fudge factor

…this is the solution to the problems with Measure 2. I’d prefer a better Measure 2, but I can see value in having Measure 2 be very simple to describe, and then to fix the problems later.

Official stance on measure 3

The one piece of data we have that tells us a lot and is hard to game is a user’s reputation on the existing sites.

If you have a lot of reputation, you’re much more likely to actively use the site, because you’ve shown that you actively use similar sites

If you have a significant amount of reputation across multiple sites, you’re even more likely to actively use the site, because you’ve shown that you actively use many such sites

On the other hand, if you’re some random person off the internet with no reputation, you’re very hard to quantify but there’s a good chance that you won’t contribute very much

Here’s the formula we have right now. It’s almost certainly wrong and we’ll be tweaking it as we go:

Better than Civ6? Bookmarkable links for Civ4 mod: Master Of Mana sources

Master of Mana was a great game – much better than Civ5, and from what we’ve seen of Civ6, Firaxis is still playing catch-up in a few areas :).

The author has disappeared, and his website has been taken over by scammers (not even going to link it), but the community has kept going the SourceForge-hosted copy of the source and continues to update it. The files are ordered confusingly (inherited from previous projects, and Civ4 itself, which was mainly shipped as a commercial game, not as a moddable game!). Here’s a few key links to find interesting / useful game-design gems:

Simple #civ5 clone in Unity: hexes, movement, unit selection

Current features

commit 26eafb7865965fd5ef5ee3ad4863f00acf8d10a2

  • Generates hexes landscapes, with heights (Civ5 bored me by being flat-McFlat-in-flatland)
  • Every hex is selectable, using custom fix for Unity’s broken mouse-click handler (see below)
  • Any object sitting on landscape is selectable (ditto)
  • Selected units move if you click any of the adjacent hexes (shown using f-ugly green arrows on screenshot)

The green “you can move here” arrows look like spider-legs at the moment. #TotalFail. Next build I’m going to delete them (despite having spent ages tweaking the procgen mesh generation for them, sigh) and do something based on wireframe cages, I think.

Screen Shot 2016-04-11 at 22.59.25

Techniques

Hexes

I started with simple prototyping around hexes, but soon found that it’s worth investing the time to implement all the primitives in Amit’s page on Hexagon grids for games: http://www.redblobgames.com/grids/hexagons/

In practice, especially the ability to create a class that lets you do “setHex( HexCoord location, GameObject[] items )” and “getContentsOfHex( HexCoord location )” and things like “getNeighboursOf” … is very rapidly essential.

Mouse clicks in Unity

IMHO: work pretty badly. They require the physics engine, which – by definition – returns the WRONG answer when you ask “what did I click on?” (it randomises the answer every click!). They also fundamentally oppose Unity’s own core design (from the Editor: when you click any element of a prefab, it selects the prefab).

So I wrote my own “better mouse handler” that fixes all that. When you click in scene, it automatically propagates up the tree, finds any listeners, informs them what was clicked, and lets you write good, clean code. Unlike the Unity built-in version.

Procedural meshes for arrows

With hindsight, I should have just modelled these in blender. But I thought: I want a sinusoidal curve arrow; how hard can it be? I may want to animate it later, by destroying/adding points – that would be a lot of work with Unity’s partial animation system (it’s great for humanoids, less great for geometry) – but animating points in a mesh from C# code is super-easy.

In the end, I spent way too long tweaking the look, and on having 2-sided polygons that broke the Unity5 Standard shader by being too thin (on the plus side: I now know what that mistake looks like, and I’ll recognize it in future Unity projets. It has a very peculiar, unexpected, look to it).

I should have just made them in Blender, and – if I got as far as wanting to animate them – re-modelled in source code later (or found a “convert blender file to C vertices array” script, of which I’m sure there are hundreds on the web. Doh!

#lessonLearned.

Improved interactive GUI for Snap-and-Plug (glue/vertex snapping for complex objects in #Unity3d) #screenshotsaturday

Some screenshots from today’s improvements. I’m moving gradually towards releasing version 2. Shortlist of changes/improvements below…

From this mess … to this:
Screen Shot 2016-03-12 at 14.59.24 Screen Shot 2016-03-12 at 20.43.32
Building some odd machines to test it works:
Screen Shot 2016-03-12 at 15.00.21 Screen Shot 2016-03-12 at 19.50.44

Features and fixes recently added

  • Use shaded, materialed meshes for in-editor handles, instead of flat ugly rectangles and tris
  • Click/tap a socket’s handle to directly select it in the Scene view
  • Meshes are resized to fit the user-selected “socket size” variable
  • Only handles that are facing you are rendered; HUGE improvement for complex levels/machines/buildings/etc
  • Only handles you can see are clickable/draggable; HUGE improvement for complex scenes (where accidental clicks happened too often!)

Brief look at obvious #UX mistakes in Civilization 5 (and why you should never buy another Firaxis game)

Civilization was one of the best games ever designed and shipped.

Civ5 is tragic. It’s one thing to launch a AAA title full of nerfed gameplay and obvious, in-your-face bugs, but quite another to leave them unfixed for years after. It’s one thing to officially fix your bugs only in pay-for add-ons – but quite another to keep those add-ons at full price for years after they released.

Here’s a quick view of what’s still broken in Civ5 today, if you buy it direct in the online stores:

  • The game autosaves every 10 or so turns; this has NEVER been correct for Civilization (from memory, the original game used to save every other turn by default (maybe not; running out of disk space was a real concern back then); modern teams at Firaxis seem to be too amateurish to implement this. Civ 4 used to crash so much that putting it on “save every turn” was a requirement).
    • No-one at Firaxis should be “unaware” of the need for every-turn autosaves
    • I struggle to think of a rational explanation; best I can think of so far is some weak game-designer thinking that autosaves are “cheating”, so they decided to deliberately break the concept so it only half worked.
    • I haven’t yet found an easy way to un-break this in civ5. Given how crucial it is to the game, and how it’s been present in every previous version, it should be in the game-options, but it’s not. That’s two bugs for the price of 1!
  • The user-interface for moving units is more broken than in any version of Civ to date. Civ1 had a perfect system (but predated the existence of a mouse on every computer): units moved where you told them by pressing numeric keypad keys. Civ3 and Civ4 had “automatic” pathfinding that was badly broken: it often walked your units into 100% certain death for no reason.
    • Civ5 takes this one further: if a unit is selected and you move across another unit, civ5 moves BOTH units, causing double the catastrophe.
    • This automated action – that IME is almost NEVER what the player wanted to do, and is extremely destructive, frequently causing game-losing events – cannot be undone. This breaks the cardinal law of user-interfaces: if you do an automated, un-asked-for, action (which you generally shouldn’t) … then you MUST provide an Undo.
  • Civ5 also has a strangely bad algorithm for pathfinding: it generally takes 1-4 seconds to run the algorithm during which time the game lies about the game-rules, and claims that your unit is “immovable”.
    • This appears to be a junior programmer discovering “asynchronous” coding for the first time in their life, and not realising the obvious side-effects
    • I have no idea why the algorithm is so insanely slow. It is slowest in a huge game, but even in a tiny game, with nothing happening, and only a tiny game-world, it randomly takes anywhere from no time to 1-2 seconds to “switch on”
  • The buttons for “required” actions are deliberately placed in the worst-possible positions: the far OPPOSING corners of the screen.
    • This breaks the most basic and obvious guidelines in UX design
    • For bonus points, the buttons don’t get larger on large/wide screens. Those buttons are so small and so far away you rarely see them, let alone find it easy to press them
    • It’s as if the Firaxis team were out to beers with the misguided team at Microsoft who decided that Windows 8 would rely upon a single “magic pixel” to activate core functions, and thought: “hey, I know how we can really mess-up our players! That impossible-to-hit pixel idea is great! It’ll make the game so much harder!”
  • The interactive HUDs giving critical information on the global state of politics, that made Civ4 a significant improvement over previous versions – and that were extended massively by the community, increasing gameplay without removing any challenge … have been deleted.
    • The question begs: we know Firaxis has many people who’ve played the previous civs; how on earth did they forget how critical and popular the dashboards were?
    • The game is almost unplayable without dashboards. It’s a waste of time: you have to play solo, or click through a series of menus every single turn simply to find out the current status of your opponents. A massive step backwards in gameplay.
    • Best explanation I can think of: failed game-design strategy to “make it more mass-market friendly”.

That last point leads into the legion of game-design failures in Civ5. As I understand it, most of the game was “Designed” around the idea of dumbing-down: apparently the Youth of Today are so stupid and lazy that they cannot play games that are deep, enjoyable, or interesting. The way to make money is to make games idiot-proof with as few options as possible and no meaningful decisions.

Ironically, this is the exact opposite of what the legions of Civ fans had shown they valued in the Civ franchise, via the overwhelmingly popular mods for civ4. Master of Mana added depth, difference, more depth, more variety, more difference, and yet more depth, across the board. It hacked the tech tree into becoming 5 different tech-trees, all running in parallel (WTF? Oh, yes!) – and players loved it.

One day, I may write a post on the flow of game design, successes and failures, and the #facepalm that civ3 and civ5 were (between the two of them, both abject failures). Strangely enough … the two things in civ5 that I remember the community being most afraid of (hexes and 1-unit-per-tile) … seem to have worked fine. The radical changes were a success; it was all the easy, “you can’t possibly screw this up”, parts that the dev-team screwed up. And that is why I consider civ5 “tragic”: they got the hardest bits right, despite the odds … and tripped over their own shoelaces messing-up the easy bits.

Civ4 had a similar trajectory, with two differences:

  1. It appeared to be a legitimate mistake: they didn’t realise until after shipping how broken their own game was
  2. Within a couple of years, the add-ons were being bundled with the core game for free, or at most five dollars. As they should be: they were mostly re-adding content that had been removed, and fixing launch-bugs, with only a tiny sprinkling of extra content/changes.

For Civ5, someone in charge (publisher? studio director?) appears to have decided: “hey, we shafted the consumers and exploited the franchise well there – but we could do so much better! Let’s do it deliberately this time: save money by deliberately shipping incomplete product, then use online market-controls to force everyone to pay 3 times to get a working game! We’ll be RICH!”.

In their defence, Firaxis did ship one major content update for free, which was wonderful: they added retina support. That’s unnecessary (not a bug, retina’s didn’t exist when it came out) and nice to have – but in no way justifies ignoring the rest.

#Unity3d hardware usage + implications – Summer 2015

There’s tonnes of blogs out there, so I only talk about the bits that other people have missed, or were too polite or inexperienced to cover. Often that means I’m the one pointing out the flaws (most people don’t want to write bad things. Screw that; ignoring the bad points does you no favours!).

Sometimes I get to talk about the good bits that – sadly – few people have noticed. Here’s one of those.
Continue reading

New #unity3d feature: Virtual Scenes

Unity3D has a great core architecture – it’s easy to understand and use. However, it has some significant flaws.

One of the recurring problems I run into is that Unity requirs you to have precisely one “Scene” at any one time, but often you need to have multiple scenes at the same time. Problem? Yes, lots…

Unity 5 has some hacks to make it “sort-of possible” to have multiple scenes at once in-Editor.

Note: these were mentioned by Unity corp in August 2014, but aren’t available to most users yet

But they (appear to be) hacks: they help for a fraction of the use-cases. That’s fine: Unity has 10 years of software written on the assumption there is only one “Scene”; that’s an enormous amount of code to change! But can we do something about this?

TL;DR: I’ll put this on the Asset Store

If you just want a working solution, here’s the Unity Asset store page / support page, new versions will appear here first.

I’m using it myself on my own projects, and will do some beta testing with other people’s games. If it works well enough, it’ll go on Asset Store. I suggest reading this full post anyway – it’s an example of how to creatively solve small issues like this in Unity.

(if you’d like to beta-test this, tweet me @t_machine_org or email me (address at top of page). Unity Corp only let me have 12 beta-testers, so you’ll need to give me some info about what you’ll use it for, how soon, how much feedback you’ll give me, etc! Sorry :( )

Continue reading

Writing a #unity3d mini-game … to help you design a AAA game

One of my hobby projects is a testament to the Ultima and Elder Scrolls games – a massive open-world, where everything you do impacts the world around you. This has long been promised by commercial games – and it sucks from a gameplay perspective; it’s just not fun. But a very old ASCII-graphics game, Omega, showed a couple of ways of doing it that delivered on that promise while still being “fun” – very fun! That’s what I’m working towards.

It’s a test-bed for the high-performance Entity System I’m writing for Unity (more info here). I’m aiming for “gameplay considerably richer than Skyrim” with “graphics about the level of Oblivion”. To be clear: Oblivion was released almost 10 years ago! To reproduce those graphics today is fairly easy.

Challenge: Believable Cities that evolve over time

One of the things I have yet to see in any FPS RPG is believable cities, and more: cities that actually evolve. The nearest I’ve seen is the beautiful “large towns” of the Assassin’s Creed series (they represent cities, but the distances are way too small).

That doesn’t cover the “evolve” part though – even the AC cities are 100% static and unchanging. Hand-crafted, and because they cannot change (technical design choice) the player is incapable of altering them. You can’t burn down blocks, or build a new bridge. You can’t buy two houses and knock them together.

Hey, RPG industry, you can do a lot better!

This is one of the main new gameplay elements in my design. If all I managed was to take an off-the-shelf-RPG mod and add living, growing cities … I’d probably be content. What does this mean, though?
Continue reading

#UX conveying critical info to public via number rating: Food Hygiene Stickers

How do you make good UX / GUI to present information to a mass-market audience with widely varying levels of education and attention-span?

This is a problem faced all the time by game designers and developers. It’s one of the most under-appreciated skills of the profession: good game developers know more about “presenting information and choices” than almost anyone else, anywhere. Because games are generally overloaded with info, and the dev teams have to filter that down and present it clearly – but if they get it wrong, the player’s in-game character dies, the game is lost, and the game itself tanks commercially. The developers then – ultimately – lose their jobs when the studio goes bust.

I’m going to start looking at non-tech examples of design and UX through the lens of game-design, and see where it goes…
Continue reading

2015 talk: Progress on An Entity System for #Unity3d

Slides from my talk last night at Unity Brighton.

Three parts:

  1. First: introduction / overview of Entity Systems, and why you care (as a “person who makes games”)
  2. Second: Progress so far: screenshots of the Unity Editor with explanation of the new features I’ve added
  3. Third: Challenges and solutions I’ve encountered so far

Aliqua-progress-2015-BUUG-v3

WordPress, HTML, the web etc – don’t support “presentations” yet. No, I’m not creating a fake Slideshare account just so you can wait ages for a non-bookmarkable slide viewer to (slowly) load. Until then … we have PDF. Enjoy!

Rogue2015 April update

Added a level-select screen:

Screen Shot 2015-03-30 at 02.59.45

I say “level-select”, but … that background is a full 3D terrain, and the cities are procedurally generated/unlocked, so … it’ll hopefully become something a lot more, eventually.

Blender tips: set your 3D lights for edit mode

When you first install Blender, DO THIS!

Menu: File > User Preferences… > System

Screen Shot 2015-03-04 at 10.02.37

When you look at objects in edit mode, they’ll look something like this:

Screen Shot 2015-03-04 at 10.02.49

Why?

Blender makes it very easy to get a face back-to-front.

Or to have two faces overlapping.

Or … any number of other topology bugs. At best, these kill performance in any game that uses them. At worst, they cause nightmares for your programmers and level architects when Weird Stuff Keeps Happening. They can even cause crashes (e.g. a surface that has strange holes, or inside-out faces … and then gets processed by collision detection).

This lighting setup tells you at a glance if your normals are correct. Which in turn tells you if you have pieces out of place, or if you have an angle between faces that’s smaller/bigger than you expected (quite common to spot a pair of faces that have a sharper angle than expected/intended).

Bonus: 3D printing

If you’re 3d printing, the mistakes that slow down or crash a Game engine … will cause 100% failure of prints (Wasted time, wasted plastic – and in some cases I’ve seen: damaged printers!).

So, yeah. Getting this wrong can cost thousands of dollars. Don’t do it; replace Blender’s defaults with something sane that works :).

Blender UX for the lose

This should be the default. But then … Blender’s team seems philosophically opposed to doing anything the easy way :).

How much should you use a Scripting language when writing a Game?

Ask 10 game developers if you should use more script code or less, and you will get 11 different answers. They are all correct: it’s very situation-specific. Use of scripting languages is highly dependent on the humans and the practical / project-management issues.

Why?
Continue reading

Debugging A* Pathfinding in Unity

I needed fast, efficient, … but powerful, adaptable … pathfinding for my hobby project. My minions have to fly, walk, crawl, teleport, tunnel their way across a procedural landscape. Getting to that point has been tricky, but the journey’s been interesting.

We want something that intelligently routes creatures around obstacles, and picks “shallow” routes instead of scaling cliffs (or vice versa for Giant Spiders etc). Something like this:

Screen Shot 2014-08-10 at 20.09.36

Continue reading

World-exploration game, done differently

Inspired by Markus / @notch, and how he got MineCraft going in the early days, I’m live-prototyping a game idea I’ve been thinking about for ages. It’s about exploring a landscape … where cities affect dungeons, and dungeons affect cities.

(this is stress-relief for me, an “evenings and weekends” project. By day, I’m helping Schools teach children to program, but that’s HARD (no investors, lots of costs – at the moment, I get paid nothing))

Play in web browser here (very early prototype!)

Screen Shot 2014-07-25 at 12.31.23

July 2014

Current build focusses on the “City building” interface. Initially, you won’t be building cities, you’ll be building small camps / trading forts, etc. So this lets me play with the interface, the scale, the rendering, etc. Make sure it’s fun.

Create something – but take screenshots! Because there’s no “save” yet. Super-early prototype.

Long term gameplay

  1. Explore a huge landscape in FPS
  2. Any location, “create a camp”, and it switches to the isometric view you see in current demo. Build yourself a home/fort/etc.
  3. Fast-travel between locations, but this triggers “random encounter” events … or run between locations manually.
  4. Turn-based / DungeonMaster style dungeons are randomly generated near to each camp. Explore the dungeons for resources and to level-up.

Unlike e.g. Skyrim … when you find an interesting location, you can’t fast-travel to it. You have to build a camp next to it, and fast-travel to that. But your camp can be overrun/destroyed/stolen while you’re away.

So … you’ll be building (and maintaining) a lot of bases around the world. I want to be sure that base-building is easy and fun, even after you’ve done it lots of times already, before progressing with the rest!

(I’m trying to make it “repeatably fun” by having the landscape HUGELY affect your base design)

How to Become a Game Designer (2014)

Step 1: Do not buy the book with this title.

Writing a book is tough, and I respect the time and effort that goes into it. But I don’t rate a book highly simply because it was hard to write: it has to fulfil it’s purpose, and help the reader. Some books are so poor they actively hinder the reader.

This one is being marketed to bloggers to promote it (for cash) without reading it. This (no review copies) might be a beginner’s mistake. I hope so; the alternative is horribly cynical.

For bonus points, the email was sent from a bouncing email address. If you want a job in the games industry, you probably don’t want to be advised by someone so careless/clueless they send out emails from broken email accounts.

That annoyed me enough to look through the marketing materials for this book, and it seems weak.

The author does not appear to have been a recruiter, nor a hiring manager, and apparently has never run a studio. If you read a book on this topic – make sure the author has spent years recruiting, hiring, and managing people in the industry. That’s the core expertise you want from the author – if they don’t have it, they need a really good excuse.

Further, the title seems deliberately misleading – linkbait for readers. It’s titled “become a game designer” but the content appears to be “get a job, somehow, doing something – anything you can scrape-by on – in the games industry”. Core topics are missing from those listed – e.g. how to advance your skills as a game-designer (key to getting hired!), etc.

…but I haven’t read the book, so I can only give vague suggestions and guesses at what it contains.

TL;DR

Personally I’d steer clear of all such books, and spend the time entering Game Jams instead. Every jam you enter will teach you more, and give you more experience that’s directly exciting to hiring managers, than reading books like this one.

I have classes of teenagers making their own games with little or no help; if they can do it, why can’t you?

Data Structures for Entity Systems: Contiguous memory

This year I’m working on two different projects that need an Entity System (ES). One of them is a non-game app written natively on iOS + Android. The other is an FPS in Unity3D.

There are good, basic Open-Source ES’s out there today (and c.f. the sidebar there). I tried porting a few, but none of them were optimized for performance, and most of them were too tightly coupled to a single programming language or platform. I’ve started a new ES of my own – Aliqua.org – to fix these problems, and I’m already using it in an app that’s in alpha-testing.

I’ll be blogging experiences, challenges, and ideas as I go.

2016 Update: Support me on Patreon, writing about Entity Systems and sharing tech demos and code examples

Background: focus on ES theory, or ES practice?

If you’re new to ES’s, you should read my old blog posts (2007 onwards), or some of the source code + articles from the ES wiki.

My posts focussed on theory: I wanted to inspire developers, and get people using an ES effectively. I was fighting institutionalised mistakes – e.g. the over-use of OOP in ES development – and I wrote provocatively to try and shock people out of their habits.

But I avoided telling people “how” to implement their ES. At the extreme, I feared it would end up specifying a complete Game Engine:

…OK. Fine. 7 years later, ES’s are widely understood and used well. It’s time to look at the practice: how do you make a “good” ES?

NB: I’ve always assumed that well-resourced teams – e.g. AAA studios – need no help writing a good ES. That’s why I focussed on theory: once you grok it, implementation concerns are no different from writing any game-engine code. These posts are aimed at non-AAA teams: those who lack the money (or expertise) to make an optimized ES first time around.

For my new ES library, I’m starting with the basics: Data Structures, and how you store your ES data in memory.

Where you see something that can be done better – please comment!

Aside on Terminology: “Processors, née Systems”

ES “Systems” should be batch-processing algorithms: you give them an array/stream of homogeneous data, and they repeat one algorithm on each row/item. Calling them “Processors” instead of “Systems” reduces confusion.

Why care about Data Structures?

There is a tension at the heart of Entity Systems:

  • In an ES game, we design our code to be Functional: independent, data-oriented, highly efficient for streaming, batching, and multi-threaded execution. Individual Processors should be largely independent, and easy to split out onto different CPU cores.
  • With the “Entity” (ID) itself, we tie those Functional chunks together into big, messy, inter-dependent, cross-functional … well, pretty much: BLOBs. And we expect everything to Just Work.

If our code/data were purely independent, we’d have many options for writing high-performance code in easy ways.

If our data were purely chunked, fixed at compile-time, we’d have tools that could auto-generate great code.

But combining the two, and muddling it around at runtime, poses tricky problems. For instance:

  1. Debugging: we’ve gone from clean, separable code you can hold in your head … to amorphous chunks that keep swelling and contracting from frame-to-frame. Ugh.
  2. Performance: we pretend that ES’s are fast, cache-efficient, streamable … but at runtime they’re the opposite: re-assembled every frame from their constituent parts, scattered all over memory
  3. Determinism: BLOBs are infamously difficult to reason about. How big? What’s in them? What’s the access cost? … we probably don’t know.

With a little care, ES’s handle these challenges well. Today I’m focussing on performance. Let’s look at the core need here:

  • Each frame, we must:
    1. Iterate over all the Processors
    2. For each Processor:
      1. Establish what subset of Entity/Component blobs it needs (e.g. “everything that has both a Position and a Velocity”)
      2. Select that from the global Entity/Component pool
      3. Send the data to the CPU, along with the code for the Processor itself

The easiest way to implement selection is to use Maps (aka Associative Arrays, aka Dictionaries). Each Processor asks for “all Components that meet [some criteria]”, and you jump around in memory, looking them up and putting them into a List, which you hand to the Processor.

But Maps scatter their data randomly across RAM, by design. And the words “jump around in memory” should have every game-developer whimpering: performance will be bad, very bad.

NB: my original ES articles not only use Maps, but give complete source implementations using them. To recap: even in 2011, Android phones could run realtime 30 FPS games using this. It’s slow – but fast enough for simple games

Volume of data in an ES game

We need some figures as a reference point. There’s not enough detailed analysis of ES’s in particular, so a while back I wrote an analysis of Components needed to make a Bomberman clone.

…that’s effectively a high-end mobile game / mid-tier desktop game.

Reaching back to 2003, we also have the slides from Scott’s GDC talk on Dungeon Siege.

…that’s effectively a (slightly old) AAA desktop game.

From that, we can predict:

  • Number of Component-types: 50 for AA, 150 for AAA
  • Number of unique assemblages (sets of Component-types on an Entity): 1k for AA, 10k for AAA
  • Number of Entities at runtime: 20k for AA, 100k for AAA
  • Size of each Component in bytes: 64bits * 10-50 primitives = 100-500 bytes

How do OS’s process data, fast?

In a modern game the sheer volume of data slows a modern computer to a crawl – unless you co-operate with the OS and Hardware. This is true of all games. CPU and RAM both run at a multiple of the bus-speed – the read/write part is massively slow compared to the CPU’s execution speed.

OS’s reduce this problem by pre-emptively reading chunks of memory and caching them on-board the CPU (or near enough). If the CPU is processing M1, it probably wants M2 next. You transfer M2 … Mn in parallel, and if the CPU asks for them next, it doesn’t have to wait.

Similarly, RAM hardware reads whole rows of data at once, and can transfer it faster than if you asked for each individual byte.

Net effect: Contiguous memory is King

If you store your data contiguously in RAM, it’ll be fast onto the Bus, the CPU will pre-fetch it, and it’ll remain in cache long enough for the CPU(s) to use it with no extra delays.

NB: this is independent of the programming-language you’re using. In C/C++ you can directly control the data flow, and manually optimize CPU-caching – but whatever language you use, it’ll be compiled down to something similar. Careful selection and use of data-structures will improve CPU/cache performance in almost all languages

But this requires that your CPU reads and writes that data in increasing order: M1, M2, M3, …, M(n).

With Data Structures, we’ll prioritize meeting these targets:

  1. All data will be as contiguous in RAM as possible; it might not be tightly-packed, but it will always be “in order”
  2. All EntitySystem Processors will process their data – every frame (tick) – in the order it sits in RAM
    • NOTE: a huge advantage of ES’s (when used correctly) is that they don’t care what order you process your gameobjects. This simplifies our performance problems
  3. Keep the structures simple and easy to use/debug
  4. Type-safety, compile-time checks, and auto-complete FTW.

The problem in detail: What goes wrong?

When talking about ES’s we often say that they allow or support contiguous data-access. What’s the problem? Isn’t that what we want?

NB: I’ll focus on C as the reference language because it’s the closest to raw hardware. This makes it easier to describe what’s happening, and to understand the nuances. However, these techniques should also be possible directly in your language of choice. e.g. Java’s ByteBuffer, Objective-C’s built-in C, etc.

Usually you see examples like a simple “Renderer” Processor:

  • Reads all Position components
    • (Position: { float: x, float y })
  • Each tick, draws a 10px x 10px black square at the Position of each Component

We can store all Position components in a tightly-packed Array:

compressed-simple-array

This is the most efficient way a computer can store / process them – everything contiguous, no wasted space. It also gives us the smallest possible memory footprint, and lets the RAM + Bus + CPU perform at top speed. It probably runs as fast or faster than any other engine architecture.

But … in reality, that’s uncommon or rare.

The hard case: One Processor reads/writes multiple Component-types

To see why, think about how we’d update the Positions. Perhaps a simple “Movement” Processor:

  • Reads all Position components and all Velocity components
    • (Position: { float: x, float y })
    • (Velocity: { float: dx, float dy })
  • Each tick, scales Velocity.dx by frame-time, and adds it to Position.x (and repeats for .dy / .y)
  • Writes the results directly to the Position components

“Houston, we have a problem”

This is no longer possible with a single, purely homogeneous array. There are many ways we can go from here, but none of them are as trivial or efficient as the tight-packed array we had before.

Depending on our Data Structure, we may be able to make a semi-homogeneous array: one that alternates “Position, Velocity, Position, Velocity, …” – or even an array-of-structs, with a struct that wraps: “{ Position, Velocity }”.

…or maybe not. This is where most of our effort will go.

The third scenario: Cross-referencing

There’s one more case we need to consider. Some games (for instance) let you pick up items and store them in an inventory. ARGH!

…this gives us an association not between Components (which we could handle by putting them on the same Entity), but between Entities.

To act on this, one of our Processors will be iterating across contiguous memory and will suddenly (unpredictably) need to read/write the data for a different Entity (and probably a different ComponentType) elsewhere.

This is slow and problematic, but it only happens thousands of times per second … while the other cases happen millions of times (they have to read EVERYTHING, multiple times – once per Processor). We’ll optimize the main cases first, and I’ll leave this one for a later post.

Iterating towards a solution…

So … our common-but-difficult case is: Processors reading multiple Components in parallel. We need a good DS to handle this.

Iteration 1: a BigArray per ComponentType

The most obvious way forwards is to store the EntityID of each row into our Arrays, so that you can match rows from different Arrays.

If we have a lot of spare memory, instead of “tightly-packing” our data into Arrays, we can use the array-index itself as the EntityID. This works because our EntityID’s are defined as integers – the same as an array-index.

rect3859

Usage algorithm:

  • For iterating, we send the whole Array at once
  • When a Processor needs to access N Components, we send it N * big-arrays
  • For random access, we can directly jump to the memory location
    • The Memory location is: (base address of Array) + (Component-size * EntityID)
    • The base-address can easily be kept/cached with the CPU while iterating
    • Bonus: Random access isn’t especially random; with some work, we could optimize it further

Problem 1: Blows the cache

This approach works for our “simple” scenario (1 Component / Processor). It seems to work for our “complex” case (multiple Components / Processor) – but in practice it fails.

We iterate through the Position array, and at each line we now have enough info to fetch the related row from the Velocity array. If both arrays are small enough to fit inside the CPU’s L1 cache (or at least the L2), then we’ll be OK.

Each instance is 500 bytes
Each BigArray has 20k entries

Total: 10 MegaBytes per BigArray

This quickly overwhelms the caches (even an L3 Cache would struggle to hold a single BigArray, let alone multiple). What happens net depends a lot on both the algorithm (does it read both arrays on every row? every 10th row?), and the platform (how does the OS handle RAM reads when the CPU cache is overloaded?).

We can optimize this per-platform, but I’d prefer to avoid the situation.

Problem 2: memory usage

Our typeArray’s will need to be approimately 10 megabytes each:

For 1 Component type: 20,000 Entities * 50 variables * 8 bytes each = 8 MB

…and that’s not so bad. Smaller components will give smaller typeArrays, helping a bit. And with a maximum of 50 unique ComponentTypes, we’ve got an upper bound of 500 MB for our entire ES. On a modern desktop, that’s bearable.

But if we’re doing mobile (Apple devices in 2014 still ship with 512 MB RAM), we’re way too big. Or if we’re doing dynamic textures and/or geometry, we’ll lose a lot of RAM to them, and be in trouble even on desktop.

Problem 3: streaming cost

This is tied to RAM usage, but sometimes it presents a bottleneck before you run out of memory.

The data has to be streamed from RAM to the CPU. If the data is purely contiguous (for each component-type, it is!), this will be “fast”, but … 500 MB data / frame? DDR3 peaks around 10 Gigabytes / second, i.e.:

Peak frame rate: 20 FPS … divided by the number of Processors

1 FPS sound good? No? Oh.

Summary: works for small games

If you can reduce your entity count by a factor of 10 (or even better: 100), this approach works fine.

  • Memory usage was only slightly too big; a factor of 10 reduction and we’re fine
  • CPU caching algorithms are often “good enough” to handle this for small datasets

The current build of Aliqua is using this approach. Not because I like it, but because it’s extremely quick and easy to implement. You can get surprisingly far with this approach – MyEarth runs at 60 FPS on an iPad, with almost no detectable overhead from the ES.

Iteration 2: the Mega-Array of Doom

Even on a small game, we often want to burst up to 100,000+ Entities. There are many things we could do to reduce RAM usage, but our biggest problem is the de-contiguous data (multiple independent Arrays). We shot ourselves in the foot. If we can fix that, our code will scale better.

es-datastructures-structured-bigarray

In an ideal world, the CPU wants us to interleave the components for each Entity. i.e. all the Components for a single Entity are adjacent in memory. When a Processor needs to “read from the Velocity and write to the Position”, it has both of them immediately to hand.

Problem 1: Interleaving only works for one set at a time

If we interleave “all Position’s with all Velocity’s”, we can’t interleave either of them with anything else. The Velocity’s are probably being generated by a different Processor – e.g. a Physics Engine – from yet another ComponentType.

mega-array

So, ultimately, the mega-array only lets us optimize one Processor – all the rest will find their data scattered semi-randomly across the mega-array.

NB: this may be acceptable for your game; I’ve seen cases where one or two Processors accounted for most of the CPU time. The authors optimized the DS for one Processor (and/or had a duplicate copy for the other Processor), and got enough speed boost not to worry about the rest

Summary: didn’t really help?

The Mega Array is too big, and it’s too interconnected. In a lot of ways, our “lots of smaller arrays – one per ComponentType” was a closer fit. Our Processors are mostly independent of one another, so our ideal Data Structure will probably consist of multiple independent structures.

Perhaps there’s a halfway-house?

Iteration 3: Add internal structure to our MegaArray

When you use an Entity System in a real game, and start debugging, you notice something interesting. Most people start with an EntityID counter that increases by 1 each time a new Entity is created. A side-effect is that the layout of components on entities becomes a “map” of your source code, showing how it executed, and in what order.

e.g. With the Iteration-1 BigArrays, my Position’s array might look like this:

rect3859

  1. First entity was an on-screen “loading” message, that needed a position
  2. BLANK (next entity holds info to say if loading is finished yet, which never renders, so has no position)
  3. BLANK (next entity is the metadata for the texture I’m loading in background; again: no position)
  4. Fourth entity is a 3d object which I’ll apply the texture to. I create this once the texture has finished loading, so that I can remove the “loading” message and display the object instead
  5. …etc

If the EntityID’s were generated randomly, I couldn’t say which Component was which simply by looking at the Array like this. Most ES’s generate ID’s sequentially because it’s fast, it’s easy to debug (and because “lastID++;” is quick to type ;)). But do they need to? Nope.

If we generate ID’s intelligently, we could impose some structure on our MegaArray, and simplify the problems…

  1. Whenever a new Entity is created, the caller gives a “hint” of the Component Types that entity is likely to acquire at some time during this run of the app
  2. Each time a new unique hint is presented, the EntitySystem pre-reserves a block of EntityID’s for “this and all future entities using the same hint”
  3. If a range runs out, no problem: we add a new range to the end of the MegaArray, with the same spec, and duplicate the range in the mini-table.
  4. Per frame, per Processor: we send a set of ranges within the MegaArray that are needed. The gaps will slow-down the RAM-to-CPU transfer a little – but not much

es-datastructures-structured-megaarray

Problem 1: Heterogeneity

Problem 1 from the MegaArray approach has been improved, but not completely solved.

When a new Entity is created that intends to have Position, Velocity, and Physics … do we include it as “Pos, Vel”, “Pos, Phys” … or create a new template, and append it at end of our MegaArray?

If we include it as a new template, and insist that templates are authoritative (i.e. the range for “Pos, Vel” templates only includes Entities with those Components, and no others) … we’ll rapidly fragment our mini-table. Every time an Entity gains or loses a Component, it will cause a split in the mini-table range.

Alternatively, if we define templates as indicative (i.e. the range for “Pos, Vel” contains things that are usually, but not always Pos + Vel combos), we’ll need some additional info to remember precisely which entities in that range really do have Pos + Vel.

Problem 2: Heterogeneity and Fragmentation from gaining/losing Components

When an Entity loses a Component, or gains one, it will mess-up our mini-table of ranges. The approach suggested above will work … the mini-table will tend to get more and more fragmented over time. Eventually every range is only one item long. At that point, we’ll be wasting a lot of bus-time and CPU-cache simply tracking which Entity is where.

NB: As far as I remember, it’s impossible to escape Fragmentation when working with dynamic data-structures – it’s a fundamental side effect of mutable data. So long as our fragmentating problems are “small” I’ll be happy.

Problem 3: Heterogeneity and Finding the Components within the Array

If we know that “Entity 4” starts at byte-offset “2048”, and might have a Position and Velocity, that’s great.

But where do we find the Position? And the Velocity?

They’re at “some” offset from 2048 … but unless we know all the Components stored for Entity 4 … and what order they were appended / replaced … we have no idea which. Raw array-data is typeless by nature…

Iteration 4: More explicit structure; more indexing tables

We add a table holding “where does each Entity start”, and tables for each Component stating “offset for that Component within each Entity”. Conveniently, this also gives us a small, efficient index of “which Entities have Component (whatever)”:

es-datastructures-structured-megaarray-by-component

Problem 1: non-contiguous data!

To iterate over our gameobjects, we now need:

  • One big mega-array (contiguous)
  • N x mini arrays (probably scattered around memory)

Back to square one? Not quite – the mini-arrays are tiny. If we assume a limit of 128,000 entities, and at most 8kb of data for all Components on an Entity, our tables will be:

[ID: 17bits][Offset: 13 bits] = 30 bits per Component

…so that each mini-array is 1-40 kB in size. That’s small enough that several could fit in the cache at once.

Good enough? Maybe…

At this point, our iterations are quite good, but we’re seeing some recurring problems:

  • Re-allocation of arrays when Components are added/removed (I’ve not covered this above – if you’re not familiar with the problem, google “C dynamic array”)
  • Fragmentation (affects every iteration after Iteration 1, which doesn’t get any worse simple because it’s already as bad as it could be)
  • Cross-referencing (which I skipped)

I’ve also omitted history-tracking – none of the DS’s above facilitate snapshots or deltas of game state. This doesn’t matter for e.g. rendering – but for e.g. network code it becomes extremely important.

There’s also an elephant in the room: multi-threaded access to the ES. Some ES’s, and ES-related engines (*cough*Unity*cough*), simply give-up on MT. But the basis of an ES – independent, stateless, batch-oriented programming – is perfect for multi threading. So there must be a good way of getting there…

…which gives me a whole bunch of things to look at in future posts :).

PS … thanks to:

Writing these things takes ages. So much to say, so hard to keep it concise. I inflicted early drafts of this on a lot of people, and I wanted to say “thanks, guys” :). In no particular order (and sorry in advance if final version cut bits you thought should be in there, or vice versa): TCE’ers (especially Dog, Simon Cooke, doihaveto, archangelmorph, Hypercube, et al), ADB’ers (Amir Ebrahimi, Yggy King, Joseph Simons, Alex Darby, Thomas Young, etc). Final edit – and any stupid mistakes – are mine, but those people helped a lot with improving, simplifying, and explaining what I was trying to say.

2014 Entity Systems: what are your Unity3D questions and problems?

In 2014, I’ll be making a new game in Unity that makes intensive use of an Entity System.

This will give me lots of ammo for a new post exploring the pros and cons of Unity’s “partial” Entity System architecture. I’ve been thinking about this a lot for the last couple of years, but I’ve been unhappy with the draft posts, and didn’t publish them.

Over the next couple of months, I’d love to hear from all of you the challenges, confusions, problems, and questions you have about this. I’m not promising quick answers – but it will help shape the blog posts I write, and as soon as I have a good enough set of answers, I’ll start posting them :).
Continue reading