27 Aug 2014, 09:34

Small Project in the Rust Language

The Simulation

The idea of this game/simulation is this: You have multiple worlds. Worlds that are within a certain distance of each other are connected. Every world either produces or consumes four resources at a fixed rate randomly selected at startup. So some words will get lucky and produce all four resources at a fast rate of maybe 5 per stick, while some may consume one resource at say a rate of 2 or may neither produce or consume another for a rate of 0. Each world in addition to resources also has some money. Worlds will set a buying price for each resource based on its supply every one and a while. If supply is low, the price goes up. If supply is high, the price goes down. Thus worlds will be willing to pay more to get a resource if they don’t have much of it.

Traders also have some money and will randomly travel between worlds and will maintain a moving average of what the average price is for each resource that they have encountered along their journey. So naturally each trader will have a slightly different moving average depending on which worlds it visited in the past (After all what makes me differ from you if not our differing past experiences?). At each world, traders will buy a particular resource if it is lower than what it considers to be the “average price” that it inferred from its travels, while it will sell if the price it encounters is particularly higher. This allows traders to sometimes make “mistakes” and to sometimes make sweet deals since no trader will ever have perfect information. They will have information decay for the worlds they visited a while ago, and will have no information for worlds they haven’t visited. This adds variation and contribution to the feeling that the system is “alive”.

The natural question is what happens if you leave the simulation going? I haven’t run the simulation long enough to know for certain, but I believe that the trend is that, eventually the world that produces the fastest will end up with all the money. Worlds who constantly consume their resources will naturally have to keep raising their buy prices and will eventually go bankrupt. Two words may enter into a symbiotic relationship if they each produce and consume a different resource. It would be interesting is it really does converge to a case where one world gets everything or if it reaches some kind of equilibrium with a few worlds relying on each other.

Ideas to spice up simulation.

In an effort to combat these boring states where one word ends up with all the money, there could be a percentage “tax” that each world must pay. Richer worlds would have to pay more and then the money would be distributed evenly among the worlds. Given the right percentage, this should keep the system in an interesting “living” state. It also mimics a real life government. While I’m not sure how this simulation could be turned into game play, it can at-least provide a autonomous and living setting or backdrop for a story. Feeling like you are inside a living and breathing world is an important part of immersive gameplay.

There are many other ideas too. Traders could also consume resources. Resources could be perishable once off-world adding time-pressure to the Traders. Traders could exchange information with one another.

Thoughts on rust

I was interested in the up and coming system programming language so I tried to make something less than trivial in it namely this simulation. First thing that surprised me was how easy it was to get started compared to c++. I just had to use the package manager, Cargo, to set up a dependency to the rust bindings for sfml 2.0 and I was already running a simple example. It automatically downloaded the library from git, compiled and linked it everything.

There are many things I love about rust. Combining interfaces and templates/generics makes so much sense. Lifetimes are great! That said programming in it can be very frustrating because the compiler is very strict on what is allowed. Consider this code that goes through the arcs of a node to all its neighbors, and sets the correct distance to each of them.

