Blog Redesign

One more quick blog post.

You may have noticed if you have been here before, that I redesigned my blog last week. I fancied getting my teeth into some classic CSS and design stuff. I hope you like the results.

Oh, and yes, ALL the artwork, design and coding was done by me. Including the vector DS which I actually drew in Microsoft Visio (don't ask!).



As for me, I need to get out of the library and get to bed. Although I am enjoying this 24/7 library thing! :)

Laters.

Particles!

Three blogs in one day might be excessive, but its just passed midnight so I guess I'm ok.

So then ladies and gentlemen. One thing I have not blogged about as of yet is the project I'm working on with some guys from university for our "Team Project" module.

Quck brief. Team of 8. Half programmers, half designers. 8ish months. 1 game prototype.

We, "Team C" have been building our game for a while now and it's finally coming together quite well. The game is called Quintessence, which roughly translates from latin as "five elements" of the "fifth element".

Quintessence is a Marble Blast / Super Monkey Ball style game where the player must control the ball, rolling it from the start of a level to the finish, as quickly as possible. The challenge is added in the form of elements. The ball is transformed into different elements by rolling onto "Altars" which change the current element in order for the player to overcome obstacles such as hedges, water, and brick walls.

There are 5 elemental balls in total, each with their own characteristics in terms of weight, speed, acceleration, grip and visual style. They are Neutral, Fire, Water, Earth and Air.

Fire burns hedge, Water(ice) freezes water, and Earth smashes wall. Air is just floaty-light!


So that's the game, and I've been working on a particle engine this weeks which I adapted from a 2D particle engine tutorial into a fully 3D version. :)

The particle system is to be used for fire effects, ice and snow particles, chunks of rock, water splooshes and much more.

The visual style is cartoony and we are in the process of redrawing almost all of the texture to make it even more so, hence the blobby cartoony style of the fire. At last, here is a video of the effect.

Since making that video earlier in the week I have created a fireworks effect for when the player finishes the level, and snow and ice particles that fly off the Water(ice) ball when it rolls.

More Web Programming

I figured that because web programming is soooooo easy compared to the sort of coding we do everyday, I might as well get it learnt and add it to my big pot o' skills.

So this week I decided to have a look at JavaScript and more in depth with PHP. A simple image viewer / gallery seemed a wise thing to make as a test, so I grabbed a bunch of album cover images I had lying in a folder and got to work.

After a while it all started to make sense and I whacked together a simple php page shows a list of images which can be scrolled through using buttons or by clicking the image you want to skip directly to.

Click here to view the page.



Its all quite nice and works well enough. The whole system is completely flexible, allowing it to be used with any number of images and with any amount of images on screen at once (changeable using a little form and php post values).

I also figured it'd be wise to have the code viewable, but just using the browser's "View Source" option doesn't display all the php. So I wrote another php page that parses and a displays the index.php code in the same folder. Another php file is included in the index.php page which adds a small link box to the code parser in the bottom right hand corner of the screen. All neat and reusable for future php stuff.

Click here to view the code parser page.

On the point of future php stuff, I'm going to look into making an editable contact info MySQL database page for names and addresses accessible to certain users to act as an easily maintained global address book for families (specifically mine). This way, everyone can easily access and update family member's addresses, phone numbers, email addresses and much more.

Sketch Processing Update

Today I have 3 exciting new developments for you, along with the usual enthralling updates!

We'll start with the bit most of you will just want to see. The video.

Fun Colours

After developing the application to its current state with little more than the odd pure red, green or blue line to keep my brain awake, I decided it was time for some bright colors!

Technically the real reason behind all this, was to have a simple way of identifying different properties by colour coding the line segments based on specific properties such as how curved they are.

Last year I spent a few weeks writing low level colour manipulation algorithms for mobile phones, so I knew that a HSV to RGB converter would provide me with the ability to transform the parameter to an angle (Hue), and pump out nice rainbow colours.

This diagram is a good representation of HSV colour space:
(H: Hue, S: Saturation, V: Value )



I found a simple HSV -> RGB conversion function online, which was using floating point numbers. Again, after my work on mobiles last year I have accustomed to avoiding floats where possible, so I rewrote the function with bit shifted fixed point numbers to save some processing speed.

