Thursday, July 11, 2013

We're Moving

Although indicated otherwise a few days ago, I've still ultimately decided to move my blog to a self hosted static site.

The new blog is running at http://blog.macuyiko.com/, i.e. the same address as before. All posts have been migrated, but

(i) URLs have been lost -- sorry about your deep links and bookmarks and
(ii) comments are lost as well.

Therefore, the old blog (the one you're seeing now) will continue to be available at http://bedagainstthewall.blogspot.be/, although new posts will not appear here.

Sunday, June 30, 2013

A Bukkit Jython Console Plugin for Minecraft

Summary

This post describes how you can create a Python interpreter for a Bukkit Minecraft server, providing access to the full internal API. Commands are issued on a separate console window and do not require players or server administrators to be running the game itself.

Introduction

Unless you've been living under a rock, you probably know about Minecraft, the famous open block based 3D building/crafting/exploration/survival game.
Minecraft is a game about breaking and placing blocks. At first, people built structures to protect against nocturnal monsters, but as the game grew players worked together to create wonderful, imaginative things.

It can also be about adventuring with friends or watching the sun rise over a blocky ocean. It’s pretty. Brave players battle terrible things in The Nether, which is more scary than pretty. You can also visit a land of mushrooms if it sounds more like your cup of tea.
Minecraft has been wildly successful. Not only because of the LEGO-like main gameplay, but also thanks to the developers' friendly stance towards modding, causing an incredible amount of modifications being released, ranging from additional creatures to custom biomes.

Lots of people have also emphasized the fact that Minecraft is a great way for parents to bond with their children. Also in the classroom, Minecraft has been used as a teaching aid to inspire children.

Combine the two aspects above (modding and teaching), and you ultimately start wondering whether Minecraft could also be used to teach programming. When the Raspberry Pi put online their announcement that a special Minecraft version would be available for their miniature, cheap computer, the answer to this question indeed seems to be: yes, since their "Minecraft: Pi Edition" would come with a programming Python API built in, as shown by the following screen shot.

Minecraft running on the Raspberry Pi

Back on the PC-side, the great interest in modding Minecraft eventually led to the Bukkit project -- a community-created Minecraft server with a comprehensive API to allow others to create plugins, extending the world, gameplay and rules of the vanilla Minecraft experience. Minecraft server administrators also enjoy having some sort of console available to be able to modify a Minecraft world at runtime. Banning players, erecting or destroying structures or changing the time of day without having to restart indeed comes in handy when you're running a server. The Bukkit development API makes it very easy to create such kinds of plugins, but they often require the list of possible commands to be specified beforehand (in the Java plugin), which are then made available through the game's chat window. For instance, issuing the command:

/weather sunny

Would mean that you have a plugin running which is able to handle the command /weather and converts this to appropriate Bukkit API calls, e.g. setThundering.

Other than that, lots of people have started to learn Java or other languages by trying to create a Bukkit plugin or some sort of Minecraft-inspired clone. Following list provides just a tad of what is out there:
This is all nice, but a bit too high-level for what I wanted to build. I wanted to have direct access to the Bukkit API, similar to how the Minecraft: Pi Edition provides direct access to its API.

We're thus going to create a Bukkit plugin which gives server administrators or programming students direct access to the full Bukkit API. The actual plugin is actually very simple, thanks to the magic of Jython, a Python implementation in Java which allows for Python<->Java crosstalk and saves us from having to implement any command in the plugin itself. Commands are issued on a separate console window and do not require players or server administrators to be running the game itself.
The base idea behind what we're going to do is certainly not new by any means. The Minecraft: Pi Edition, as mentioned above, implements a similar idea (see also this article). The Mag Pi magazine even featured a nice tutorial to show off what you can do with it.

Other than that, there's ScriptCraft, providing a Javascript based programming interface for Minecraft:
ScriptCraft is a Minecraft Mod that lets you extend Minecraft using the Javascript Programming Language. ScriptCraft makes modding Minecraft easier. It includes a logo-like "Drone" object that can be used to build complex buildings, roads, villages, even entire cities. It also includes many other features that make modding Minecraft easier.
You can find more information about ScriptCraft here and here. It's certainly a great project to teach programming, but comes with the drawback that it offers programmers its own API (implemented in a Bukkit plugin), meaning that you'll have to program using Bukkit chat commands, for instance:

/js box("5").up(3).left(4).box("1").turn(3).fwd(5).right().box("1").move("start")

ScriptCraft also includes a "Drone" class which simplifies movement and building in Minecraft, similar to the "turtle" in the LOGO programming language (LOGO is a Lisp-like programming language which used to be popular to teach kids programming; fun fact: the first "real" programming language I learnt actually was a LOGO derivative).

This is all nice, but still too high-level. I want to be able to get direct access to all Bukkit's API functions (not only exposed ones through a plugin), preferably not having to use the game's chat.

ComputerCraft also inspires people to learn coding, but is even more high level. It actually provides a "console block" in the game offering a rudimentary shell which has nothing to do with the inner workings of either Bukkit or Minecraft.

Finally, plugins such as PyDevTool and RedstoneTorch come closer to what we want to achieve. For instance, PyDevTools allows to:
Execute arbitrary python code from console or ingame
Execute saved python scripts
Interactive interpreter mode
This is almost exactly what I wanted to build, but still requires to log into the game to execute /py <statement> commands. Yes, these can also be entered in the Bukkit console (offering some kind of interactive shell), but I wanted to remove the /py clutter. A simple trick indeed will allow us to do so, let's get right to it...

Making the Plugin

We'll be using Eclipse to make our Bukkit plugin. I'll assume you know how this IDE works already. If you're not familiar with Java and just want to try the plugin, you can skip this section. Otherwise, follow along.

First of all, we're going to create a new Java project in Eclipse. I'll call this BukkitConsole. We create a plugin.yml file in the project root with some basic information:


Next up, we create a lib folder in which we're going to place two libraries:
  • jython-standalone-*.jar: to be downloaded from the Jython web site
  • bukkit-*.jar: the Bukkit development API, which can be downloaded from here (more information on their Wiki)
Add these libraries to the build path. You'll now have the following structure:


Next, we'll create the plugin classes themselves. Create a package under src called com.macuyiko.bukkitconsole. We're going to add two classes.

MainPlugin.java, this class just loads the libraries from the lib folder and spawns a PythonConsole window:

package com.macuyiko.bukkitconsole;

import java.io.File;
import org.bukkit.plugin.java.JavaPlugin;
import org.bukkit.plugin.java.PluginClassLoader;

public class MainPlugin extends JavaPlugin {
    public void onEnable(){
        getLogger().info("BukkitConsole: Loading libs");
        try {
            File dependencyDirectory = new File("lib/");
            File[] files = dependencyDirectory.listFiles();
            getLogger().info("BukkitConsole: JARs found: "+files.length);
            for (int i = 0; i < files.length; i++) {
                if (files[i].getName().endsWith(".jar")) {
                    getLogger().info("BukkitConsole:  - "+files[i].getName());
                    ((PluginClassLoader) this.getClassLoader()).addURL(
                        new File("lib/"+files[i].getName()).toURI().toURL());
                }
            }
        } catch (Exception e) { 
            e.printStackTrace();
        }

        getLogger().info("BukkitConsole: Starting Jython console");
        new PythonConsole();
    }

    public void onDisable(){
        getLogger().info("BukkitConsole: Plugin was disabled");
    }
}

PythonConsole.java, this class employs Jython to execute console.py in the python directory:

package com.macuyiko.bukkitconsole;

import org.python.core.Py;
import org.python.core.PyString;
import org.python.core.PySystemState;
import org.python.util.PythonInterpreter;

public class PythonConsole {
    public PythonConsole() {
        PySystemState.initialize();

        PythonInterpreter interp = new PythonInterpreter(null,
                new PySystemState());

        PySystemState sys = Py.getSystemState();
        sys.path.append(new PyString("."));
        sys.path.append(new PyString("python/"));

        String scriptname = "python/console.py";
        interp.execfile(scriptname);
    }
}

Things'll now look as follows:


That's it for the Java side! Export your project to bukkitconsole.jar.

We're now going to setup the server. Create a folder server somewhere. Next, download craftbukkit-*.jar from here (Bukkit is the development API, "CraftBukkit" is the actual server; again, more info on the Wiki) and put it in this folder.

We're also going to create a simple run.bat in this folder:

java -Xmx1024M -jar craftbukkit-*.jar -o true
PAUSE

Execute run.bat to see whether CraftBukkit works fine and if you can connect with your Minecraft client (note: if you're running the current snapshot, the launcher should allow you to create a profile with version 1.5.2, which is what we're using here). Normally, you should get something like:


Enter stop to stop the server. CraftBukkit will have create some new folders in your server directory:


Next, we're going to download a Jython console. I picked this one by Don Coleman, since it is simple and offers fairly robust code completion. Note that I had to make some changes to it which can be found on the GitHub repository I've created for this project. Not using these changes is okay but will lead to some error spam on the Bukkit console.

Create a folder called python in server and extract the Jython console. python should contain:
  • console.py
  • history.py
  • introspect.py
  • jintrospect.py
  • popup.py
  • tip.py
We also need to create a lib folder in server and put in the following JARs:
  • bukkit-*.jar
  • jython-standalone-*.jar
Yes... the same ones we've included in our Eclipse project. It would have been possible to package these into the JAR, but loading in resources from JAR files is a bit of a pain which I didn't want to go through. Feel free to add lib and python to the JAR and submit a pull request on GitHub if you get things working.

That's it. Try executing run.bat again. If all goes right, Bukkit should be able to load in our console plugin and will present you with an interpreter:


We can try out some commands. Note that you'll have to from org.bukkit.Bukkit import * to get access to the Bukkit API (or from org.bukkit import Bukkit -- you'll have to use Bukkit.* but will allow autocompletion)!

