Getting Hyperdash Right

published 07 Jan 2013

Over the last week, I have been working on fixing long-standing issues with the “Hyperdash” algorithm in Catch the Beat mode. Hyperdash is a gameplay tweak that was added to CtB in order to ensure that all patterns are catchable – no matter how far apart they are. It does this by makring certain fruit (objects) which would previously be impossible to catch as “Hyper” fruit. On catching these fruit, your catcher speeds up to the precise speed required to reach the next fruit in time.

hyperdash

This has always worked in roughly 99% of cases. Today I will detail the two main issues which caused the flaws in the remaining cases. For brevity, I have left out some other more obvious cases which were fixed earlier on last month.

Same Direction Chain

The catcher needs to catch three (or more) fruit in a line, where all but the last are hyperfruit. In the initial algorithm, the current X position of the catcher was always considered to be centered on the destination fruit by the time required, but because hyperdash would disengage earlier than this, catching all fruit were not possible.

same direction 1

The first fruit is caught as expected.

same direction 2

The second fruit is caught, but the catcher is dashing in overtime to get there. The green silhouette is where the algorithm expected the catcher to be.

same direction 3

Because the algorithm expected the catcher to be further than it actually was, the third fruit is not catchable. Hyperdash was required earlier on in this pattern.

Fixing this issues involves keeping track of:

  • The current direction of the catcher
  • The excess time after reaching the destination.

If the catcher has been moving in the same direction over more than two fruit, the excess required movement (if any) is added to the required distance, allowing hyperfruit spawning where required.

Hyperdash disengage times were also made more precise to ensure reaching the perfect position to catch the fruit.

Sub-frame Movement

The most edge case meant that some fruit may be possible or impossible to catch only by luck and frame limiter settings. Internal calculations where done on a sub-frame level, meaning:

possible_movement_distance = (object2.startTime - object1.endTime) * velocity;
require_movement_distance = abs(object2.x - object1.x);

if (possible_movement_distance < required_movement_distance)
	hyperdash(object1);

The problem here is that the possible_movement_distance was calculated based on the number of milliseconds separating the two objects. As osu! internally runs at 60fps in the worst-case scenario, possible_movement_distance may have been less or more than the actually available movement, due to where calculation frames end up falling (which is completely uncontrollable and random).

Correcting this is a matter of rounding available time downwards to the nearest frame + 0.5, which ensures that in worse-case scenario the time calculation will be 0.5 frames more lenient than required (ie. the objects will still be catchable):

frame_time = 1000/60; //60fps (16.66667ms)
actual_frames_available = floor((object2.startTime - object1.endTime) / frame_time) + 0.5;
possible_movement_distance =  actual_frames_avilable * frame_time * velocity;

sub-frame 1

When the game’s frame limiter was set to 60fps, frames were guaranteed to be a full 16.6ms, rounding calculations upwards and allowing slightly more movement. They would therefore match the old algorithm and be catchable without hyperdash.

sub-frame 2

When the game’s frame limiter was set to 120fps or unlimited, frames could be any length, causing higher precision in calculations, and introducing the possibility of sub-frame errors as seen above. While the fruit should technically still be catchable, rounding errors meant that they were not catchable around 50% of the time.

comments

This Week in osu!

published 06 Jan 2013

