One of my favourite things about Clojure, is constantly discovering
new, and usually shorter ways of re-writing code. An example I
discovered today has to do with maintaining a particular ordering in
a map. When creating html lists using hiccup one needs to make sure
the columns of the table all line up. This can be difficult when
using a map since the ordering of a map is not defined.
Fear no longer, today I discovered sorted-map-by. This creates a
map which maintains an order as defined by a comparator. So here is the easy way I came up with to keep a map in a
Reducers - Rich Hickey
I saved the best for last. This is the best talk I have watched in
awhile. Rich does a great job of walking through reducers and
explaining why they are important. I keep meaning to download the
Clojure 1.5 beta and try these out for myself. In the Clojure
programming that I have done it seems that the majority of maps and
filters are not order dependent and therefore could greatly benefit
from the use of reducers.
I recently attended an undergraduate thesis presentation where one of
me to thinking, what would a Clojure game engine look like. I have
played around with other Java gaming engines, such as
Slick. Slick is a really easy engine
to work with and lets you immediately focus on developing the game, not
contorting the engine to work for your game. Since Slick is so great,
why not just write a Clojure wrapper for it? The problem rests in
Slick’s heavy dependence on the OOP paradigm. A wrapper would end up
causing the programmer to “fight” Clojure at every turn as we sneak
objects and, even worse, mutability into the engine. My goal is to have a
game engine which embraces the ideals of Clojure.
The design which I have been building in my head is an entity-oriented
engine (which I wrote about in a previous
post). A world
reference will be a bag for all the entities in the game. Entities
would only contain their state, and their categorizations. For example
you could have a player entity, and also have an entity for each
projectile currently alive in the game. An interesting idea would be
to make each processor of entities a different thread. This would
impose the problem of not being able to deterministically order their
execution, but the idea of creating a game based on independent
modules seems intriguing. My goal is to create a highly concurrent
gaming engine. A cool resource to check out is Rich Hickey’s famous
ant demo which was used to demo
Clojure’s concurrency in the early days of the language. It is pretty mind blowing how much simulation
is packed into so little code (the whole thing is 300 lines, with
comments and license).
The rendering and world updating will be done by two (maybe more)
agents. Clojure’s wonderful STM will trivially (maybe easy is the
better terminology :)) allow these tasks to be
independent. I haven’t yet chosen what the renderer is going to be
yet, but this will be a 2D engine, so for the minimal amount of effort
it will probably end up being the
Light Weight Java Game Library, which Slick
uses underneath. The unfortunate part of this is that LWJGL requires
the use of native libraries. An alternative option would be to also
include Swing support, thus making the engine support cross platforms easily. I will
have to research to see if the Canvas in Swing is performant enough.
This is all just thought development now, but I have the whole summer
ahead of me. Maybe this will make a good project :)
Updated: made a mistake in the random algorithm… left out the random part :) all fixed now and the chart has been updated
Last week we were going over some median finding algorithms in class. To be honest I had never thought of this problem before. In class (before the algorithms were revealed to us) I jumped to the naive approach of sorting the list then grabbing the middle. This is obviously going to have the complexity of sorting, with best case O(nlogn).
We were presented with two algorithms, one random (selection by partitioning) and the other deterministic (median of medians). Both end up averaging a complexity of n, but the random algorithm has a worst case of O(n2). The funny thing is that the random algorithm massively outperforms the deterministic version. This is always an iterating situation, when the theoretically better solution ends up performing (when implemented) far worse than the theoretically worse solution.
Lets see how much worse the deterministic algorithm performs. I created an implementation of both algorithms:
Conveniently both algorithms have the same core, and the only difference between them is how they determine their pivot value. As the name suggests in the random algorithm, the pivot is chosen at random. In the deterministic version, the pivot is chosen to be the median of medians. Finding the median of medians is interesting as the recursions are intertwined, the median finding algorithm is called by the median finding function.
There are also some laziness optimizations sneaking in here as well. In the core, only the “less than” partition is fully realized. The “greater than” partition is only calculated when required, which is only when the median exists within.
Alright, so now I got to take my first attempt at using Incanter, the R-type library for Clojure. Incanter was really easy to use and I found the documentation to be very verbose (in a good way) and well written.
This is the analysis code I whipped up:
Which I used to produce the following chart:
Due to some strange “features” in Incanter, you have to jump through some hoops to get the groups to label correctly, so I left the legend off the chart. The blue points are the deterministic algorithm’s results and the red points are the random algorithm’s results. As you can clearly see from the graph, the random algorithm outperformed the deterministic one by at least one metric bunch.
A few friends and I have undertaken a game project, and I get to be in charge of the technical side of things. I immediately thought of using Clojure (since it is only the best language ever), but changed my mind as my main criteria was a easy to use game engine (I’m lazy). I ended up choosing to use the Slick engine which is java-based. To supplement this Slick engine I have decided to use an entity based approach to programming the game. Artemis is an entity framework which was originally designed for use with Slick, but since it has no dependencies, could be used with anything.
The Artemis framework is based on a series of blog posts from T=Machine. The TL;DR of these blog posts is that an entity system in a gaming environment is very extensible and can be parallelised (the articles revolve around PS3 development, which needs done concurrently to take advantage of the hardware). Whilst I don’t have any immediate needs to delve into concurrent game development, this approach has a real functional smell to it (reminiscent to that of fresh baked bread), so it must be a good thing.
Well, I haven’t been doing much in the way of coding over the last couple weeks, but today that changed. I came across Tom Bell’s ruby implementation of a trollscript interpreter, and figured that the clojure community needs an interpreter too. A couple hours later and I had whipped up my first version of a trollscript interpreter.
Now that TodoClj is done (unless I come up with some new features), it is time for a new project. A while ago a friend and I started messing around with the game of Go.
It quickly became apparent that there are no good Go clients out there. The ones that do exist are extremely old, and either do not run on modern hardware, or are almost completely unusable. So the first step in creating a bearable Go client is to make an easy to use wrapper for the gnuGo client. By interfacing with gnuGo, one gets all the rule enforcement and AI for free.
I have decided to name my wrapper after one of the first (founded in 1612) Go houses in Japan, Honinbo. This should be a good chance for me to practice some meta-programming as the interface with gnuGo will take place using the Go Text Protocol (GTP).
I have finished the first version of TodoClj. Please check it out. Note that I have put almost no error checking into the parser, therefore things will crash if not perfect. Windows users should compile from source (to get version 1.0.1) since the ANSI codes used to colour the output do not render and the new version prevents colour from being rendered when run on Windows. If you have lein installed compiling is as easy as: