Mass Destruction Update 1: Bare Bones

It turns out with a powerful engine like Unity, Bomberman isn’t that hard to replicate! Here’s what I’ve got working so far:

  • Able to spawn breakable and unbreakable tiles on startup
  • Player can spawn bombs at his location
  • Player can pass through the bomb until he walks out of the bomb’s hitbox, at which point the bomb becomes a solid
  • Bombs detonate in 3 seconds, creating a cross-shaped explosion
  • On contact, explosions will kill the player, detonate other bombs, and destroy breakable tiles

As to coding strategy, I’ve taken a more independent object approach as opposed to having a “main controller” that moves everything around. Unity offers a tagging system, so if one object wants to interact with another, it just checks the tag to see if it’s of the proper type. The stage itself controls spawning of objects, so it would be the “main controller”. However, the objects move themselves and the stage doesn’t know what happens unless one of them tells the stage to do something (i.e. spawn more objects).

So far, I’m loving Unity! It’s not nearly as complicated as it seemed before, and the project is going smoothly. Of course, I haven’t gotten into graphics/animation yet, but we’ll see how hard it is (might find someone else to do them).

Bomberman, Unity Style

I recently got (back) into Unity and decided to try my hand at making a game! The modern world lacks a good version of Bomberman, so I’m going to do this game justice by making a clone of it: Mass Destruction!

If you’ve never played Bomberman or a similar game before you’re missing out. It’s an arcadey game where you walk around setting bombs to blow up tiles and other people. The version of my childhood, Dyna Blaster also had a campaign mode where you blew up critters, but the main draw is the multiplayer aspect. Here’s a decent online version that explains it well (and in penguin style) : http://www.gamesxl.com/multiplayer/bomberman-multiplayer.

On Unity I’m going to attempt a version of the game with 3d graphics. Hopefully by then end I’ll have a fleshed out game with the following classic Bomberman features:

  • Walk a round setting bombs which kill people and tiles
  • Tiles drop a couple powerups (more to come on creativity): extra bombs, extend bomb range, kick bombs, walk faster
  • Timer that once expires, kills players by shrinking the stage
  • Online feature to play with other people

The last one will be the hardest of course, as I’ve never attempted something like it. However, equipped with Unity’s great tutorials, I’m sure it will be doable. Speaking of Unity’s tutorials, after finishing their basics tutorial here, I’ve already got a functional moving ball (later to be the player) set up, with some changes. Notably different from the tutorial, is that in this game, the player doesn’t accelerate/decelerate but instead moves at fixed speeds.

Build 1

Nothing too exciting yet. But have high expectations!

Instruction Set Architecture: The Bare Minimum

I’d like to introduce my understanding of “Instruction Set Architecture” aka ISA here, and close off with a pretty cool example we learned in class. To kick it off, here’s a question that floated around in my head but sort of took for granted:

Do different programming languages compile into fundamentally different programs?

And the answer to this is no. As in, once source code is compiled, the resulting program is a common computer language called Assembly. (There’s different versions of assembly, and I think this depends on the compiler/computer.) So no matter your programming language, ultimately the compiled program is written in the one language that your computer can actually read and run.

What does this language do? Our programs have tons of instructions that do things which seemingly never affect the actual, real computer that it runs on. If I define a variable with ‘int x = 0;’, what happens? Assembly makes it clear what each line will do, and what actual pieces of hardware it manipulates.

This is where Instruction Set Architecture comes in. ISA is the line between software and hardware in a computer: it lets you communicate between the program and the components of a computer. I’ll introduce the different components in a later post, but first understand this: every program instruction changes something in the computer. Be it defining a variable, adding two numbers, or calling a function, something physical has to happen to excecute it.

So what happens? Glad you asked. As it’s name implies, there ISA is a set of instructions, sort of like function names. If I want to add two numbers, I might call the “add two numbers” instruction, and the computer will run some stuff through its memory and ALU (arithmetic and logic unit) and add two numbers for me. The actual implementation of this adding instruction is found in something called the “microarchitecture”. The microarchitecture essentially contains the implementations of the functions named in the ISA.

There may not be an “add two numbers” instruction that does exactly that in the ISA. Instead, there are instructions that are capable of adding two numbers, but may not do only that. Let’s put that more clearly. Every programming language has thousands upon thousands of basic commands and functions. When compiled, all of this has to be transformed into a bunch of ISA instructions. So we know the ISA has enough instructions to perform everything you would want to do. But instead of creating carbon copies of the 1000’s of commands, the ISA uses far fewer, along with a smart compiler that can express all sorts of commands as a combination of these instructions.

How much fewer? Let’s get to my cool example (yay!). What is the smallest number of instructions that we would need in order to express every single C++, Java, and other programming language’s operations? It may seem overwhelming, but often operations can be grouped together.Let’s break down the different types of tasks we want to do:
1. Arithmetic. Adding, subtracting, and the like are all important. Note that once we can add, however, we can do everything: subtracting is easy, and all other operations can be approximated in some way by it.
2. Access memory. Everything has to be stored somewhere. If we want to reference a variable, we need to read it from somewhere. If we performed an operation, we need to store the result somewhere.
3. Conditional logic. The ones that probably immediately come to mind are if(), for(), and while() loops, but even things as simple as calling a function involves jumping around in the code. We need ways to do all of these.
And that’s it! Every single operation we ever write can be coded into one of the above. (Side note, when learning this our teacher never mentioned input/output such as displaying text, but I assume this is somewhere else in the architecture, since things like display are part of the hardware.)
So how many instructions do we really need? If you’re ballsy you might say 3, one for each category. But actually, we only need one! That’s right, one instruction can successfully compile every single operation out there. And it looks like this:
subleq(a,b,c){
Mem[b] = Mem[b] – Mem[a];
if(Mem[b] <= 0) goto c
}
Subtraction is easy to see here. We can access memory by letting b be where we access and a be 0. We can jump to something by putting a negative number into memory and letting b reference it.
That’s not fair, you say! That function clearly uses things like subtraction and an if conditional in it. Where’s the implementation for those? Well this whole thing is all one instruction, you see. The microarchitecture that performs each part is still all one instruction and inseparable. Obviously it’s not the most efficient way to do anything, but it’s the smallest! (If it seems like a loophole, better suck it up, because CS is all about loopholes!)

Writing the A* Algorithm

This is Part 3 of my A* Pathfinding!
Part 2: Reading and Displaying Boards of Tiles
Time to work on the A* algorithm! I had this explained to me from policy almanac: http://www.policyalmanac.org/games/aStarTutorial.htm. It should be about the same everywhere, although other sites discuss it more in terms of nodes and graph theoryish stuff.

Taking on this algorithm is the scariest part of the project–there’s a lot of data to handle, and I’m not too familiar with all of it. Luckily, the site describes the steps pretty clearly, and I should be able to make a clearish outline.

Given map, start, destination
1. Add start to open list
2. For each reachable square:
– add to open list
– signify that start is ‘parent’
– compute F score
3. Remove start from open list, add start to close list

Process then repeats more or less, with a couple changes.
1. Remove A from open list and add A to closed list, where A is tile with lowest F score on open list
2. For each reachable square from A not in closed list:
– add to open list if not already in
– compute F score if it doesn’t exist
– compute G score using A otherwise, and replace old G score if new one is lower
– change parent to A if new F score is used
3. Cycle back to first step

Terminate at step one once A is the destination. The shortest path is found by tracing all the parents back to start.

There are a couple details that are dependent on the model. For my grid, reachable squares are adjacent up/down/left/right and not diagonals. Also, F score is computed through F = G + H.
G = movement cost from start to tile, one per tile walked
H = distance from tile to destination
= |row of dest – row of tile| + |column of dest – column of tile|
For those new to A*, the calculation of distance, H, is one of the most variable parts of the A* formula. For example, I couuuuld use the standard distance metric of root(x^2 + y^2), but since we’re walking tiles I’ll choose not to.

Bonus
Back when I was a math major I was learning of different “metrics”, and there was a class of them called d_p, where ||x|| = (x1^p + … + xn^p)^(1/p), and they defined some complicated spaces called L_p spaces. Thought it was totally useless. But now I see that my “distance” is d_1 on two dimensions, and the standard distance is d_2. Maybe for different tile arrangements (hexagon, more dimensions, etc), other distances could be used?