>>> from org.bukkit.Bukkit import *
>>> getWorlds()
[CraftWorld{name=world}, CraftWorld{name=world_nether}, CraftWorld{name=world_the_end}]
>>> w = getWorld("world")
>>> w.getTemperature(0,0)
0.800000011920929
>>> w.getBiome(0,0)
PLAINS
>>> w.getTime()
12557L
>>> w.getPlayers()
[]
>>>

The Bukkit API docs provide a full overview of all that is possible with the complete API. Broadcasting messages, changing inventories, changing worlds, spawning lightning, all is possible.

You can also save functions in Python scripts if you want to. For example, try creating a scripts.py in the server folder:

import random
import time
from org.bukkit.Bukkit import *

def punishPlayer(name, power):
    p = getPlayer(name)
    p.getWorld().strikeLightning(p.getLocation())
    p.getWorld().createExplosion(p.getLocation(), power)
    broadcastMessage("Player %s has been punished!" % (name))

Now, in the console, we can:

>>> import scripts
>>> scripts.punishPlayer("Macuyiko", 6)

Which will explode a player with a lightning strike to warn other outlaws. The server administrator's "command center" now looks like this:


Wrapping Up

That's it. We've created a Bukkit plugin spawning a Jython interactive console which is able to use the full Bukkit API.

This is a nice starting point to create administrative support scripts, in-game games, or course material for a Minecraft Python programming course.

The following video shows some more tinkering:



(Protip: I'm a bit awkwardly using alt-tab and the inventory screen here. If you press T to start typing in chat, you can alt-tab out of the game without pausing or having the inventory screen opened, which allows you to better see what's going on.)

The source code for this project can be found on the following GitHub repo. The repository also hosts everything you need to get running without having to code/compile anything. Feel free to modify both the Python and Java sources and submit pull requests with improvements. I'd also love to hear about any cool or interesting things you do with this.

Saturday, June 29, 2013

I Almost Switched to Pelican, a Static Blog Engine

Visitors familiar with my blog will notice a pretty big change when viewing this post. The blog's been due for a redesign for some time now, so a few days ago I finally went through with it.

The redesign took more time than expected, since I spent quite a lot of time setting up Pelican -- a static blog engine written in Python, including converting all my Blogger posts to Markdown. I will describe some of the reasoning behind this, together with the reason why I ultimately stayed with Blogger -- for now.

What's Wrong with Blogger?

I've been using Blogger for many years. Delving into the archives of this site suggest I've been seriously using it since 2005, with my main blog being called "Macuyiko's Mindcube" back then. In fact, it's still online, with the last post redirecting visitors to my new blog ("Bed Against The Wall").

Throughout the years, that -- this -- blog went through a series of redesigns and shifted through topics of interest. To be honest, I was never that good at consistently putting out content, but being able to keep the thing running for almost ten years now is an accomplishment in itself, I suppose.

Anyway, I've been getting somewhat disappointment with Blogger lately, something which started some two or three years ago, when I started putting out longer articles, containing also more code fragments. Don't get me wrong, I don't think Blogger is bad, but the following things were becoming an annoyance:
  • I've seen my fair share of Javascript WYSIWYG editors -- either bolted to your favorite blogging platform of choice or "that PHP Content Management System from the nineties". While libraries and frameworks such as JQuery have helped to clear out some of the mess, I honestly feel that 99% of them still behave like crap.
    I'll not go into details about all the things wrong with Javascript editors now. Still, there is one silver lining which is worth mentioning: the amount of great Markdown based Javascript editors which have appeared during the past years. For example, check out EpicEditor, markItUp!, markdown live editor, WMD (outdated) and its many spinoffs. I absolutely love Markdown, and have even forced it to users of websites I've built, using one of the aforementioned Javascript editors to make it clear how easy it is to write Markdown text.
    At this point you might be wondering what, exactly, is so messed up about the Blogger WYSIWYG editor. There isn't anything really wrong with it, but the following has been bothering me:
    • Inserting code is a problem. You have to deal with pre, tt, code tags together with installations of Pretty Print (or similar libraries). Don't forget to convert your <'s to &lt; or things won't work. Make sure your whitespace is correct, meaning that you alternate between tabs, spaces, or a bunch of &nbsp;'s.
    • So okay, maybe Blogger isn't great for code, but at least it's perfect for writing, right? Not really. It's okay, but the rise of recent "modern magazines" such as Medium and SVBTLE have made it clear that writing can be a much smoother process. Heck, even Wordpress' editor is nicer, and will apply many typographic fixes such as converting two dashes to an em-dash.
    • Blogger allows too many formatting options. Since its editor is a WYSIWYG on top of HTML, it's perfectly fine to copy-paste in ugly text coming from an e-mail message or that Word document you typed out... <span> with mso-style, anyone? Please, just allow me to apply headings, emphasis, lists and paragraphs to my text, but let the theme CSS do its thing and leave out the styling.
  • Making changes to the template is bothersome. Blogger's template system is fine as long as you keep using one of the default themes, maybe make some slight color or font changes, and leave the rest as is. Once you want to start moving stuff around however, add backgrounds or lots of custom CSS/JS, things get harder and you quickly and up in the middle of "tag soup". I didn't even manage to change the background of the final theme I was using once, even though I was initially planning to do so once in awhile. It's not hard, but my laziness outshines the difficulty.
That said, there are plenty of things which I do like about Blogger. It's very easy to set up a basic blog, there are many widgets to choose from, basic templating stuff is fine if you don't mind your blog having a common look and feel. Also, comment management and moderation works pretty well, especially now with the Google+ integration.

So, in short, what I wanted was:
  • The ability to write in Markdown
  • The ability to easy add in code, syntax highlighted if possible
  • Nice typographic options, beautiful text
  • Easy theming support
Blogger was starting to make this pretty hard.

Solutions, Workarounds and Alternatives

Just continue to use Blogger?

I'm not alone in my desire to use Markdown with Blogger. The topic has actually been discussed to a great extent, with solutions including the following:
  • Write Markdown on your computer, then convert to HTML with one of many tools out their. Cons: redundancy, no central "post" repository, making edits is hard. Not 100% web based.
  • Use one of these neat apps such as Byword (MarsEdit as well?) which lets you publish to Blogger. Cons: not 100% web based, no central posts repository. Often Mac only...
  • Write a web app using Blogger's API which would allow me write posts using Markdown and publish them to Blogger after converting them to HTML. But this would've taken so much effort.
  • Include a bunch of magic Javascript scripts/parsers on your Blogger blog which will perform the conversion of Markdown to HTML client-side. This keeps your posts centrally stored, but relies on too much hacks to feel like a great solution. Still, it's being used. mmd.js seems to be the preferred Javascript Markdown parser as of now.

Switch to another service

There has been a renaissance of writing on the web. When 2012 used to be about Tweets and short status updates, sites like Neocities or Medium are putting the emphasis back on simple, well written web sites.
Indeed, the options for a minimalistic blog are many. Many of them support Markdown out of the box. Many of them do away with many typical overblown blogging features. No comments, no complex theming, just writing:
I will admit, these all look fantastic. I'm already using Tumblr for my random stuff I find online blog; the Dropbox based options look like great Zen-like blogging experience. I have my invite for Medium, and the platform looks fantastic.

I would've gone with one of these options (in fact, I'm still on the fence), but I was a bit disappointed with (i) the lack of code formatting support on most of these platforms, (ii) the lack of any theming to make yourself stand out.

Host it yourself, static-like

A final alternative solution I was considering was hosting the blog myself using a static blog engine. I don't mind Wordpress, but think it's completely overkill for a simple use case such as mine. I considered the following options:
  • Jekyll: Ruby, Markdown or Textile, robust, proven, powers GitHub Pages...
  • Octopress: sits on top of Jekyll to provide a more full featured blogging platform.
  • Hyde: "Jekyll's evil twin". Python, Jinja2, full-featured.
  • Hakyll: Haskell, robust, esoteric.
  • Acrylamid: Python, Markdown and reStructuredText, Jinja2. Fast, experimental.
  • Utterson: Unix, HTML. Basic, experimental.
  • Rog: Ruby, simple, young.
  • Cyrax: Python, Jinja2, young.
  • Second Crack: PHP, one of the few PHP static blogging engines worth mentioning these days (shows how the language has evolved, actually...). Created by Marco Arment, so you know it can hold its own. Not suitable for everyone though.
  • Pelican: Python, Jinja2, Markdown and others, well-featured, easily usable.
Ultimately, I settled on Pelican. I liked Jekyll, but wanted a Python based engine since I didn't want to deal with installing Ruby on the server I'd be using. Installing Pelican is very simple. Just pip install pelican, Markdown and typogrify and you're set. Typogrify is a great Python library which helps you to prettify written text, mostly thanks to Gruber's fantastic SmartyPants plug-in.

Configuration is just an easy step consisting of modifying pelicanconf.py:
#!/usr/bin/env python
# -*- coding: utf-8 -*- #
from __future__ import unicode_literals

AUTHOR = u'Your Name Here'
SITENAME = u'Your Title Here'
SITEURL = ''

TIMEZONE = 'Europe/Brussels'
DEFAULT_LANG = u'en'
TYPOGRIFY = True

# Generation
DIRECT_TEMPLATES = ('index', 'archives')
MONTH_ARCHIVE_SAVE_AS = 'archives/{date:%Y}/{date:%m}/index.html'
YEAR_ARCHIVE_SAVE_AS = 'archives/{date:%Y}/index.html'

# Feeds
FEED_ATOM = 'feeds/atom.xml'
FEED_RSS = 'feeds/rss.xml'
FEED_ALL_ATOM = None
CATEGORY_FEED_ATOM = None
TRANSLATION_FEED_ATOM = None

# Blogroll
LINKS =  (('Name', 'http://url.com/'),
    )

# Social widget
SOCIAL = (('Twitter', 'http://twitter.com/username'),
     )

DEFAULT_PAGINATION = 10

# Template
THEME = "themes/custom_theme"

I then picked the TuxLite ZF theme from pelican-themes as a starting point to put in custom_theme. I changed the color scheme, header sizes and spacings and fonts (making use of Google's web fonts to pick out a nice heading font which would work well with large-sized OpenSans for the normal text, which I'm currently in love with -- it works great for slides as well, try it!). Editing the Jinja2 themes was a breeze and mostly consisted of taking stuff away -- like tags and categories -- which I didn't need. Finally, I made sure to made the background "pop" behind the single-column content, using inspirational, high resolution foto's.

Next up, the hard part, converting all my Blogger posts to Markdown... Luckily, Lars Kellogg-Stedman has had the same problem and describes possible approaches in this post. I thus created a folder with the following:
You'll need to install lxml to get everything to work. This didn't work for me using pip, but easy_install did the job. Once this is setup, create a new directory posts and run:

blogger2md.py --html2text --output-dir posts blogger-export.xml

The script will start crunching and convert everything. Afterwards, I went through every post to rename the file name, correct the meta data, fix the links (Pelican wants (|filename|FILE_PATH)) and clean up some formatting issues still present after the conversion (quite a lot of them). This took a few evenings, but I now have a collection of Markdown posts for this complete blog.
Side track: a trip down memory-lane
While I was converting all these posts, it struck me how long I've been blogging, and how "face-palmingly" bad my writings were as a kid. Luckily, my Geocities page has since long disappeared thanks to Yahoo! (actually, I should retrieve it from the archive for a laugh), but this wasn't that much better. "This dog is gonna check out town"... really, young me? I wanted to keep everything intact, but made some modifications to the language where I really felt I had to (swearing, "hackz0r M$"-bashing, referenced to piracy... hey, I was a poor kid).

It's also funny to see the topics my blog has shifted through:
  • Games, with sad reviews of "classics" such as Scarface... and Portal.
  • Linkdumps, oftentimes based on what I'd read on Digg (yes, Digg!) that day. Is Digg still around? I almost forgot about the HD-DVD "number gate" back then.
  • Linux related posts. Mostly following after acquiring my now pre-historic Thinkpad X60 which is, in fact, still somewhat being used.
  • Hacking and thinkering... like here and here. Some of these are not that bad. The Kippo article has been pretty popular, together with the PalettestealerSuspender tool. Others just show off my horrific PHP skills.
  • Puzzles, algorithms, optimization. I like these as well, but they should be proofed for language, spelling, formatting.
Anyway, back to the main programming now.

Just stay with Blogger?

So here I was, ready to launch with Pelican. Admittedly, some of the posts needed some further formatting, some links has to be corrected and the Disqus comment system had to be implemented, but that could be done later. All there was left to do was relink the domain name (blog.macuyiko.com) and put up a message on the old blog that things had moved.

Still, I wasn't feeling sure about things. Just to be sure, I decided to have another look around to see if things had improved on the Blogger side as of yet, since it'd been a while since I'd searched for solutions.

Turns out there is a web app called StackEdit which provides a great Markdown writing environment, is able to sync to Dropbox or Google Drive (sweet) and is able to publish to Blogger. Alright, maybe one more chance, then. I spent some time revamping the old theme to match the design I'd put together for the static site (you're probably looking at it now), using the same fonts and colors. I had also set out to be able to change the background every time I made a new post, so I made sure I'd be able to do that from now on as well. That's why you're currently looking at a summer-y "pelican" background. It'd be great if I could made the background post-dependent, but maybe that's going too far.

So I'm keeping things a bit longer with Blogger. As I said at the beginning, it offers some nice features, and this way I don't have to introduce yet another commenting system.

On the plus side, I'm now able to write and keep posts as Markdown (using StackEdit with Google Drive) and host at Blogger. The theme doesn't look too bad (will need some further fine tuning) either. Still, if it turns out that I'd rather go to Pelican anyway (or maybe one of the services mentioned above), I now have a collection of Markdown posts at the ready.

I realize this post didn't really offer any information. I guess this was an exercise in keeping things the same while still putting in lots of work. Still, it was nice reading up about static blog engines, and I'm still pretty intrigued by these hip, new services (Blogger certainly feels like the old guy in the block). In addition, the refresh of the Blogger theme has been inspiring in trying to conjure up some new content, so the remainder of the year will see the arrival of some other posts as well -- so long as this experiment goes right, this is a first test post after all. I should still go through the older posts to clean them up, but we'll see what we can manage.

Tuesday, January 01, 2013

Games I'll Keep An Eye On In 2013

In the same spirit as last year, this is a (preliminary) list of game I'm interested in, releasing in 2013.

