Saturday, July 7, 2012

Crazy Chickens game with Motion detection

Past some time I was working on update of my application Crazy Chickens for N9.

In new version, Game character recognizes gesture based on user motion and move his bucket accordingly to catch egg. Game uses the phone back camera to capture image and recognizes gesture by tracking motion of some predefined colored object, which user is holding and moving to move the character. Hope you will enjoy the new update.

There also some minor update in UI and game logic to make game more enjoyable.

You can download app from following link,
- Fixed web browser: http://store.nokia.com/content/200523
- Nokia mobile browser: http://store.ovi.mobi/content/200523


Game need some setup before you play the game, You will need to connect phone to TV using TV out cable and place phone such that it back camera faces you. Game can recognized four color, Red, Blue, Yellow and Green. You need to choose one color and hold that colored object in hand. To move character to put bucket under hen, you need to move colored object in direction of hand. 


Please also make sure that you are fully visible and color object's movement does not go out of camera frame. Also make sure that there is enough light in room else game might has problem recognizing color clearly.

If you don't have TV out cable then you can install VNC server on Phone and connect it from PC to project phone's screen on PC.

Hope you will like the update. Please let me know if you have any feedback. I will try to update game with your feedback.

Sunday, July 1, 2012

Binary heap based priority queue in Qt

Long time ago, I posted implementation of Priority Queue implemented using Qt's
 QQueue data structure. Here is old post.

That code was offering o(n) performance for enqueue operation and o(1) performance for dequeue operation. This might be acceptable for small data set. But for large data set you might want to use Priority queue based on Binary heap implementation.

I tried to implement my old priority queue using Binary heap, here is my implementation.

Following code implements BinaryHeap using QList. BinaryHeap class implements enqueue, dequeue and count method.
template <class T>
class BinaryHeap {
public:

    void enqueue(T item) {
        mList.append(item);
        int i = mList.count() - 1;
        int parent = (i-1)/2;
        while( parent >= 0 && mList[i] < mList[parent] ) {
            T temp = mList[parent];
            mList[parent] = mList[i];
            mList[i] = temp;
            i = parent;
            parent = (i-1)/2;
        }
    }

    T dequeue() {
        if( mList.isEmpty()) {
            return T();
        }

        T item = mList[0];
        int i = 0;
        mList[0] = mList[ count()-1];
        mList.removeLast();
        while( i < count() ) {
            int left = 2*i+1;
            int right = left + 1;

            if( right > count() - 1) {
                break;
            }

            int min = left;
            if( mList[right] < mList[left] ) {
                min = right;
            }

            if( mList[i] > mList[min] ) {
                T data = mList[min];
                mList[min] = mList[i];
                mList[i] = data;
                i = min;
            } else {
                break;
            }
        }
        return item;
    }

    int count() const {
        return mList.count();
    }

private:
    QList<T> mList;
};

And based on above BinaryHeap class, following is my PriorityQueue class.
enum Priority {
    Low = 2,
    Normal = 1,
    High = 0
};

template <class T>
class PriorityQueue
{
public:
    void enqueue( Priority priority, T data) {
        Item item(priority,data);
        mHeap.enqueue(item);
    }

    T dequeue() {
        Item item =  mHeap.dequeue();
        return item.mData;
    }

    int count() const {
        return mHeap.count();
    }

private:

    BinaryHeap<Item> mHeap;
};
And Item class looks like below.
    class Item{
    public:
        Item() {
        }

        Item(Priority priority, T data ):
            mPriority(priority),mData(data)
        {}

        bool operator<(const Item& other) {
            return mPriority < other.mPriority;
        }

        Priority mPriority;
        T mData;
    };