Anyway. My computation of H is easier than all that.
Once I’ve found the shortest path, I’ll return a path struct, containing an array of tiles (starting at start and finishing at destination), and an integer for the length of the array.

One extra paramenter I’m taking in is an integer determining what tiles are walkable. I may change the implementation later but it’s good to have it. For example, “0” means I can walk tiles labeled “0”. But maybe I’ll have tiles labeled “1” that “0” can’t walk through, but if I want to bypass that I can change the parameter to “1” to indicate that.

Once I can output paths, I’ll work on a function to turn it into a highlight array, as well as update the drawing function to handle it.

The moment I start, it becomes glaringly obvious I’m going to need a buttload of arrays to store my lists. Some of these are 2d integer arrays, but some data has to be stored in 2d point arrays when I need to store (x,y) values. This involves creating the point struct.
Int arrays:
– tiles, original array that is inputed
– closed & open, each spot is 1 or 0 for whether it is closed (or open)
– gScore & hScore, containing gScore or hScore
– fScore, sum of gScore and hScore. This was added in later because I figured it’s better to precalculate this value than risk having to calculate the same value multiple times.
Point arrays:
– parents, indicating the parent of the tile
– path, the array that is returned. This is a 1d array.

Here are the additional functions that I ended up writing to ease creating structs. A lot of these are pretty standard when working with tiles, so I’ve written those before and doing them again isn’t too hard.
– pt to generate a point with given values. Since everything is in integers, so will the point’s x and y values.
– blank2d to generate a 2d integer array filled with 0’s
– point2d to generate a 2d array of empty points
– neighbors to generate a path containing the 4 adjacent tiles of a point
– valid to return whether given point is on board
– reachable to determine whether a tile is walkable under a filter. This part will be modified once more tiles are introduced.
– g and h functions to calculate respective scores
– updateF to update fScore when g or h is changed
– newParent to change a point in the parent array. This is a function because the old point (if it exists) needs to be freed every time.

Implementing all the functions wasn’t too difficult. The one major compiler error I ran into was a segmentation fault, as usual. The lldb debugger wasn’t telling me which line it was occuring on for some reason, so I ended up narrowing it down through commenting out code and using printf to make checkpoints. As it turns out, it was because I tried to access points in the closed array before I checked that these points were actually valid. With that figured out, everything compiles nicely.

A little bit of testing on various boards reveals that my path isn’t always optimal. Dammit! I always fear errors after a successful compile the most, since they are a lot harder to pin down. In this case, I made the right guess as to the problem in one–the portion of the code that changes the parent if something is already in the open list but has a lower G score via the new A tile. I had a less than symbol pointing the wrong way (facepalm), an easy fix.

Without any further noticeable errors and a pretty much instant run time on a 15×15 grid of numbers, all that is left to do is to make a draw function that highlights our path. To increase support for highlighting in general (say I want to highlight two different paths, etc), I’m going to convert the path into a 2d integer array, with 0’s where there are no highlights.

pathToArray is pretty easy to write, and along with that, I updated drawBoard function to handle the highlight array by modulating the color of the highlight with the tile (each of r,g,b are 0-255, so multiply them and divide by 255 once)

And with that, my A* project is complete!
Most important functions:
– boardToArray reads a file of 1’s and 0’s
– shortestPath finds the shortest path given a board and two tiles
– drawBoard turns a board and highlights into a .ppm image

The most prominent changes I would make if I worked further:
– incorporate the list struct into my project. Notably, I currently find the next open tile to work with by searching every single tile, which is inefficient. Instead, I can track the tiles by just adding coordinates to a list, and only check that list.
– output a different image format. Unlike lists, this is a skill I haven’t actually learned yet. Nobody really uses ppm files, and I’m pretty sure their file size is bigger than they could be.

