Category: Kev’s Blog

Posted on

Game development in progress: Space Invaders clone – update 2

Earlier this year I started developing a Space Invaders inspired game for Android. I started back in March, and have worked on it for a around 20 to 30 hours or so, on and off. Not being an expert in Android development or game development in general, it’s been a learning experience. The book I read back in March, Android Game Development by Example, was a good book to get started. I realize I probably could have got to a playable game quicker if I’d used a game development platform like Unity3d, but I wanted to get to grips with writing a game by from the ground up first. I’ll circle back and probably rewrite it using something like Unity later.

Right now I’m at a point where it’s playable but there’s a few key features I still need to add, like the bases/shields at the bottom of the screen, and the invaders need to shoot missiles at the player. It’s a pretty easy game at this point 🙂 I have a few ideas for some gameplay variations to add too.

I started implementing as a standalone Java app using the Java2d api and the 2d game engine that I’d previously worked on for my first attempt at a game in Java, a version of one of the classic Nintendo Game n Watch games, Turtle Bridge.

I tried to replicate the animation of the invaders moving one at a time, one row at a time and got pretty close:

Compared to current day AAA tier video game development projects which typically have multi-million dollar budgets and teams of artists, story writers, sound engineers, QA, developers, as well as marketing and PR teams, I find it fascinating that Space Invaders was originally developed by a single developer, Tomohiro Nishikado. Not only did he develop the sofware for the game, but he also designed the hardware on which the game runs.

There’s some interesting features of the game that were not part of the original design, but resulted from limitations of the hardware. For example, the invaders speed up as fewer are left remaining on the screen. This is a defining feature of the game, but was a side effect from the 8080 processor being unable to animate a full screen of invaders at the same speed compared to a screen with only 1 or 2 remaining. Rather compensate in software to keep a constant frame rate, this feature was kept.

Other features in the game play logic could easily be overlooked by a casual player:

  • The mystery ship appears on a regular, timed basis, at around each 25 seconds
  • The mystery ship is worth 300 points on the first 23rd shot on each screen, and then 300 on every 15th shot for the remainder of the screen. For all other shots it’s 100 points (if you play for high scores, then this fact is probably very well known to you 🙂 )
  • Missiles from the invaders will not kill the player if fired from the last row on the screen

Here’s a quick video of how far I’ve got so far. This is running on a device simulator, so the frame rate is not as fast as on a real device:

I’ve still got some work to do, but I’m pleased on my progress so far.

Posted on

Unix source commit history from 1970 to present (and links to other shared commercial source)

A single github repo has been shared that combines historical commits for the Unix operating system going all the way back to 1970.

As a software developer I find it fascinating to look at the source of other software that you use and often take for granted. We’re lucky enough to be able to freely browse source of many open source projects, shared on github and other online repos. You can learn a lot from looking through code written by other developers.

There’s also a many interesting and previously commercial systems that have had their source publicly shared. A few examples that I’ve come across:

Posted on

Android development: drawing text on a Canvas

I have an Android project bubbling away. More details soon 🙂

I’m using a SurfaceView and needed to draw some text on it. The rest of the app is mostly drawing on the SurfaceView Canvas directly, but I need some text too.

I’ve dabbled with some Android development before, and I have to admit getting the layouts to do what you want them too almost seems to suck up the majority of my development time 🙁 This time round I got sidetracked trying to create a layout that was using a mix of TextView elements and adding my SurfaceView programmatically. This didn’t go too well, didn’t work at all, so I found a few posts like this, and worked out you need to draw directly on the canvas. Something like this does the job:

Paint textPaint = new Paint();
textPaint.setColor(Color.WHITE);
this.canvas.drawText("Hello world!", 20,50, textPaint);

This code is in the middle of a game display loop, but for completeness, to be able to draw to the Canvas first you need:

SurfaceHolder surfaceHolder = this.getHolder();
if (surfaceHolder.getSurface().isValid()) {
    this.canvas = surfaceHolder.lockCanvas();
   ...
}

And then to release the Canvas after you’ve finished drawing:

this.surfaceHolder.unlockCanvasAndPost(this.canvas);

 

Ok, next up, what about custom TTF fonts? Drop the TTF font you want to use in your assets/fonts folder, and then load it up with:

Typeface typeFace = Typeface.createFromAsset(this.context.getAssets(), 
    "fonts/yourfont.ttf");

To use this font with the text snippet above, just call setTypeface() and pass it in:

textPaint.setTypeface(this.typeFace);

