Monthly Archives: July 2011

An OpenGL ES Adventure – Part 2

As I mentioned in my previous post on this topic, I’ve been working on a scene graph, render manger and material system for my GL engine. Some of the stuff has induced a bit of head-scratching, but on the whole things are coming together pretty well. I thought I’d share a bit about what I have in place now, and a few things I hope to complete soon.

My current scene graph implementation is probably not very optimal, but it works for what I need now. It’s essentially just a hierarchy of SceneNode objects and their subclasses. Each SceneNode can have an arbitrary number of children, which are stored in a custom dynamic array class.  A SceneNode is the highest level class; it’s not a renderable object, but is used for grouping objects. It’ll be able to act as “folder” in the scene graph. The SceneObject, which is a direct subclass of SceneNode, is the base class for all renderable objects. Sky, water, meshes etc will all be in the class tree of SceneObject.

The second SceneNode subclass I have written at the moment is a SceneCell, which is the physical equivalent of a SceneNode. It groups SceneObjects into renderable cells, which allows for quick culling. Cell_0 is always visible, as it contains basic environment objects like the sky, terrain, large bodies of water, etc. From that point on, a maximum of 4 cells will be visible at any time depending on what’s in view. The cell the camera is in will obviously always be rendered, and any adjacent cells that are visible.The contents of the cells will be further culled based on the view. The maximum occurs at the corner case. For example, if the camera is in the yellow cell then the green, red and blue cells will have potential renderable objects in them:

When the scene is traversed, if an object is deemed fit for drawing it is added to the appropriate group in the RenderManager. This set of classes will handle materials, batching and the actual GL calls to render the frame. This code is really in its infancy at the moment.

Anyways, that’s all for now. Hopefully I’ll have some more attractive in-engine screenshots for the next blog post on this topic. I still have to write a mesh loader, since I’m just using const arrays of vertices for all my objects at the moment. I’m considering using Blender’s .blend format for all my models, since it contains all the data I’ll need. I’ll have to look into that in a bit more detail though. I’ve also heard Collada is a good format.

T

Advertisements

Monopoly Math Theory

Like I said in the last post, I spent some time working on the actual probabilities for each square in Monopoly. First thing first: Chance/Chest cards suck.

About half of the Chance/Chest cards can be classified as “move cards”, as they instruct the player to move to a square. Lets say you draw the “Go to jail” card from Chance and move to jail. That card now goes to the bottom of the stack, so the probability of anyone getting that card is now 0 for the next 16 Chance draws(there are 17 Chance cards), and 1 on the 17th draw. Therefore the probability of the squares is affected by the initial order of the C/C cards, since its common for not all the cards to be drawn during shorter games.

The number of players also affects things; obviously more players will go through the C/C cards faster, but it also complicates the “get out of jail” cards. I never pay the $50 to leave jail, therefore I either need a “get of jail” card or a doubles roll. If two other players already have the freedom cards, that means when I leave the jail it’ll be on a doubles roll. This means that I can’t land on squares 3,5,7,9, or 11 on a jail exit move. Though the effects are probably negligible in the grand scheme of things, they’re definitely present.

The only other factor, aside from standard two-dice probabilities, is that rolling three doubles in a row immediately moves the player to jail.

With all these factors considered, solving things gets pretty complex. Example: You’re on Water Works, and roll double 4s. You’re now on Chance. This Chance turns out to be a “Go Back 3 Spaces” card, putting you on Community Chest. The Community Chest card is an “Advance to Go” card. Since you had double 4s, you get to roll again; doing so gives you get double 1s, putting you on Community Chest. Go To Jail! At the end of it, you’ve visited four different squares on a single turn. On the other hand the same outcome could have occurred if double 1s were rolled from Water Works, as this would have put the player on the “Go To Jail” square.

Such complex move sequences are very rare, but are certainly possible. Therefore instead of trying to come up with an equation, I decided to calculate the potential pathways to each square and the probability of said pathways. I also took some liberties with C/C cards and simply treated them as a random draw. I’ve attached the final Excel sheet as usual:monopoly_final_paths

And, a screenshot of the final ordering and game board composition:

There are definitely some differences between the theory and the experimental results, but the general trends are fairly similar. Railways and orange still appear as the most popular properties. There’s a lot more “smoothness” in the theory though, especially in the middle range properties. The one last thing to do with this data would be to factor in costs of buying and rent, to see which are the best price wise. I’m sick of this game and data though, so maybe another day. 🙂

T


Monopoly Math

So it was family game night tonight, and we decided to play Monopoly. Because the game can take a while, we generally set a time limit, something between 1.5 to 3 hours depending on how late we start the game. My strategy for playing is pretty straight forward: collect as many railways and utilities as possible, and go for orange, yellow, and dark blue property groups. It tends to work pretty well for me, so I decided to do some data recording this game. I tallied up every squared landed on in Excel, including Chance/Chest cards like “Go directly to jail”, “Advance to boardwalk”, “Go to go”, and so on. We don’t play with any custom rules that affect moving, so the data reflects standard Monopoly procedures.

Unfortunately the game only lasted around 1 hour 20 minutes (I had a lucky start & early win), so the dataset isn’t very big. I wasn’t about to ask for a rematch though and we probably won’t play Monopoly again for a week or two, so I decided to work with what I had. Here’s the full organized data and analysis; click for full-size of course:

Haha, go Orange and Railways! I knew I was backing the right horse. 🙂 I think the reasoning behind the high frequency of orange landings has to do with the fact that it’s outside of the jail. Some of the most probable rolls on two dice (6,8,9) will land you on orange. There are also Chance/Chest cards that take the player to the pink squares right before orange, and the railway right before orange. Railways/corners are obviously going to be popular because of the aforementioned cards, and because they’re well spread around the board. Same goes for Chance/Chest, which combined make up 6/40 or 15% of the game board. Also, I find it funny that Tax squares received the least hits.