First of all, let's revisit 2012... Here are the games I was interested in last year, together with the outcome -- at least according to me:
  • Star Wars: The Old Republic: skipped it
  • Kingdoms of Amalur: Reckoning: it was okay, but nothing special
  • Binary Domain: let-down
  • SSX: okay, not great
  • Syndicate: let-down
  • Jak and Daxter Collection: great nostalgia trip
  • The Darkness 2: actually quite an awesome game
  • I am Alive: didn't buy it
  • Mass Effect 3: the one which disconnected me from the series (and I was a huge fan). I've heard there's some great DLC, but I've yet to play it
  • Diablo III: okay, but not as I expected
  • Devil May Cry HD Collection: have yet to buy it
  • Silent Hill HD Collection: have yet to buy it
  • Prey 2: didn't release
  • Starhawk: meh
  • Far Cry 3: awesome! In my 2012 top five list
  • Max Payne 3: a great game, but alas missed by many top 2012 lists
  • Darksiders II: greatly enjoyed it
  • Prototype 2: okay, but quickly forgotten compared to the other open-world games of 2012
  • Tomb Raider: didn't release
  • Guild Wars 2: best MMORPG of the moment
  • Borderlands 2: not bad, but got a bit of a "more of the same"-feeling here
  • The Last Guardian: didn't release
  • Lollipop Chainsaw: fun, but not spectacular
  • Grand Theft Auto V: didn't release
  • BioShock Infinite: didn't release
  • Doom 4: didn't release
  • Journey: again an awesome game, top listed
  • XCOM: Enemy Unknown: another great title and a must-play
  • Monaco: fun indie game
  • The Witness: did this release?
  • Firefall: still waiting
  • Cube World: didn't release
  • Overgrowth: did this release?
  • Path of Exile: couldn't hype me
  • Grim Dawn: didn't release
  • Starfarer: did this release?
  • Legend of Grimrock: a great indie title but alas flew a bit under the radar
  • Torchlight II: gave me more hours of fun than Diablo III did
  • Survivors of Ragnarok: did this release?
  • Project Zomboid: did this release? I should check up on this one
  • Masters of the Broken World: did this release?
  • Warlock: Master of the Arcane: did this release?
  • A Game of Dwarves: let-down
  • Jagged Alliance: let-down
  • Castle Story: didn't release
  • Retro City Rampage: actually pretty fun
There where also some surprises which I didn't list last year, most notably: Dishonored, Faster Than Light, Fez, Spelunky, Sleeping Dogs, The Walking Dead, Hitman: Absolution and Hotline Miami.

And thus, my top 10 of 2012:
  1. Far Cry 3
  2. Hotline Miami
  3. Dishonored
  4. XCOM: Enemy Unknown
  5. Faster Than Light
  6. Journey
  7. The Walking Dead
  8. Sleeping Dogs
  9. Darksiders II
  10. Torchlight II
And now, these are the games I'll be watching in 2013 (note the rising number of "kickstarted" entries):
  • Bayonetta 2
  • Bioshock Infinite
  • Castle Story
  • Castlevania 2: Lords of Shadow
  • Castlevania: Lords of Shadow: Mirror of Fate
  • Command & Conquer Generals 2
  • Companty of Heroes 2
  • Crysis 3
  • Cube World
  • Dead Space 3
  • Doom 4
  • Double Fine Adventure Game
  • Elite: Dangerous
  • FireFall
  • God of War Ascension
  • Grand Theft Auto 5
  • Grim Dawn
  • Legend of Dungeon
  • Limit Theory
  • Metro: Last Light
  • Miami Hotline 2
  • Planetary Annihilation
  • Prey 2
  • Project Godus
  • Routine
  • Saints Row 4
  • Shadowgate
  • Shadowrun Returns
  • Sim City
  • Star Wars 1313
  • Sui Generis
  • The Last of Us
  • Tomb Raider
  • Wasteland 2
  • Wasteland 2
  • Watch Dogs
  • World of Darkness

Tuesday, May 22, 2012

Ubuntu 12.04: "fixed channel mon0: -1"

Still having problems in Ubuntu with the fixed channel being -1 when using aircrack and friends? Luckily, the solution does not require patching this time (as it used to), as the following (obtained from this forum post) now works for me (the problem is basically that the channel can not be changed while the card is in monitor mode).

Just create a bash script as such:

#!/bin/bash
#change this to the interface you wish to change
IFACE="wlan0"

ifconfig $IFACE down
iwconfig $IFACE mode managed
ifconfig $IFACE up
iwconfig $IFACE channel $@
ifconfig $IFACE down
iwconfig $IFACE mode monitor
ifconfig $IFACE up

iwconfig $IFACE

And everything should work just fine. Just continue to use $IFACE (e.g. wlan0) in all subsequent commands (airodump,...) you use. Naturally, you do not need to use airmon-ng anymore to put the network card in monitor mode (as $IFACE now already is in monitor mode).

Sunday, May 13, 2012

An Attempt At Making A Javascript/HTML5 SliceIt! Clone, And A (Failed) Attempt At A Genetic Algorithm Based Solver

One of the niceties of owning a smartphone is the huge amount of apps available for download, many of which are games.

Some time ago, one of these games which was keeping me occupied was SliceIt! from Com2uS. Don't worry if you don't know the game or haven't played it, I'll quickly explain it below.

The Game


SliceIt! is presented in a cute crayon-looking style:
A typical SliceIt! level. Players draw lines (as shown here) to split a given shape into equally sized areas.

The goal of the game is to draw a number of lines to divide ("slice") the given area into a number of pieces. Both the number of lines and required pieces are fixed and given beforehand. You have to use all the strokes given, and have to match exactly the number of needed pieces. No more, no less. The final requirement of the game is that the resulting pieces need to have about the same area. While their form may differ, their area (size) has to match. This means for example that if the goal is to get four pieces, all these four pieces need to have a size around 25% (100%/4) of the original area. Pieces don't have to be of exactly the same size. If their areas differ slightly, the level is still won. This allows for levels which have straightforward but not-quite-perfect solutions and perfect but hard-to-find solutions as well.

The Idea


