Evolved Goatman

I recently collaborated with a friend to build a Web App in a Hackathon. We used GitHub as our version control for the server source files which is written in Ruby on Rails and Heroku for the actual production app.

For the Hackathon, I contributed mainly in html and css but due to time constraints, I was not able to set up a local test environment of Ruby on Rails on my machine. To make matters worse, I'm completely new to Ruby and Rails and Postgre, so we decided to test directly on Heroku for time frame of the hackathon.

Now that the hackathon is over, I've had some time to actually sit down and figure out how to install everything on OSX. In particular, how to set up postgre and use it with the GitHub Ruby on Rails files.

Start the Ruby on Rails server

After installing Ruby, Rails and Postgre, I wanted to run the server to test. Firstly, open a Terminal and navigate to the directory of the GitHub Repository:

cd [GitHub Repo]

start the server:

rails s

which is short (and equivalent) for:

rails server

Stop the server

I also quickly learned to stop the server is simple to stop the process. So use Ctrl+C in your terminal to stop it.

DB Error?

Upon accessing the localhost page (typically http://localhost:3000), I encountered this error: "Could not load database configuration. No such file - /Users/../config/database.yml"

I found that this file 'database.yml' was a settings file for the server to user to connect to the database. In my case, I was using Postgres, so I copied this template and edited the values accordingly and saved the file into the config directory:

development:   adapter: postgresql   encoding: utf8   database: db_name   username: user_name   password: db_password   host: localhost test:   adapter: postgresql   encoding: utf8   database: db_name   username: user_name   password: my_db_password   host: localhost

For mysql, check this.

The reason is the file may not be uploaded to GitHub by your collaborators is because it contains the user and password of their local database. So one alternative is to change the yml contents to use environment variables like so that you are able to upload the yml file:

password: <%= ENV['APPNAME_PROD_PWD'] %>

Once the file is in place in the config directory, double check your database that you have created the user and the database with the name specified in this database.yml file so that Ruby on Rails server can communicate with it.

Setup the database from Schema

Finally, the last step is to set up the database based on the schema from your repository. To do this, run this from terminal:

bundle exec rake db:setup bundle exec rake db:migrate

This command is explained further here and here. Essentially, it will use the schema from the GitHub repository to set up the database on your local machine, then potentially fill (seed) it with some values, and finally, if there are any migrations, it should run those. To quote from the rails guide, "You can think of each migration as being a new 'version' of the database. A schema starts off with nothing in it, and each migration modifies it to add or remove tables, columns, or entries."

Setting up Postgres

As for setting up Postgres database itself, I found this video tutorial very concise and useful.

Conclusion

I haven't been a big fan of component game object architecture. Checking out functional reactive programming. It sounds very powerful. I do prefer a more declarative approach.

Might be handy for HTML5 preloading?

I started working on trail effects! I've always been mesmerized by them in Japanese games, and perhaps because of using Unity3D recently for a jam, I came across this effect but I've never yet written the code for this effect, so I wanted to try and build one for my own games.

What is a Trail?

A trail is a series of polygons that follow your cursor or object around and leaves some marks or lines behind. Unlike particle trails however, the one I set out to make are made of geometry instead of just drawing a particle at the position.

Quads Vs Triangles?

Since I was focusing on Starling, I decided to keep the trail in quads rather than triangles, the reason being quads could be batched better in Starling.

It would be also easier to texture quads than to texture individual triangles

It is not obvious how to maintain a width for the trail if we were dealing with triangles.

Easy-Peasy-Repeat

A trail code loop sounds simple enough to do, here's the pseudocode:

//set the head of the trail update(quads[0]); for(int i=1; i < quads.length; i++) quads[i].copyFrom(quads[i-1]);

Done? I thought it'd be easy to do as well but the proper trail effect took me a few full days over the course of a week to actually finish. In this post, I'll be documenting my mistakes and progress for this effect.

First Mistake

What's wrong with the code above?

The problem is that the iteration is done from 1 to n, where 0 is the head. Head here is defined as the most recent trail position recorded, which is where the object should be at. 

So the iteration should start from the back instead, otherwise, the entries will not be copied in the correct order. We also want to set the head last because of this reason.

for(int i=quads.length-1; i >= 1; i--) quads[i].copyFrom(quads[i-1]); //set the head of the trail update(quads[0]);

How to update the Quad?

I did several iterations to get this right and learnt a fair bit along the way. I believe some of these methods could be used on purpose to achieve other kinds of trail effects. In fact you can come up with your own algorithm!

Extending Closest Edge At first, I was thinking that quads should be updated by extending the vertice of closest side of the quad towards the direction. Then each quad vertex is simply copied to the previous quad every update. This resulted in a really cool but unintended effect. There were holes and several disconnected parts due to twisting of the quads.

Rotating the Quad and stretching it So every time a new position is set for the trail, we rotate so the quad edge is a tangent to the direction of the new position and we stretch the quad from the previous position to the new position. This worked relatively well but ended up becoming very blocky and quads did not connect with each other.

Rotating and extending the Top Edge only After trying the rotating quad approach, it became obvious that I should not rotate the bottom vertices as well, so I only moved and rotated the top edge and this resulted in a very nice trail effect. However, one small problem was that the trail would still overlap when turn sharp corners. This was the result of the tangent crossing over the previous quad's space.

Rotating Top Edge but snap vertices if crossed previous space So finally, I managed to solve the problem with the sharp corners by first checking if the tangent crosses the space and that is done by calculating the: dotDir = dot product of direction and the previous direction; dotPos = dot product of the vertex relative to the previous position and the previous direction;

After which, we check if (dotDir * dotPos < 0) because if they have opposite signs, it means that they are on different sides of the quad and would mean the vertex crossed the space. If this condition is true, we snap it back to the previous quad vertex position to avoid the crossover.

Gradients

A trail of 5 quads colored according to a gradient from white to black.

Naturally, one of the important features is to add a gradient to the trail.

Updating Colors While coding the trails. I was originally thinking that I could get away with just setting the color upon initialization and not have to update it. Because I was stretching the quads every time a new position is added to the trail, this resulted in a non-uniform gradient that might not be intended. As such, updating the colors for every vertex is required. However, this introduces another problem.

Gouraud shading / Sampling issue One problem that this current system faces at the moment is the same problem that gouraud shading has and that is that if there are not enough quads in the trail, the color could be diluted because we will miss the position of the color we are looking for. However, since trails are very fast effects, and the color is being updated, we can get away with it for now (until an artist comes and complains to me!).

Optimization As an optimizaiton, the top vertices of a previous quad will have the same color as the bottom vertices of the current quad. So color only has to be computed 2n times in a chain of n quads, rather 4n times for each quad vertex.

Texturing

After coloring a trail, the next most obvious feature is to be able to texture it. With texturing, we can achieve many effects. Here are some:

One side gradient texture

Middle gradient texture

Trail Width

Trails also have a certain width that is associated with them and this would affect the tangent calculation mentioned in the update step.

One further feature I implemented was to allow the trails to taper off.

I originally wanted the tapering feature to be able to set exactly how many pixels to taper to, or essentially a start and end trail width, and linearly shrink the width across the quads. However, I did not do this because it would require me to store the tangents and recalculate  the width of each quad every update.

I decided that this was too expensive a calculation for such a simple feature, so I went with a multiplier instead. So instead of calculate an exact length, I just multiplied the tangent width by the taper multiple (e.g. 0.9) each update to keep things simple for now.

It is entirely possible to recalculate and update each quad but perhaps I will do that as a separate implementation so as to keep the simple trail features cheap and fast.

Future Additions

One possible addition could be to change the vertices into splines instead. That would allow more vertices to be generated and allow the curvature of the geometry to be smoother.

One of my friends was having a problem with transparency and tinting of 2D sprites in Unity3d, so I decided to help him out. The problem was that there did not seem to be a 2D unlit shader which had tint support built-in, or at least it was mostly confusing as to which shader he should have picked. We googled around a lot and did not find much help, noting that many people had chosen to write their own tint shaders too. So I also decided to write the shader for him.

Shader "Custom/Unlit/UnlitTint" { Properties { _MultColor ("Color Tint Mult", Color) = (1,1,1,1) _AddColor("Color Tint Add", Color) = (0,0,0,0) _MainTex ("Base (RGB) Alpha (A)", 2D) = "white" } Category { Lighting Off ZWrite Off Cull back Blend SrcAlpha OneMinusSrcAlpha Tags {Queue=Transparent} SubShader { Pass { SetTexture [_MainTex] { ConstantColor [_MultColor] Combine Texture * constant } SetTexture [_MainTex] { ConstantColor [_AddColor] Combine previous + constant } } } } }

It was simple enough. The part that got me a little stuck was the lack of documentation on the combine instruction. It was not very clear whether there could be multiple constantColors declared in the SetTexture block or not. I wish there was though. At this point in time, I'm not sure if calling SetTexture twice (as seen above) has an additional cost rather than writing our own custom shader code and doing the multiplication and addition together. Tinting

Just a brief explanation on how tinting works.

Assume we have a pixel color. And here, color is defined as a set of [r,g,b,a] values each of which range from 0 to 1.

We could have gotten this color from geometry or a texture, it doesn't matter, just assume we have an input color from somewhere and we want to tint it, meaning we want to modify that color value. Here's the obvious way to do that. OutputColor = InputColor * TintColor

However, one of the problems with this is that you can only bring down the color value since you are only multiplying it from 0-1. That means if you start with a white input color, you can tint it to any color, if you start with a yellow input color, you can tint to any value between blue and green but not red. You cannot tint black color to anything. 0 * 1 = 0. Therefore, an offset is needed.

OutputColor = InputColor * TintColor + OffsetColor

Now, we can add color to the input! In other words, we can colorize (I think that's the photoshop term) black to any other color. 

Started the practice with red black trees, but I figured I've forgotten how to code Binary Search Trees as well, so I might as well get my basics right.

The node structure and tree find and insertion were easy enough to do. Binary trees are easy to define. Every node has two children, nodes in the left sub-tree are smaller than itself, and nodes in the right sub-tree are greater than itself.

Node Structure

struct BinarySearchNode { int value; BinarySearchNode* left; BinarySearchNode* right; BinarySearchNode* parent; BinarySearchNode(int value_, BinarySearchNode* parent_ = nullptr) : value(value_) , left(nullptr) , right(nullptr) , parent(parent_) { } ~BinarySearchNode() { left = nullptr; right = nullptr; parent = nullptr; } };

Insertion and Find

class BinarySearchTree { private: BinarySearchNode* findRecurse(BinarySearchNode* node, int value) { if(node->value == value) return node; else if(node->left && node->value > value) return findRecurse(node->left, value); else if(node->right && node->value < value) return findRecurse(node->right, value); else return nullptr; } void insertRecurse(BinarySearchNode* node, int value) { if(value < node->value) if(node->left == nullptr) node->left = new BinarySearchNode(value, node); else insertRecurse(node->left, value); else //if(value > node->value){ if(node->right == nullptr) node->right = new BinarySearchNode(value, node); else insertRecurse(node->right, value); } public: BinarySearchNode* root; BinarySearchTree() : root(nullptr) { } BinarySearchNode* find(int value) { return findRecurse(root, value); } void insert(int value) { if(root == nullptr) root = new BinarySearchNode(value, nullptr); else insertRecurse(root, value); } };

However, the deletion got me a little stumped. Reading wikipedia, I learnt of the ingenious technique of swapping the in-order successor or predecessor node with a node that has two children. This is because the in-order successor or predecessor has only one child or zero children, by definition of the Binary Tree. Thus, it is easy to remove a leaf node or node with one child instead of messing around with the node ordering in the Binary Search Tree. Its no wonder I have forgotten about it.

void remove(BinarySearchNode* node) { // deleting node with two children if(node->left != nullptr && node->right != nullptr) { // have to choose either in-order successor node or in-order predecessor node to take position // in-order successor node is the left-most child in the right sub-tree // in-order predecessor node is the right-most child in the left sub-tree // in either case, node will have either 0 or 1 child. // for now we implement choosing in-order sucessor always // but this may lead to an unbalanced tree BinarySearchNode* newSuccessor = getInOrderSuccessor(node); // replace value of successor with self node->value = newSuccessor->value; // remove successor node remove(newSuccessor); } // deleting node with one child else if(node->left != nullptr || node->right != nullptr) { if(node->left != nullptr) { // deleting root node with one child if(node->parent == nullptr) root = node->left; else node->parent->left = node->left; // update parent of child node->left->parent = node->parent; delete node; } else { // deleting root node with one child if(node->parent == nullptr) root = node->right; else node->parent->right = node->right; // update parent of child node->right->parent = node->parent; delete node; } } // deleting a leaf else { if(node->parent->left == node) node->parent->left = nullptr; else node->parent->right = nullptr; delete node; } } BinarySearchNode* getInOrderSuccessor(BinarySearchNode* node) { if(!node || !node->right) return nullptr; BinarySearchNode* inOrderSuccessor = node->right; while(inOrderSuccessor->left) { inOrderSuccessor = inOrderSuccessor->left; } return inOrderSuccessor; } BinarySearchNode* getInOrderPredecessor(BinarySearchNode* node) { if(!node || !node->left) return nullptr; BinarySearchNode* inOrderPredecessor = node->left; while(inOrderPredecessor->right) { inOrderPredecessor = inOrderPredecessor->right; } return inOrderPredecessor; }

After I completed my binary search tree, I was thinking about how to iterate over it and was also curious about iteration of trees in general, especially without recursion or use of the stack. I researched some links (1), (2) and learnt that most iteration still requires some sort of stack.

Stack Iterator

class BinarySearchStackIterator { public: BinarySearchNode* lastSeenNode; BinarySearchTree* tree; vector<BinarySearchNode*> parentStack; BinarySearchStackIterator(BinarySearchTree* tree_) : tree(tree_) , lastSeenNode(nullptr) , parentStack() { parentStack.clear(); pushLeftChildren(tree->root); } BinarySearchNode* getNext() { // once the stack is empty, we are done if(parentStack.empty()) return nullptr; lastSeenNode = parentStack.at(parentStack.size()-1); parentStack.pop_back(); if(lastSeenNode->right) { pushLeftChildren(lastSeenNode->right); } return lastSeenNode; } private: void pushLeftChildren(BinarySearchNode* node) { while(node) { parentStack.push_back(node); node = node->left; } } };

Alternatively if you have a parent pointer in your node structure and if the iterator stores the lastSeenNode, it is also possible to iterate through the tree. I had a lot of trouble wrapping my head around this iteration. Essentially, we have to split it into a few cases:

Traversing to the left-most child of the root or a right child, i.e. the in-order sucessor of a node.

Traversing to the parent if we're coming from the left child upwards.

Traversing multiple parents if we're coming fom the right child, up to the point where the child is no longer a right child.

No stack iteration

It's my first attempt writing a trie tree. I read the wikipedia page and tried to understand it, the image on stuck to my mind and I tried to code it from my understanding of it.

After much time spent, I figured I didn't know enough and I searched online for more information. It turns out this image is more like a radix tree, which is a specific type of trie tree, where intermediate substrings can be grouped. I decided to back up a little and went back to basics to focus on just getting the trie tree right first before moving on to a radix tree implementation (in future).

As a small challenge, I tried to code the bitwise implementation instead of character implemention. The code below is what I came up with. It turns out to be easier than expected to code, since basic trie trees create a node for every element (be it a char or a bit) in a string. 

At first, I assumed encoding a bit string had to be done from the Most Significant Bit (MSB) to Least Significant Bit (LSB), meaning more significant bits would appear higher in the Trie Tree. However, after much thought, I coded the structure to go from LSB to MSB, and the resultant tree seems to be more elegantly formed than if it were to be MSB to LSB.

While researching trie trees, I also learnt a lot about:

Deterministic acyclic finite state automaton (DAFSA), where basically child nodes can combine thus saving space but not allowing auxillary information to be stored.

Radix trees, where the nodes in a trie trees and be condensed, saving space, but adding more complexity to the insertion and deletion algorithms.

_BitScanReverse and other compiler Intrinsic functions, it's the first time I encountered these, specifically, there are fast low level functions to do various operations like count the leading zeros in an unsigned long.

I implemented a simple hash table today in c++, with separate chaining with linked lists. My first pass was to use open addressing but I read up on Wikipedia and decided to switch to linked lists. But it looks like dynamic arrays are still the best?

Either way, I learnt a lot about the Hash Tables, Universal Hash function as well as The Power of Two Choices. 

Got some practice for insertion sort. Oddly enough, I think I remember an alternative version from the wikipedia one where it sorted from the back. Also I confused myself with Bubble Sort, since this had swapping of adjacent cells, I thought it couldn't be Insertion Sort. Then I realized that, actually if it were sorted, it would be O(n), whereas in Bubble Sort, it would still take O(n^2). I guess I must be careful to remember that difference.

Coded merge sort for practice. This time I succeeded in doing this completely from memory of the behaviour of the algorithm and I did not have to Google for it. Surprisingly simple and elegant. After I finished, I did end up looking at the wikipedia page and learned that it is useful for external sorting. I must have somehow forgotten all these from school days.

Leveling up and revising algorithms starting with Quick Sort. I tried to code this completely from memory but I failed to remember the partition step, in particular, I forgot about the storeIndex. I think the algorithm can also be further optimized slightly by avoiding the swap if the swap indices are the same. I also made some mistakes with the recursion in quicksort function.

It's a funny thing Aliasing. We used to hate it, but now we love it.

Here's an image of anti-aliased rendering of text in Unity, it's not as bad as it seems but it's not purrfect either...

I wanted to avoid smoothing out the text in Unity, but apparently there's no easy way to do it. I started out with Unity's built-in 3D Text, then I found out that I couldn't change any setting to make it render as aliased.

I thought maybe it could be the shader and I was looking into the Shader Lab settings and figuring the tags and all that. I then came across this 3DText template and copied it.

But then found these: http://forum.unity3d.com/threads/13037-Is-it-possible-to-turn-anti-aliasing-off-in-a-shader http://answers.unity3d.com/questions/172516/shader-for-pixel-art.html

Which led me to think that it could be the texture setting of the font. I then went back to Unity, dismayed to find that I cannot change the texture setting of the font texture (generated from the TTF). So I guess that meant I had to work with bitmap fonts.

I had prior experience with bitmap fonts and used BMFont to export fonts which were used in mobile games. However, I was not sure if Unity had support for them. Finally, I found this post Pixel Perfect Bitmap Font, which doesn't look well design code-wise. It's a great demo but it's not a library.

I'll be honest, I'm a bit lazy right now, so I think I'll decide to skip over this whole aliased text issue for now. Maybe I'll figure it out after the jam too.

Meteors Incoming!

Import Blender to Unity3d Next was to import it into Unity3D, I also only just found out that Unity supports blender files! http://docs.unity3d.com/Documentation/Manual/HOWTO-ImportObjectBlender.html

Export Blender file with Textures Next up is to find out how to export the blender file with the textures. I couldn't really figure this out and read something about uv unwrapping which I did not fully understand. Its clear that Unity does not import the materials directly, so I fumbled around a bit but managed to magically get it working after a while. I'll come back to this after the jam.

Meteor Particles I also worked on the particles systems for the meteor. I made them change color over their lifetime but I almost forgot how fire looked like for a moment and totally messed up the gradient! I set it like red->white->yellow->black for some strange reason. Luckily Google comes to the rescue once again. 

Next was to make the particles always move up in world space. I found the solution here: http://answers.unity3d.com/questions/281475/how-do-you-make-a-particle-effect-always-emit-upwa.html