There’s a lot more I could do with this as far as comparison to theory goes, but the problem is calculating theoretical probabilities for each square. Since there are a lot of different routes to get to squares, with the possibility of going to jail, getting a Chance/Chest card that moves the player, etc things get complicated. I do intend to sit down and work through the math later tonight/tomorrow, so I’ll post again with an update at that point. And, as always, if anyone wants the data to play with: Monopoly.xlsx. The first Sheet is the raw data, and the second is the analysis page shown above.

T


An OpenGL ES Adventure – Part 1


I decided to take a stab at writing an iPhone game engine in OpenGL ES, with the intent of gaining a better understanding of GL and graphics programming in general. I’ve already done a bit of work with DirectX and general 3D graphics programming via Torque Game Engine Advanced, but this is my first attempt at writing a rendering engine from scratch. I’ve been working on this for around two weeks now, including doing a bit of research into GL itself and reading some 3D math primers. I should also mention that my end goal is to support both GL ES 1.0 and 2.0, although at the moment I’m only working with ES 2.0.

As it is now, I’ve completed a basic math library and started working on scene management and materials. The Matrix class was largely based on the one included in the Oolong Engine for iOS, as my knowledge of matrices is limited. I’ve also started to abstract as many of the rendering calls as possible to make it easier to add ES 1.0 support down the road.

There aren’t a lot of visuals to show right now as I’m still at the “single spinning object” stage as far as my scene goes, but here we are:


Both objects are running a basic lighting shader with a single light in the scene. That’s really about all for now. I plan on posting up some of my engine structure documents later, once I move them into something digital (they’re notes on paper at the moment).

T


Coke + Rust = Results!

The results of this little experiment were actually not bad. Upon opening the container of Coke today I saw two small patches of gunk floating on the surface. These turned out to be directly above the screws, as expected. The bubble plumes mentioned in the previous post were also still present, though they were much smaller.

Once the coke was drained, I realized one mistake I’d made during the experiment. Both of the screws had been placed with the flat side of the head facing downwards, against the bottom of the container. I think this the reason for why the heads are still very rusty, as seen in the photos that follow. In both images the one on the right was the untreated screw.

The things coming out of the Coke weren’t brand new and shiny, but there was a bit of improvement. It’s also possible that leaving them in longer would clean off more rust.

T


Coke + Rust = ??

This is a bit of a deviation from what I normally blog about, but we have a ton of extra Coke cans at home and I nobody drinks it. I’ve heard a few times that Coke (well, the chemicals in Coke) are excellent at doing things like dissolving calcium, removing rust, etc. I figured I’d give the rust a try.

The hardest part by far was finding enough identical rusty objects. I wanted at least 2; one control and one to actually soak in the Coke. I ended up having to use these:

The container was just an empty yogurt container, which happened to be the perfect size:

I ended up tossing 2 of the rusty screws into the Coke, keeping the third out for comparisons. As soon as the screws hit the liquid sizable plumes of bubbles started forming around them, and continue even as they settled on the bottom of the container. I’m not sure if this was just CO2 escaping due to nucleation or some sort of reaction between the rust and the Coke. I also put the lid on the container, which had some interesting implications. Within the first minute or two the lid was bulging and pressure was seeping out from the rim of the lid. Again, I’m not sure if this is entirely regular Coke behavior or not. Either way, I added air holes in the lid.

I’m going to check back in a couple of hours to see what’s happened, and then again tomorrow morning and afternoon. I’ll post the results then.

T


Array Sort

Earlier in the week I was working on something completely unrelated to programming (sorting some school work actually) and I had an idea about sorting integers using array indices. I finally got around to implementing and benchmarking it in Java this morning.

The process is fairly simple, though it might be kinda hard to explain. To start with I’m going to describe a simplified version that uses a bit more array space than my optimized version.

Imagine you have an array of integers, something like    int myArray[] = {5,9,3,8,4,10,2,8,6,4};   for example. The first thing the code does is loop through the whole array once to determine the maximum value in the array. In this case that would be max:10. Using this value, we create a second empty array, as follows:    int sorted[] = new int[max+1];   

Here’s where the trick comes in. Rather than using the array itself to sort the data, we use the array’s indices. This means that we now loop through the original myArray and for each value we encounter, we do   sorted[value]++;   

Once we’re done looping through myArray, we’re left with: 

sorted[0]=0    sorted[1]=0    sorted[2]=1    sorted[3]=1    sorted[4]=2

sorted[5]=1    sorted[6]=1    sorted[7]=0    sorted[8]=2    sorted[9]=1    

sorted[10]=1

Since array indices are sorted, all we need to do now is loop through the array one more time and printed out the indices that have non-zero values. If the value is >1, we print out the number that many times. This gives us 2,3,4,4,5,6,8,8,9,10. And look, it’s sorted!

With a small-scale array like this, QuickSort is much faster. However with datasets at around 50,000 or more the “ArraySort” method starts to start looking very nice. I recorded and graphed some running times at intervals of 100,000, between 100,000 and 3,000,000. Each array contains n elements generated by a for loop, with each element being set to:  (int) (Math.random() * 1000000);

 Here’s the resulting graph:

I couldn’t believe the results. I changed the ArraySort program to print out the sorted array at the end of the run, just to make sure it was actually sorting, and it was. I guess the difference here is that 1) ArraySort only uses a constant 3 loops and 2)QuickSort is recursive, so with more things to sort more method calls have to be made.

 I plan on trying this again using C++ instead of Java later today to see how the performance compares.

T


%d bloggers like this: