Jason’s babblings.

Nothing super interesting to write about last week.

Mostly just a lot of moving around data to support adding new screens into the game. Specifically a screen for inventory management and a screen to view Red’s status. The data storage needed to be relocated because opening a new screen requires that the game drawing thread be terminated, and since the game state data is stored in the game drawing thread, that would be terminated along with it.

To prevent this, I needed to decide whether to write all game state data into the save file, like you were quitting the game, or remove the data from the game drawing thread, then fix everything that breaks as a result. Saving the data to a file takes too much time and resources when we want to seamlessly switch to a new screen, so I went for the latter option.

Some other updates include:

• Projectile weapon charge tracking for the three types of projectile weapons mentioned in the post for Day 16.
• Player menu is dynamic based on whether or not you’re on stairs (to ascend and descend) or if you have a projectile availabile.
• Saved game versioning, so when I make an update the game doesn’t crash when I try to load an old version of the save file.
• Added inventory items into the save and load game routines.

Today and this weekend I’ll be writing up a random dungeon generator. Perhaps I’ll even have a full day to work on it between now and when I finish. I think I’m going to cut out some extra-curricular activities next week so I can put some solid blocks of time into the game. Chipping away at my todo list for only an hour every day isn’t cutting it anymore.

Current demo:

Red can change gear, drink potions, and read scrolls. Gear includes weapon slots for projectile and melee weapons, an armor slot that reduces damage, and two ring slots which can give various effects.

I haven’t had a chance to work on the game much in the past week since car shopping took up most of my free time. In fact, I’m not even sure if I’m really on day 16 or not (I don’t count days I don’t touch the game). Whatever, I’ll continue counting from there in the future.

Last weekend and yesterday I’ve been making some major tweaks to things that go on behind the scenes. First I’ve optimized the frequency of garbage collection, which has reduced random noticeable slowdown, dare I say, completely. Another fix was making the game sleep when the phone sleeps. Previously if you were to turn off the phone with the game running, it would continue to idle and drain the battery. After that was fixed, I decided to tweak the application lifecycle calls a little bit better. Basically I moved some things around so they happen in the proper order, and don’t happen when they don’t need to – like I don’t need to save the game when the phone goes to sleep, just pause the game thread.

On the visible side of things, I’ve started planning and designing an inventory system for the player. I’m concentrating on weapons and armor for now, and the idea of damage types. Like a flame sword would do fire damage, and fire armor might reduce fire damage but make you more vulnerable to ice damage. These immunities and weaknesses also apply to monsters, of course. I’ve also moved the magic (fireball) charges into the specific weapons, so you can find a wand with 7 fireball charges, but when you use them up you have to find a new wand. Unfortunately, this system is very rudimentary right now. I’d like to polish the system to distinguish between [bow/arrows which can be found in the wild] vs [magic charges which cannot be recharged] vs [throwing weapon which can be retrieved].

Current demo:

Game doesn’t suffer from noticeable random slowdown anymore. Context menu pops up when you tap on Red with Inventory, Status, and Zap. Only Zap works for now.

I’ve already been seeing a bit of slowdown in my game, and I have a hunch it’s because of the way I set up my core state machine and timer. But that’s not what I want to write about today. Today we’re going to use Dijkstra’s Algorithm to make our monsters smarter.

Dijkstra’s Algorithm takes points connected by lines with weights and tries to find the path between two points with the least combined weight of the connecting lines. This is trivial if there’s only one path from A to B, but not so much if there’s multiple routes. The algorithm goes something like this:

1. Start with all points’ values to infinity and not-final.
2. Set your starting point to zero and remember it as current.
3. For each point connected to current:
4. -If that point’s value is not-final, ignore it.
5. -If the point’s value is less than current’s value plus the weight of the line connecting, ignore it.
6. -Otherwise set the point’s value equal to current plus the weight of the line.
7. Mark current as finalized.
8. Pick a non-finalized point connected to current and repeat steps 3-8 until there are no more non-finalized points in the graph.

Now each point’s value is the shortest possible combined weight of the path to the starting point. To find exactly which lines to travel, just traverse backward through the lowest-valued points until you reach the destination. Easy!

The point-line paradigm can be easily applied our game map: the points are map tiles, with a line to each of the tiles surrounding it. If we mark the player’s location as the starting point and each line has 1 weight, we can determine the number of steps required to hit each map tile, and the optimum path for each tile to get back to the player. So now if we have a monster on any tile, we can chase the player around corners; instead of having the monster blocked by a wall while trying to go north-west, it can go north to get around the wall. The monster can also seek out higher valued tiles if he wants to run away from the player.

I tried three approaches to write this algorithm for the game. The first attempt was an elegant recursive algorithm, which threw a Stack Overflow error after traversing 250 lines. Next attempt worked successfully, but took about a full second to calculate each tile – much too long. After some tweaks, I had it down to 1/20th of a second. Much better.

Aside from that, I did end up rewriting the core state machine to make the game very noticeably faster. And a few more things since day 10:

• Haste status effect: you make two moves for every one enemy move.
• Slow status effect: enemies make two moves for every one of your moves.
• New slime enemy that uses the slow effect.
• Optimized how projectiles are handled.
• Fixed nasty bug when when monsters and projectiles are destroyed.
• Moved all strings into resources so they can be easily translated in the future.

Current demo: Game runs at double the previous speed, and enemies follow you without getting stuck on walls. There’s a new type of enemy that keeps slowing you until you kill it.

Now that we have our first trappings of a proper game, we should make it save the game between gaming sessions.

Android provides us with four ways to save our data from being lost forever, but first I will go on a tangent to explain the two types of data we should be concerned with: persistent and transient. Let’s say we’re writing a race timer application that keeps track of fastest times and includes a stopwatch function. In this case, the fastest times are persistent data because we want to be able to go into the application and see them after we close it. The stopwatch timer is transient because we don’t care to keep it if we close the application after a session of races. In most cases it’d be a nice feature to keep the stopwatch timer, but for the sake of the example, we don’t care about it.

Android offers us three ways to store persistent data: simple-settings based based, flat-file based, and database based data files. It also comes with a fourth way for transient-only data, but we’ll get to that later.

The first way is the simple-settings file, which will store simple primitives – a boolean true/false, a number, some text – and offers a very clean way to load the data later. This is good for simple settings, as the name would imply, but it’s not great for more complex things like custom objects or dynamic lists of simple objects, or dynamic lists of complex objects, god forbid. For that we’ll need something more flexible.

Databases offer a wonderfully powerful way to easily organize data and link the relevant pieces together, and provide a great interface for pulling only little bits of data at a time as it’s needed. For instance, if you have a notepad application that you want to pull out the titles of each note to display in a list, then you click on one and it loads that specific note’s body text at that time – the benefit is you don’t need to pull every note’s body text to display the initial note list, you can save it until you choose which note you want to view. The drawback of using this method is there’s a lot of overhead to creating and using the database. If we’re not selectively loading our data – as is the case with the game – the benefit is lost and the overhead is not worth it.

Finally, we have the flat-file. For this, we can only read and write text to a file. It doesn’t sound very complex or helpful at first glance, but it’s lack of complexity is made up for with it’s immense flexibility. If you can create a way to translate your complex objects and lists to and from a text string, you can simply write it to a file and read from it. The hard part is formatting your complex objects into a string that can be parsed later. Fortunately there’s a few libraries out there that can help us with this (json, xml, etc).

Now, the Android has a strange quirk where if you change the orientation of the device – landscape or portrait – it’ll destroy all data, even in the middle of running an application. You can stop this from happening by locking the device into a specific orientation, but offering support for multiple orientations is more user-friendly. This is where, in addition to the persistent data being captured using one of the methods above, we’ll capture transient data – so we don’t see the timer clock (using the run timer example) reset when we tilt the screen. This transient data is stored in a special fast-access section of memory so it’s quickly stored and retrieved, but it’s not intended for the often-more-hefty persistent data, which is stored on the file system.

Game updates:

• Added the hooks necessary to let us know when we need to save and load.
• Created a load method to match the save method from last update.
• Players and Monsters can now cast projectile spells.

Current demo: Monster AI changed to throw one fireball when the player is in range. Red can launch a fireball too, but he only gets one per monster he’s already killed. The number of enemies per level is increased, as is Red’s initial health to make games last a little longer.

Here’s a video of the enemies and fireballs in action.

Now the good stuff. Let’s make some enemies! This is actually really easy with polymorphism, or inheritance of object properties.

Monsters will extend the Character class to inherit any Character stats and routines (most importantly the movement functions), similar to the Player extending the Character class. Also similar to the Player class, the Monster class will add a few extra things that are specific to monsters (like the AI routine). Really all we need to do is to define the sprites for this Monster and give it an artificial intelligence. That is the beauty of polymorphism.

We can do some fun stuff with the AI routine. For instance, we could have the monster pursue the character, or look for other enemies of its own type and group up before attacking, or hide and ambush the player solo. For now, let’s give our simple monster a routine that if Red is within two spaces of him (using our Coord’s distance function) he’ll chase Red and attack, otherwise wander randomly. Again, since we have everything set up in Coord, we just need to hook it all together and we’re done. Other monsters will have different attack strategies, but I won’t reveal them just yet.

Now let’s update our Player object. Since we have enemies, we want this character to be able to kill them and level up. The Player is inheriting the movement routine from the Character class, but we want to override it so we can check to see if we’re close to a monster, and if so, attack it. Here we only need to define our attack routine to define how much damage we do, and we’re set.