let ref w=self.worlds[worldid as uint];
let p1=w.pos;
for cons in w.connections.iter(){           
    let p2=self.worlds[cons.dest as uint].pos;
    let dis=(p2-p1).len_sqr().sqrt();
    cons.dis=dis; //can't do this

I commented the problematic line. Of course the problem is that cons is not mutable, but it is no easy to make it mutable because the problem is that i must access a mutable world, and then through that word access another mutable world. As long as the other world is not the same world as the current one, that shouldn’t be a problem. But with iterators, either you get a mutable iterator over the whole vector or a immutable iterator over the whole vector. After asking for help on the rust subreddit, I found the best you can do without resulting to unsafe code is below.

let w_id = worldid as uint;
let p1 = self.worlds[w_id].pos;
for i in range(0, self.worlds[w_id].connections.len()) {
    let p2 = self.worlds[self.worlds[w_id].connections[i].dest].pos;
    let dis = (p2 - p1).len_sqr().sqrt();
    self.worlds[w_id].connections[i].dis = dis;

But this is not as elegant and not to mention slower than it needs to be. You shouldn’t have to re-index, and you should be able to use iterators.

Another thing I missed was non-type template parameters. In C++ you can pus integer values as parameters to a template type, but not in rust. So the array type ( [int..5]) is essentially “magic”. So if you want to make a generic extension of an array type with variable length you’re out of luck.

I will likely not touch rust again at least until the official release, but I will write c++ differently now. For example I will avoid constructors and and instead use static methods that return the created object a la rust. You really have to wrestle with the compiler. It’s incredibly strict. But once it compiles, there’s a high chance everything will just work without a snag. As a project grows bigger and bigger this will be the better alternative than a compiler that is less strict that lets through more mysterious bugs. This allows you to be more bold and program less defensively and rely on the compiler to catch the details. The compiler hurts, but to quote Rihanna, I like the way it hurts.

27 Aug 2014, 09:34

Android Muti-touch Test

This is a little App I made to learn the Android SDK. This one is written in pure Java. It was after this project that I decided to learn how to get c++ code running on android. This is definitely not the way to make real-time games.

In order to combat frequent garbage collection, I found myself writing ugly code to reuse small temporary objects like 2d vector objects which are allocated on the heap even though their lifespan is local to a small function. I was under the impression that Java did escape analysis to put such objects on the stack but it seems there is no guarantee that it will do this only a possibility.

The android canvas API, while offering a wide range of shapes to draw, is not suitable for real-time rendering. In this App I have less that 20 bots and my moto G can only handle comfortably 30fps. Contrast this to my stress test written in C++ which handles 3000 bots at 60fps. Granted I use quad-trees for collision detection in my C++ version, but with only 20 bots the n squared complexity is still small.

27 Aug 2014, 09:34

HTML Canvas steering example

It’s amazing how hard it can be to get from point A to point B if you must adhere to certain and perfectly reasonable steering constraints. Here is the problem I was trying to solve. Get to point A to point B by only accelerating at a constant rate in the direction you are facing or by accelerating at a constant rate rotationally to the left or right. These are the only ways you can steering to get to point B, and all the while you are subject to the laws of Newtonian physics. So your mass matters and your rotational inertia matters.

This is something I wrote in Javascript using the canvas element a while ago to try to tackle this problem. I was taking calculus 3 at the time which turned out to be very useful. It’s all vectors. Dot products, cross products, etc. As you can see from the short video, the solution is not very perfect but it’s believable enough to me, at least. I suppose javascript is an OK language to write quick prototypes like these where performance is not an issue as it allows for easy sharing.

Try it in your browser!

Try another version with different debug lines in your browser!

27 Aug 2014, 09:34

Spring System

Modified my previous simple android engine to make a spring engine. Behaves similar to the system in the game World Of Goo. I was just thinking about how slow collision detection was when it occurred to me that the system World Of Goo uses is incredibly efficient. You don’t have to find the colliding pairs every step, because once a node is connected it will always interact with it’s neighbors. You only have to find collising pairs when you add a node. And you only add a node at a time. So the complexity is just n+e where n and e or the number of vertices and edges respectively. This is better than it sounds considering world of goo -like structure graphs are planar meaning e is smallish. (e is bounded from by 3n-6 for planar). The complexity of this system is really just n. Very fast and yet very interesting physics.

As a side note this system has a weird bug where the energy is the system keeps growing and growing when a structure spins until it breaks apart. I don’t know what is causing this. Maybe it is the result of using Eularian physics steps instead of something more stable like verlet.

Google Play Store Link - it’s free!

27 Aug 2014, 09:34

Efficient Collision Detection

This is a stress test of my simple collision detection and handling system that I made from scratch in c++ running on android. It uses a quad tree for collision detection. My implementation has a simple method for_every_colliding_pair() that takes a visitor function, which it calls for, you guessed it, every colliding pair. by using this function, I only have to traverse through the entire quad tree once, instead of querying the quad tree for every bot (bad idea). This app has 2300 bots and runs at 60 fps on my Moto G.

I should confess that it is not runing at true 60 fps. Sure the bots update their positions 60 times a second, but I handle collision between bots 30 times per second and then cache the results. The profiler said this operation was the bottleneck.

Update: I’ve since updated the app to run 3000 bots smoothly on my moto G.

Google Play Store Link - it’s free!

27 Aug 2014, 09:34

Efficient Triangle Android Game/Simulation

This is a “game” I made that uses my collision system as well as my steering system.

Google Play Store Link - it’s free!

27 Aug 2014, 09:34

HTML Canvas Quad-Tree

This is something I wrote in coffeescript a while ago. It uses the canvas element to draw rectangles which split into four smaller rectangles when touched. Colors are generated at random on every split. Perhaps more interesting would be for the colors of the parents to be the determined by mixing the colors of the children together. So first you could randomly generate all the smallest possible nodes, then build the colors for the rest of the tree from the bottom up. It is efficient at rendering for two reasons:

  • I only update the canvas when a quad is being split.
  • I only update the section of the canvas that includes that particular quad being subdivided instead of re-rendering the entire canvas.

Try it in your browser!

27 Aug 2014, 09:34

Formation System

First Lets Define a Formation

Lets say every formation has certain characteristics. They are roughly rectangular in shape. Meaning every row much be filled to the same length except for the back rank which may have less bots. The back rank must be centered.

Formation Dimension Change Handling

How can you best rearrange the bots from an old dimension to a new dimension?

These animations show my various attempts of coming up with the right algorithm. The first two are very efficient algorithms (n^2 complexity) but have back rank issues. The last one is the solution.

I did not solve the problem. What I did do is finally realize that this problem reduces down to a previously solved problem called the assignment problem for which an polynomial time (n^3 complexity) solution was found in 1955 called the hungarian algorithm. At this point, I considered implementing the algorithm myself. Then I looked at the algorithm and said, I’ll just find library. But it solved the problem!

The problem reduced down the assignment problem in this way. When we want to rearrange the formation we want to minimize the total distance traveled by all bots on their way to their new assignments. In fact, you get better results if you instead minimize the total distance squared traveled. Computing this is also easier since you don’t have to find distances which is an expensive operation because of having to use sqrt().

Bot Removal

Say you have a formation of bots. What happens when one of the bots dies? The formations must rearrange itself. This can be done by moving the bot from behind up to replace the missing bot. You continue this until you get to the back rank. Then you find the bot closest in the bank rank to the now missing spot in the second to last rank and assign that soldier to it.

At this point I had to different ideas about how removal should effect the formation. Y

I had the idea of adding two extra properties to a formation.

  • A formation should maintain roughly the same aspect ratio
  • The bank rank of a formation should be at least half full. (for aesthetic reasons)

So how do we remove a bot under these new constraints? First compute the aspect ratio before removal. Then solve the below simul for the new width and height based on this aspect ratio and the new number of bots.

width/height=aspect ratio
width*height=number of bots     

You are almost guaranteed to always get non-integers since for it to be a non-integer, the area must be composite and must be factorable such that the width and height perfectly meet your aspect ratio. So if they are not integers, simply round them. No there’s a couple of cases.

  • newarea>=numbots

    • newarea - oldarea<=newwidth/2
      • don’t do anything. bank rank will naturally fill up to at least half
    • newarea - oldarea>newwidth/2
      • shrink width by one, and add those spots to the back rank.
  • newarea<numbots

    • grow width by one, and fill up with bots again to reduce the problem to one of the above.

In this way you can get the dimensions that best fit into the new constraints. Once we figure out the new dimensions, we remove the bot we are removing, then we simply rearrange the bots using the previously described algorithm to fit into this new dimension.

  • The other alternative is that the formation should not try to preserve aspect ratio. The result is that formation will get thinner and thinner but will try to remain the same width for as long as possible. You will also have bank rank cases with only a few bots which can look bad.

Bot Attacking

Each formation maintins a radius determined by it’s shortest side. I then use a stadium shape to define a border around each formation. If two formations’s boundaries intersect, bots are matched together. For every unmatched enemy bot in a formations boundary, select three of the bots closest to this enemy bot, assign these three to attack this bot. The enemy formation does the same thing. So as you can imagine a battle will escalate as one matching pulls more bots into the others radius which pulls more bots, etc.

27 Aug 2014, 09:34

HTML Canvas Graph Simulation

Here is also a second video show casing the A star algorithm.

This is something I made a while ago that showcases the steering algorithm I had previously made. There are 200 bots that each employ the steering algorithm to reach the next randomly selected neighbor node. They will prefer not to go back to the node they came from if given the choice. They also all collide with each other. This is a very expensive operation having n squared complexity. This can be reduced to n log n time using quad trees. So not only is this an expensive algorithm, but we are running this algorithm using Javascript. So naturally performance is very bad. My laptop could handle less than 200 bots at 30fps. Compare this to my c++ android quad-tree implementation that could manage 2300 bots at 60fps on my phone! In this project I also implemented the A star algorithm in Javascript.

Instructions for link below:

  • create nodes by clicking. click on a node and drag to another node to connect them.
  • press r to make the bots start to random traverse your constructed graph
  • press q to have the your bot apply the a star algorithm to go to the node that is nearest to your cursor

Try it in your browser!

27 Aug 2014, 09:34

HTML Canvas Gomoku

This is something I wrote in Javascript/Jquery while ago. This was basically an improved version of my previous Gomoku AI implementation that I wrote with game maker a long time ago.

The ai is very smart. I have never successfully beat it. It works by building two weight maps of the grid: one for offense, and one for defense. The best move can be found by summing these two weight maps and selecting the cell with the highest value. In my older version, I also simulated believable weak ai by choosing a threshold such that cells with values above this threshold are chosen at random uniformly. The lower the threshold, the weaker the ai.

This version allows you to have up to four players that play in a round-robin fashion any of which can be either a human or an ai. It is interesting to see the ai fight it out against themselves. Somethings this leads to a draw, sometimes not. This shows that the ai is not perfect because it was proven that provided perfect play, in a game of gomoku, the player who plays first can force a win.

Try it in your browser!

27 Aug 2014, 09:34

Thoughts on Competitive Gameplay

Make a game too predictable and it is boring. Make a game too unpredictable and it is also boring. Whether it is by nature or nurture we humans have a particular interest in the things in-between. Music that is too predictable is boring, but also music that doesn’t follow any kind of structure is also boring. Games just like Music has to have the right amount of expected, and unexpected to be interesting.

But unpredictability is not something that should exist in, my opinion, in a competitive game. If something can not be predicted, no amount of skill can give you an edge over your opponent. You are at the mercy of some small amount of randomness. If a game has unpredictable components, however small, you will allow players to sometimes “get lucky” and win because of it, and “luck” is something that should be minimized as much as possible in a competitive game.

But how can you make a game fun and competitive at the same time? Well a system does not have to be truly random for it to appear random. Take for example the weather. The weather to the average person appears to be random. It could rain tomorrow, it could not. Who knows? But if you understood enough about weather patterns you would be able to predict whether it would rain tomorrow or not. In this way the system is as random as you let it to be. You can disguise order as chaos. Competitive gamers should feel like explorers. Explorers trying to find the order in the chaos. Who ever can see further into the patterns of the complexity of a game will be able to better predict the future and thus win. Pattern recognition is how “skill” should be defined.

Will players still on occasion get lucky? Yes. They may happen to stumble on the correct solution, but I see no way to eliminate this. Best you can do is to make a game with a high branching factor thus reducing the chances of stumbling on the right solution. So even completely orderly games with apparent chaos are random enough. There is no need to inject pure randomness into a competitive game. For people who are skeptical about a orderly game that can also be fun, I direct you to “life”. Every object in this universe just follows a select few laws like gravity, and from these simple laws seemingly chaotic things crop up. You could argue that life isn’t truly orderly citing quantum mechanics, but can you really argue that that is the source of all the chaos in the world especially when there are many examples of perfectly deterministic physics simulations that still produce seeming chaotic systems. Look at a simple double rod pendulum for example.

27 Aug 2014, 09:34

Game Maker Experiences

Gamemaker is a software suite that does what it says on the box in a beginner friendly way. This was my first experience with programming as a freshman in High-school. This was back when it was still version 5 when it was a small. It was an incredibly good way to learn how to code, with a very vibrant and helpful on-line community. I was lucky enough to meet some very helpful mentors along the way. I eventually began to see the limits of game maker, and have since moved on.



27 Aug 2014, 09:34

HTML Canvas Tank Game

I wrote this a while ago using the canvas element. The user can control the tank as well as the turret. Nothing fancy going on with respect to computer science, but it was interesting to implement. Javascript lets you embed images into the html file itself to reduce file dependencies. So the base tank, the turret, and their respective shadow images are all stored in the html file. The javascript source could also be embedded in the html file so literally the whole game could be in one file.

Try it in your browser!

27 Aug 2014, 09:33


I am a finishing Rutgers computer science/mathematics undergrad student who likes programming. Please hire me!

Resume: [html] [pdf] [docx] [plain text]