Wednesday, 20 April 2016

SpIn - A Space Invaders / Intel i8080 Emulator

So as a follow up to my CHIP-8 interpreter I dove right in to some interpretive emulation. Next on the roadmap to learning emulation seems to be the Intel 8080 processor, according to all the good learning sources, as its simpler instruction set makes it a good choice when you want to see encouraging results relatively quickly. In fact, to play Space Invaders, you don't need to emulate the entire instruction set.
   This isn't going to be a long or particularly technical post, however, as, similarly to the CHIP-8 post, I don't want to reiterate information already shared and better explained by other sources - rather I'd like to share some of my own specific experiences.
    Firstly: interpretive emulation is tedious. Implementing each opcode is dull, and you need to implement a LOT of them before you see any result. If this taught me anything it's the power of unit testing. Being able to test each opcode individually is a real benefit and makes life much easier when it comes to debugging. Yes, you have to write more code, but it's worth it, believe me. You can see how I set up my unit tests here - although on reflection the code design could have been much better, and would have allowed the use of unit testing frameworks such as Catch or the Visual Studio test suite. You live and learn I guess. Secondly, implementing a video system to draw the graphics is rather interesting. Of course I used SFML for my graphics and audio output (as well as windowing and input parsing), and translating emulated video memory to pixels on an OpenGL texture was an enlightening experience. What really pleased me about this project though was that, although the software is far from bug-free, it's accurate enough to run not just the original Space Invaders software, but other games too such as Lunar Rescue and Balloon Bomber which were designed for the same hardware.


I admit I had big plans for this project, including extending the instruction set to emulate the (theoretically) compatible Z80 processor, although this is unlikely to happen. Currently xygine and a new game project are taking up rather a lot of my spare time. With any luck future posts will be about the features of xygine, and return to a more SFML oriented theme.

The full source code for SpIn is on Github.

References:
Emulator101 - Space Invaders emulation tutorial site.
Computer Archaeology - Arcade machine hardware and software information.

Sunday, 6 March 2016

Chip8 - A CHIP-8 / SuperCHIP Interpreter

Recently I decided life wasn't complicated enough, so I thought I'd turn my hand to emulation programming. It appears to be a very complex topic to get in to, and resources on the internet are rarely clear cut. After a bit of research though it became apparent that the general recommendation was to not start with an emulator per se, rather to look at the 1977 bytecode language CHIP-8, and write an interpreter for it. An interpreter differs slightly from an emulator, as, in this case, the CHIP-8 bytecode is interpreted on the fly, by an intermediate layer of software, into executable code for that platform. This means that a single CHIP-8 program can be run on multiple pieces of hardware without any changes, assuming that that hardware has an interpreter available for it. This was a common approach used by 8-bit machines of the 80s when running BASIC, and is the foundation of modern languages such as Java and anything which uses the .net/mono framework. There are a good deal of resources on CHIP-8, a language simplified by the fact that it only has 35 opcodes, 45 when extended to SuperCHIP, so I'll not go into detail here, opting instead to link some of the articles I found most useful:

Matthew Mikolay's CHIP-8 breakdown
Cowgod's technical reference
The Cosmac VIP Manual (the original hardware implementing a CHIP-8 interpreter)
Laurence Muller's coding tutorial

The latter is a very useful link when writing your own interpreter, and is the basis for Chip8 (my own implementation). Chip8 differs slightly from the interpreter outlined in the article in that it uses SFML for input and graphics (of course!) and also implements the extended SuperCHIP opcodes. If you are interested in writing your own implementation I highly recommend Laurence's article (as well as the other links for details of all the opcodes), and of course you can check out the source of Chip8 which is released under the zlib license. Here's a video of Chip8 in action:


Rather than talk about Chip8's internals, which are already well documented in the aforementioned articles, I thought I'd write something about the CHIP-8 bytecode itself. When writing Chip8 I wanted a program which would test opcodes for me as I implemented them, so I set about writing a short piece of bytecode, that can be found in the Chip8 source here. The bytecode is initialised directly into an array which can be loaded into the interpreter's virtual memory. The test program can be seen in action at the beginning of the video, which displays a message saying Test OK! along with a logo.

CHIP-8 bytecode varies slightly from most common bytecode formats used in interpreters in that each opcode is 16 bits wide rather than 8. This is because the opcode parameters are encoded in the opcode itself, rather than the following 2 or more bytes as is more common in other languages. CHIP-8 opcodes are big endian, and can be read from memory like so:

uint16_t opcode = (pc[0] << 8) | pc[1];

where pc is the program counter pointing into the interpreter program memory. This is, therefore, also incremented two bytes at a time. A typical opcode, such as JMP which jumps to another address in memory, looks like this:

0x1NNN

The upper nibble of the most significant byte, 1, tells us that this is a jump opcode. NNN are 3 values representing the address in memory to which the program counter should jump. So

0x124D

will jump to address 0x24D. Once the format is understood it is quite easy to write a simple program in CHIP-8 bytecode, especially if you've ever done any programming in an assmbly language (If you haven't and are interested in learning then I highly recommend Human Resource Machine as a great introduction). One thing to note about writing in bytecode directly is that without the convenience of things such as labels, which one might use when writing assember, you are required to manually track the address of every single opcode in memory. This can become a pain, particularly when inserting a new line somewhere, as this requires updating all opcodes, such as jumps, which use an address as a parameter. In other languages removing lines would be easier, as an opcode could be replaced with a NOP (no operation) which would keep the memory addresses aligned, but in CHIP-8 there is no NOP opcode so we're out of luck. This is why in my code you'll notice a comment on every line starting with 0x2XX, the address in memory at which the current line of code starts. In the CHIP-8 interpreter all programs are loaded at 0x200 in memory, so this is the base address. I recommend planning out your program as thoroughly as possible in advance as inserting a line, updating all the comments then seeking out all opcodes which need updating can quickly become tedious. With that in mind let's break down the test program.

The very first opcode is a jump. Looking at the example above we can tell that this jumps to 0x248 in memory. This is because static data used to represent sprites (in this case font sprites) and subroutines are placed at the beginning of the program. The jump simply skips this data and jumps to the beginning of the executable code. The characters in the reduced font set are used to display the test text, drawn as a series of sprites. Sprites in CHIP-8 are drawn in rows, each row of 8 pixels is represented by one byte, with up to 15 bytes representing 15 rows (0-F in hex). If a bit in a row is 1 then a pixel is drawn, else if it is 0 it is not drawn. Rows start at the top of the sprite and are drawn moving down the screen. The characters in this particular case are 4 pixels wide, so the lower nibble is always 0, and are 5 rows high, making each character 5 bytes in size. The comments next to each row of bytes in the source code describe the character which the sprite is meant to represent. After the font set there is an empty byte used to pad the current address to an even value. This is because the CHIP-8 spec requires all opcodes to start on an even value address, although in practice I have found that it doesn't appear to matter.

The first piece of executable code is a subroutine. This is used to create a small delay between drawing each character (as well as test the subroutine opcodes), before drawing the character itself. CHIP-8 includes a timer which ticks down at 60Hz. The subroutine uses this by first copying the value 7 into register V2, followed by moving the value of V2 into the timer counter. The sprite is then drawn, before entering into a loop which reads the value of V2 and checks if it is zero. If it is the program moves on to the next opcode exiting the subroutine. If it is not then the current timer value is read into V2 before jumping back to the zero value check again. This causes the subroutine to loop while the counter decrements. Eventually when the timer has counted down to zero the subroutine will exit.

Following this is the main entry point of the program, at which the jump on the very first line arrives. The code block is quite repetitive, although simple. First the I register is set to the address of the first byte of the character to draw. For example the first byte of the letter C is at 0x202. The opcode documentation tells us that 0xANNN is the opcode which sets the I register. Therefore the next line reads:

0xA2, 0x02,

Then, to decide where the sprite should be drawn on screen, the V0 and V1 registers are set to the X and Y coordinates respectively where 0, 0 is the top left corner of the display. 0x6XNN is the opcode which loads value NN into the register X. 0x2NNN calls a subroutine at address NNN. In this case we call the subroutine detailed above, which starts at 0x23A

0x22, 0x3A,

This pattern is repeated for each of the characters that make up the text 'CHIP 8 Test OK!'.

