Sunday, 11 June 2017

Teach Yourself Game Programming in 21 Days - Day 8

This is the chapter I've been waiting for.

I'd messed around with coding and writing games before (on an ancient Casio handheld, among other things) but this chapter made me seriously reconsider everything I'd written until then. It's called "Warp Speed, Anyone?" and it's all about optimising code; optimising for speed, that is. A game can be utterly beautiful, but if it isn't responsive, then it's probably not going to be very good.

The first thing the author mentions is compiler optimisation. Essentially, a compiler is free to reorganise or eliminate code that it deems is in the wrong place or unnecessary. Generally the compiler lets you control how much it tries to 'help' you, which is good, because sometimes it can make the wrong assumptions and make it virtually impossible to track down bugs. Knowing how to write code is one thing; being able to debug the resulting assembly language is another. I've done this a few times in my life, so it's a skill I have (kind of) but I will point out that it's often not the best use of your time. Accordingly, André recommends leaving compiler optimisation settings low, despite the potential speed increase. Games have some of the most complicated code out there; you want it to work, first.

The next major subject is that of the memory model. This will be completely alien to anybody who hasn't worked with DOS before. Early on in IBM's history, the decision was made to separate code (executable memory) from data (read-only memory) by the use of segments. This prevents code from overwriting itself. This is a good idea. However, as the PCs of the time had very little memory, each of these segments was only 64KiB large. This was a bad idea, but nobody knew just how much storage was going to expand in the years to come.

All of the programs I've written so far have fit into the Tiny memory model; only one segment required for both code and data. For a little future-proofing, I've been compiling with Compact (one code, many data) but the author actually recommends Medium (many code, one data)! The reason given is that having only one data segment means it's easier to write inline assembly, because DS always has the same value. If more than 64K of memory is needed (and it will be), it will have to be allocated from the FAR heap, which slows down data access slightly. This might be how DOSJUN ends up; it has a lot of code already. I'll have to write 'far' next to more of my pointers.

The next part makes me sad. The Plot_Pixel_Fast function a large part of the book code has been using is an important candidate for improvement; every use involves a function call and pushing of three parameters, which seems like slight overkill considering all it's doing is setting one byte. My solution to this would be to declare the function as a macro, but the author chooses instead to declare the function's parameters as globals, then add a new Plot_Pixel_Global function which uses these globals. André was probably going for maximum compatibility here, but I can't help but note he missed a trick.

Next come standard techniques - aliasing structures or pointers to temporary variables so they don't have to be repeatedly dereferenced (compilers probably do this automatically) and unrolling loops to reduce the time spent incrementing a counter and jumping. There's also a mention of marking certain important variables as 'register' to ask the compiler to optimise them differently.

Then, lookup tables. This is an easy measure to implement in future programs. It's just a matter of trading memory for execution time. This was already done in Chapter 5 to store the results of sin and cos calculations, but it could be done for a lot more... I'm thinking of using the technique for DOSJUN's graphics.

The largest treatment is given to the technique of fixed-point numbers. The gist is to use integers to store non-integral amounts by keeping some of the bits for the fractional part. This allows us to use the efficient integer addition operations instead of the slower floating point calculations that are offloaded to the co-processor. This is the largest code listing in the chapter, and it has been dutifully typed out here.

The chapter finishes with a fairly lengthy and snarky look at DOS extenders, a sad but necessary evil in the transition period between real mode and protected mode processing. This enabled 32-bit programs on the otherwise 16-bit DOS. I'm not sure if I'll need this for DOSJUN, but I hope not, because it's something I've never done. I think it would be quite bizarre to write a DOS program that required 4GB of RAM. Also, I'd have to find a free online one, or write my own.

Despite the dearth of code, this was a difficult chapter to get through as it is quite dense and there's no pictures for me to take! The next chapter is about playing sounds, which would be great if I could get it to work.

Sunday, 28 May 2017

Introducing... DOSJUN

It would be remiss of me to merely type out a few words while reading through a programming book from over 20 years ago. Actually developing a video game using what I (re)learn would make a lot more sense. To that end...


It's been a dream of mine for ages to create a dungeon crawler. It's also a lot of work; I've lost count of the number of times I've started making a game only to abandon it or find some other project to throw myself into. Hopefully, this time can be different.

While I haven't settled on any mechanics yet (other than having 6 party members and there being health and mana, apparently) there is a bit of work done on the graphics engine. I'm also attempting to lay my code out in vaguely sensible ways. Feel free to follow along as I attempt to finally finish something.

Friday, 26 May 2017

Teach Yourself Game Programming in 21 Days - Day 7

