My project was to make a super simple flight simulator in OpenGL with about 10 hours worth of work. The end result looks pretty nice.

Finished product running in high detail

Now, the midpoint displacement algorithm is fairly easy to get working right, especially in 2D.  Here is the page I got all of my information from.   I started with simply getting a 2D version rendered on the screen, and eventually built my way up to 3D.

Generating the 3D terrain is a bit trickier than first glance.  First off, I wanted to use triangles instead of quads, there you already have some issues with how you are going to store everything.  The easiest approach is typically to use quads, so I used an interesting approach to get it all working.

What you see above are two different coordinate frames.  The one on the left, “square space,” is more easily understood and makes terrain generation very nice.  The one on the right, “triangle space,” is harder to work with for some things, but looks much better when rendered.  To get from one to the other you simply apply a shear transformation.

I was able to generate tiles of terrain in square space by starting with four vertices.  Using the midpoint displacement algorithm I simply increased the depth until I had very fine terrain.  The result was then transformed to triangle space, not that only x & y were affected, not the vertical z direction, and used these vertices to display my terrain in OpenGL.

Basically the same image as above, but rendered in wireframe

So now I can create an render a tile of any size and render it on the screen.  To get nice looking terrain I had to be able to stitch tiles together.  I ended up creating a 10 x 10 grid of tiles, which I then generated in a manner to ensure that their edges were seamless.  I also made sure that the far edges wrap around as well.  Thus, when flying around in my virtual world there is basically and endless set of scrolling terrain.

Why did I bother with tiles?  Because that way I can choose which tiles to render and which not to.  I take my viewpoint, convert it from triangle space to square space, use that to figure out where in the grid I am, then only render the tiles I can actually see.

Some additional things I had to do to get it looking nice was adding color and lighting.  The first was simply done by lerping between colors  based on vertex altitude.  Getting the vertex normals was a tougher job.

The surface normal for a triangle is well-defined, but for a vertex between six triangles you have to do some magic to get a good vector.  I ended up taking the cross product of all six triangles (getting that to work at the edge between two tiles was tricky), then averaging them to get the normal.  The end result I unitized to get my vector.  This was all computed at the very beginning in terrain generation.

The last fun thing I did was add camera flight control and distance rendering.  Camera flight control has the user control heading and camera pitch via the arrow keys, and has the user fly over the terrain.  Pretty neat, nothing too hard there.

Distance rendering was a way to cut down on triangles farther away from the user.  This was somewhat tricky.

Here I have distance based rendering enabled.  The closer terrain is rendered to a higher depth, whereas the farther terrain is rendered with a lower depth.  To make it look nice I have a smooth transition between to two.  Thus, I can render to non-integer depths, i.e., depth 1.5, by rendering depth 1 with the depth 2 vertexes displaced only halfway from the midpoint.

I did not have the time to get the tile edges to stitch together perfectly, but am happy nonetheless.  The user can toggle between uniform depth rendering and distance based rendering.

As always, code is available.  See here.

-Tim

After pouring over the internet and considering various options, the test group was chosen. It consisted of:

1. Byonics MicroTrak AIO: a strong, dependent, long lasting ham radio telemetry system
2. Spot Satellite Messenger: a small, proprietary tracker used commonly by hikers
3. Motorola i290: super small, super lightweight cell phone custom programmed to sample its gps and transmit data to sensor.network

In addition, a Sun SPOT equipped with an SHT15 temp/humidity sensor and a 3-axis magnetometer was sent up.

Launch:

We took off just a bit north of the Mexican border beside a farmer’s field in 95 degree weather.  Things went fairly smoothly, especially considering that we were launching two balloons that day. (We also launched a larger balloon with climate sensors)  The Byonics and SunSPOT were placed together in one styrofoam box, the spot messenger and i290 went into a smaller box equipped with strobe lights beneath that.  All three trackers had emergency lines directly attached to their casing in case their styrofoam boxes broke, and I built a simple harness for each box and attached it to the main line.  A radar reflect, parachute with hoop, and 1000g Kaymont balloon finished it all up.

We let it go at about 9:20, and sought refuge at Best Buy for air conditioning and internet.  We also bought lithium batteries.  According to google aprs, the balloon was actually bending south and headed towards Mexico, all the time keeping a perfectly consistent altitude of 14324 ft.  We were worried, as the Ham beacon was supposed to be more reliable, and the spot messenger didn’t provide much data and the i290 had left cell phone range right after take-off.  However, the gps stream corrected itself and the balloon was actually headed north, and all was well.