I spent the last week stumbling around trying to keep up with both real life as well as osu! commitments. I don’t have much to show this week so instead I will go a bit more in detail than usual on what I did get up to.

  • I got really annoyed at cross-compatibility of symlinks which are committed to git, so took a day to get rid of every symlink (more effort than you’d think!). The real issue only shows itself when you are using a git repository shared across multiple PCs using Dropbox.

    Most symlinks were in place for large data stores which may be mounted across disks or PCs (using NFS). Removing them meant replacing with nginx location/aliases where possible, or absolute paths in other cases.

    For example: ./repo/www/mp3//data/large/mp3/

    In this example, we see ./repo/www/mp3 inside a git repo pointing to an absolute path which may be a local folder or mounted hard disk. In the case of storing these in git, there is no initial issue – symlinks are a file with a special link attribute set and contain the path to their destination.

    After checking out the repository on a unix based system, symlinks will correctly point to their absolute destination, so if you have a folder available at /data/large/mp3/ it will work instantly after deployment via git. This works great for automatic server-side deployment without having per-system configuration containing locations of certain sets of files.

    I store all my git projects inside Dropbox, which means I can use multiple PCs simultaneously without a tiresome commit->push->pull to get both PCs in sync. When symlinks are synchronised across to windows PCs via git, windows is unable to keep the link attribute intact (it contains no such attribute), and the links become non-linked text/binary files. This causes a conflict between the two dropbox connected PCs and results in really weird scenarios which generally break git until you pause one PC’s Dropbox syncing and reset any file changes.

    Long story short, I would highly recommend avoiding symlinks inside git unless completely required :).

  • Database was getting big, so I took a day to prune unnecessary data and do a clean-up of indices. I aim to do this about once a month (basically as soon as things start to fill up) to both keep the overall filesize within acceptable limits and keep the database running in an optimal state.

    This generally involves:

    • Review any new tables added. Decide if data needs to be stored permanently – if not, start culling old data on a daily or weekly basis.
    • Use some smart index queries to find any unused (or very infrequently used) indices on new or old tables. These can usually be removed and result in a positive impact to insert performance due to less disk writes.
    • For data paths which are read and write heavy, it may be possible to move indices to slave database servers, leaving the master free to write only the base data, but still have performance benefits when querying slaves.
    • Check for any tables which have abundant free space. This generally happens when large amounts of data are temporarily written to tables (sometimes due to a bug, something due to a short and sudden increase in traffic). Cleaning these up is as simple as running an OPTIMIZE TABLES n; command, and defragments remaining data in the process.

    End result was a 10% reduction in database size!

  • Ephemeral started widescreen support for the editor, and I finished it. Feels pretty nice to use! Also if you run osu! fullscreen, the editor will always default to borderless fullscreen now, meaning an almost imperceptibly smooth flow to the editor.

  • A lot of time spent trying to get Catch the Beat “Hyperdash” to work correctly for all patterns. Previously there have been issues in cases where objects next to each other should be hyperdahsed, but aren’t due to sub-frame calculation errors. Still haven’t finished work on this, and it is holding up the next public build, so is my highest priority at the moment. You can read about the specifics of fixing hyperdash in my separate blog entry.

comments

This Week in osu!

published 30 Dec 2012

I hope everyone has an enjoyable Christmas break. I took a day or two off, but spent the rest of the week focussing on some scalability issues creeping up on osu! – the main one being the initialisation process when first connecting to bancho.

  • Using the concept of caching user information locally, I reduced the amount of data from server→client by 90%. osu! can now play in solo mode without ever receiving more than userIds of all online players. When users need to be displayed or interacted with (chat / multiplayer / online users display) this information is requested on-demand. I am still experimenting with the best balance between local cache size and expiry times, but you should already be able to see the improvements when first starting osu! and connecting to bancho. THis should help out those with slow internet connections quite a lot.

  • I reworked much of bancho’s internal to treat all clients (osu! / irc) evenly. Previously there were a lot of special cases to handle multiple logins from the same account, including osu suffixes on all osu! client’s username, and the inability to have an IRC client share a username with an osu! client in many cases.

    These changes not only allowed dropping that ugly username suffix, but also means that a single user can have multiple IRC clients all running under a single unified username. In the process, I also removed the ability to change IRC usernames, so it should be a lot easier to identify people too (even though you could only add a suffix previously). The code for handling user connection is also a lot cleaner, and will allow for special cases like tournament spectating without having one osu! account per running client.

  • I fixed most of the remaining widescreen compatibility issues, and also went through a lot of hard crash bug reports and fixed them. osu! should be a whole lot more stable after this week’s updates. In addition, I changed the way crashes are handled so a lot of errors (>80%) that would previous hard-crash osu! are now handled (and reported to me) without the game dying completely.

  • I made some fixes to input handling which allow prioritising certain groups of game elements on a situational basis. The main reason for doing this was to allow universal volume adjustment – now available either using up/down arrows or mouse wheel, and in dialogs where it wasn’t previously by holding ctrl+shift while using the controls – but also allows for a lot finer control of input handling, especially in cases where there are many scrollable areas, buttons and overlapping layers on screen at once. Quite large internal changes, but quite invisible to the end-user.

  • I have started work on fixing long-standing Catch the Beat hyperdash issues, where fruit would occasionally be impossible to catch due to sub-frame calculation errors. It is going to take a bit more time to get things finely tuned without affecting the difficulty of existing maps, but should be ready for the next public build, if not the one after.

Let me take a moment to note that I have recently been streaming dev sessions on twitch.tv. Make sure to follow me if you’re interested in coming and watching, asking questions or whatever. It’s a lot of fun, and I play some epic music playlists to boot :).

comments

This Week in osu!

published 22 Dec 2012

