Author Archives: Warty

An Algorithmic Approach to Beating Indecision

I’m incredibly indecisive over the most minor of things. We’re talking about spending an hour at a supermarket debating upon bags of chips. Over the last two years I’ve avoided such paralysis with the following algorithm:

The Algorithm That Follows:

Let’s say it’s 6:38PM and you have 4 options:

  1. red bag of chips
  2. blue bag of chips
  3. green bag of chips
  4. purple bag of chips

38 mod 4 = 2. (see mod defined below)
2 + 1 = 3.
Take option 3, the green bag of chips.

Analysis:

My strategy uses the current minute as a source of randomness. If you’ve used that recently, consider these variations: Adding the current hour to the current minute, iteratively eliminating rather than selecting the algorithm’s decision, or using your dominant shadow as a minute-hand with a forward-facing noon and a non-ambiguous up/down vector.

Nobody will notice you doing any this. Except, maybe, the hunting for your shadow thing. I made that one up.

Results:

I can now decide upon a bag of chips in 10 seconds. Yay me!

Side-note – Definition of Mod:

mod: Arithmetic operation that computes the remainder of a division.

a mod b = remainder of a/b division.
5 mod 3 = 2
6 mod 3 = 0
7 mod 3 = 1.

dargon-root, an aggregate repository

Time for a short update. I just pushed the-dargon-project/dargon-root which aggregates all of our repositories into one pullable entity. It’s sort of nice.

More importantly, it solves a pain point regarding NuGet, .net’s de-facto package manager. Until we get our hands on dnx (google it, it’s awesome), we’re stuck with HintPaths that break builds if you use a project in more than one solution. Exactly a year ago, I moved us over to a system where every major project shipped as a NuGet package and other projects depended on those packages. I think the benefits of project-to-project references heavily outweighs anything we’d gain from NuGet, so as a next step I’m going to work on overhauling the way we handle packages and CI (probably have a NuGet project in every solution, sort of like Fody).

Weaving with Fody – Creating A Lombok-Style RequiredArgsConstructor in .NET

Dargon’s codebase extensively leverages constructor-based dependency injection.

As a result, much of our codebase looks like this:

using ItzWarty.IO;
using System.IO;

namespace Dargon.Nest.Daemon.Hatchlings {
    public class NestDirectorySynchronizer {
      private readonly IFileSystemProxy fileSystemProxy;
      private readonly DaemonConfiguration daemonConfiguration;
      private readonly NestDirectoryImpl nestDirectory;
      private readonly NestContextFactory nestContextFactory;

      public NestDirectorySynchronizer(IFileSystemProxy fileSystemProxy, DaemonConfiguration daemonConfiguration, NestDirectoryImpl nestDirectory, NestContextFactory nestContextFactory) {
         this.fileSystemProxy = fileSystemProxy;
         this.daemonConfiguration = daemonConfiguration;
         this.nestDirectory = nestDirectory;
         this.nestContextFactory = nestContextFactory;
      }

Yuck, that’s six lines of boilerplate! I once worked on a team that leveraged a tool named Lombok which let you write Java code like….

import lombok.*;

package io.dargon.nest.daemon.hatchlings {
   @RequiredArgsConstructor
   public class NestDirectorySynchronizer {
      private final IFileSystemProxy fileSystemProxy;
      ...
      // no constructor!
   }
}

Nifty, eh? A year ago I started looking for this feature in C#. It didn’t seem to exist… but, over the last few hours, I built it! Those lines of code now look like:

using Fody.Constructors;
using ItzWarty.IO;
using System.IO;

namespace Dargon.Nest.Daemon.Hatchlings {
    [RequiredArgsConstructor]
    public class NestDirectorySynchronizer {
      private readonly IFileSystemProxy fileSystemProxy;
      private readonly DaemonConfiguration daemonConfiguration;
      private readonly NestDirectoryImpl nestDirectory;
      private readonly NestContextFactory nestContextFactory;

The code’s pushed to GitHub at ItzWarty/Constructors now. I’ll write a more in-depth post sometime soon, but the tl;dr is that I leveraged Fody and Mono.Cecil to add the constructors as a post-build process. The code is extremely simple, though it touches on basic CIL (.NET Bytecode) and requires understanding a bit about how C# code gets compiled – it’ll be a fun post!

I’ve also pushed Constructors.Fody to nuget.dargon.io, for those of you who wish to try it out :P

That’s all for now!

Michael.

Character Detection in League of Legends Artwork

So we’ve been working on Dargon. You know, the mod installer we’re shipping before the sun explodes.

For a plethora of reasons, we’ve needed a way to generate modification thumbnails. Good thumbnails have the following criteria:

  1. They focus on the character featured in the modification.
  2. They are sourced from images of decent resolution.
  3. They actually improve our user experience.

Goal 1 is the hardest: We can’t use facial recognition on characters like Kogmaw.

Kogmaw!

Here’s how we generate thumbnails: You can follow along our code here or watch it’s development stream here (jump to 2:10:00, we hit 30 viewers!):

Step One: Edge Detection and Edge Density Histogram

The core of our algorithm relies on three ideas:

  1. 2D character artwork is usually drawn by artists.
  2. When 2D character artwork is drawn by artists, artists tend to place more details on the characters that the artwork should focus on, to draw attention to them.
  3. The majority of characters tend to stand upright, rather than lay sideways.

Our algorithm is simple, involving edge detection and a luminosity histogram:

Kogmaw Histogram!

From there, we compute the mean (Green line) and median (Red line) of the histogram. Starting at the median, we run a hill-climbing algorithm that attempts to select a range with the highest luminosity (Region between Purple Lines).

Nerd note: The cyan lines contain the region within one standard deviation of the median. We have other methods of computing spread, so we don’t really use this.

Step Two: Image Ranking

The algorithm performs this operation for many images while generating a score for them. The score factors in a few variables:

  1. Wing Spread Factor – Punishes characters like Anivia for spreading features across the image.
  2. Focus Factor – Rewards images for having their details squishes into a tiny width.
  3. Width/Height Factor – Punishes images for being too tiny to help in thumbnail generation.
  4. Brightness Factor – Rewards images for being bright. This helps filter particle textures.

Anivia

Step Three: Character Slice Compositing

Finally, we select the best images (with a bit of randomization). When compositing a final image from multiple images, we rank our image ‘slices’ based on luminosity and shuffle them in a way that alternates light and dark images. We need to improve this a bit, but here are our final results:

Results

Clearly, the algorithm doesn’t work so well on in-game texture files (they are drawn with different design considerations), but at the least they’re representative of their modifications. Surpringly, though, the algorithm works very well with character artwork, where facial detection would likely fail.

Final Thoughts

Requirement three was that our algorithm improve our user experience. The thing runs pretty fast and in the background. The only filters we use (which take most of our algorithm’s processor time) are AForge’s Grayscale filter and Homogenity Edge Detector – the Grayscale one iterates per-pixel and multiples rFactor * R + gFactor * G + bFactor * B while the other simply looks for a pixels’s maximum contrast with its neighbors.

Gangplank Bimodal Failure Case

Our algorithm does not handle images with bimodal edge distributions. Future improvements might detect these “humps” in our images and generate two output slices. There’s a ton of improvements we could make to this algorithm after we ship Dargon, though for now, we feel pretty k.

So long for now,
Michael Yu

Our Baby Dargon

Introducing MiniSynapse: A Tiny Razer Synapse Alternative

In a fit of 3AM Rage, I decided to write an alternative to Razer Synapse.

And then I realized most people don’t like Razer Synapse, so I decided to stop Razer Synapse from running at startup.

And then I restarted my computer and discovered that without Synapse, my mouse wasn’t configured properly.

And then I became annoyed. I don’t like being annoyed.

And then I created MiniSynapse. You can find MiniSynapse on my Github page at ItzWarty/ItzWarty.MiniSynapse.

And thus it was K.

MiniSynapse works by logging into your Razer account (using whatever login info you used previously) and loading your device configurations. I’ve only tested it with a BlackWidow and a Deathadder Chroma, so I have no clue how it operates with whatever other devices (e.g. mousepads… if they have drivers for whatever reason, headsets, laptops, touchpads, etc). Oh yeah, and Razer Surround seems to still work fine after all this, though I don’t think it depends on Synapse at all (good for them!)…

Stay safe, don’t drive drunk or do drugs, cya next time.
-Michael ‘ItzWarty’ Yu

Adventures in Shade 04: Dabbling in Pathing I

Pathing! What fun!

After yesterday’s post on picking and ray-to-convex-polygon intersections, we were able to move our hero around our plane. Now, our hero can walk along an arbitrary path (a collection of points) at an arbitrary speed!

In order to find these paths, I’m generating a navigational mesh (navmesh for short) which is passed into a pathfinder. I’m not yet done here, so the rest of this post will be largely speculative

Navmesh and Rendered Path!

Bitmap-based dungeon generationPathfinding: Notice line stemming from our hero.
Navigational mesh: Triangulation drawn in cyan, graph links drawn in red.