After a brief escapade to a farm field to pick up the other balloon we waited for this one to drop below 60,000.  It had traveled considerably farther than the other balloon, and actually ended up landing in the desert in a bombing range.  We got the balloon in the 114 degrees in a 1.5 mile hike and returned, too tired to bother turning everything off right then and there.

End Results:

Byonics:

• Reliable
• Easy to use
• Durable
• Strange initial drift

Spot Messenger:

• Useful for finding the balloon
• lacks altitude
• 10 minute update time

Motorola i290:

• No data from altitude (code may be improvable to fix this)
• Probably works better if it lands somewhere with 3G service (like not in a bombing range)
• Small and cheap

The data we got from the sunspot was somewhat disappointing, since we had turned it on and taped up the boxes, only to take 45 minutes to fill the balloon, wait and fill the second one, discover that we needed more helium and refilled.  Consequentially, the spot ran out of space before it even reached burst altitude.

Overall I felt it was still a good launch, and look forward to more work on the perfect high school balloon launch package.

Balloon 1:

Send a balloon with various climate change experiments which high school students might want to conduct in the future.  We are flying a ppm sensor, a CO2, O2, a Geiger counter, and a SunSPOT with a 3-axis accelerometer and SHT15 Temp / Humidity sensor.

Balloon 2:

Send a small, cheap balloon with various tracking systems to test for low-cost solutions and their effectiveness.  As noted above, we are using a Byonics MicroTrak, a Motorola i290 programmed to send data to hibal.org and sensor.network, and a SPOT satellite tracker.  Also onboard is a SunSPOT with its 3-axis accelerometer, SHT15, and a 3-axis magnetometer.

We launch tomorrow (7/17) very early.

Basically, I wrote my own clock genetic algorithm in java, which overnight managed to get to the 1-handed clock stage.  I never bothered to see if it would get farther than that, because my final project deadline was looming.  Instead I wrote a program which only evolved the clock gear ratios, letting gears connect to each other’s rims or shafts.  This was executed in a nice tree structure, each node having a linked list of rim connections and a linked list of shaft connections to gears farther down the line.  It actually works very well, and finds a perfect solution after 15 minutes.

The parameters can be adjusted, such as the number of available gears, teeth, hands, ect.

It is nice to be reminded how amazing these algorithms are.

Here is my project video, enjoy!

A fun little program I decided to write up in my free time.  Basically, the idea stems from whether or not gravity travels at the speed of light.  Image that the sun vanished.  Would Earth be flung out into the depth of space instantly, or would it take about 8 and a half minutes? (Time it takes the sun’s light to reach Earth)  I am of the opinion that it takes 8 and a half minutes, because information can’t travel faster than light speed.  Imagine that gravity could be felt instantly.  Then, someone on another planet could swing around a heavy object, and theoretically and very precise gravity measuring device light years away could pick up on it, effectively carrying a message faster than light speed.  Everything else in science goes against this.

Anyway, my program has little asteroids flying around which are attracted to where the other asteroids were rather than where they are.  At every tick, where asteroids are are registered, and it creates a sort of ripple in space-time, propagating outwards.  Any asteroid on the ripple will see the asteroid as being where that ripple was first triggered.  Hence, a time lag.  Adjusting the speed of light adjusts the lag, and accelerating towards an asteroid will decrease the lag, etc.

As always, code is here.

Warhammer 40k is a tabletop game in which players collect plastic miniatures which are fielded as their army. Lots of six-sided dice are used in firing, dealing damage, etc. The greatest thing about it is that it is turn based, the events of the game split between moving, shooting, and melee combat. This means I don’t need to worry about the real-time graphics problem, resulting in a game which isn’t beyond the scope of my abilities.

Another reason why I chose Warhammer is because I have marveled at the idea of how cool it would be to see this game officially released on the PC. The game’s problem of arguing over rules and the judgement of distance or line of sight would be eliminated, for the computer would calculate all of that for you. Things would move much faster, you wouldn’t have to spend hundreds of dollars (thousands?) on models, and some sort of campaign mode would let you slowly accumulate a dominating force. After seeing Spore, I thought of how cool it would be to customize your own models, purchase armies, and create striking color schemes. Seeing your models come to life in the 3D virtual world of modern day video games would be breathtaking. Basically, it would be awesome, and getting an extremely basic, 2D version of it up and running is a task worth working on.