Spent this last week finishing up work on widescreen background support during play mode, and took the opportunity to improve the transition between song select and play mode, along with the loading process.

  • All loading is now done asynchronously on a separate thread. This means there is no visual pause when loading beatmaps. While this doesn’t mean much for most people with fast hardware, it was a prerequisite to the changes I wanted to make to the transition into play mode.

    For the time being, I added a fixed one second delay to the loading process to make the UX how I envisaged it working (especially important for fast PCs). I have further plans on what will happen during this loading process to make it more than just loading, but that will come in a future update.

  • Fun Spoiler has been renamed to Visual Settings, and buffed a bit. It is now possible to dim background images to black after playing maps at least once. The new dialog is also featured in a much more prominent place, hopefully meaning more people will see and make use of it.

    visual settings

  • Widescreen support for play mode, with aspect fill now used for all backgrounds and videos. Automatically detects when storyboards are present and falls back to 4:3 display, to ensure alignment is not broken as a result. There are still a few cases where artifacts can be seen here, suck as storyboards which used to have hidden elements due to letter-boxing now being visible. This will be fixed and improved going forward, along with the option to make widescreen storyboards.

    As a side note, you can now start using widescreen backgrounds and video and they should be recognised appropriately.

  • I made some fixes to opengl display – especially to the initialisation process. This means that opengl should load faster than ever and no longer flicker on load. I also looked into getting context sharing over multiple threads, to bring opengl up to the same level of threaded performance is direct x. One more step forward towards dropping direct x support completely – part of my master plan of ridding osu! of XNA and supporting more platforms more natively than ever before.

  • Added the ability to set custom refresh rates (for fullscreen mode) and custom fps targets for frame limiter mode. Should be useful for people playing osu! on 120hz monitors, or those who are after a frame-rate limit somewhere between unlimited and 120fps.

  • Best of osu! 2012 voting is now open! Make sure to check it out and vote for the beatmaps you enjoyed the most over the last year.

I have quite a bit of stuff to organise over the coming weeks, so updates may be a bit slower than usual. I do have plans for a small osu!stream update, including a new map pack, so keep an eye out if that kind of thing interests you :).

comments

This Week in osu!

published 17 Dec 2012

Running a bit late with the post this week, due to an all-weekend LAN event which involved updating and taking along my two osu!arcade units! Currently playing catch-up with both sleep and work.

  • I again spent some time optimising the tourney spectator client during the weekend’s OWC matches. Mostly just some minor tweaks to ensure smoothness and reduce buffering.

  • Made some UI changes to the updater – mainly that the “use test build” checkbox has been removed. Some people seem to have been accidentally clicking this without understanding what it means, and locking themselves into the test build. Also looking at changing the update process a bit. Not too happy with how the updater is such a context switch out of the game.

  • Switched CDN/static content over to https with SPDY support. As most major browsers support SPDY, there is no need to distribute content over multiple domains to achieve parallel throughput, so I also moved all javascript resources locally. Based on my own performance tests, the difference was not discernible, but I have had positive feedback from countries such as China, where this kind of thing matters.

  • Improvements to lobby layout, making better use of available screen space. The filters toggle is no longer available, with filters always being shown instead. I have plans for further changes here, but still brewing in my head. The users list is no longer displayed, saving on a bit of network traffic as well.

    lobby changes

  • I rewrote the in-game chat link parsing algorithm. This was a pretty big endeavour, replacing some at-times-hacky character counting for link styles like [http://test.com test words [may contain brackets]] with single regex match-and-replaces:

    \[([a-z]+://[^ ]+) ([^\[\]]*(((?<open>\[)[^\[\]]*)+((?<close-open>\])[^\[\]]*)+)*(?(open)(?!)))\]

    Explaining this would be require a separate post, I think. Let’s just say that chat links now support line breaks, cases where multiple links are on the same line, and gracefully display erroneous links. They also look a bit nicer!

    new link format

  • Messaages in chat by silenced users is now removed from in-game chat history. This ensures that bad behaviour – especially linking inappropriate content – has minimal effect on other users. Took this idea from twitch/justin.tv’s book.

  • Hosted osu!arcade units at RFLAN yet again. This included adding experimental support for conversion of osu! maps to osu!stream, which is working pretty well! I spent about half the LAN watching people play and modifying the game to provide a better experience based on this feedback.

    Make sure to check out this highlight of an osu! map being played with a straw, or dive in and watch some of the recorded stream of the 24 hour event!

  • I also released an osu!stream update on the App Store with iPhone 5 support.

I’ve got some interesting stuff planned for osu! updates in the near future, so stay tuned :).

comments