Thursday, August 28, 2014

All the LD30 games in one mosaic!

I updated my mosaic script to consider rotations of three tiles as well as straight swaps.  To be honest, its diminishing returns, but the mosaic is one of the prettiest yet:

More on the LD web site :)

Connecting Ludum Dare to the Real World

Ludum Dare is a really popular game making contest.  Three or so times a year several thousand competitors all over the world wait for the theme to be announced and the contest to start!

Last weekend was the 30th contest (LD30) and the theme was “Connected Worlds”.

The voting wasn’t even close, which is a shame as I was very lukewarm to the theme.  I feared there’d be lots of platform games where you run two levels in parallel, or can swap between levels, etc.

And that’s what 90% of games are, sadly.  I don’t mean they are bad games - many of them are really exceptionally good! - I just mean the theme lent itself to a very literal interpretation.

My interpretation was to try and connect Ludum Darers to the real world instead :)

I recalled that hidden away on the LD website was a map where LDers could record their position on a map.  It was not terribly well known, but there were several hundred player’s latitude and longitude in there.  It was enough to make sure that any map wasn’t completely empty for the first player…

So I made a ‘game’ where you report your position, and then see other contestants near you and can browse LD games on the real world map.

The game aspect is the gamification of rating LD games.  In order to discover the overall LD winner, contestants play each other’s games and rate them.  They have 3 weeks to do this, and then the standings are announced.  And I wanted to encourage that participation, as there’s really games that go unplayed and contestants that don’t play.

I scrape the LD website and, as a proxy for rating others games, I note who has commented on whom.  As well as rating games you can comment on games, and whilst these are distinct they are often done together.

So I draw the map with line art, and use a GL stencil buffer to expose an underlying map where you’ve commented on games or others have commented on your game:

image

Play it online here!  If you’re not an LD player, you can pretend to be!

The map that you expose is illustrated by me and the usual suspect, who goes by the handle Wombatica on the LD site.

I’ve been overwelmed by the popular appeal and compliments!  I hadn’t expected to get so many appreciative LDers!  I’ve been rated over 150 times already, which is many times the ratings I’ve received on previous contests.  People keep coming back, and people keep checking progress.

People are saying the nicest things too!  Here’s some of the over-the-top ones :)

  • WOW. Now that is original. Genius. I’ll be playing it for the next few weeks.
  • Hah, what an awesome idea, gamification of Ludum Dare! This it how I’m going to vote all entries from now, keeps voting fun! 
  • Thumbs up for innovation/originality!
  • super awesome idea, have all my stars!
  • Now the fourth wall have been shattered.  thank you.
  • Will - really, really good job… This should win I think, just for the sheer cheek of subverting the idea and pointing LD at itself, can see this becoming a favourite interface for LD in the future… very great !
  • You made playing games a game, that’s a 5 stars on innovation, no doubt. Also, connecting the LD world with the real world… Another 5 stars for theme!
  • Man. This is SO neat! This game wins like all of the LDs. Amazing job!
  • I gave you an award on your profile for this game.
  • Oh my god this is briljant!

Oh there’s more.  Lots more :)  Now excuse me while I float off ecstatically tired…

Thursday, August 21, 2014

The average of all photos is … Emergent Orange!

A long time ago, when the internet was young, Jim Bumgardner (a.k.a. KrazyDad) discovered that, if you average the pixels in enough images you find on the internet, the resultant picture is always much the same colour… and that colour is Orange!  Emergent orange, as its now called.

Of course when I heard about this yesterday I had to put it to the test!

My script is here, and here’s some results:

  • first up, as a test, I checked my code produced the input image when run on a single image
  • second, here is the script when run on a folder of photos from a recent regatta, so lots of boats.  This looks like you’d expect too:

image

  • and here’s the average of my Ludum Dare folder; there’s lots of screenshots and title screens from people’s games in there (remember the beautiful image mosaics I was making from them?):

image

Now that’s a bit more orange!  A bit, anyway :)

From this image, the average of all Ludum Dare screen shots, we can infer that the average Ludum Dare contestant uses Windows 7!

(Don’t worry, we still respect them/you!)