Seeing as I am not using any third party software to help me out, (no premade GUIs, OpenGL, etc, except whatever NetBeans provides) I figured it was time to learn how to use the JPanel form in NetBeans. The online tutorial on this is pretty good, and covers the basics for writing an extremely simple temperature converter.

For my game, I figured that a larger layout similar to that of Starcraft would be best, with a large panel depicting the battlefield, a small battlefield map in the bottom left, a central area for depicting the stats of selected units, and an area on the right for buttons such. My crude version still in development looks like this:

This was created, as mentioned, but using the NetBeans JPanel form (right click on your project, new → JPanel form). Netbeans will open up a nice graphical user interface which will help you automatically generate your own user interface for your game. You can design the layout in the GUI section, then modify the code by switching tabs. Swing elements such as buttons, JFrames, borders, and labels can be dragged and dropped in, and the code to create it is automatically written to the file.

I simply added four JFrames and a label for my four panel areas, and set the variable values. A first I was stumped on how to write the code for what is displayed in these frames, but found that creating JFrame classes for each and then editing the code in the auto-generated code to implement these classes worked best.

The end result? A simple GUI I can develop into a decent version of Warhammer 40k!

Two weeks ago I wrote about Minimax, a simple algorithm which looks into future possible board positions to pick the move which minimizes an opponent’s good moves, and maximizes one’s own. I claimed that my algorithm had produced a proficient checkers player, but I was unable to really test it until I had completed the user interface. Now I have, and you can check it out here.

Unfortunately, I found that the minimax, as I have created it, performs rather poorly, most likely due to the simplistic nature of the board evaluation function (It judges how good a position is), and how my implementation leads to the same evaluation for many different board states.

Consider the following two board positions. I admit that I am not a great checkers player, but in my opinion the one on the left is fairly equal, whereas the one on the right has black within an inch of getting a King with several of white’s pieces about to be destroyed. However, in my current approach the two board positions are evaluated as equal, since the pieces are all that count.

Chinook, the famous checkers program which cannot lose, uses several factors to evaluate board position. Among them are, according to Computational Intelligence in Games, an interesting book I recently checked out, “(1) piece count, (2) kings count, (3) trapped kings, (4) turn, (5) runaway checkers (unimpeded path to king); and other minor factors.” Multiple other approaches might work, such as assigning pieces at the board’s edges a higher value than those in the center, or looking to reduce the number of possible moves for the opponent.

I tried the following, (based off this article), weighing a piece’s position using the grid:

This improved my checkers AI, but there is still a lot of improvement to be had. For some reason, once the AI gets a king it likes to jump it back and forth infinitely, getting nothing done when it could be advancing another piece. I have no idea why it does this, and am trying to figure it out. If anyone has any observations, feel free to post them.

However, my next undertaking will not be to follow the shoes of Chinook, with its human-crafted board evaluation function. Instead I will take the path of Anaconda, the program described in Computational Intelligence in Games, which uses a genetic algorithm and neural nets to evolve an expert level checkers ai out of essentially nothing.

I was struck by the idea of a computer “knowing” how to win a game, and set to write my own checkers AI. “Knowing” of course is a bad use of the word. A computer does not know things. Instead, it creates a logical formula, and sets about crunching out its solution.

Before we begin looking at the algorithm itself, consider a game of checkers as an abstract collection of board positions, each board position representing a score. In positions where black has the advantage, the score is high for black and low for red, when red has the advantage, the opposite. How are these scores determined? In a perfect world, every possible board position could be analyzed and placed into a giant tree and connected together, each possible move acting as a string to another board position. Those positions leading to a win for black, without a chance for red winning, are good for black. The opposite is true for red.

However, in real life we can’t do this, due to a limitation on processing power and space. According to wikipedia, American Checkers has 10^20 positions, far too many for my computer to store or analyze. Instead, programmers use some formula to determine a board’s value. This is called a heuristic. In my algorithm I chose to find the difference in number of pieces, Kings counting as two. If black has more pieces, I assume black is winning. At least that is the idea. More complicated heuristics consider the position of pieces on the board, pieces in corners or on the sides (invulnerable positions) contributing more to a board’s score, or do any other complicated analyses. I stuck to something short and simple.

So now, given any board position, we can come up with a value.

The minimax algorithm lets us use these values to come up with the best move given a certain number of possible moves, by looking into the future.

Consider this: At the start of the game, the first player has 7 possible moves (each involving shifting a piece in their first row up by one.) We can look at the value of each of the resulting board positions and pick the best one.