So far, so good. After playing the game for a while, I encountered the following level:
Another SliceIt level (goal: 5 strokes, 10 areas),

This level introduces another gameplay concept: blocked areas. Drawing lines which crosses these areas is forbidden, so this solution won't work:
This solution would use 5 lines to form 10 equal areas, but the red areas forbids the player to draw the final line.
After fiddling for a bit, we find the following acceptable solution:
A solution.

While messing around, a thought popped into my head: could a genetic algorithm be used to solve a SliceIt! puzzle? At first sight, this seems like a good idea. The game itself is pretty easy. A chromosome representation can easily be established (since we know the list of strokes beforehand, so a population member can be represented simply as an array of coordinate-pairs:

[
  ((l1x1,l1y1), (l1x2,l1y2)),
  ((l2x1,l2y1), (l2x2,l2y2)),
  ((l3x1,l3y1), (l3x2,l3y2)),
  ((l4x1,l4y1), (l4x2,l4y2)),
  ((l5x1,l5y1), (l5x2,l5y2))
]

And finally, the solutions can be easily checked (just compare areas with a known goal).

And so I set out to test this theory as a weekend project.

While lines, areas, points and polygons can all be expressed and compared mathematically, I wanted to create a graphical representation of the game as well. Moreover, I wanted to build a playable version, before implementing a genetic algorithm. Finally, I wanted to do this with HTML5 (canvas) and Javascript, as I've been pretty jealous of all these other cool genetic algorithm implementations available on the web:

I didn't want go completely overboard, though. I only wanted to implement to most basic puzzles found in the game, as described above. Later levels add all sorts of crazy stuff (like bouncy edges and so on). Still, the game allows for some constructs which are pretty challenging:
  1. Levels are created by defining a number of polygons. A level can be build out of multiple shapes.
  2. These polygons can both be convex and concave.
  3. The polygons can contain holes as well (not sure if there are levels like this in the game).
  4. Polygons can be added to a level which denote "forbidden areas", though which no lines may be drawn.
Feature number three is the most challenging one. To solve this, you have to first create a polygon defining the outermost shape, and then additional polygons to define the holes. The area of the obtained shape is then calculated by subtracting the areas of all holes from the areas of all the outer shapes. While I was planning to implement this add first, I dropped it, mainly out of laziness, and because much of the logic in the game would've become quite harder when this aspect would be included.

The Implementation


The code turned out the be pretty complex. I created multiple Javascript object types, either handling game logic, or representing geometrical concepts. This means that types were made for:
  • A point: constructed out of two numbers (x and y coordinates).
  • A line: constructed out of two points (point one and two).
  • A polygon: constructed out of an array of lines (the edges).
  • A rectangle: constructed out of two points (upper left and lower right corner).

The rectangle type should actually have been based upon the polygon type (a rectangle is just a special type of polygon). Similarly, in hindsight, the polygon object should have been defined as an array of points, instead of lines. For lines, methods to get the length and intersects with other lines were added. For polygons and rectangles, methods to get the area of the shape were added as well. I had to refresh my memory on geometry a bit:

For the game logic, I created the following types:
  • The surface: attached to a canvas element. Handles Javascript events (mouseup, mousemove...).
  • The drawer: contains methods to draw various things using a surface. These contain methods for drawing the level, the forbidden rectangles, and a cutting line when a player drags the mouse.
  • The level: contains level data, such as the number of allowed strokes and required pieces. The definition of the polygons making up the level, and the list of rectangles defining the forbidden areas. 

The level object type also contains some methods for handling the harder game logic. E.g., methods which take a line, and figure out how the current list of level polygons should be cut.

The way levels are cut after drawing a line works like this. First, compare the drawn line with all the edges defined by all the polygons to get a list of intersects. Then, some basic checking is performed to figure out if the line is valid. Finally, if the line is valid, polygons are split up, and a list of new polygons is created.

An example can help here. The following figure shows how a line "splits" a single convex polygon:


When a new line is drawn, the procedure is repeated for each polygon "crossed":


The basic check mentioned above to see if a line is valid is thus implemented in a very simple manner: check if the number of intersect points is even. For convex polygons, this is all we have to do, since each line drawn through a convex polygon will always create two other convex polygons. When dealing with concave polygons, things can get a bit harder:




To solve this problem, we should either adapt our method in order to "clip" the drawn line with the given polygon. Instead of doing so, I opted to work with convex levels only.

As a side note, you might be tempted to think that the following adaptation of the "line validity" check could work as well, i.e.: find the intersect points, and check if -- for each polygon p containing an intersect point -- that p has two intersect points (one entry and one exit). This prevents the line in the example above from being drawn (there are four intersects for the single given polygon). This also restricts the number of possibilities to splice a polygon with a given stroke (which might be the desired behavior). Still, it should be noted that this doesn't work either, since it can't be guaranteed that the two intersect indeed "enter" and "exit" the polygon in the right order:


So convex-only levels for now. If someone wants to hack in support for complex polygons (concave and/or holes): links to the code will be posted at the end.

The last thing which was added were methods to check if a level is solved correctly.To avoid that the player has to have ultra-precise eye-hand coordination, very small polygons (e.g. less than one percent of the original area of the level) created by drawn lines are disregarded when checking the areas and number of goal areas. Now that the game was playable, I converted the level which was giving me difficulties to coordinates, and started working on the genetic algorithm.

The Genetic Algorithm


To implement the  genetic algorithm, I used the "Mona Lisa"-painting genetic algorithm by Nihilogic as a starting point. This algorithm implements a simple tournament-based genetic algorithm. As said earlier, each population member can be represented as a fixed size array of points denoting the position of the lines.

Crossover is easy as well, as we can just take one half of the array defined by parent number one, and combine it with the second half of the array defined by parent number two. I say "half", but it's not necessary to split the two arrays neatly in half; the crossover point can be randomly chosen.

Mutation works similarly. When the decision is made to mutate a member of the population, each point is randomly moved to a new position.

The Result


The algorithm and Canvas/JS implementation of SliceIt! can be tested here. If you run the genetic algorithm (click "Evolve"), you'll notice that, although sometimes a valid solution is found, the algorithm has a tendency to get stuck in a local optimum (e.g. where only four of the required five lines are drawn). The reason for this is something we haven't yet talked about: the fitness function.

As with many applications of evolutionary computing, the definition of fitness function is certainly a hard task in this case. The main issue is that three variables have to be incorporated when evaluating a solution:
  • The sizes of the areas created.
  • The number of areas created. 
  • The number of valid lines drawn.

The first point is quite simple, just compute sum of the the (squared) differences between each area and the optimal target area. For example, if a level has an area size of 1000, and 10 areas have to be created, then we compute the fitness as:


Using this function alone, however, often leads to the algorithm getting stuck in local optima. Therefore, we need to punish for missing lines/areas as well. The problem is finding a function which drives the algorithm towards adding/moving a line when it is invalid, while still remaining able to "escape" local optima by making a line or the number of areas temporarily invalid.

I've tried different fitness functions, but none of them seem to be particularly efficient (feel free to modify the code in "Candidate.prototype.calcFitness", I've left the code uncompressed).