There's been something quite obvious missing from our game programming so far. Every time we've handled input, we've been using C's kbhit() and getch() functions. If you've messed around with the demos, you'll have noticed that they suck. That is, holding down a key will result in keypresses based on your OS settings, so input will merrily be processed for some time after you release the key. Also, getch() is quite difficult to use with things like the arrow keys. The reason for that is simple: keyboards are weird.


Every time you hit a key, it sends what's called a scan code to the PC. This is one or more bytes. Another, similar code is sent when you release the key. The keyboard driver's job is to transform these random-looking series of bytes into something that software can sensibly use. Of course, we're programming for DOS, so... you have to write the keyboard driver. I previously did this when I was messing about with OS programming. Typing all those scan codes in was so fun, and I got to do it again!


However, there's more to video games than keyboards. At the time, joysticks ruled the gaming world thanks to their use with Atari and Commodore machines, so naturally some people decided to release them for PCs, too. Coding for them isn't as tedious as for the keyboard, but there is an additional stickler in that every joystick's range of movement is somewhat different. This lead to the universal 'joystick calibration' screen in DOS games where you would be required to waggle it around so it knows what extents to scale your joystick input by. André dutifully gives code for this, presented to you in the joytst demo.


The last input device that the author considers is the mouse; an extremely important tool for strategy games which happily has the easiest driver code of all. mousetst presents what is possibly the simplest paint program of all time. As with many of the demos, it's ripe for improvement. The most galling thing is that it paints one 2×2 block of pixels at a time, but doesn't update fast enough to smoothly draw lines.

This ends the first week of the course. It has covered sprite graphics, vector graphics, loading images from disk, screen transitions, tile-based game worlds, scrolling and input devices. That's enough for a very low-tech game, but we're clearly missing things like sound, AI, physics and special effects; perhaps even multiplayer or networking. There are also more nebulous topics like good game design and playtesting. Still lots to go, and I'm not sure two more weeks are enough to cover it.

Sunday, 21 May 2017

Teach Yourself Game Programming in 21 Days - Day 6

This is an important chapter, for sure. It's titled "Real-Time Animation and Effects", which is a little odd considering that's pretty much all we've been doing until this point. However, games are written in a fundamentally different way to that existing code, and that's because of something called a double buffer.

If you've been running the programs up to this point, you'll notice that the display flickers, seemingly at random. This is because we're updating the screen while it's being drawn. Console hardware has a variety of ways around this problem; from my time with the Game Boy, I know it's very common for screen drawing to be done during the Vertical Blank Interrupt. This means you'll never see a half-drawn frame, unless the game lags heavily. André recommends a similar method for the PC, though without the use of a hardware interrupt. It polls the VGA status register to work out what's happening (see vertical), and waits until it's safe to do an update.


Because we have to maintain this separate buffer which represents the frame to-be-drawn, it requires as much memory as the screen does. This isn't too bad; our typical display resolution of 320x200 mandates a buffer of 63KiB. At the time a typical PC might have 2MiB of RAM, so it was a viable technique. Now, PCs have massive stacks of high-performance memory (mine has 8GiB) and buffering is done by specialised graphics hardware, but it's neat to see how these tricks changed development.

Of course, that means all of our functions that write to the screen should now write to the double buffer instead, so this chapter adds a lot of stuff to our quickly-growing game library.


As a child, the most exciting part was when the author started to describe scrolling. This is a fundamental technique to pretty much all 2D games; either by swapping in new rooms when you enter them or smoothly moving with the player character. You probably won't be surprised to learn that early console hardware was specialised for this, but with the PC you have to do it all manually. Reading this, all kinds of ideas for games burst into my head, and they really haven't stopped coming since. Combined with the quickly-following discussion of using cell-based game worlds to reduce memory use, I was hooked to games (and game development) for life.


I recommend you try out robo because it's a decent beginning for a platformer. Again, I had to recreate the graphics, so excuse my terrible pixels.

There was one listing from the book that I didn't type out; it's called paper and it uses colour rotation to achieve animation. Essentially, the same paper aeroplane is drawn at different points on the same image, but in different colours. Then, the code loads that single image and rapidly changes which palette registers are black and non-black. In this way, very little work is being done by the processor. I don't think there are many wide uses for this technique, but it is interesting nonetheless.

As always, the code is available here.

Monday, 15 May 2017

Teach Yourself Game Programming in 21 Days - Day 5

Polygon Engines, ahoy!

Reading this chapter gave me huge nostalgia vibes, as one of my favourite games growing up was Asteroids. I used to play it for hours a day on MAME, trying to beat my high score. I'd like to think I got reasonably competent at it, and it's a major reason why I played Subspace for so long. There's just something I really enjoy about its inertia-based controls.