This, however, is pretty lame, since each move has the same board value (at least in my setup), and doesn’t get you very far. Instead, we continue on into the future of possible moves and find that for each move, player 2 has 7 possible responses. That makes 49 possible board configurations 2 moves into the future. Now, since player 2 is responding, we will assume that they are intelligent and pick the response that is best for them. Therefore, if we were stopping here, instead of picking the board position that maximizes the score, we pick the board position which minimizes the score (hence the mini-max name).

Now that we know what they are going to do, we can pick the move that leaves them with the worst set of moves for them.

What the minimax algorithm does is look a certain number of turns (aka, depth) into the future, and using successive minimizing and maximizing, find the one move that screws the other player over the most, and simultaneously helps themselves the most.

While this approach is simple, it has its setbacks. First, any human can tell you that most of the analyzed moves are wasted cpu time, because the majority of those configurations are dumb board positions that no one would ever play through. Additionally, if for every move the other player has about 7 responses, that means the number of possible ending positions is 7^d, where d is the depth of the search. Looking only, say, 6 moves into the future results in 117,609 board positions! (My computer runs out of Java heap space if I check more than 8 moves in the future, about 5,750,000 board positions.) A human can get rid of all but the most likely ones in seconds, whereas a computer blindly checks them all.

It is important to remember that computers are simply mathematical constructs, but if you steer one in the right direction, they manage to cast a glimmer of brilliance.

This document is the output for a game with each side looking 8 moves into the future.  It ends in a draw, where each side would oscillate forever with its kings.  r = player1, b = player2, capital letters signify kings. Eventually I will get around to making a nice graphical interface where you can play against it.  As always, the code is online.  You can find it here.

Remember how each neural takes in charge, figures out if it is higher than a certain threshold, and then sends out charge to other neurons? Well, it turns out that this can be easily represented as an equation.

In the simplest case you have one neuron with a singe neuron before it, and a single neuron after it. The neuron has a singe value, say T, which represents its threshold. If the charge coming into the neuron, say C, is larger than T, {if(C > Y)}, then it will fire. C, in this case, is simply the charge from the one neuron before this one.

Okay, so we have the math logic, {if(C > Y) fire!}. This neuron now gives off charge to the next one down the line. We call this amount of charge the weight of the connection, W. A higher weight is how much of the neuron’s charge goes to the next neuron. If a pulse has 1 charge, then the next neuron gets W * 1 = W charge.

The great thing about this simple mathematical model is that it is easy to expand. Consider the following setup, 2 neurons → 1 neuron → 2 neurons.

Here, C for the middle neuron is {C = Winput1 + Winput2}, and if C is > Y, it will fire an amount Woutput1 and Woutput2. Simple. Easy. Efficient.

Now consider 2 → 3 → 2. The middle layer (the 3 neurons) C values can be set up as follows:

F1*W1,1 + F2*W2,1 = C1

F1*W1,2 + F2*W2,2 = C2

F1*W1,3 + F2*W2,3 = C3

F is 0 or 1, depending on whether the previous neuron fired or not. W n,m is the weight of the previous neuron n to the next neuron m.

For those sharper mathematical fellows, this is a very simple set of linear equations. This simply means the equation forms a straight line, and because of its straightforward linear properties, can be easily converted into a set of matrix equations. The previous example reduces to the following matrix equation:

[W11    W21]    [F1]    [C1]

[W12    W22] * [F2] = [C2]

[W13    W23]    [F3]    [C3]

The first matrix is called the Weight Matrix, the second I call the Pulse Matrix, and the last is the Charge Matrix. The Weight Matrix contains the information of how strong the charge connections between neuron layers are, the Pulse Matrix is whether or not the neurons in that layer are firing, and the Charge Matrix is the sum of the charges on the next layer. All you need to do with the Charge Matrix is see if it is bigger than the threshold for the neurons it represents to get the next Fire Matrix.

Using this math you can reduce a very complicated neural network into a streamlined set of matrix equations. Instead of evolving a set of neuron objects, you can adjust the contents of each layer’s weight matrix and threshold matrix, and presto, you get an evolved creation. The following is a demonstration video for a juiced up version of my last program, now using matrix math.  (Note: the creatures now are more like tanks, with a left tread and a right tread.  They adjust their motion by adjusting the speed of each tread.  Hence the tight turns.)

The code for my upgraded matrix math neural net can be found here.