Back to the main game handler, we’ll keep track of a list of monsters, so we can cycle through them to draw or do the AI. We should also give the game an objective: kill as many monsters as you can before they kill you, and spawn them each time the map is cleared. Sounds fun doesn’t it? Yes, it does.

Some other updates since last time:

• Added a HUD to display Red’s level, gold, and health.
• Optimized the game’s state handler to kill some potential memory issues down the line.
• Added a save-game for when we exit the game. Haven’t created the load-game yet, so this is useless for now, but it will be useful later.
• Moved the animation frame tracker to all Character classes (Monsters and Player) so they can keep track of their individual animations.
• Updated the draw routine to make all monsters walk between tiles (instead of teleport, as Red used to do).

Current demo: Enemies have a health stat, and they fight back if they aren’t killed quickly. The game ends when Red loses all his health.

I decided to publish the game as it is and hang up my Android development hat. Back to playing WoW. There’s a little late April Fools joke for you; I hope you enjoyed it.

There’s one more game control feature we left out from yesterday that I’d like to add.

The touch screen, as we left it yesterday, requires you to tap the screen every time you want to move Red a space. The TOUCH event only fires once, even if we hold our finger on the screen. We want to make it so if you tap and hold, it keeps moving your guy in the same direction. For extra credit we’ll make it so when you move your finger, the guy will start moving in the new direction. The thing is, Android doesn’t come with a HOLD touch event, so we’ll have to get creative with the TOUCH, MOVE, and RELEASE events.

First we should update our TOUCH event to store the touched coordinates into a variable (we’ll call it touchCoordinates), and set a flag that says we’re holding our finger on the screen (touchHolding), then we’ll call the analysis routine to periodically check if we’re still touching the screen and which direction we need to move. Now we’ll make the new RELEASE event to unset the touchHolding flag, so the analysis routine knows to stop checking. Finally, we’ll define the MOVE event to update the touchCoordinates location. Our analysis routine now knows when we touch and release the screen, and when we move our finger to a new direction. Clever huh?!

Next update I’ll write about adding enemies.

Current demo: We can tap-hold to move Red now. I’ve also added enemies with very simple AI (wanders randomly) and no stats. Here’s a video if you want to see it in action: http://www.youtube.com/watch?v=VsK2LJ9BmqA

Today we add a very important feature to the game. Some Android devices don’t come with a keyboard, so we must allow users of such devices to play the game using the touch screen. We’ll also add diagonal movement into the mix and make it so we can add solid walls into the map.

First step in the touchscreen process is to divide the screen into nine parts – four cardinal directions, diagonals, and center. Android comes with a really handy Rect object that stores a series of coordinates (like the Coord object from yesterday) that represent the top left and bottom right corners of a rectangle, and a Rect.contains(x,y) method that tells you if an X,Y point is contained in the rectangle. This is very easy stuff to do myself, but why reinvent the wheel, right? Right. We’ll make nine of these to store the nine regions of the screen, and We’ll test the X,Y touch point against each to figure out which direction Red should go.

Next we need to capture when the user taps on the screen. Android makes this easy for us by allowing us to override certain system calls; we can say “instead of doing what you normally do for screen taps, do this“. This, in this case, will be to move Red one square in the direction we tapped.

I should mention that TouchEventListener (aptly named, as it listens for when the user touches the screen then does what we want) listens for three events: TOUCH, MOVE, and RELEASE. Interestingly, the system ignores all RELEASE events unless we acknowledge a TOUCH event. This make sense because a RELEASE event should not be expected without a TOUCH event, but it’s annoying because we might not care to do anything when the user touches the screen, only releases, and we don’t want to have to take the extra step to acknowledge it. This doesn’t affect my game because I’m doing everything on TOUCH, for now.

Now we have our touch screen mapped to eight directions and a center (unused for now), and we have our previous movement code from the keyboard. We just copy it over and be done right? WRONG! Repeating code is generally bad – it’s sloppy and difficult to maintain. Let’s say we need to update our movement algorithm, so we update it in the touch screen but forget to update it in the keyboard. The game might act weird at best and catastrophically fail at worst. Instead, we’ll move the character movement code into the Character class, and call the Character’s movement functions from both the touch screen Listener and the keyboard Listener.

Current demo: Red can move diagonally using either the keypad or the touch screen. He is now trapped in a predefined map with corridors and rooms and walls.

Up to this point I’ve been hard-coding a lot of things in the game and not leaving a very much room for expansion. This is quick and good enough for testing things, but ultimately as the project gets bigger, it can get messy. Today we’ll do some code redesign so we can expand to add new map tiles and and character types – that means enemies! For today’s note, if you’re unfamiliar with Object Oriented programming and design, you might find yourself going a bit glossy-eyed. I’ll forgive you.