The result was lovely, but in the end I decided just to use the colours for the input stroke, with the colours cycling based on the input point ID.

Slider Bars

Developing on a really low-level platform like the DS means you are constantly having to write your own little classes to do the most basic of tasks.

Think of a button for example. You would think it'd be pretty straight forward, right? No.

Anyway, as annoying as a solid button system was to implement, a slider bar was all the more frustrating (actually, that's a lie, I quite enjoyed building it!). The toggle buttons simply link to a Boolean value which is altered as they are pressed, reflecting the current state of the button (toggled = true, and untoggled = false).

I started with my screen object class which had a "Touched" and "Released" inherited functions which were passing in a bool of whether the stylus was inside them or not. This was fine for the buttons, but when you want a slider which needs to know where abouts within the itself the stylus is, more information is required. This meant rewriting the function from the top, with the stylus co-ords being passed in, and the root object calculating and passing down whether it was inside or not.

This worked well and the rest quickly fell into place, and I added a linked a linked variable with min and max values acting as the effected value.

I was using my first slider as a multiplier for the calculation of the Beziér control points (see the next chunk of text), but these were generated when the sketch was processed (only once at the end of the stroke input). To rebuild them I had to press the "A button" which ran a little function that reprocessed the stroke.

Unfortunately whenever the slider was adjusted I had to rebuild the stroke manually. This is when I decided to get my head around function pointers.

They turned out to be surprisingly straight-forward and I quickly added a function pointer to the slider that would run whichever function you specify whenever the slider value was altered. I was really impressed with the result, and it makes the application much more interesting to use. :)

Beziér Curves

The final stage of the Stroke Approximation technique is to identify the curved areas of the stroke and represent them with Beziér curves. To identify the curved areas, a ratio is calculated for each line segment of the final hybrid fit polyline. l2:l1.

l2 is the distance along the original stroke from one point on the polyline to the next, and l1 is the distance directly between the two points.

Curved areas will obviously have a higher ratio than the more accurately represented straighter segments. The identified curved segments can then be removed from the polyline and represented with Beziér curves.

Beziér curves are a represented by a start point, an end point and a number of control points. The more control points a curve has, the more complex it becomes. The number of control points denotes the "order" of the curve, representing its mathematical complexity. A cubic curve (as seen below) has two control points.



Generating the Beziér curves to represent the curved ares of the sketch is a matter of finding an empirical value that best fits the user's drawing style. This is the multiplier that the slider adjusts.

To render a bezier curve it is best to represent it as a polyline when you have limited rendering capabilities available. This means we need to work out several points along the curve and use them as the polyline representation of the Beziér representation of the polyline representation of the original stroke! This is starting to get crazy!

Basically you need to boil down the of the curve by calculating sub curves using the control points, until a curve with 1 control point remains. this will give you the coordinate required at a chosen percentage along the original curve.

I won't go into the maths too deep at this point as I doubt anyone will even read this far, but there are some really interesting overlaps with Fibonacci series here which I may look into more at a later point!

If you want to have a play with an insane Java Applet of a cubic Beziér curve, I recommend checking out this site.

This image was just too cool to leave out. :)

High Scores and XML

Its time for something a little more fun in my exciting blogging world!

Today, XML!

To cut a long story short, I used to play games pretty competitively, vying for the best times / scores on various websites. A problem with having multiple websites to track scores and multiple games to keep track of, I always wished I could have a way of storing my high scores in a simple way that could be easily updated or manipulated.

HTML was too static and Excel was too local, but now, XML provides a wonderfully flexible solution to the problem. Hooray!

I figured I would write a basic XSLT stylesheet for my new XML file so I can plop it onto my website and make it look pretty and readable.

So far I have added several games to my data file and it can be viewed in all its glory HERE.

Gold stars like this indicate world records

Current games:

• TimeSplitters 2
• F-Zero GX
• Marble BlastUltra
• Metroid Prime
• SSX 3
• Super Mario 64 DS
• Super Monkey Ball

I'm intending to write a php wrapper page for it which can be used to sort / manipulate the data via the web page, but for now I would love to hear your thoughts on it so far.

Thanks, and enjoy!

Sorting Algorithms

During the development of my Sketch Processing application I reached a stage where the processing of each stroke was starting to take amounts of time noticable to the naked eye. At this point As the application was at an early stage of its life, my concerns were that if I was getting slowdown already then I had much worse to come.

Generally the processing was taking around seemingly exponential lengths of time in comparison to the number of points in the input.

After a quick time profiling addition to the code I was able to break down the processing in order to find if there was one chunk of code eating up my processing time. It soon became apparent that sorting the curvature and speed data (float arrays equal in size to the number of input points) was accounting for around 98.5% of the processing for an input of 200 points (around 2 seconds to process!).

I was relieved to find it was just a sorting algorithm that was the nuisance as I knew plenty about them and knew there would be a quicker solution available.

After reading through my basic and frankly terrible original sorting process, I realised that I'd written a type of Insertion Sort algorithm(one of the slower types of sort).

Some quick googling revealed a nice selection of algorithms and explained how there were basically 2 groups of comparison sorts. Fast, and slow.

These handy graphs show the variations in speed between the two groups, O(n^2) and O(n log n).





You can see that the slow algorithm graph has a vertical scale measured in hudreds of secionds whereas the fast algorithm graph has a vertical scale measured in tenths of seconds. This is clearly a huge difference.

Some more research helped me identify the Comb Sort as a reasonable solution. It acts in a similar way to the Bubble Sort, a relatively slow algorithm, however instead of comparing adjacent values, an initial gap of the data length is used and reduced by 1/(~1.3) each recursion over the data. This "combs" through the data and eliminates the comparison of a large portion of the unneccessary comparison, making the algorithm nearly as fast as a Quick Sort, whilst retaining the simplicity of a Bubble Sort.

Once the Comb Sort was applied, I recorded increases in speed of around 100 times, bringing the total processing time back down to unnoticable speeds.

Sketch Application Progress

It has been about a week since I got the initial system of feature point identification in place in my application and since then I have been working on completing the process, refining the system and general improvements all round.

The system now has a fully functional Average Based Filtering process in place, as well as Hybrid Fit Generation and refining.

Average Based Filtering

Average Based Filtering involves taking the initial raw input data from a stroke and processing it to pick out key data points, representing intended features such as corners. By joining these feature points together we create a basic polyline representation of the sketched shape.

The incoming data consists of a list of points recorded each frame whilst the user has the stylus on the input device. The co-ordinates of each input point are stored in two integers; one for the x-position and one for the y-position. A time value is also recorded, as the amount of time passed in milliseconds since the start of the stroke.

From these three key pieces of information, curvature and speed data can be calculated for each point "n". Curvature values are created using the change in angle between points n-1 to n, and n to n+1, and the classic formula "speed = distance / time" is used to create a list of speed.

Means are calculated for each set of data with any curvature regions above the curvature mean and any speed regions below 90% of the speed mean, being stored as feature regions. The peak values of the intersection of the two region sets are then used as the initial feature points of the sketch.

The feature points are thus located at areas of great change in direction and low speed.

Hybrid Fit Generation and Refinement

Once an inital set of key feature points have been located, the result can be improved by adding extra points to provide a closer fit to the original input. The best output would involve the closest match to the original stroke, while containing as few points as possible. Getting the balance right is of key importance.

To start with an initial Hybrid Fit if created, consisting of the output from the average based filtering. From this we can then add the points that will provide the greatest improvement.

To pick the best candidate point we create 2 possible new fits, one with the best unused speed point and one with the best unused curvature point. These are decided by sorting the speed and curvature data (a problem unt its own!).

With two possible candidate fits, a metric is required to identify the better of the two. This comes in the form of an error value created from the sum of the orthogonal distance squared of the original points to the corresponding line segment of each candidate fit. The fit with the lowest error is then chosen as the new Hybrid Fit and the other is discarded. This cycle is then repeated until the error value drops below a specified value, and thus the final Hybrid Fit is found.

Discussion

The system's reliance upon empirical values such as the means in the average based fitering and the error threshold in the hybrid fit refinement, mean that optimum solutions are less likely from person to person as each user's input style varies. A better system would not rely on these values which require tweaking to achieve the best results for a specific person.

The next system that I will implement will use scale space to identify the key feature points of the input without the need for any empirical data.