LONG BLOG
Fledgling Retrodev: Mix
Not that long ago, Qix (Taito, 1981) was released on the Arcade Archives series on consoles. This was a game I recall from various other adaptations but I was never a massive fan of it.
Qix on Switch.
The core gameplay idea is that there's an enemy (Qix) in the game field, and the player (Stix) has to cordon off the Qix by drawing lines on the field to limit where Qix can go. Once a given percentage of the game field is cut off, the level is cleared. Qix is the red-blue collection of lines in the picture above.
The danger comes in the shape of sparks (Sparx) traversing the boundary of the game field and the Qix moving about. If Sparx touches the player, the player loses a life. If a Qix touches an unfinished line the player is still drawing, the player loses a life.
I was unaware that there had been a Qix port made for MSX2 at some point, so I thought, "Creating a Qix-inspired game on MSX1 would be a nice challenge, since I'd have to treat characters as a bitmap" and finish it as my entry to MSXdev'22.
I lived to regret that thought.
Title screen for Mix, a variant of Qix for MSX I'm writing about now.
The player is the red cross. The green face is the big enemy. The red on the left is a Tracer going clockwise. The yellow outline above that is another Tracer getting ready to respawn. Tracers are Mix analogues of Sparx and the green cabbage head is the analogue of Qix.
As per norm, this blog is more about the development process than the game itself. If you are so inclined, you can go check it on MSXdev's page.
The difficulty of drawing into a bitmap
Even the "high res" graphics mode on MSX1 is actually a character-based mode. A brief explanation of how the video memory is set up in this case is therefore useful.
The display will contain 32x24 characters, in three sets of 256 characters. The first 8 lines on screen are the first set, the middle 8 lines the second and the last 8 lines the last. Each set refers to its own definition of characters on screen -- both how what their colours are and what their pattern is.
So to determine what colour an on-screen pixel has in the main program code, I would need to first check which set the pixel row would map use, then what character is used for that 8x8 pixel area, then the byte defining the 8x1 pattern in the character, and finally the colour table that would tell what colour that one bit refers to.
There are some easy ways to simplify this, and how I did it:
- The playing field uses characters 0 to 22*8-1 (or 22*7-1 on the top and bottom sets), and they're assigned in order (0 to 22*8-1 or 0 to 22*7-1). This lets me avoid reading the pattern name from VRAM (video RAM, stuff that the video display processor reads and paints on screen every frame automatically).
- The foreground and background colours are ignored, and just status of the pixel being of foreground or background colour matters. This lets me avoid reading the colour data from VRAM.
Just about everything difficult to implement in the game is solved by having the level stored twice in RAM and once in VRAM.
White: free in all three copies. Black: active playing field outlines, present in one RAM copy and VRAM. Orange: already claimed parts, present only in VRAM. Blue: Line currently being drawn, present in one RAM copy and VRAM.
The first RAM copy is used for keeping track of the perimeter of the remaining area. The second copy contains the pixels the player has been drawing. And in VRAM, we have what is actually displayed on screen: the union of these two copies and also the painted-in field in whichever pattern I'm using.
The first RAM copy is used to limit the movement of the edge-tracing enemies move and the player. The second copy is used to make collision checks with the main enemies easy, but also to quickly remove the unfinished line from VRAM in case the player dies.
The difficulty of staying in the lines
A good part of the game's algorithmic difficulty comes in determining which pixels are inside the drawn area, and which side to not "flood-fill".
Let's assume you have the outline of a polygon drawn on paper. If you're pointed a spot on the paper, how to find out if that point is inside the polygon even if the polygon has hundreds of lines?
One answer is to place a ruler so that its edge touches the point in question and then count how many times that edge crosses lines belonging to the polygon. If the number is odd, the point is inside the polygon. (Something I learned on a graduate-level CS course, even though I think I should've figured this out on my own...)
Blue are the polygon boundaries, X is the point in question, red is the beam and black ticks mark the four intersections with the polygon. Four is even, so X is outside the polygon.
If we had the polygon outlines, we could then do the painting quick and easy. Conveniently, getting the polygon outline to RAM is easy enough -- clear the old RAM copy of the perimeter, take the position of one enemy, look to the left of that until you find a painted-in pixel in VRAM, and then follow that perimeter in VRAM for a full circle, all the while painting those pixels in the RAM copy.
After updating the copy of the fence edges in RAM, I would scan through every other pixel line and count how many times I was crossing the perimeter. Even or a perimeter pixel, I should paint that pixel. Odd, the pixel is still unclaimed area. (I'll explain the "every other pixel line" shortly.)
The next issue, then, is that since I'm doing this on pixel level, what to do when encountering a horizontal line? The line might make just a U-turn, in which case these pixels shouldn't toggle the in/out parity.
Avoiding the problem is easier than solving it: don't have horizontal lines on the pixels you scan, and we do this by restricting the player movement to only even coordinates, with (0, 0) being a coordinate the player can reach.
We still need to paint the pixels on even lines as well, but we only need the information on an adjacent odd-numbered line to do this. The only pixels lit on odd-numbered lines are either outside the polygon or a part of a vertical line. A vertical line can now end only on an even-numbered line, and pixels inside the perimeter are surrounded either by the perimeter or other pixels inside the perimeter, so all pixels lit on the odd-numbered line have to be lit also on the even-numbered line. This means applying just the logical OR with the pixels lit on the odd-numbered line and the perimeter pixels on the even-numbered line to get the pixels to be lit on the even-numbered line.
Blue pixels are outside the polygon, red pixels are the area outlines, and white pixels are inside. On the left, the vertical line continues through the even line. In the middle, the line doesn't turn 180 degrees but continues downwards, unlike on the right.
Overall, this is a single-pass algorithm with constant memory requirements and doesn't need a stack like a recursive flood-fill might (even if that might be faster, since we handle also parts outside the painted region). Unfortunately, the constant in the memory requirements is rather large.
As a very convenient side effect, by moving the player in two-pixel increments between odd coordinates I'm avoiding the case of two lines brushing against one another. This makes implementing the player controls a lot simpler.
The difficulty of having enemies
Qix had three kinds of enemies: the edge-tracing ones (Sparx), Qix in the middle, and Fuse that will follow the player along the unfinished line if the player stops. Implementing Qix was out; I wasn't going to start looking into drawing lines pixel by pixel (that would be by Bresenham's algorithm). Besides, when I had made this decision, I hadn't thought of having the second RAM copy for the in-progress line (in which case telling Qix and the player drawn line in VRAM would've become complicated). But using a fixed-size sprite actually displays how clever Qix is in its design (at least in the sense of how parts of Qix could have been implemented, but I don't know how it really was.
- When the location of Qix is updated, a new line would be drawn. While each pixel is lit, the game could just check if the pixel underneath is a part of the player's incomplete line and if yes, the player would lose a life.
- As a collection of lines, Qix would also fit through many small gaps in the map.
- Its movement is also wonderfully erratic and fluid.
Somehow, I needed to resolve all these three issues.
I didn't really succeed.
The enemy movement is a simple random process: when the enemy encounters a wall, pick a new random direction and a new random number of pixels to move in that direction.
Collision detection with the perimeter is done only at the center pixel of the enemy. This is to allow the enemy the (theoretical) chance of moving to any nook and cranny on the field.
The collision with the player's line is done for the whole enemy sprite.
The difficulty of differentiating from Qix
I didn't want to make a direct clone of Qix while keeping the core gameplay concept as is. Time to actually think what to do rather than just look at Qix.
One key difference comes from the graphical limitations. I'm not keen on the idea of colour bleed on the playing field, so I'm limited to having each pixel on screen just lit or not. As the player claims new areas, in Qix the old perimeter segments stay in the background. I suppose I could have done that here as well, but that would've meant making the painting routine and the Tracer AI more complex. Instead, I chose that the player can defeat the tracers by placing them outside.
Second is that in Qix, the player can move twice as fast with another fire button for lower score. While MSX has two-button joysticks in the standard, the vast majority of the joysticks sold here were of the regular Atari variety with only one fire button. As a result, the player can only move at one pace in Mix. (I also made the game a lot faster.)
Time. In Qix, the timer running out doesn't kill the player but instead it spawns a new Sparx. Or so I think. In Mix, the timer running out will kill the player.
Delay. When in Qix the player starts drawing a new line, stopping while drawing for too long will kill the player. This is sensible, because when the player has drawn even a bit of new line, they're safe from Sparx, and Qix might not be coming around soon. In Mix, though, there's no such penalty for stopping. The timer will still count down, and given how fast the Tracers are and how quick the main enemies are, the safety is a welcome respite.
Later levels in Mix have multiple main enemies (the pale imitations of Qix). In Qix, if you manage to separate them on different sides of the fence, the level is cleared. That's basically what I did here as well: in such case, one of the two would always be on the wrong side of the perimeter. This is actually a risk the player should be enticed to take. As a reward, in Mix the player is awarded for the whole remaining area on the field (as if it were painted 100%) and the remaining time bonus is doubled.
I think this is, in the end, different enough.
The difficulty of the end result
How to calibrate the game difficulty and scoring? I don't think I got this right. I should've used more testers that weren't me.
The biggest question I had was if the game speed should be cut to half. If the game field is 176 pixels tall, the game runs at 50Hz speed and every time the player moves, the character moves two pixels, character would go from the bottom of the screen to the top in under two seconds. At half-speed, four seconds.
In the end, I used the "full-speed" option. Qix felt too slow for me, so this was my attempt to make it more appealing to myself.
The second question is the enemy. Qix constantly changes shape and location, but I was limited to a 16x16 sprite. Its movements are random, it moves only in the four cardinal directions, and they don't "mix" around the maze well enough.
As a result, clearing the stage by splitting the two enemies on different sides of the perimeter feels too easy to me.
Left to improve?
There are some things I could improve yet before the contest deadline is over.
- Improved fill rate. Currently, the scanline for filling goes through every row, but I think this could be optimized to start from the higher row of either the scanline or where the number of perimeter pixels differs from the previous time. The scan would then end on the lowest row. I'd also need to keep track of other auxiliary variables, and I'm not 100% sure this would still cover everything.
- The cabbage heads move in only 4 directions. I should make them move in 8 directions to improve their mobility.
- Music?
- Improved static graphics. With the levels being so small in ROM, there's still plenty of room on the ROM.
- Improved sprite animations. The cabbage heads don't have a death animation.
- Bugfixes.
- The scoring from splitting the enemies doesn't double the time bonus like it should. This might already be patched in my local copy.
- Somehow, the level may be cleared with no real reason, and I have no idea what causes this to happen.
- I didn't set up the typical sprite-flickering yet, which is needed when there are more than four sprites on the same line.
And how did the game turn out?
Creating Mix had been a big task. I don't know how many hours I spent making it, but looking at file dates, I think it took about a month and a half. I think a fair guess would be 40-60 hours of work. In the end, I had to finish it because it was taking too much energy I need at my dayjob.
I don't think I reached the spot of "it's 100% done". In the off-chance that someone reaches the last level (18th), the game won't crash, just repeat that level over and over. The game doesn't have music, but since I'm not much of a collaborator and I don't know how to write music, it's not happening. Visually, there's still room to animate the enemies better, decorate the static graphics better, maybe change that cyan colour scheme to something less eye-watering.
And I really am angry at myself for drawing the game's logo apparently when I was too tired to write ASM: the M should be turned upside-down.
From the technical side, I'm satisfied. I'd like to think I could optimize the repaint routine since it always scans the whole game field. A simple solution would be to paint up and down from the player's location until no changes are observed, but I also think that's uglier than a single scan.
There's also room for speed optimization in many cases, but the game runs at 50Hz (on 60Hz systems I drop every 6th frame to match the speed), which is good enough.
In the end, when the results to MSXdev'22 are released, I expect this to rank somewhere in the middle, maybe a bit lower. The games will be rated on gameplay, sound and graphics. I'd dare to say the gameplay might be even 4/5, the sound maybe 1/5 (still better than 0/5) and the graphics at most 2/5.
Ehh, it's mostly done, so now to do other things.
LOOK WHO CAME:
