WY Progress Report #2

It’s been 2 weeks since the last post, I’ve kept my word. Here’s where I’m at with Wasted Youth.

Since then, I’ve mostly spent my time finding some free, open source software and script libraries, and butchering them for my purposes.

Admittedly, I’ve only touched the surface in developing the actual game engine, I’ve been concentrating more on creating an easy system for generating graphics and game assets.

Unfortunately I can’t just draw something in Flash and have it magically render without any thought or consideration.

Just keep in mind I’m still transitioning and I’m not finding it terribly easy.

 

I mentioned last time I was considering making the world out of tiles, much like I used to with RPG Maker before my foray into Flash, so I found myself a tile editor (it’s called Tiled if you’re interested).

But it isn’t that simple. Unlike most ‘tiled’ games, my tiles come in all shapes and sizes, and they have special properties that need to be taken into account so that they render correctly.

That’s the short of it, but basically there’s a whole load of little changes I needed to implement in order for this software to serve my purposes, or to even display a map properly.

So I got myself the gear needed to edit and compile this software myself.

It’s all written in C++ which up until now I’ve completely avoided, so it hasn’t been easy.

 

 

As things go along, I think I’ll need to keep coming back to this and altering it as my needs change, but currently I’m quite happy with what I’ve managed to do with it.

It allows me to draw walls and floors and place objects many times faster than it was when developing Wasted Youth, Part 1.

If for instance I needed to change the dimensions of a room, it would take me a long time in Flash, as I was literally redrawing walls with a graphical editor.

With a tile editor I can change the floorplan with no more than a few clicks, so in almost every way it’s a huge improvement over Flash.

As with anything there’s some annoying quirks which I have to live with. It’s certainly not perfect. I’d like to improve upon it some more but I’m trying not to get carried away with that kind of stuff.

 

After that, I’ve spent almost a week creating a system for making spritesheets.

Spritesheets are large images, consisting of many sprites. The more sprites you can pack into a single spritesheet the better. It means the GPU doesn’t need to keep unnecessarily flicking between several spritesheets when drawing a scene.

A potential problem I could encounter later on is having too many spritesheets, so this is something I need to take into account during the earliest stages of development.

 

There are many tools and algorithms for compiling spritesheets out of many images, but none of them suit my needs exactly.

My problem is quite an unusual one. Some of my sprites are very large and irregularly shaped. For instance, look at this spritesheet I compiled with a normal rectangular packing algortihm:

 

 

(The sprites in this are just placeholders for the actual graphics by the way.)

As you can see, there are large gaps around anything non-rectangular, particularly the horizontal staircase and the separated bannisters.

Another thing to consider is if each sprite consists of the rectanglular bounds and they have to be drawn pixel by pixel by the GPU, then think of how many transparent pixels are needlessly being drawn by the GPU? It’s a ton, and it can be improved upon greatly.

The solution is to pack them tighter… it sounds simple but trust me, it ain’t.

 

The way you feed a GPU instructions is not entirely intuitive. In the simplest terms, you give it an image (spritesheet), you give it some vertices (points), so it knows which bits of the image to display.

A GPU only draws triangles, so it reads the vertices in groups of 3, each point representing the corner of a triangle, and draws each triangle individually.

For most 2D games, the shapes you’re drawing are almost always rectangles (aka quads), which consist of 2 triangles.

Unlike a 3D game where the triangle count at any point is often in the tens of thousands, in a 2D game it’s more in the region of hundreds or less.

So the triangle count in a 2D game is often so little it’s negligible, instead it’s often texture memory that developers have to keep an eye on.

For retro styled pixelated 2D games though, that’s not a big problem either, because if you’re using less pixels then obviously it’s less memory on the GPU.

Lucky bastards.

 

Unfortunately for me I’m not going down the retro, pixelly design look. For me it’s high resolution, fat-ass sprites. And not just a few, tons of them.

 

Back to the problem at hand - how do I pack them closer together?

The only way we can is by considering the actual shapes of the objects, so for each shape I’ve drawn polygonal bounds close to the actual shape (like cutting it out with a pair of scissors), converted them to triangles, and now we have something that looks a bit like a flat 3D wireframe:

 

 

The left one is what I get if I were to strictly convert every edge perfectly, but that’s almost 90 triangles. We don’t need to be that accurate so here’s something more appropriate, made of just 4 triangles.

 

So now I have a load of jagged irregular polygons. Is there an algorithm to position these on a spritesheet to take up the least amount of space?

No, not exactly. There is no way of finding the optimal placement of so many irregular shapes, unless you own a super computer from MIT (which I don’t).

But there are some very clever genetic algorithms that get pretty close.

Yes, genetic algortihms… I’ve been down this particular rabbit hole for a couple days, I won’t go into the finer details, but basically it involves lots of random iterations, finding the best match and getting better and better with each iteration.

Like evolution.

 

It’s not completely there yet, but now I can create a spritesheet like this:

 

 

Not bad! The total area of the objects is close to 70% of what it was.

There’s still a lot of space in that image which could further be optimised by allowing certain objects to rotate by 90 degree increments, which I’m currently working on.

If you can imagine lots of smaller objects they could fit into loads of nooks and crannies, with this method of packing, so hypothetically I could fit in loads more items and it won’t increase the overall area of the image!

 

This is quite a modern way of doing things for 2D games, and for my project it’s pretty vital that I take this approach I think.

I’m not at the point where I can do any benchmarking, but I think there’s a reason you don’t see many 2D non-tiled orthogonal perspective RPGs with high resolution sprites…

Maybe that’s a tad specific, but I'm sure there's an element of truth to that statement.

 

Oh right, I’ve waffled a bit haven’t I.

I think I’ll leave it at that. Progress is slow but I hope by the next post I’ll have the basics down so that I have a character with a following camera that can move about in an environment, with animation hopefully.

 

By the way, it’s been a bit disheartening to see so few comments recently.I’m holding off on starting our Patrion still, but with the recent lack of liveliness on here I’m beginning to think there’s not enough of audience to make Patrion or kickstarter really viable.

Prove me wrong and make some noise, I need some motivation.

 

More details next fortnight!