Anyway. The author notes that polygon-based graphics are very old; they were originally used in specialised hardware (so-called vector monitors) which functioned similarly to an oscilloscope. They could draw polygons reasonably quickly using a single electron beam, rather than the huge array of pixels we associate today with computer displays. This isn't the only way that polygonal graphics are used; of course 3D games throw billions of triangles at us, but there are also plenty of 2D games using them for stylistic reasons. André mentions Out of This World as "one of the most impressive exhibits" of their use.

There's a lot of algebra in this chapter. It's nothing particularly advanced (if you remember your trigonometry) but I remember finding it quite daunting when I was younger. I've always been mathematically inclined, but the notion that I could use maths to make games was oddly novel.


To a modern game developer, used to relying on an existing game engine to draw all their graphics for them, there's an oddly long amount of time devoted to drawing lines. Dredging up your early geometry, you might remember something like $$y = mx + c$$ to calculate where your lines go. While still a useful formula in a game engine setting, we need something that cares about discrete values (i.e. pixels). The code readout to do this is about three pages of the book. That was fun to type! There are much longer ones than that, though...


The first actual program (linedemo) of the chapter duplicates that old bouncing-line-with-trails screensaver that all the computers at my school had set by default. Being the weirdo that I was, I wrote a snow falling thing in QuickBasic and replaced as many of them as I could.

After this comes a whole bunch of functions for creating, translating, rotating and scaling polygons. Dealing with such a simple mathematical object is easy; the least accessible part is the rotation, which uses cos and sin to move each vertex around a hypothetical 'origin' of the polygon. The real wrist-breaker was clipping a polygon to fit inside a display rectangle. Here's a sample:


Thanks, whoever lost the companion CD. I really wanted to type that out again.

Still, my efforts were rewarded with a passable copy of Asteroids's graphics in the boringly-titled rockdemo. If anybody is following along, I'd encourage you to grab the code from this chapter and run it, because it made me smile to see.

There's not much more to this chapter, dominated as it is with giant code listings. There are a couple of exercises that centre around making rockdemo better; making the ship fire and adding a Gravitar-esque black hole. If nothing else, I might do these ones.

If people want it, I could easily provide all the code compiled to run inside DOSBox (including any exercises I can be bothered to do).

Tuesday, 2 May 2017

Teach Yourself Game Programming in 21 Days - Day 4

Annoying, this chapter is named Getting Sprite to the Point. It is an important one, though.

"Admittedly, a sprite is well-known to be a little elven creature from mythology." Yeah, good start. This is where the library development starts to get serious. Not only does it deal with moving graphics around the screen, it also contains code for loading the hilariously old PCX graphics format.


Dealing with PCX files is a little annoying, because they use run-length encoding to compress their data. BMP files can do this too (an early Windows graphics format) but it's optional, whereas pretty much every PCX file out there is going to be encoded. It's not a particularly difficult task to decode them, but it's there. Still, this does introduce the idea of having to process files from common design formats to use in a game. An engine which really cares about loading time would save this post-processed format as its own file, for more speed.

Here's what makes a sprite, according to André:
Most of the fields should be self-explanatory, but he comments them anyway. It will take a long time for the book to use all of these. Still, almost everything you could think of is doable with this base definition, and everything else could be attached to that extra_data field if you need to. As a side note, I don't like the whole "define a pointer typedef" thing, I'd rather just see sprite*. Ho hum.

"Unless you want to algorithmically generate images for your games, [...]" Haha! Before I go on, it's worth talking about this. There aren't all that many games out there that generate images algorithmically, but it's incredibly common to run into so-called roguelite games these days; randomly generated dungeons and items and so on have found their way into blockbusters like Diablo and The Binding of Isaac. Spore is an example of a game which generates models algorithmically, which is pretty neat.

Anyway. "[...] you'll have to draw them using some kind of bit-map paint program that works with mode 13h. My favourite is Deluxe Paint (Dpaint) and Deluxe Animation (DA), both from Electronic Arts." Wow, remember when Electronic Arts made things other than FIFA games? I remember Dpaint because I used to have it on the Amiga, but I've never used the DOS version. Seeing as I'm missing the companion CD, I had to make my own (terrible) graphics, and I used Usenti, which can save to PCX for some reason. Possibly because it's easy to import into games. 8)


Next, the author explains how to use an image as a sprite-sheet, a useful technique which is still used today in pretty much every 2D game. Essentially, parts of the image are separated into (usually) equal-sized cells. These cells are then used in sequence to form animations; this also mirrors the physical animation technique.

There's a whole bunch of boilerplate code here also for creating and deleting sprite structures. While boring, this also properly teaches how to dispose of unused resources. Of course, higher level languages take care of this for you now, but that garbage collection brings its own problems. André doesn't discuss such things - I don't know a great deal about how modern engines account for this. I imagine they just expose some garbage collector call, so you can just run it in your loading screen or something.