The Retry (Using the Watchmaker library)


As an extra exercise, I rewrote a very basic version of the algorithm using Java. To implement the genetic algorithm, I opted to give the excellent, thorough Watchmaker library a go.

Just for fun, I recorded a timelapse of some of my coding:



This version works a bit better, mainly since there are no "forbidden areas" and the mutation operators are a bit more fine-tuned. See the suggestions below for more ideas if you want to try this experiment yourself.

Conclusions and Suggestions


Despite fact that the result works less perfect than expected, this still was a fun weekend-project. This project was a good exercise emphasizing the importance of a good fitness function when dealing with genetic algorithms.

Working with Javascript and Canvas in this manner was also quite new for me. While I've had plenty of experience applying Javascript in a normal web/DOM context, dealing with geometry is something else entirely. Writing object oriented code in Javascript as done here was also something which required some getting used to. In hindsight, the code could have been made a lot cleaner.

Programming a project like this one is somewhat easier in Java. The Watchmaker library especially seems like an amazingly engineered piece of software; I'll certainly revisit it later.

People who want to try this project for themselves or who want to extend my code are certainly free to do so. (The Javascript version can be found  here -- just view the source of the web page. The Java version is on github.) Some suggestions:
  • Try implementing complex polygons (i.e. concave polygons or polygons with holes in a robust manner). This is something I'd like to come back to later, as the current implementation bugs me.
  • For the initial construction of the population in the genetic algorithm, several techniques can be used. The one I use here just randomly draws lines, with no regard if they're valid of not. An alternative technique could opt to only start from valid lines (by requiring that lines stay outside the given starting shapes, for example).
  • For the mutation operators, I just move the points of lines to new random locations. The Java version is a bit smarter and moves points slightly to a neighboring position. Additionally, another "mutator" (with a lower mutation chance) is added which completely creates a new solution. Try making the algorithm "smarter" in this manner.
  • The current version has no regard for symmetry, while human players will often prefer symmetric solutions. Try to find a way to determine and score this aspect.
  • Finally, try coming up with better-performing fitness functions. Just using the squared sum of differences might work, provided you leave enough freedom to search for non-local solutions (e.g. high population size, enough chance for mutations). The way crossover (offspring generation) is performed doesn't seem to matter much, given the simple solution structure.
  • Changing the population members' format could work as well, e.g. allow members to contain more lines than the goal number (n) given, but only evaluate the first valid n lines. This allows members to "carry" with them some genetic variety for more generations.
The links, once more:

Saturday, March 24, 2012

Gibbed's Mass Effect 3 Audio Extractor: "IO.Path.Combine path1 cannot be null"

To fix this, use regedit to go to

  • HKEY_LOCAL_MACHINE\\SOFTWARE\\Wow6432Node\\BioWare\\Mass Effect 3 (on 64 bit machines)
  • HKEY_LOCAL_MACHINE\\SOFTWARE\\BioWare\\Mass Effect 3 (on 32 bit machines)
Add a new registry entry (right click -> "New" -> "String Value"). Name it "Install Dir". Set the value to your installation directory (the same value as the "Path" registry entry). Close regedit. Re-open Gibbed's Mass Effect 3 Audio Extractor.