My game uses a semi top down perspective, kind of like the old school zelda games. That means I have to keep track of which object is in front of the other. If I don't, the player might end up looking like he is walking across the top of an enemies head, when in fact he is supposed to be behind him.
So how do you accomplish this on the NES? Well, the sprites are drawn in a prioritized order from the OAM (Object Attribute Memory). Whichever sprite comes first in the OAM will be drawn on top of the ones after. The simplest way to achieve this is to keep a sorted list of all the objects, sorted by their Y coordinate. Then I can copy the sprites to the OAM buffer in this order every frame.
I settled with a simple insertion sort, since it is a very simple algorithm, and performance is very good on almost sorted lists. Since the objects don't warp around the map at high speed, chances are the order of the list won't change much from frame to frame. So I spent this week writing a special sorted buffer and an insertion sort routine. I say this week, since I ended up with some stupid little bug that had me debugging forever. I finally just deleted the routine and rewrote it, and bang! Now it works. Assembly can sure make the simple things crazy hard.
Now on to the next problem. I mentioned in my last post that the NES can only handle 8 sprites at once on a scanline. After that the sprites with lower priority simply disappear. Since I now have 15 characters potentially on the same scanline at the same time, I had to figure out how to handle that. I can't do a simple random order of all the sprites since that would undo all the work of sorting them in the first place. So what to do?
For now I have a simple solution based on the PPU sprite overflow flag. This flag is automatically raised by the PPU when it detects more than 8 sprites on a scanline. It's supposed to be buggy and unreliable, but I think it works OK so far. If this flag is raised, I cycle all objects in groups of four. That way, most overlaps stay fine, but some glitches might occur (and do). They are very small, however and are overshadowed by the flickering anyways.
Here is a little video showing 15 characters animated and walking around randomly on the screen. Youtube can only show 30fps, so the flickering looks a bit strange with the frame blending. Anyways, I think it looks OK.
I'm not 100% done with this part yet, but I have a working solution. I also have a better idea down on paper and I might implement it in assembly this week or later on, which might improve the result. The trick I will use requires me to make some assumptions about the game, like that all sprites will be 2 sprites wide and 2 sprites high. That will work fine for this game, since the only time I might use bigger sprites is in boss battles, and I can use another algorithm for those.
My plan is to scan through the sorted list and find every occurrence of 5 or more objects that are closer than 32 pixels from each other in the Y direction. That means those objects will have to be cycled and I can leave the rest alone. That way I can minimize the errors in "Y ordering" and only sacrifice it for the ones that are really necessary.
In my last post I mentioned that I wanted 60fps with 6 enemies on screen at once. Why 6? Well, there is a logical explanation for that number. The NES does not work like a typical raster display that you find in a PC. Instead it uses a very specialized PPU, or graphics chip. The graphics chip can output a background made up of various tiles, and up to 64 sprites on top of this background.
This tile based display greatly reduces the amount of RAM used for the display, and it also offloads the heavy act of drawing the graphics to the PPU, while the CPU can spend the time doing other stuff. Compare the NES to a common PC of its time, and the advantages of using this design for a game system is easy to see.
Sprites are independent graphics objects that can be placed anywhere on top of the tiled background. They do not have to follow the tile grid, and are therefore perfect for players, enemies, bullets etc. There are however some limitations to the sprites. A sprite on the NES can be either 8x8 pixels or 8x16 pixels. Each sprite can have one of four palettes, each consisting of three colors plus transparent.
Examples of how the meta sprite would be split up in 8x8 or 8x16 mode.
The player and enemy sprites in my game are roughly 16x24 pixels large. That means I can either choose to use 8x8 sprites, and each character will take up 6 of the 64 possible sprites, or I can choose 8x16 sprites and have each character only use 4 sprites. So why choose 8x8? Well, as the NES has a very limited graphics memory, there is a better chance that I can be able to reuse a sprite twice or more. For example, the top of the head might be the same in all frames of an animation, so I don't have to store it twice. Plus, when using 8x16 sprites, I have to save the empty space beneath the character and waste space.
I had initially started by using 8x8 sprites, making the maximum number of characters available on screen at once 10. I also knew that I had to save some of the sprites for things like effects, crosshairs, health indicators and stuff like that. So I was left with 6 enemies and two players.
Having a maximum of 8 characters on screen also fit nicely into the sprite limitations per scanline on the NES. One of the biggest limitations of the NES is that it can only show 8 sprites on one scanline. If you try to show more, they will simply not appear at all. What most programmers did to solve this problem is to draw the sprites in a different order each frame. That way, when there were too many sprites on a scanline at once, they would only become invisible every other frame. This was very common on the NES and can be seen in almost any game.
Sprite flickering example in Megaman 2 (esp at around 1:06)
Since my characters are 16 pixels wide, they use two sprites. So if all characters happened to stand next to each other, half of them would disappear. The simple solution, since I know there is no possible way more than 16 sprites can show up at once on a scanline, is to just draw the sprite buffer backwards every other frame (If I need to, more on this will come). That's why I wanted 6 enemies at once.
But I have since become greedy. This is a game about zombies. No zombie apocalypse has ever been much to call home about with only 6 zombies. I want hordes of them! That is why I have chosen to change thigs up and go for 8x16 sprites instead. This means I have a theoretical limit of 14 zombies and 2 players on screen at once. I'm still not sure I will be able to pull this off, but that's what I'm aiming for.
As you can tell from my sprite, I can still get away with the 3 color limitation when using 8x16 sprites. The pants need to use a different palette, but the top of the body only uses three colors.
Next up is the great challenge of drawing the sprites in order and keep track of what to flicker and when. More on that soon.
Mineshaft was written mainly in C. I was comfortable with C since before, and getting from zero to Mineshaft took about a week and a half. Shiru, a member of the nesdev community, has a great library available free for anyone to download on his page.
On my next game, I also started in C. As you may or may not know, C is what is called a high level language. You write code that is easy to understand for a human which then gets translated to machine code by a compiler. This conversion produces code that works, but the code can get bigger and slower than you might want. On a modern platform such as a normal Intel/AMD x86, the compilers will most of the time be able to produce better code than a human. But on such a limited CPU as the 6502, a C compiler will have a bit more trouble. Writing assembly code can save both CPU cycles and code size even if you are not a master sorcerer of assembly.
The result of writing the new game in C was that I spent more time optimizing for speed than I spent on developing game features. I had set a goal for myself that I wanted 6 enemies plus 2 players moving about on a level in my game, while still maintaining 60 fps. When I had the game running with all zombies moving about with simple AI, music playing and collisions happening, I was using almost the full frame time for calculations. There was no more time left to do anything else. It would either have to be a very simple game in terms of mechanics, or I would have to sacrifice the 60 fps. All the opimizations also made the code a mess of hacks and it was becoming hard to read.
When starting over this time around, I had started looking at writing the game in 6502 assembly directly. It seemed like a massive undertaking at first to learn a whole new way of programming. I had never really done any assembly programming before, except going through the excellent Nerdy Nights tutorials over at Nintendoage.com, and making a few small additions to the scrolling in Mineshaft. Would I be able to learn 6502 assembly well enough to make a game in a reasonable time frame?
I started messing about and doing some tests of stuff like moving and animating metasprites. After a few days of trinkering I began to get an OK understanding of the way things worked, even though I still messed up simple stuff and spent hours debugging stupid newbie mistakes. Pretty soon I felt comfortable that I would be able to write the game, or at least the low level engine, in assembly.
The results so far are encouraging. I am still very much a newbie at assembly, and the code I produce is most likely shit compared to the greats, but so far things are looking good on the performance side. I won't give away too many details, but 6 enemies are now not an issue.
I am a guy born in the early 80s. When I was a kid I never played sports, or rarely even played outside (at least if I could help it). What I did was play video games. What got me started was, like most people my age, getting a Nintendo Entertainment System for christmas. Ever since I played that first video game I was amazed at the magic at work. I wanted to know how they worked behind the scenes, and I wanted to make my own.
Since making games for the NES was pretty much out of the question, and since I had figured out it was basically some type of computer inside, I got really into computers. I bought my first computer probably around age 7 or 8 with my savings. It was a used Atari 520ST.
On the Atari was an application called STOS Basic. This was my first meeting with any form of programming. My friend had the manual to STOS lying around, and it had instructions in it on how to make your own game. The instructions were in English, and combined with never having programmed anything in my life it was quite hard to understand much more than how to get a picture on the screen. I really wanted to get good at STOS, but my 9 year old mind was just too stupid.
A year or two passes and my mom buys our first PC. Her sisters' work place was switching to newer machines and the 386s they had were sold off for cheap. With this PC came something called QBasic. QBasic was my second go at making something more like a game. I did text adventures and simpler pong type games. But I was still too stupid to learn anything cool. Remember, there was no googling for tutorials in those days.
In 1994, when I was 11 years old, an amazing piece of software comes along; it was called Klik & Play. This applicationl let anyone, even a stupid kid like me, make their own game without any programming involved. I was finally able to be a little creative without thinking too much about the technical difficulties. I could just imagine a game idea, draw a few ugly sprites and backgrounds, and make stuff.
I have lots of fond memories of using the Klik line of software, all the way up to the more modern versions of it called Multimedia Fusion. But as I grew older, I noticed that I was not as stupid as I used to be anymore. I began tinkering with programming once again. This time around I was about 15 years old, the internet had come along, and my English was good enough that I could read books, articles and forums and not have to worry about the language.
Programming was more fun now. I didn't get stuck on drawing simple shapes or text. I was experimenting with making stuff that actually resembled games. I never made anything spectacular, but I finally was starting to understand how games fit together. My interest for programming continued, but eventually turned into developing other stuff than games.
When I started college I was mainly interested in the technology behind video and audio processing. So, I spent lots of years at university doing that stuff. But I kept tinkering with games. By now, games were filled with 3D worlds spanning gigabytes of data and content. Making a game like that had become an impossibility for some loner like me. But I kept looking back at my first Nintendo with great nostalgic appreciation of the lovely chip tunes and pixel graphics.
One day, I stumbled upon nesdev.com. A forum full of tinkerers like me, but it turns out they actually had figured out how to create real actual NES games. I was instantly hooked and started reading through all the material the community of homebrew developers had managed to gather over the years. Some of these guys are serious geniuses. It turns out that making a Nintendo game is not magic. You can actually make your own games for the NES quite easily these days. Emulators, graphics editors, compilers, assemblers and flash carts have made my childhood dream a reality.
I immediately started to port an old flash game I had made to the NES. It was itself based on a great little game I had played on an old mac in High School. It was a simple infinite arcade game where the goal is to survive as long as you can to get a high score. It was a learning experience, and a small enough project that I knew I could finish and release it. The game is called Mineshaft, and you can download a ROM here.
When I was done with Mineshaft, I started on a new project. I wanted to do something bigger. I had a game I had started on in XNA which I thought would fit the NES quite well. I already had some graphics ready, and a nice game idea. This was in early 2012. I had just been promoted at work, and my own business on the side was picking up. I got a little bit on the way, but eventually real life was too much. Development slowed to a crawl, and whenever I had time over to work on the game I spent more time figuring out where I was and what the hell my code did than moving forward. Here is a small video showing a bit of early code:
This year, life is more stable. I have my own place, I don't have to commute, and I don't spend as much time on my side business. So, I decided to start over, rewrite the game again from scratch. On this blog I will try and keep anyone interested updated on the project. I might write about other cool stuff I come across or tinker with, but I hope to keep most posts about my foray into NES development.
_(nes_game).gif "Mineshaft NES screenshot")