Our game uses a lot of X/Y coordinate pairs. It’s not a terrible inefficiency to have two variables here, but it looks a bit cluttery when declaring the two variables, and if we have to set both variables at the same time. A Coord object would do nicely to store both X and Y coordinates of anything – pixel coordinates, map tile locations, player locations, etc – so we can create and update both X and Y variables at the same time. Not necessarily more efficient, just cleans up the code a bit. We can also add some helper classes to this Coord object to check if it’s within a specified rectangle, or to check the distance between two of these types of coordinates easily. This will be handy later when we have characters interacting.

Next we’ll create a BitmapHelper object that initializes, processes, and stores all of the graphics files used by the game. Think of it like a librarian that knows exactly where all books are at all times. We can ask the librarian for any tile, creature image, or series of animation images and it’ll give them to us, ready to be drawn. Moving the graphics stuff into its own object is also nice if we want to use it in another app, we can just grab the object file instead of copying and pasting pieces of code from the Game object. We’ll also see benefit from this by not having to wade through game code to add another graphic, everything is neatly packed away in the graphics object.

Current demo: Aside the background changes, I added a walking animation so Red walks to adjacent tiles instead of jumps.

Please note for today’s writeup, all coordinates assume the very top-left is 0/0, increasing X as you go right and increasing Y as you go down. Also when I say map location, I mean the location on the entire map, grid or ‘visible map’ means the visible portion of the map on the screen, and pixel is each little dot on the screen. Now that we have that cleared up for the less technically savvy, on with the show.

Yesterday, we left the game drawing a subset of the map and Red traveling around the subset. Today We’ll make it so Red can travel around the entire map. To do this, we’ll need to come up with a way to represent movement around the whole map.

We could keep the visible portion on the same section of the map no matter what – even if Red is not on a visible tile. This is just silly, and I’m disappointed you would even suggest it.

Another option is to keep the view stationary until Red reaches the edge of the map, then adjust the visible portion of the map so we can still see where Red is going. This is better, but it still leaves some surprises if there’s an angry killer bunny right next to us on the next screen that we didn’t see (this is one of the things that bugged me about old Zelda games).

Yet another option is to keep Red in the center of the screen at all times, and move the grid around him. Essentially, adjust the visible portion of the map whenever Red moves to a new tile, so you always see the same range of tiles no matter where you are on the map. This is the method I’m going to use for this game.

This change will require another major overhaul to the drawing routine to figure out exactly how to choose which map tile to start drawing in the upper left, and how to nudge the map so Red appears in the middle of a tile (instead of standing between two tiles). I won’t go into details here to keep things simple, but you can ask if you want details.

Current demo: Red stays stationary in the middle of the screen and the grid is drawn around him. As Red moves, the grid is adjusted so you always see the same range of tiles around Red at all times.

Today’s goal is to change the screen drawing method to use the second method described yesterday, and implement a tile-based map that Red could be drawn on and move around.

Taking a look at the sample code is overwhelming. It’s important to take code like this and poke with it, intentionally break things to see how they break, and just have fun. The debugger that comes with the Android Dev Kit is really nice and works well to see what’s going on in the sample. Once we’re done messing around, we’ll take the code and clean it up to its most basic elements: the game setup, the keyboard movement routine, and the drawing routine.

The map for the game is a grid of tiles, with each tile being a wall tile, floor tile, trap tile, switch tile, etc.

The first experiment was to draw the entire map on the screen at one time – even the tiles that weren’t drawn on the screen would be run through the drawing routine and put into memory. The map held 40,000 tiles (200×200) where each tile is 400 pixels (20×20). That means the routine would process and draw sixteen MILLION pixels with each time the screen would redraw. This resulted in a very poor frame rate -  4 frames per second – and would probably kill the battery dead in no time.

We should probably optimize this to calculate the number of visible tiles on the screen based on the device’s screen resolution (more on this later), and only draw those tiles for each frame. On the emulator, the screen fit a 23×17 section of the map, so we really only need to draw approximately 156,000 pixels each frame. This will improve the frame rate to faster than the LCD is physically able to draw, with time to spare for the inevitable extra logic in the game for enemies’ artificial intelligence and such. Reaching a hardware limitation is a very good thing.

As an added note, this graphic routine should automatically resize the visible map based on the hardware configuration of the device you’re using. If we were to configure the game based on the screen resolution of the lower resolution G1, the game would look like crap on the higher resolution Droid. Taking the resolution and screen size into consideration early will save a huge headache later when testing on multiple devices.

Current demo: Red is displayed with a two frame animation on a grid map. Pressing a direction will move him to a new grid location and update the direction he’s facing.