Try it yourself!  If you have time before you enter this weekend’s Ludum Dare contest, that is…

Thursday, August 14, 2014

Python annotations and type checking

Someone got at Guido!  He comes back from some talk with the idea of blessing mypy type checking annotations in Python!

Now those following along may recall my own type-checking library obiwan that also uses annotations.  Its on pypi so you can use it already today!  What are you waiting for?

I’m keen on static checkers, although I prefer static type inference and have ideas along those lines such as Static Single Type Assignment (SSTA).

Fundamentally, though, restricted Python isn’t Python.  We want a dynamic language, and this hits on the limits of static checking.  Obiwan’s runtime checking is a compliment to a static checker and its ability to check external data e.g. tainted JSON input from an API is a major plus too.

What we want is for static checkers, auto-completion in IDEs and runtime checkers like obiwan to all use the same syntax and conventions.

But I don’t like the mypy syntax; its baroque and it even overloads comments (yuck!).  I much prefer obiwan’s style and would like annotations to be supported in-block as well as on the boundaries i.e. declarations.

Consider this mypy example:

  from typing import List, Dict

  def word_count(input: List[str]) -> Dict[str, int]:
      ...

Obiwan would instead say:

  def word_count(input: [str]) -> {str, int}:
      ...

Which I consider far clearer and pythonic.

My reply to the list is here.

FWIW, I don’t imagine anything will come from this.  There is unlikely to be consensus, and although I’d like a solid PEP that puts annotations into blocks it would so risk slowing down programs that I think it unlikely to be adopted.  So we may be left with a clear message that people are to use mypy or whatever, but no actual solid move forwards.

Friday, June 27, 2014

Devoxx4Kids Inspiration!!

Roy van Rijn makes the really really great Devoxx and Devoxx4Kids videos.  Really really upbeat and inspiring!

Next time, send your kids too!

Thursday, June 26, 2014

Lots of programmers make nests.

When you’re working alone on something, its very tempting to make a whole library of code to support yourself programming something.. to put off solving real problems and so on ;)

Here’s an example I read today of over-engining sprite sheets (been there, done that myself!)  That game looks absolutely stunningly awesome, of course!

But here’s a game engine I’ll call out as having potential: image

IceEntity by NicoM1; check it out!  A nest you might be comfortable sitting in yourself?

Seems from these links that I’m all nostalgic for a minimalist artsy XKCD-inspired platform puzzle adventure game… maybe an idea for LD30 August 22-25th 2014?

Wednesday, June 4, 2014

An Impartial Press

Well we all hear reports (on the BBC) about how the separatists in Ukraine are fed a distorted pro-Russian media diet… but generally the BBC tries to be objective.  However, this choice of “stock photo” jumped out at me:

Yes we know its just vapour, but I think we’re in the minority… the overall spin this picture gives the story for the general reader is rather different?

See also: Salami Tactics

Tuesday, June 3, 2014

Compressing Scrabble Dictionaries

The newest rec.math Al Zimmermann Programming Contest is a solitaire Scrabble puzzle called ‘Alphabet City’.

Wait, what do you mean you’re not entering that programming contest??  Its a really really nice clean problem and it’s addictive as 2048!

To lookup scrabble words quickly, people use a GADDAG.  The GADDAG is a tree data-structure.  Each node represents a character, and has pointers to all the child nodes that continue all possible words.

The key thing is that every rotation of each word is stored in the GADDAG.  To have a GADDAG of the words ALL, BALL and CALL, for each word we add all rotations.  This is LLA@, LA@L, A@LL for ALL, and LLAB@, LAB@L, AB@LL, B@ALL for BALL and so on.  (@ is my choice of ‘start-of-word’ marker; its a good choice because in ASCII its the character before A.  When you have arrays of child nodes [A..Z], this can easily be extended to have a slot pointing at the start-of-word node [@..Z].  And it looks nice enough in the graphs too.)

To speed up Scrabble searches, the prefix of each word is stored reversed which facilitates ‘hook’ searches.  To search for all words with one letter then A then another empty then L (?A?L), you start with the first known letter - A - and look for all those with one character in front (a child with a @ child), terminated by an L.