The next block is a bit more interesting. First a counter is incremented which counts the number of times the test loop has been run. If the value reaches 2 it is reset and jumps to check the state of register V4. This is used to decide whether or not to switch the test program to hi-res mode (0x00FF) or low-res mode (0x00FE). The hi-res mode is actually a SuperCHIP addition, and the opcodes are part of the extended set. This is here in the program to check the opcode implementation, as well as the graphics renderer. When the resolution is switched as is the value of register V4. When the program runs it will now toggle between display modes each time it has finished displaying the test sprites.
    Once the display mode opcodes are tested we find another block of static data. Ideally this should have been placed at the beginning of the code along with other static information but, as this was added later to test the SuperCHIP large sprite implementation, it was easier for me to insert near the end, due to the previously mentioned problem with shifting data addresses when inserting new lines of code. The block of data is, infact, a large sprite, 16 x 16 pixels in size. It works similarly to the CHIP-8 sprites, except that 2 bytes are used per row instead of 1, and the height is fixed at 16 rows, totalling 32 bytes. The opcode used to draw this is the same as the CHIP-8 opcode, except that the height value is set to 0, as large sprites always have 16 rows. The opcode immediately preceeding the sprite data is a jump, used to skip the data (if this were mission critical code the data block would certainly be at the beginning, removing the need for any jump). The sprite, when it is drawn, appears as a circular '8' logo on screen.

Finally the program tests the sound output, before entering a delay loop, similar to that of the delay in the draw subroutine. After the delay the program jumps back to the beginning. To test the sound output CHIP-8 requires only a single opcode, 0xFX18, where X is the V register from which to load the duration value. The CHIP-8 interpreter outputs a single tone all the time the sound timer value is non-zero. The timer counts down at 60Hz, the same as the delay timer, so setting the sound timer to 20 will output a tone for one third of a second.

The test program is rather simplistic, and doesn't test every opcode, but it was fun to write and interesting to learn about. Next time, however, I would probably consider using one of the assembler options provided by sites like Pong Story or CHIP8.com, if only because the use of labels would make life easier when inserting lines of code anywhere other than the end. Searching for 'CHIP-8' on Github also reveals many interesting projects, although in varying states of completion.

Hopefully this experience will provide a gateway to future emulation projects, which I will, of course, eventually document in a future post.




Monday, 22 February 2016

2D Physics 101 - Pong

Recently a discussion on the SFML irc channel  included a question about how to perform very simplistic collision detection in a game such as a clone of Pong or Breakout, where full blown physics simulations provided by libraries such as Box2D or Chipmunk were overkill, and the programmer themselves wanted to learn a bit about writing their own collision code. As I find this an interesting topic, and have implemented systems of my own on occasion, I decided I would share my take on the subject.
    First I should note this is *very* simplistic. Pong and Breakout don't need an accurate physics simulation to be fun, so this post won't cover simulating force, mass, friction etc. The post assumes a single dynamic object (the ball) while all the rest of the objects are static and do not react to collisions. While the bat (or paddle) does move (because it is controlled by the player) it does not react to the impact of the ball, and is therefore considered static. The post will not consider any collision detection optimisations, and so will not scale well with a greater amount of objects. I will start with AABB (Axis Aligned Bounding Box) collisions as SFML provides some handy functions for these out of the box, before briefly touching on circle-circle collisions towards the end. When all is done hopefully I will have presented a diving board for developing a Pong or Breakout clone, as well as perhaps a good starting point for developing a more detailed physics simulation.

To start let's break down what happens (or what we expect to happen) when the ball collides with a solid object. Firstly we need to detect if there's actually been a collision. Using SFML shape classes is handy here, as all SFML drawables have an AABB available via the the getGlobalBounds() function. This function returns an sf::FloatRect which itself has a function called intersects() that returns true if one rectangle intersects another. It also provides a useful feature allowing the overlapping areas to be returned as a new sf::FloatRect. It follows then, that all we need to do is test the AABB of the ball, obtained via getGlobalBounds(), against the global bounds of each of the static objects.

When a collision is found it needs to be handled, or resolved. Resolving a collision means that the ball is returned to a state where it is no longer colliding with a static object, and that its velocity is updated in an at least semi-realistic way. The first part of resolving a collision is to calculate the manifold. This contains, at the very least, a vector representing the collision normal, and a penetration value. The collision normal is a unit vector representing a direction from which the ball has collided with the solid object, perpendicular to the colliding face. As we are using AABBs there are only four faces, therefore only four directions which can be represented by the normal. This makes things easier to calculate further down the line. The penetration value is the amount by which the ball overlaps, or has penetrated, the solid object.




    Once we have this information we can update the ball's position so that the two AABBs no longer overlap. This is simply done by moving the ball along the collision normal by the penetration amount. Secondly the ball's velocity needs to be updated so that it starts to move away from the solid object. We could just invert the ball's velocity, but this looks unnatural. Really the velocity should be reflected, much like light reflecting off of a surface. Our collision normal comes in handy again here, as we can use this to reflect the ball's velocity accurately.




