Seeker missiles revisited

If you follow me on twitter, you saw back in February that I was attempting to get enemy-seeking missiles working correctly. At the time, I felt like I got all the bugs worked out, and they were good to go. But now that I'm at the point in content-creation of the game that the player actually GETS the seeker missiles, I'm not quite satisfied with how they behave, so it's time to revisit them.

The thing about seeker missiles (or any sort of "move an entity directly toward another entity at a set speed) behavior is that it's not as simple to get right on the 6502. (at least if you care at all about performance and would like to get more than 1 frame per second in your game).

The reason why is because of trigonometry.

There are two parts to making good enemy-seeking missiles. First is to select which enemy to target (usually the closest, although you might have a priority system instead to that they always target the most dangerous enemy or something. For this post, I'll assume we're targeting the closest enemy)

The way you'd do this on modern hardware is by first finding the closest enemy by using the Pythagorean theorem -- distance is the square root of x² * y². You can even omit the square root if you only care about finding the closest -- just find the sum of squares of the x and y distances for each enemy, and the closest is the smallest.

Unfortunately, arbitrary multiplication is slow on the 6502. Without a multiply instruction, you're stuck adding in a loop, (or bit shifts for multiplications times a power of 2). If the x distance is 74, that means adding 74 to itself 74 times in a loop.

That would look something like this (squaring a single 8-bit value into a 16-bit value):

  ldx val        ;3 cycles
  lda #0         ;2
  sta result     ;3
  sta result+1   ;3  (11 cycles for loop setup)
:
  lda result   ;3 
  clc          ;2
  adc val      ;3
  sta result   ;3
  lda result+1 ;3
  adc #0       ;2
  sta result+1 ;3
  dex          ;2
  bpl :-       ;3  (24 per each time through loop)

  ;11 + (24 * 74) = 1787 cycles 

I scribbled that down without checking it, so it may be off by 1 or something, but it's something like 6% of a frame just to do that single 74*74 calculation. Good luck trying to also do y², then computing this for each possible enemy. So we need a better way.

To be honest, I haven't found a perfect solution for this. Luckily, for this part of the problem, we don't really have to be exact. If the missile targets an enemy that's not exactly the closest, I don't really care.  So for this first step, I just compare x + y instead of x² * y². Sure, that overestimates how far away enemies are that are more diagonal from the missile, but ... I don't care.

The more interesting part is the second half of the problem. Doing the math to determine the X and Y components of movement to move the missile toward the target.

The easiest solution is just to move at full speed horizontally until your x component matches the target, and also move at full speed vertically until your y component matches the target.  The problems with this are obvious though: the missile moves too quickly in a straight diagonal, until it gets even with the target in one dimension, then moves straight until it hits it.  This is a fairly obviously ugly movement.  It's fine in some cases, particularly if the entity is moving fast enough that you don't really pay attention to the movement itself.  I used this method in Super Homebrew War when a player gets the "swap everyone's location" power.  I didn't have the programmer time or rom space for something more complicated, so I just went with this. The swapping all happens so quickly that you don't really notice that it's ugly.

Another solution would be to use to a constant TIME instead of constant VELOCITY.  If you assume that the missile will always take approximately a second to reach the target, you can divide the x distance into 64 pieces (dividing by 64 is fast with bit shifts), and divide the y distance into 64, and move each by that amount every frame.  That will produce a nice even movement, BUT the speed will change based on the total distance traveled. A missile will take the same amount of time to reach enemy A as enemy B, which may be undesired.

The REAL solution involves trigonometry, which is hard on the 6502. You find the angle (the arctan of y / x). Then to find each frame's x and y components of movement, you use cos(angle) * vel = x.  (or sin to find y).  It's simple high school trigonometry. Easy if you have a calculator or a modern processor. Not as easy on the 6502.

But for Halcyon, I want things to look nice and polished, so I wasn't happy with either of the two previous solutions. So trigonometry it is.

For the arctan, I found a pre-written routine that does a pretty good fast estimation of arctan that was written by one Johan Forslöf. I don't pretend to understand the math behind it (he claims it simply "uses logarithmic division to get the y/x ratio and integrates the power function into the atan table"), but it does what I need it to do.

For sin and cos, the trick (like many things on the 6502) is just to use pre-computed tables. If you assume that the angle is a 1-byte value, then there are only 255 possible sin values you have to compute. So you can compute them ahead of time (using a python script or something similar), and just put them into your rom as a lookup table. The cartridge rom that I'm using for Halcyon has plenty of rom space, so a 255-byte table is no big deal.  Then to compute the sin, you just look up the precomputed value for any angle. Table lookups are one of the things that the 6502 does best, so this is nice and fast:

ldx angle      ;3
lda sinTable,x ;4 (7 cycles total)

For cosine, you can take advantage of the fact that cosine is just sine rotated by one quadrant, so you add (or is it subtract? I never remember) 64 from your angle and use the same table.

So with these tricks, you can have a pretty nicely functioning enemy-seeking missile, without using too much CPU time.

Now if I could only figure out why it's not working, and my missile is just bouncing along in a goofy-looking sine wave pattern.

Scrolling glitch

For an 8-way scrolling engine with 4 nametables (ie 4 in-memory screens for the camera to pan across), it's easy to end up with a lot of small glitches in the background. Scrolling diagonally across the seam of screens, it's easy to get some of the PPU memory address math wrong, and end up writing to the wrong spot on the screen. But it might only happen when the screen is aligned exactly wrong, so it can take awhile to find and fix all the glitches.

The gray outline shows what's actually on screen. The rest is video memory that's not shown.

Over the past couple of years of working on this project, I've gradually worked through what I thought was every single scroll glitch, and fixed them. Mesen, the NES emulator that I use, has some wonderful features for debugging this sort of thing. You can play through the game, and when you notice a rare, hard-to-reproduce bug like this, you can save your game history, then go back and replay the whole history through the debugger, stepping through what you did, rewinding if you went too far, and watching updates as they happen. It's amazing.

Despite all this, there's one scrolling glitch that, until tonight, I've never been able to reliably reproduce enough to find and fix. It only seems to happen in one particular room, and then, only rarely, even if I do the exact same movement when I enter the room.

The room that gave me all the trouble. Depending on some random numbers, you can end up with 7 enemies going at once, which has the potential to slow things down.

Luckily, tonight I caught the glitch in the emulator!  I went to quickly hit the "save history" button, and I accidentally pressed "reload save state" and jumped back to some previous point in the game, and lost it.   ARRGH!

But, I had the good fortune of being able to reproduce it again fairly soon after, and this time I managed to save the history, and replayed it over and and over and over again.

It didn't make any sense -- as I was scrolling diagonally through the room, it would just skip updating the background for a single frame. So instead of writing new tiles at the edge of the screen, garbage tiles would just scroll in instead. I couldn't figure out why it was skipping an update.

After about the 30th time I replayed it, though, I noticed something. My frame counter was jumping from $1d to $1f when I advanced a single frame. That's not right! 

To make a long story short (too late), I tie some of my scroll logic to the frame counter (to alternate between a few types of updates). In the rare case that too much is happening in a single frame, you can end up with that dreaded NES slowdown, which means that you hit vblank before you finish your frame's logic (ie you get 2 screen draws per logical frame, cutting your game to 30fps instead of 60).  During the screen draw interrupt (NMI) is when I advance my frame timer. 

You can use a grayscale bit in the video settings as a poor-man's profiler. The gray shows how much of my CPU time I'm using this frame.

So this one single room has enough enemies to very occasionally cause a slowdown (usually only for 1 or 2 frames so I never even notice), BUT during those slowdowns, my frame timer advances twice per logical frame. So my scrolling updater (which depends on that timer) fails.

It was an easy fix once I realized what was happening -- I now just use a separate counter for the background updates, and only increment it after actually doing an background update. It wastes a byte of ram, but this is the NES, which has a whopping 2k of ram! What's a wasted byte?

So now, for maybe the 100th time, my git commit message said "Fixed what was hopefully the last scroll glitch."  Maybe I'm actually right this time?

Who needs enemies?

One of the things I keep thinking as I'm building content in Halcyon is "does this room really need any enemies?"  I mean, the fun of the game is supposed to be about exploration. Enemies just slow that down, right?  Or maybe it's just that I'm being lazy and don't want to figure out what enemies to put into a room. Do I need to mix it up for each room, or is it ok to have a few rooms in a row with really similar enemies?  Will the players find this room to be boring, too similar to the last room? 

I have no idea.  But regardless, it sure is tempting to leave a lot of rooms empty.

Enemy names

I realized that I'm not all that creative when it comes to enemy names. For my enemy code, each enemy has a textual name that it's referred to in labels, in the map editor, etc.

Here's a handful of the names so far:

• flapper
• hopper
• walker
• gunner
• diver
• zapper
• spitter

And then some that are even more boring:

• blob
• boss1
• boss2
• boss3
• barrier
• fish

Good thing these names are all secret....

What sort of game is this anyway?

I've said before that I'm making a Metroidvania. A kind of mash-up of Metroid and Blaster Master in this case.  But these days, that Metroidvania label (as well as "rogue-like") gets attached to almost everything under the sun. Dead Cells, a procedurally generated level-based action platformer routinely gets labeled as both a roguelike and a metroidvania (while I would say it is neither).  Even among things that actually could accurately be described as Metroidvanias, there's a huge range of variety in what that can mean, and what sort of thing a game really is. So this post is my attempt to answer the question: "What sort of metroidvania is Halcyon?"

To answer that, there's a number of different aspects that are worth discussing: non-linearity, challenge, and reward structures. Let's dive in.

Linearity

The first question is how linear is the game? At the far non-linear side of the spectrum are games with a big open world where you can really go anywhere in any order you want. The recent NES homebrew game Lizard by Brad Smith is a good example of this, as is Super Pitfall. There's a big giant world, and it's yours to explore. You can really do things in just about any order you want.

You can go any way you want in Super Pitfall, but mostly you just die. A lot.

Then there are games that have a little more linearity to them: the original Metroid is a good example. You can't really progress until you find the missiles and bombs. But when it comes down to it, you can go kill Ridley or Kraid in either order, without ever finding a number of the other powerups.  There may be a recommended order to do things, but you're not always doing everything in the same order.  (The original Legend of Zelda was very similar in it's non-linearity. There was an order to the dungeons, and some of them required items from other dungeons. But there's not much preventing you from doing some of them out of order(and we did so when we were first exploring the game as kids....if you got stuck on level 6, you went on to try level 7 instead).

Next up are games that are slightly more linear, like Super Metroid. Advanced players know how to exploit the game and can do things out of order, but the average player will end up doing things in mostly the same order every time. Sure, there's plenty to explore, and plenty of secret passages that you may or may not find. But the general order ("find this powerup to open the way to the next section. Find another and then you can go back through that other section") is generally the same for each player. (assuming they aren't purposely going back and trying to break the game sequence).

Despite the awesome Metroidvania-style map, Circle of the Moon was a huge disappointment to me. Each colored section was a distinct "level" that you had to play through in order.

At the far linear end of the Metroidvania genre are games like Castlevania: Circle of the Moon. Although it's one big world, it's divided into clear level-like areas. You beat the boss of the first to get an item that lets you explore the next. Beat that next level, and you get rewarded with the power that lets you explore the 3rd section. And so forth. These are the least interesting to me: although they pretend to be big contiguous-world metroidvanias, they're really not much different than a linear level-based game.

Where does Halcyon fit into this spectrum? I'm attempting to place it somewhere between Metroid and Super Metroid. I'd like the player to have a little bit more freedom in the order of things than Super Metroid, but I found Metroid to be a little too painful in terms of a beginning player not having any idea of where to go. A few parts of Halcyon will require you to go get powerup X right now to continue, but there will be other parts of the game where you can decide which way you want to go, with a number of different areas to explore and routes to take.

As a side tangent -- the world in Halcyon is a euclidean contiguous world. There are no warps between worlds or front/back (like Goonies 2) or weird non-euclidean layouts like Blaster Master. It (like Metroid) is just one large mappable world.

Difficulty

I've made some hard games in the past. My friends who have played my original Robo-Ninja for Android may have had some unkind words about me at times. Robo-Ninja (also a metroidvania) was designed to be HARD. The world wasn't big or complicated, but each room was a challenge.

Robo-Ninja -- possibly the world's first tap-to-jump metroidvania?

When I'm talking about a difficulty spectrum here, I'm talking not about how big or confusing the world is, but how difficult the enemies, obstacles, and other "platformer skill" elements are. The original Metroid was a pretty tough game, particularly at the beginning when you didn't have many energy tanks). Lizard is HARD -- you die A LOT. Blaster Master had a weird difficulty curve -- some levels were really easy, but some levels (and bosses) made you want to punch the screen.

The game was fun and easy-going until you had to fight THIS GUY.

Super Metroid, on the other hand, wasn't a very hard game. There were a couple parts that were tricky, but you really didn't die all that much. The fun of the game was exploring and figuring out where to go, and looking for secrets. The enemies were mostly just there to keep you on your toes.

Symphony of the Night was also like that. Other than that one boss (I don't remember his name, but I'm sure if you played it, you know who I mean), it was a fairly easy game, mechanically. The joy of the game wasn't in the finesse of fighting and jumping.

Unlike Robo-Ninja, this time I'm going easy. Halcyon is (hopefully) going to be more like Super Metroid or Symphony of the Night in this regard. If I can get the difficulty set the way I want, you might die a couple times, just enough to keep you interested and careful. But the combat isn't supposed to be hard. Anybody with moderate video game skill should be able to take their time and explore and enjoy the game.

Reward

One of the things that I want from Halcyon is for exploration to feel rewarding. Super Pitfall had a giant world with lots of areas to explore, but it was just a vast mostly-empty world. There was nothing that made you feel rewarded when you went this way vs that way. You'd explore a route and die, without having found anything interesting. You'd try a different route and die. You never seemed to make any sort of progress.

Lizard also had a fairly brutal reward system (in my opinion). There were coins scattered around the world, but you had no idea what they were for, and you'd lose them if you died. If you explored a lot, you could find a new power (a new lizard costume), but you didn't get to keep it. Even defeating a boss just mostly felt confusing to me.  These were all purposeful design decisions that Brad made (as opposed to just poorly-designed flaws), but playing it helped me figure out what sort of feeling of reward I wanted to put into Halcyon.

This screenshot from Lizard sums up how I felt most of the time.

First, I wanted a map screen that would be permanently revealed as you explored. (Like Super Metroid, Symphony of the Night, or many other newer games). With a revealed map, you always feel like you're making progress. Even if you get fairly lost, and don't discover where to go, your adventurous route is marked on your map. There's some internal feeling of reward in uncovering the map. You did something permanent. You got here once and you know how to get here again.

Second, I wanted a lot of powerups scattered throughout the world. Heart containers in Zelda and missile packs in Metroid were great -- they could distribute them freely all over the place, giving you lots of minor rewards throughout the game. I love Super Metroid's method of putting a minor reward behind some secret passage. The real thrill was finding the secret passage, but they gave you a permanent upgrade as a reward once you found it. To make this happen, I have a number of types of powerups in Halcyon, so that I can hand them out like candy. There are a few major ability powerups (which are the keys to unlocking content and progressing), but there are also new alternate weapons, max health increases, weapon power increases, energy increases, etc.  If it was ONLY health increases, I think they would quickly become boring and lose their sense of reward. So my goal is to have all sorts of types of things to find to keep it feeling rewarding.

A tiny sliver of Halcyon's minimap

Hopefully my describing where Halcyon fits in along each axis will help provide a better picture of "just what is this game all about, anyway?" But just a few more bullet points might be helpful:

- There's a little bit of story/plot, but not much. If all goes to plan, and
  we can get the details ironed out, there will be an opening story sequence, a tiny bit of plot along the way, and and ending story. But this won't be a story-driven game. You won't be talking to lots of people, getting clues in towns, or interacting with a lot of characters and dialog.

- Like Blaster Master, there will be a dynamic of getting in and out of your
  vehicle to explore different areas that are better handled on foot or in-vehicle. Unlike Blaster Master, there are no overhead sequences. The world is one single contiguous side-scrolling map.

- There will be secret passages and hidden items. More Metroid than Blaster
  master in this regard. Some will be pretty obvious. Others might be rather difficult to find. (dare I say obtuse?) My goal (if I pull it off well, which I may not) is that all of the secret passages necessary to win the game will be fairly intuitive to find, while many of the optional routes or powerups will be better hidden.

 If you have any questions, I'd love to hear from you! Pester me on Twitter or email at nathan@bitethechili.com.