There's a treatment of transparency and not smearing the background under the sprite. Interestingly, there's also an unimplemented discussion of something called "transparency encoding", which I hadn't thought about before. I'll let the author enlighten you:
"When we wrote the sprite-drawing function Draw_Sprite(), we uncovered an unfortunate fact: the function had to be able to implement transparency, and the only way to do this was test each pixel before it was drawn. This was time-consuming; a simple calculation showed that 256 ifs would be executed for a simple 16x16-pixel bit map. There's got to be a faster way to draw sprites that somehow deals with transparency better, right?"

The written solution is to essentially run through the sprite once with RLE beforehand, taking note of when there's a drawable pixel or not. This information is then saved over the original buffer. Then, upon writing the sprite to the screen, it uses control information encoded into the buffer to skip runs of transparent bytes, instead of if-ing every one. This is a reasonable speed-up (during the main game loop) at the cost of a bit more loading time (only happens once per sprite).


And of course, collision detection! "Most of a video game is just testing whether you hit something or it hit you!" Wise words; as such, he uses a very fast algorithm for this, checking for bounding box overlap. As a responsible developer, the author then explains why bounding boxes suck, and recommends you shrink them slightly so that you get less false positives. My optimisation brain tells me this is the kind of information that could also be stored in the sprite structure, rather than having to calculate the size a few times every frame.

The chapter rounds off with a thrilling game called Attank!!! Spoilers, it's not thrilling. It could be decent with a finished AI, and a fire button, and... well, that's the point of the book. Make it a good game!

All the code listings can be found in the appropriate directory in my code repository. I haven't done any of the exercises for this one, because I could barely even spend the time to write this post. One day! I also had a vague idea of somehow making these demos run inside the browser using Emscripten or some kind of custom interpreter/engine. Aaaaah! Why do I never run out of ideas for coding that will take months of my life?

Sunday, 30 April 2017

Teach Yourself Game Programming in 21 Days - Day 3

"Painting the Screen with the VGA Card", the first chapter with whole programs.

First, a bit of hardware history. The PC, being general-purpose, did not originally have a dedicated video card. The need for this became evident quickly, but there were many competing standards available.  VGA started to be used in 1987 (almost as old as I am), and the interface was so useful and easy to implement that almost every video card manufacturer conformed to it. Even cards today support it, I believe. Super VGA was a later improvement which added larger resolutions, but was otherwise quite similar architecturally.


VGA provides for a number of display 'modes'. The most important modes are:
  • Mode 12h: 640x480 with 16 colours, 1 page
  • Mode 13h: 320x200 with 256 colours, 1 page
  • "Mode X": 320x240 with 256 colours, 3 pages
There are a huge number of auxiliary modes with sliding scales of resolution, colour bit depth and refresh rate. If you don't mind being limited to the EGA palette, for example, you can run at 800x600 if your monitor supports it.

You might be asking why anybody would ever use Mode 13h when Mode X is available; the difference is in how the memory is laid out. Mode X (which is really just one of a family of unchained versions of other modes) uses a planar memory layout. This means that the bits for each pixel on screen are split between different parts of memory, requiring a command to be sent to the VGA controller for each plane. By contrast, Mode 13h simply has one byte per pixel, so it's easy to write code for.


The first code listing in the book is presented in its entirety below:
This gives some insight into both how André lays out his code and how lengthy this stuff gets. All this code does is change the video mode then back again. The next example shows how to actually draw stuff. I'll be uploading the code I write to a public repository so that I'm the only one who has to break their fingers. If you look in the repository, you'll notice I've worked ahead slightly. This is mostly because I'm not sure how much time I'll have each day to do this work.

About the code; as mentioned before, the author is using Microsoft C. I'm using Turbo C, which has different syntax and names. I'll make note when I find these out. I'll also be formatting my code differently because I'm not insane. Still, if you want to follow along then grab my code, run it through your favourite 16-bit compiler and run it in DOSBox for a blast from the past.

There are three more listings in this chapter:
  • colorrot: Showing how to do 'colour animation' by changing the palette contents instead of drawing new pixels. This is used in pretty much every DOS game I can think of, so it's a useful technique to know
  • strfield: A parallax, three-plane starfield. I remember recreating this effect about a zillion times while messing with The Games Factory. Also shows off text writing with the built-in font.
  • dots: Drawing random dots on the screen! Not very exciting, but a demonstration of what you can do with essentially one line of active code.
There are quite a few hardware details in this chapter, and a brief treatment of how to create a code library which all the later examples will link against. Of course, the details depend on your linker, but I'll be providing the scripts I've been using in each case. He also mentions the Mode X, but mainly to clarify that all the examples in this book will be using Mode 13h because of its simplicity. Mode X is "probably the best", though.


Let me know if there are any more details you want me to add.