So how is this implemented? For this example we'll create a simple ball class which will handle everything outlined above. The solid objects will be a std::vector of sf::RectangleShapes, against each of which we can test the AABB of the ball. The ball class needs to be both drawable and transformable, so it inherits the sf::Drawable and sf::Transformable classes. It also implements the pure virtual draw() function of sf::Drawable, as outlined in the SFML tutorials. The ball needs to be updated once a frame with the elapsed time, so that it can be moved by a given velocity. The velocity is a combination of a normalised sf::Vector2f member variable which represents the current direction of the ball and a constant value, speed. Every update the ball is moved by m_velocity * m_speed * dt, where dt is the time elapsed since the last update. This on its own is enough to make the ball move at a constant speed and direction, and if you try this you'll notice the ball will continue in a straight line until it disappears off the screen.
    Once the ball has moved we can then check each one of the static objects for a collision and then resolve it, using the method outlined above, if one is found. The ball class is constructed with a reference to the vector of solid objects, which is kept as a member of the class so we can easily read the shape data.
    Earlier on I mentioned the sf::FloatRect::intersects() function, and the fact that it can be used to determine the overlapping area when two AABBs overlap, like so:



This overlap is useful in the manifold calculation because, depending on whether the width or height is greater, we can easily tell if the collision is happening in the X or Y axis. By subtracting the position of the static object from the ball's current position we also get a vector broadly representing the collision direction (remember we want to narrow this down to just one of the four AABB faces). Note that the origins of the static objects are set to their local centres, so that this works properly. These two values are then passed to the getManifold() function of the ball class.
    From this the manifold calculation is pretty simple. If the width of the overlap is less that the height we are colliding in the X axis. If the x value of the broad collision normal is less than zero the ball is on the right of the static object, else it is on the left. The penetration is the width of the overlap. If the width is greater than the height of the overlap the calculation is the same, but performed on the Y axis instead. The calculated collision normal and penetration value can then all be packed neatly into an sf::Vector3f, where the z value is the penetration value, and then returned from the function.
    The ball class's resolve() function takes the manifold and uses it to move the ball from its colliding position by moving it back along the normal by the penetration depth, and then reflects the ball's velocity about the collision normal. The reflection function can be seen in detail in the sample code.

This should be enough to have the ball bouncing merrily around the window. When looking at the code, however, you may have noticed that the manifold and resolve functions are separate when, strictly speaking, this needn't be so. On the other hand this post has only covered AABB collision - what if you want to collide circles together too? Well the theory behind that is basically the same, we just need a different method for calculating the manifold. In the second example I've added an alternate function for calculating the manifold of two circles. To detect if two circles are colliding, measure the distance between their centres. If it is smaller than the sum of the two circle's radii then we must have a collision. The penetration is the difference between the the summed radii and the current distance.




As a circle has no faces the collision normal is always a unit vector of the distance between the two centres. Plug these values into our manifold and the rest of the collision resolution remains the same.
    Note that in the code I've used the lengths of the vectors squared - this is a square root optimisation which removes the unnecessary use of the square root function when comparing distances. The result of comparing squared distances will always the the same as comparing the root of the distances, and we only need to use the square root function when finding out the actual penetration if there is a collision. A third getManifold() function could also be created for AABB vs circle collisions quite easily from here - although I will leave that as an exercise for the reader.



That pretty much sums up what I wanted to cover in this post. As I stated earlier it is a very rudimentary look at the physics in games such as Pong or Breakout, and there are quite a few things which can be done if you want (and I encourage you to) to take this further. The method above does not take in to account if you wish to collide to dynamic objects together. At the very least the resolution of the penetration needs to be shared between the two colliding objects. This method does not account for the fact that in most cases you'll want to have at least some mass for your objects, so that when dynamic objects of different sizes collide they affect each other more realistically. The example code also won't scale very well - the small amount of static objects is fine as a demo, but in scenarios where many objects are involved I suggest some sort of spacial partitioning, such as a quad tree, to quickly cull any unnecessary testing in a broad phase pass. Below are a few links which I have found useful in the past, as well as links to the example source code.

Example 1
Example 2

Further reading:
Physics Engines for Dummies @ Wildbunny
Gamasutra pool hall physics
Writing your own physics engine
Wikipedia's quad tree entry 