A naive sparse implementation of a GADDAG takes absolutely loads of memory: over a GB is not startling.  Almost all those nodes will be duplicates of other parts of the tree and almost all possible children will exist.  So we really want to get the memory usage down if we want to avoid our program waiting on main memory all the time: bottom cache is typically in the tens of nanoseconds away, whereas main memory is around a hundred nanoseconds away.  Getting the GADDAG small enough to fit into cache, even the bottom level cache (as in slowest and biggest), can mean an order of magnitude speedup!  So its well worth compressing your GADDAG.

The original paper describes compression and gives an example of partial compression.  I will talk these through with graphs:

image

Here’s the uncompressed tree.  Sorry it takes so much screen space .. it has a lot of nodes in it, which is a point I want to make :)

3 words, 11 rotations and 27 nodes.

Lets start compressing it:

The first thing to note is that, unlike the ALL, BALL, CALL example on NullWords blog, I am storing the terminating characters (the blue nodes) in a separate set off the node.  This is how the prefix LLA is followed by a single node with both B and C in it.

Read More

Thursday, May 22, 2014

pycon 2014 Sweden: the bad bits

I’m just back from pycon 2014 Sweden.

And all the tweets and commentary will be positive, as they always are. If you want to say something negative its best to not say it at all?

Hmm, not me.  Someone has to give this feedback; we can’t sweep it under the carpet.

Read More

Friday, May 2, 2014

Making Image Mosaics

imageAs followers of the blog know (thx for the mails!), I’ve been making mosaics of Ludum Dare contest entries.  It started basic, and its got better.  Each of the ‘pixels’ in the Mona Lisa is actually a screenshot of a game!  Here’s how:

We have an target image, for example the Mona Lisa, and we have some large number of small input images which we want to arrange so that, when squinted at from a distance, it approximates the target image.

Read More

Wednesday, April 30, 2014

UPDATE: blog post describing how these mosaics are made

I knew my mosaic script was doing a poor job of placing the images.

The approach it’d be taking was greedy: it’d place the closest matching image on its tile, and then the next closest matching and so on.  The outcome in in the middle column above.

After talking a bit with Roy, I couldn’t really leave it doing such a poor job.

So in what way is the greedy approach sub-optimal?  It may be that swapping two images or three or more images around will lead to a lower overall error score.

And what’s the simplest improvement to make?  Rather than tackling the true dynamic programming or other classic approach to optimisation, I simply went for random swaps.

The script will now perform random swaps if they improve the image, until you interrupt it with ^C.

And the results, as seen in the left column above, are stunning :)

Tuesday, April 29, 2014

The mosaic is made (sourcecode) from the screenshots from Ludum Dare 29, to the theme “Beneath the Surface”.  The green turtle is from wikipedia.

Monday, April 7, 2014

I’m giving a Mill CPU talk in Växjö, Sweden 2014-04-25

There are perhaps a few seats available to interested members of the public if you’re in or near Växjö at the end of the month :)

Announcing a presentation at 13.00h, Friday, April 25 at: 

Linnéuniversitetet (Linnaeus University) 
Vejdes Plats 6, Linnéuniversitetet 
Building B, Room 3021 
352 52 Växjö Sweden 

The new Mill CPU architecture 

A presentation by Will Edwards (Mill Computing) 

The new Mill CPU architecture brings DSP-like efficiency and performance to general purpose computing. Offering a 10x power/performance gain over conventional out-of-order superscalar architectures, the Mill family of CPUs scales from phones to supercomputers. 

The Mill is an extremely wide-issue VLIW design, able to issue up to 33 operations per cycle. The Mill is inherently a vector machine and can vectorize and pipeline almost all loops. The Mill is a belt machine (as distinct from a stack or register machine) and has a fine grained 
security model that facilitates microkernels without performance penalties. 

This talk will give a high-level introduction to the Mill programming model, with an opportunity for the audience to ask more detailed 
questions in areas of interest.

Tuesday, March 25, 2014 Wednesday, March 12, 2014

Russia’s Salami Tactics in Crimea

Well worth a re-watch all the way through :)