_______________________
The more I thought about it, the less it made sense to search every tile. I ended up adding a plist struct (list of points), and replaced numOpen with openList, a list that I can search through for open tiles. The most annoying part now is that I need to duplicate points when I place them into the list, since freeing of the current point A and freeing of the list is handled separately. If I could read my own code a lot faster or started with a list implementation this problem could be easily fixed. This is also reveals the advantage of languages that handle memory allocation automatically, since this would not happen.

Read my next post for the source code and some pretty pictures: A* Pathfinding Source Code

Reading and Displaying Boards of Tiles

This is Part 2 of implementing my A* algorithm! Intro: A* Pathfinding – Intro

I start off with implementing the ability to read integers off a text file. The goal is to process multiple lines of integers, separated by spaces. Reading user input in C has always been one of my fears, and the scan/get functions are a little tricky, which is why it’s always good to work with them. As it turns out, because lines have variable length, I need to iterate through the given file twice, once to count each line’s length, and again to actually track the values. The result is our first function, boardToArray, which is an array of integer arrays.

Not too difficult, and we have the first step of our drawing program.

The next step is to convert this array into pixels and print that out as a .ppm. In order to make handling our array easier, I need to somehow pass in the number of lines/tiles per line, so I change my boardToArray function to output a custom struct containing all that. One benefit is I can modify this struct later to contain a highlight array also. To handle colors, I also creat a color struct with R,G,B values.

In addition, instead of having a fixed tile width and height, my function will take in parameters for them. In the future these parameters may become optional, but I haven’t learned how to do that yet, so it’s just something to keep in mind. For now my drawBoard function will handle -1 as no tile (white) and 0 as empty tile (grey). I may add borders or flashier tiles later, but that is a lot more time consuming so it will end up being in a different project.

Once again, very straightforward implementation. One issue is that I iterate through the width and height (in pixels) of each tile, as well as the width and height (in tiles) of the board, so that I end up with operations on the order of n^4. This might not really be an issue since it’s really n^2*m^2 for pixels and tiles, and that I’m only making one calculation per pixel in my image. It might be faster if I was writing into a different kind of image file, but for now .ppm is all I have.

I also implement a boardFree function to free memory from a board. Take a step back to see my completed work:
Draw.c file
– board and color structs
– boardToArray, takes a file name and spits out a board
– drawBoard, takes a board, tile width/height, and prints out ppm file
– boardFree, frees memory allocated to a board

Before advancing, a little playing around with different boards starts to crash my program. Tinkering around reveals I allocated insufficient memory to my array–using number of tiles instead of number of tiles * sizeOf(int). A reminder that alloc functions are sneaky and might now show up even when your code runs!

A* Pathfinding – Intro

In the old days, I worked on a tile-based game where characters moved on a grid, sort of like fire emblem. The enemies were programmed to always move towards the main character, but my programming basically involved a lot of casework and was reaaaally time consuming to have them walk around obstacles and such. Now I’m trying to implement the A* algorithm, which is apprently the most efficient 2d pathfinding algorithm.

Things to do
While it seems like one project, there’s actually quite a bit to do. Given a map and two tiles on it, I’d like to generate an image corresponding to the shortest path between the points points. Using the C programming knowledge I learned from class last quarter, my general high IQ when it comes to figuring shit out, and a lot of Google, this should be a lengthy but straightforward task.

First things first
I need to be able to generate an image of a map first. I’ve learned how to print pixels to a text file in the form of a .ppm image, so that’s what I’ll be doing. This will involve
– reading a text file of integers corresponding to a map
– converting the integers into an array to describe the map
– turn each tile on the map into a rectangle of pixels, and print this into a .ppm file
For maximum compatability with later steps (and future projects!), everything will be flexible, meaning:
– support for different length of tiles in each row
– support to add new kinds of tiles (easy since we just use a different integer)
– ability to change size of tiles

Looking onward
After I finish this first step, I’ll be ready to implement the A* algorithm. This will read a text file of a map, then return a text file of which tiles to highlight. I’ll then use a map to image function similar to what I’m creating, but with added functionality to apply highlights to tiles, and generate the final image.

To Work!

Part 2: Reading and Displaying Boards of Tiles
Part 3: Writing the A* Algorithm
Part 4: Source Code