Ok, how about specifying a font size that’s proportional to the resolution of the user’s screen? This is an interesting question. To avoid using fixed pixel size fonts and then having them not scale appropriately for different devices with different screen resolutions, Android uses a concept called ‘scale independent pixels’, or SP. This is described in this post here. In short, defines an SP value in /res/values/dimens.xml/dimens.xml like:

<dimen name="scoreFontSize">20sp</dimen>

And then reference and set it like this:

int fontSize = getResources().getDimensionPixelSize(R.dimen.scoreFontSize);
textPaint.setTextSize(fontSize);

Done! (I’ll share more on what I’m working on in a few days 🙂

Posted on

Can you develop code to effectively solve a problem without understanding the problem first? (writing code to solve Sudoku puzzles)

You shouldn’t have to think too hard to answer this question. In order of most likely answer first, least likely last (I hope), your answer could be one of:

a) No. How can you solve a problem if you don’t understand what it is that you’re trying to solve?

b) Possibly, if your approach to solving a vague or poorly defined problem is to ask clarifying/fact finding questions to investigate and gain an understanding of the problem so you can get to a position where you’re able to solve the problem.

c) Yes. (Really?)

There’s no correct answer to this question although I hope you initially answered (a), but (b) is a valid possibility if you consider the effort to understand a problem is an essential part of solving a problem (which of course it is).

I decided I would have a go at writing a Java app to solve Sudoku puzzles. I’m familiar with the rules of Sudoku and have solved a few puzzles by hand. I’m not an expert by any means, but I know enough about this type of puzzle to realize there’s probably at least a few well understood algorithms for effectively solving them, but as I started out I wasn’t familiar with any particular approach.

So here’s my experiment: I decided I would deliberately avoid doing any background reading on known algorithms or reading any articles or discussions on approaches for how to solve, and would attempt to blindly develop my own approach to solve a puzzle to see how successful (or otherwise) I would be. I know the rules to the puzzle, I understand what the end result must be, so how hard can it be, right?

For those unfamiliar with Sudoku, here’s the 3 rules:

  • each 3×3 square must contain each digit 1 through 9 with no repeated values
  • each column must also contain each digit 1 through 9 with no repeated values
  • and the same rule for each row, 1 through 9, with no repeated values

Here’s my starting puzzle that I used to write my code against:

      | 8 1   | 6 7   
    7 | 4 9   | 2   8 
  6   |   5   | 1   4 
- - - + - - - + - - -
1     |     3 | 9     
4     |   8   |     7 
    6 | 9     |     3 
- - - + - - - + - - -
9   2 |   3   |   6   
6   1 |   7 4 | 3     
  3 4 |   6 9 |

(Puzzle generated by WebSoduku)

My initial approach for my algorithm was to follow the steps I would go through by hand if I were solve a puzzle on paper. This already set me off at a disadvantage because I don’t think I’m particularly skilled or experienced at solving Sudoku, so I wasted some hours trying to capture these steps in code. Going down this path I realized if you take this approach, you mentally ask several questions as you look for possible values for empty squares, but it’s not not the answer to any one of questions that gets you a correct answer, it’s the combination of answers to multiple questions (because there’s 3 constraints, above, that you need to follow). So following this approach, I wrote code to iterate through the complete grid applying my limited set of questions to find potential values for each empty cell. The result was after a couple of iterations I had inserted values into all empty cells as sets of potential values, but my approach was not complete enough to be able to solve the example puzzle I was using for testing.

This is where I reached my point of realization. Clearly I did not understand enough about the problem to be able to write a program to solve it.

After some debugging and tweaking to my approach, I did reach a point where I could solve my test puzzle in 7 passes through the grid, but when testing the same approach with another easy puzzle, my approach failed to reach a solution. So my approach only partially works when I have a starting point with enough values, or a certain distribution through the grid, but fails to solve all puzzles.

At this point I could have continued blindly in the same direction, but I decided I had already proved to myself my point that you can’t solve a problem if you don’t understand what it is that you’re trying to solve. It was time to read up on the the established algorithms to solving, so I could understand what it was that I was missing.

There are a number of established algorithms for solving Sudoku, and I won’t describe or cover them all there, but there’s a good summary on this wikipedia page. The approaches range from brute force (sequentially testing each value 1 through 9 in each cell, with backtracking to prior cells if chosen values fail to find a solution, to variations such as Donald Knuth’s Dancing Links algorithm.

My conclusion to my original question though is clear: had I recognized the problem as an example of an exact cover problem, I would have known that there are established algorithms for solving this type of problem.

You can’t solve a problem if you don’t understand what it is that you’re trying to solve.

If you’re interested in taking a look at my partial solution you can find it here on my Github.

Proudly powered by WordPress