RockPaperShotgun – one of the few games “journalism” (hah!) sites I read – just syndicated another video from the Eurogamer Expo, this one is on the Witcher 3. The video itself is not worth watching – it contains (after the requisite 8 minutes of watching people walking into a room) two trailers that were previously released, and a fairly unenlightening talk.
Those of us who have just tuned in may not be familiar with the Witcher series. It started as a series of stories (novels and shorts) from Polish author Andrzej Sapkowski. Surprisingly, that’s all you need to know about the source material – as CD Projekt – a game studio that (I believe) got its start doing translations for other companies (notably Interplay, in the form of the Polish edition of Baldur’s Gate), took the setting and characters and ran with it, picking up where the author left off to make the Neverwinter Nights-Engine powered The Witcher. The game was pretty good, managing to bury a workable RPG system and a pretty good story under layers of that indescribable roughness that European games have. I liked it a lot, but what I really liked was its sequel, the ensubtitled Witcher 2: Assassins of Kings.
At this point, if you are an RPG fan and haven’t played it, go to GOG (another CD Projekt company) and buy it. Immediately. TW2 still had the Euro-game charm (to be honest, I think it’s something about their UIs and sound design – I think they just don’t have the feedback right), but it delivered in spades with an incredible story, amazing characterization (of the main characters, that is – the side quests… not so much), and an adventure that felt driven and personal. This was all topped with a gooey layer of visuals, TW2’s engine and art design is beautiful.
Okay, with the table set, let’s move on to the main course: what is interesting about the talk has to do with The Witcher 3 being an open world game. This poses a lot of interesting questions (concerns?) that the presentation was meant to address. Now, don’t get me wrong, I like open world games. Skyrim, Oblivion, Fallout, Morrowind etc are all games that I have sunk hundreds of hours in to, but they provide a different experience. Skyrim, for example, isn’t really about the story; it’s equal parts exploration, killing people during exploration, and real estate. Well, that and wondering who on earth makes those top mods on Nexus*. As an aside, I find particularly amusing that Dragon Age 3 was originally going to be open world-ish, although it looks like they’ve toned that down a bit. In the case of DA3, I think it was mainly due to Dragon Age 2 being an absolute pile of garbage and having no retention. Some exec probably went “oh, we didn’t sell 10 million units? I hear Skyrim did! Make that!”** However, the CD Projekt guy went to great pains to claim it was an “immersion building” “technique” rather than a back of the box dot point.
So the question posed (by his powerpoint) was, essentially: “how can you make an open world game and keep the narrative focused and cinematic?” It’s a really difficult question to answer; players (much like artists – programmer joke) just do not do what you expect them to – and if you give them the ability to walk around freely, the problem multiplies immensely. TW2 had a lot of tense situations which would have completely broken down if you could have gone for a long stroll down on the beach or decided to pick some mushrooms and relax in your comfy house. Any sense of urgency driving a narrative is going to be short circuited before the first jizzing dicknipple mod is hot out of the festering pits of the Nexus Network. I can only assume they will play fast and loose with the freedom of the player, locking them in a scene until the next block of the main quest resolves itself.
Another point he made (to himself) was that open world games have a nasty habit of becoming quite generic and repetitive (*cough* Bethesda *cough*), although he gave some lame reason why that wouldn’t be an issue in TW3 (the reason was so weak I can’t even paraphrase it, and that is unheard of). They’ve also attacked these issues as they appear in Skyrim and said that they will avoid them using ~*methods*~. Finally, he mentioned problems that players might have following the interaction between NPCs and factions, especially if you’re not railroaded in a traditional way. This is probably not as big an issue for CDPR, as they have some really, really good character writers and their NPC design is probably the best in the business right now. Also unlike Skyrim, they may hire more than 3 voice actors, which would go a long way to providing diversity. Mind you, they also mentioned a concrete solution to that, animated “storybooks” and flashbacks. It sounds okay in theory, but it’s one of those things that could come off very cheesy and strange – just try imagining how the game will explain things to you; yes, this person hates you because you murdered his whole family, remember? [cut to flaming village and moody voiceover] [cut back to conversation – unlock new dialogue option].
I don’t want to see one of the best RPG franchises compromised by trying to chase an unreasonable goal, but on the other hand, at least they know it’s a concern. Something he didn’t mention is overall progression – if I choose to go to city B before city A, what happens? The fact that RPGs have a character who becomes stronger during the game causes horrible scaling issues when the design isn’t laid out. I mean, Bethesda’s level scaling is notoriously bad, but it is in many ways a necessary evil. Fallout 3: New Vegas tried really hard to get you to go a certain route, by putting impassable mountains and insta-kill monsters across many of the paths over the map, but when you do that I think you need to ask yourself what you’re getting from the open world after all. Not to mention issues around a coherent main plot – I don’t see CDPR going down the Bioware “4 disconnected regions and a finale” approach to game design, but it is another way to solve the issue.
It’ll be an interesting product, that’s for sure. I’m hoping to eat my misgivings for lunch once it comes out and blows us away. Maybe it’ll set a precedent – a cinematic, rich adventure set in a completely different framework. I can only hope.
* And then installing them, for “research purposes”
** Also because DA3 is built on Frostbite (3?), it theoretically could do quite big game worlds.
So I was watching the talks from Microsoft’s Going Native conference – it was the typical mix of modern C++ nonsense; all make_unique, rvalue references and, my new favourite*, the promise of decltype(auto) for function return types. As I watched Scott Meyers’ talk (don’t bother, it’s not worth it – here is a summary “words words words std::move words”, only imagine it going on for 59 more minutes), something caught my eye (apart from his hair, I mean – I honestly don’t know how that is legal in this day and age – and this is coming from someone whose locks look “hobbit like” on a good day), namely a bit of code and a weird justification:
void Function(const std::string argument)
{
// Do some stuff with the string here
}
After showing this, he said that the argument was passed by value “for speed“, which I can only assume was some kind of mouth-based typo for “inefficiency” (or possibly “contrivance, so I can talk about std::move until all of you congeal”). To his – and his hair’s – credit, he then took back the suggestion that it was actually faster, pointing instead to someone’s blog post as the source of the confusion. My curiosity piqued, I went in search of the post in question.
* Please don’t use this.
Just a quick post about Thief – Eidos Montreal got a talking shape to badly ramble about the new reimagining of the classic series at the Eurogamer Expo (I can’t believe that is a thing these days) – the video is on youtube here. Skip to about 12 minutes in for the level.
Notable points – they demo a level, which looks fantastic, Garret’s new voice actor is almost impossibly worse than the old one, and apparently your secondary resource (“focus”) is recharged via the ingestion (or inhalation, who knows) of what I can only assume to be opium straight from the flower.
I have heard many rumblings about this game having a difficult development, but if the demo they showed (a video – mind you) is indicative of the finished game, they should be on to a winner. I have a lot of faith in Eidos Montreal after Deus Ex: Human Revolution, which managed to modernize the Deus Ex series better than I think many of us were even hoping for. Also I am very gratified that they’re just calling it “Thief” now, not Th4if or whatever they started with.
For those whippersnappers who haven’t played this series, Thief is the quintessential (and probably first) stealth “sneak em up”, as it was called back in ye olde days. The first two games are great, but even the rose tinted glasses of growing up in the 90s isn’t quite enough to cut past the Dragon Age 2 style poly budgets for the characters – I mean, the guards have like one triangle per arm, as if they were sending all the rest off to starving Africans or something. Thief 3 (“: Deadly Shadows”), which came out during the rather painful era of the original XBox, is a genuinely good game hamstrung by an appalling engine – it actually terminates the process and restarts each time you change levels (I guess they never found that memory leak, huh) – and boy will you be changing levels a lot! The original XBox, you may recall, had about enough ram for half a shoebox at once.
Anyway, fingers crossed for Thief! It comes out alarmingly soon – February, although they may pull a DX:HR on us and push it back a billion years. Meanwhile, buy the old games on Steam. Go. Now! Go!
I have always had a soft spot for space games, so I tend to break my rules about never playing indie games when it comes to anything with spaceships. Someone on the SA Forums made a rather fantastic thread advertising a game called Starsector, which is currently in early access alpha for a very reasonable price. The developers unfortunately chose to use the worst programming language ever, but the upside is that the game has a surprisingly strong modding community (Stockholm syndrome in action).
The game is basically just a space combat simulator at the moment – you get to give some rudimentary orders to your fleet, and then you can take control of one of the spaceships and crush some heads. They have an elegant mechanic for managing a single resource (flux) in combat – your ship can only handle so much of it at once (without overloading) and your weapons and shields generate it. Add to that a ship special ability, customizable hardpoints, ammunition and support fighters, and you get a deep and involved space combat system – although I still find it somewhat hard to pilot though, as the battleships handle, well, like battleships, I suppose.
The campaign is supposedly going to be some sort of RPG/strategy/Star Control 2 inspired adventure, which sounds pretty fantastic, although currently it consists of exactly bugger all. I’m sure I’m missing something since there seems to be nothing to do except find pirates to kill, but thankfully that part of the game is great – and it’s fun to gradually buy new ships and weapons until you can steamroll anyone who stands in your way.
Anyway, hopefully the authors get a move on and make that campaign, because we could really do with a game like this!
Credit for the picture goes to Cycerin, the author of a Starsector mod called Blackrock Driveyards, which is a great mod. Download it. He also made the thread on SA, which is way more detailed and interesting than this post!
As a continuation of what I’ve been working on, my glyph pages has been packed and allocated (I use Freetype to render the glyphs, although the shortfalls of that are probably worth another blog post), but I now need to render them.
Texture updating – the process of getting an image from RAM to a form that you can render – is one of those simple things that is full of pitfalls. It is also something which tends to be very API-specific, which, when you think about it, doesn’t even make sense. Anyway, I was reading one of the many talks about D3D11 buffer management (this one by AMD), and I came across an interesting slide:
Hmm! Some quite specific instructions there! Now I generally would like to believe these sort of recommendations (and, nVidia and AMD in particular know a lot about graphics hardware), but I’ve been developing stuff on iOS for multiple years now, and, well, let’s just say I’ve started taking suggestions from the vendors with several huge trucks of salt.
Remember the rectangles? Well, I was playing around with trying to get a heuristic which approaches the best possible packing – not just a good balance of speed vs packacity. I have finally succeeded in producing a new packing strategy which consistently beats all others!
Unfortunately it is has a cubic, rather than linear time complexity.
Anyway! The algorithm is pretty horrible. For each pixel on the edge of a possible rectangle allocation, it casts out along the edge normal to find the nearest used pixel (or border of the atlas), requiring that all heuristic invocations iterate over every allocated region. Then, it sums up the logarithm (because as the distance increases, the relative importance of it drops) of the ray lengths, for each pixel on each edge. I have used the minimize area system as a tiebreaker. To improve it further, I’ve made it attempt N positions within each free rectangle – aligning the corners with other allocated regions. I guess I could have tested each pixel, which could allow me to claim the time complexity is only quadratic… Hmmm!
It did do better than the others – getting past the dreaded allocation #63! Unfortunately, the thing really did run slowly. Like, many hundreds of time slower, for my tiny test program. Oh well, I’m sure you can’t wait to see it in action. Here it is!
Update
Well obviously I was going to try checking all the pixels after musing that aloud on this post. It actually didn’t do as well on the normal test – that big beige alloc (#63) is a jerk and it’s really hard for the heuristics to deal with it. But on the small alloc test…
Brute force wins the day. Actually this is animating about 5x faster than I could generate it.
Preface
A common issue that engine developers face is dealing with multiple platform/rendering APIs – we have to marry (often quite different) system libraries into a single, consistent interface for the game teams, who are, after all, our clients. The last thing they need/should/want to worry about is whether they’re running on OpenGL or Direct3D9/10/11 (or iPhone/Windows/Linux, whatever). There are many solutions to this problem, with varying degrees of hackiness – most of the simple ones are based on conditional compilation, and, as a result of that, have a whole litany of issues. It is actually a very hard problem to solve without leaking the abstraction in one direction or another.
I’m going to start this by enumerating some of the methods I have seen and explaining what I believe the relative shortcomings are. I’ve come to my own conclusions for what I want to do for my own stuff, and I certainly am not advocating it as a perfect solution, which I will cover last.
The Rogue’s Gallery
For demonstrating the problem, I will be using a fairly simple example – but one that comes up all the time in rendering engines. A simple texture class. Now, most engines (at least those written in C++) will probably have some sort of hierarchy like the one to the right: a catch all Resource type, a general Texture type, and a specific Texture2D type (as opposed to a Texture1/3D or TextureCube). The hierarchy may continue beneath that with, say, dynamic textures, or framebuffers, or something – the point is that this is not a contrived example.
Read more…
So in my last post, I made a few animated gifs for the purposes of demonstrating an algorithm. It turns out that literally every program (specifically made) to make them is a pile of junk. I eventually discovered how to do it in Photoshop, which took about 10x longer than it really ought to, since it was hidden in one of the many sections of Photoshop I’ve never even seen before. Anyway, if you don’t have it at your disposal but you want to make some gifs, I wish you luck.
Admittedly, I only got about half a page down my Google search (“free animated gif programs that don’t suck“) before giving up. But I do have some notes for people who make those free programs:
- BMP is a perfectly valid image format, stop being such haters;
- Lexicographic ordering is so passe. I really do not like having to move images around because you decided to sort it as “frame0, frame1, frame10, frame11, frame2, …”;
- As a corollary, if you really must do that, at least let me multi-select items in your stupid list of thumbnails.
- Animated gifs can only use 256 colours – so when palettizing the frames, maybe you could be considerate enough to make sure if I dare to use the same colour in multiple frames, it encodes to the same palette entry?
Strangely enough, animated gifs are a special kind of anomaly – my results from PS not only looked better (expected), but they also came out a quarter of the size (probably because it wasn’t frantically strobing the colours each frame). This, obviously, goes completely against the First Law of Photoshop – Thy Images Will Be Curiously Larger Than Expected.
Optimal packing… or joptimal packing?
Introduction
Game engines are absolutely one of my greatest passions – although, they’d have to be, being both my job and my hobby. I have been working on a few toy ideas to develop a small engine, and I hope that this is the start of a series of blog posts dedicated to that. So, with no further adieu, let us begin our adventure!
I was considering naming this series “Adventures in Engine Design,” but then I felt that would be somewhat false advertising. Not to mention that my colleagues who read this blog would undoubtedly spend the next few years asking why I never seem to bring any design to their table.
Oh and also I’ve been silent for two years. To the three odd people who keep visiting this page, sorry about that!
The Problem
Quick! Pop quiz! Given an empty rectangular region, how do you allocate space for an arbitrary list of rectangles? Beyond some very basic estimates (let’s say the minimum and maximum possible sizes), devise an algorithm to allocate each rectangle a unique space in your initial region – they cannot overlap and you must allocate a slot immediately, you are not allowed to defer it to later.
This type of problem is called “Online Rectangular Bin Packing” according to a search I literally just did on Google, so while it may not actually be the real name for it, it at least will be the most hip at the time of writing, and if my WordPress telemetry is telling the truth, that is what you guys care about the most! This type of problem – or rather, a solution to it – is a pretty pertinent problem for us poor systems programmers, as several useful engine features end up relying on it.
Just a quick one this morning – the keynote is in about 4 hours and I am so jetlagged it isn’t funny. I have no idea what time I even think it is. So yesterday, I got my WWDC badge, and was reminded by the Macbook user behind the counter that there are to be absolutely no photos or blog coverage about anything except the keynote. Including the lobby! Harsh, hey, especially as everything in the lobby (that I could see) was:
- Visible from outside
- Already announced
Eat/Play/Hate 