Friday, 22 January 2016

How to build TMX Map loader for SFML

Soo.. the usual opening apology for lack of content - sorry! (Happy new year by the way!). Although I have a wealth of ideas I'd like to write about it actually becomes very hard to find the time to write about them when I'm busy implementing them. Long story short I've been working on tidying up the framework I use for building SFML games called xygine. Technically this post is not about that though, (and the project itself is far from finished) so if you're curious as to what my take on an Entity Component System for SFML might look like you can find the repositiory here. Hopefully one day you'll start to see some posts detailing some of the features.

To the crux of the matter: I get repeatedly asked about building the TMX map loader as, for some reason, it seems to be my most popular project. To be honest I'm a little disappointed with myself for not making this post much, much sooner but finally here it is. I've added a page to the map loader wiki which explains how to build it on various platforms and compilers, complete with an explanation for building the required zlib library on Windows. You can find the page here. Hopefully this will get enough exposure that anyone looking for it will be able to find it and build the map loader successfully. There may be a mistake here or there but, as the page is hosted on the Github wiki, anyone with a Github account will be able to contribute fixes and corrections. From now on this will be the official source of build information and I will forward  any queries to this link :)

Wednesday, 26 August 2015

Updates, updates...

... updates. I've not been toiling over any huge projects recently, but there has been a speight of update activity. First off I've pushed a few updates to the SFML TMX loader to the github repo. There's no new full release, but the updates do fix a couple of bugs, including polygonal objects losing their point data when properties are added. I've also added support for 'Collection of images' tile sets, which is more of a feature than a bug fix. If this is something you were waiting for then now is the time to pull down the latest revision.

I've also updated Pseuthe, fixing a bug where the score timer continued to run when the main window lost focus, as well as adding a colour blind mode for people who find distinguishing between red and green difficult. I've also updated the help menu. This brings Pseuthe to 1.0.3, the Windows and Linux binaries for which you can download from itch.io, or, if you prefer, the source from Github. Thanks to kind community donations there is also now an OSX binary in the works, which should appear on itch within the next few days.

Monday, 3 August 2015

TMX Map Loader for SFML version 1.1.0

I've recently published version 1.1.0 of the Tiled map loader on Github. This release includes the changes from the previous update, as well as bug fixes, and the ability to load tmx maps from xml strings stored in memory.
   I was asked recently over on the SFML IRC channel about the possibilities of obfuscation of tmx maps. It was pointed out that any end user of a game can easily cheat by loading the game's map files into Tiled and editing them to make them easy to complete. I guess this is technically true of any game, whatever the map format, although with varying degrees of determination needed to make it happen. With tmx map files, however, it is incredibly easy. I guess you could argue of someone wants to cheat to make the game easier, then it's their loss anyway, but I saw no harm in offering a bit of flexibility to devs who want to obfuscate their map files. The idea is that tmx files output by Tiled can be run through an obfuscator of choice, making them immediately difficult to load directly into Tiled - although it's not of course bullet proof. The game using the maps would then need to internally unobfuscate the map data before passing it to the map loader - hence the new ability to load files directly from xml strings. I've not implemented and obfusation routines myself, and it's not part of the map loader. Offering such things as open source would probably undermine their use anyway. Hopefully this will find some use with developers. In the future I'm also planning to support other formats such as json, and possibly even binary tmx files - so watch this space.

Tuesday, 30 June 2015

A new game - Pseuthe

UPDATE: You can now download the latest binaries for Windows and Linux from itch.io !


So I've been busy beavering away behind the scenes (and neglecting this blog) working on a casual game written using everyone's favourite C++ library; SFML. Pseuthe (pronounced 'soothe') started out as an experiment in Newtonian physics, but I was soon elbow deep adding the prettiest graphics I could muster, as well as some semblance of gameplay. You take on the role of a deepwater plankton, feeding on all the happy microbes you can find before your being winks out of existence. Last as long as you can, and don't eat any of the bad microbes (highlighted by their red markings). Here's a video to give you some idea of what it's all about:


I'm still tweaking things here and there, so there are no binaries available, but it is open source so you can compile it yourself. The repository contains a Visual Studio 2013 solution to get you started on Windows, and I've tested the CMake / make files with gcc on linux (mainly Ubuntu and Arch). It should compile on OSX too, but I don't have a machine to test it on. If anyone wants to contribute OSX support to the CMake file, I'll gratefully accept any pull requests ;)