tag:blogger.com,1999:blog-52769588846764246442024-03-19T10:01:58.223+01:00Slow FrogI'm slow, I'm French, I solve and program games in my free timeLaurent Vaucherhttp://www.blogger.com/profile/13286811917069686050noreply@blogger.comBlogger23125tag:blogger.com,1999:blog-5276958884676424644.post-57284305471615107662013-05-13T00:24:00.001+02:002013-05-13T00:24:39.691+02:00Celebrating my job changeI've been quiet for a few months. I completely lost any hope of participating in the "One Game A Month" challenge. But I've not been inactive professionnally. I've found a new job. I'll have to move to Paris in a few weeks. And to celebrate the switch, I wrote my first interactive doodle (I won't really call it a game). Enjoy it at <a href="http://www.slowfrog.com/goodbye/index.html">http://www.slowfrog.com/goodbye/index.html</a><br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjAG0a_LNSD7etPLF4S9AK1HBPrFBDqbcDtkQdvNZqYyZrfMKhpJ8PuqK1gJdeuVLuhM_1kIyVb4LTd0uwo0bl6qmTafv5S08-lW8mTWJhTYcDR_BErD-uID1HfG86KJFQIctv6-cJCHFLd/s1600/jobslots.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img alt="Job Slots" border="0" height="194" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjAG0a_LNSD7etPLF4S9AK1HBPrFBDqbcDtkQdvNZqYyZrfMKhpJ8PuqK1gJdeuVLuhM_1kIyVb4LTd0uwo0bl6qmTafv5S08-lW8mTWJhTYcDR_BErD-uID1HfG86KJFQIctv6-cJCHFLd/s320/jobslots.png" title="Job Slots" width="320" /></a></div>
<br />Laurent Vaucherhttp://www.blogger.com/profile/13286811917069686050noreply@blogger.com0tag:blogger.com,1999:blog-5276958884676424644.post-5907870729076244002012-12-17T23:06:00.000+01:002012-12-17T23:06:40.556+01:00New 2013 Madness: One Game A Month That's it. I caught the game jam bug.<br />
<br />
Not the acute, 48h, Ludum Dare variety. More like the chronic, one month strain.<br />
<br />
It all started with the story of a guy called <a href="https://twitter.com/McFunkypants" target="_blank">@McFunkypants</a>. In 2012 he set up as a personnal <a href="http://www.mcfunkypants.com/2012/quest/" target="_blank">quest</a>, among others, to code 12 games over 12 months. He <a href="http://www.mcfunkypants.com/2012/12-games-in-12-months/" target="_blank">succeeded</a> and challenged everybody to do the same in 2013. So he set up the <a href="http://onegameamonth.com/" target="_blank">OneGameAMonth</a> website, to provide a public platform to record progress. There are no prizes, mostly no rules, except the main one: write one game each month of 2013. A system of experience points (XP) has been tacked upon it, to <i>gamify</i> the making of games.<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://onegameamonth.com/logo.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="33" src="http://onegameamonth.com/logo.png" width="320" /></a></div>
<br />
<br />
And I signed up.<br />
<br />
What was I thinking? Oh yes, I know. I'm still trying to generate some external pressure to help me gather motivation and momentum. It worked fairly well for the two game jams I did this year (Liberated Pixel Cup and GitHub Game Off 2012). I think it's more because of the peer pressure of the group of people who joined me than because of the eyes of all other internauts. Real people made of blood and flesh that I see daily have more impact than virtual people made of bits and bytes. I don't know if it means I'm normal or if it means I'm old-fashioned.<br />
<br />
<h2>
The Plan</h2>
<div>
So now I have to come up with a plan for 2013. Maybe not an extremely detailed overarching plan for all of 2013, but at least a sketch, a bunch of directions.</div>
<div>
<br /></div>
<div>
<ol>
<li>I need to get more disciplined if I want to achieve the goal. Build up a routine, probably, to avoid making excuses.</li>
<li>I'll revive and explore further the "tree-growing" concept that we abandoned for game-off-2012. It's already got its own GitHub repository and the proof-of-concept is live at <a href="http://slowfrog.github.com/branch-off/">http://slowfrog.github.com/branch-off/</a>. I need to work on core game mechanics, to make sure they are viable. And I want to explore some rendering options. As a first step, I already added a drifting, procedurally generated cloud in the background.</li>
<li>In case I lack inspiration one month, I can expand on <a href="http://gamefrogs.github.com/game-off-2012/dominotrail/index.html" target="_blank">Domino Trail</a>. There were several features that we had in mind at start and did not implement (edge-walls, cells with different speeds, new pieces with special behaviour).</li>
<li>I resorted to <a href="http://videogamena.me/">http://videogamena.me/</a> to help me generate ideas. It's really fun. It's less prescriptive than game idea generators, because it only produces a name. And that's the nice point: you have to put your imagination to work to devise a game that would fit the name. I've had very good runs of the generator and will only reveal one title that could be the hit of 2013: "French Bubblegum Castle." You've been warned. </li>
</ol>
<div>
Here I come, 2013!</div>
</div>
Laurent Vaucherhttp://www.blogger.com/profile/13286811917069686050noreply@blogger.com1tag:blogger.com,1999:blog-5276958884676424644.post-25265477934189924582012-12-03T22:44:00.000+01:002012-12-03T22:44:04.067+01:00Another season, another game programming contest Just when I thought I could relax, waiting for the results of the <a href="http://lpc.opengameart.org/">Liberated Pixel Cup</a> (not really thinking about winning, but hoping at least to have a decent score), here comes GitHub with a context of its own: <a href="https://github.com/github/game-off-2012">Game-Off 2012</a>. One month to come up with a game that should be web-playable and loosely based on git concepts: branches, clones, forks, pushes and pulls. What was I supposed to do? Well, of course, participate.<br />
<br />
I thought about some concepts on my own. The first idea was to go all out on the theme, with an action platformer where you would run and jump on branches, pushing and pulling clones with forks. Nothing really original for gameplay. My second idea was to play the <i>French touch</i> by using French words that sound close to the theme: <i>poule</i> (chicken) for pull, <i>phoque</i> (seal, the animal) for fork, <i>clown</i> for clone. I did not venture further. I'm not sure I want to imagine what a game with clowns, chickens and seals would be. My third idea was to make a puzzle game. They are generally easier to make than real-time action games, and it's possible to end up with something acceptable, even without a real artist: you can always go the "abstract" way. The first puzzle idea was about a tree that you have to grow somehow, using actions like "fork" to add branches, "push" to bend them and cut to stop them growing. I even started a <a href="http://gamefrogs.github.com/game-off-2012/branchoff/index.html">proof of concept</a>, to see if it had any potential. Since GitHub required the game to be web-playable, I settled for HTML and JavaScript. Let's even say HTML5, for buzzword compliance, because it uses the fantastic <canvas> element.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="http://gamefrogs.github.com/game-off-2012/branchoff/thumbnail.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="http://gamefrogs.github.com/game-off-2012/branchoff/thumbnail.png" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Orphaned tree game concept</td></tr>
</tbody></table>
<br />
At about that time, I asked for volunteers among my coworkers to help me. I met with two of them, and after our first brainstorming session, the tree growing concept was abandoned. We could not see clearly enough what the goal could be or how to make the game challenging. I thought the goal could be to fill a predefined shape with a set of available actions, but I was afraid all levels would end up being too easy to solve. Being short on time, we focused instead on a domino game, for which the goals and constraints were easier to imagine. In each level, you would have starting points, goals to reach and an assorted set of pieces to make a path from start to goal. Oh, and the board would use hexagons, not squares, to give it an original touch.<br />
<br />
At that point, there were three and a half weeks left. I had already set up the "infrastructure" (github repo, Google Group) so we started coding, slowly, on the low-level parts: how to handle hexagons and their coordinates, how to draw them, how to match a mouse position to an hexagon. Nothing technically hard. The only problem is that it is difficult for several people to start coding from scratch simultaneously. Even more so when the other guys are not so fluent with JavaScript. Anyway, I did most of the initial coding, and we had one formal work meeting every Tuesday to share ideas and build momentum for the next week. As you can see on the graph below, representing the number of commits for the last seven weeks, momentum took some time to build, but when we stopped, we had quite a lot.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgh5QjeeUoRWq_pMwy3kAURV3NrXBPk8pHKkmgWWetK1mJNOR5ILHGK_7A8Ug39jTL4n9A75QglQL1pS99PManiVZv_345jvcpfUUdyJvwRQkNDvVCoVoZqzZHCWMunFoWSgQ_Wpv3pzdDJ/s1600/DominoTrailCommitHistory.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgh5QjeeUoRWq_pMwy3kAURV3NrXBPk8pHKkmgWWetK1mJNOR5ILHGK_7A8Ug39jTL4n9A75QglQL1pS99PManiVZv_345jvcpfUUdyJvwRQkNDvVCoVoZqzZHCWMunFoWSgQ_Wpv3pzdDJ/s1600/DominoTrailCommitHistory.png" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Project commit history</td></tr>
</tbody></table>
<br />
The idea we had, to be able to share a bit of the workload, was to make pieces and levels as independent and pluggable as possible. I refactored a big part of the code to allow that, and one of my coworker coded some of the missing pieces, the ones that fork the path. I also coded the basic UI allowing to select pieces and to put them on the board. From that, it was quite easy to make a basic level editor. The other guy was then able to completely rewrite the drawing code, replacing my ugly looking black and white rectangles that were supposed to be dominos, by a more abstract look that was more pleasant and easier to animate. We thought about making 3D models and realistic domino renderings in Blender, but had to ditch it, by lack of time and competency.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td><a href="https://raw.github.com/gamefrogs/game-off-2012/master/ScreenShot.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="247" src="https://raw.github.com/gamefrogs/game-off-2012/master/ScreenShot.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="font-size: 10px;">The last tutorial level</td></tr>
</tbody></table>
<div style="text-align: left;">
<br /></div>
</td></tr>
</tbody></table>
One week before the deadline, we had all the low-level mechanics and pieces we needed, but we had not yet produced a single level, and the global look was not very engaging. That's what we focused on in that last sprint. I wrote nine entry level tutorials, with texts explaining all the mechanics and each one of us tried to design about seven levels to reach about thirty. We got exactly there: 30 levels + 1 level editor.<br />
We enrolled a few more coworkers for beta-testing and mobile platform testing. I coded some important stuff on the last two days (level locking and in-place rotation and delete) in response to our limited user tests. My team mates worked hard the very last days to find or draw pleasing images and icons, and the game was finally ready. <div>
<br /></div>
<div>
You can <a href="http://gamefrogs.github.com/game-off-2012/dominotrail/" target="_blank"><span style="font-size: x-large;">play it</span></a> on GitHub. And you can browse the source <a href="https://github.com/gamefrogs/game-off-2012" target="_blank">also on GitHub.</a><div>
<div>
<br /></div>
<div>
For those of you who like numbers (like me), the game contains 3.500 lines of JavaScript code (blank and comment lines excluded), which is about a third of my port of Desktop Dungeons. </div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><span style="margin-left: auto; margin-right: auto;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgCgVccGBwIKRU1F_0kWIu-awmnwdPJ1vci3i0B1XGcq054MQziElOhHxyJ5cxzp47yJOAQQjKSBuMS_QiyX82jLiRiel05PwNb0HZCNZZ6zNNqz7C9jRuBMW1Qv8UmuymR_i_pfDaLt7Tr/s1600/DominoTrailSplash.png" /></span></td></tr>
<tr><td class="tr-caption" style="text-align: center;">The glorious splash screen, committed during the last 24 hours</td></tr>
</tbody></table>
<div>
<div>
<span style="font-size: large;"><br /></span></div>
<div>
<span style="font-size: x-large;">Lessons learned</span></div>
<div>
<span style="font-size: large;"><br /></span></div>
<div>
Doing a game jam is nice, doing it with other people is nicer still, at least in a small team. Different opinions can combine to produce things that would not have been possible alone. And being a small team, we could avoid the "design by committee" pitfalls.</div>
<div>
JavaScript is really cool for short prototype-y projects like this one. And apart from Opera that has poor canvas rendering performance, the game works very well on all desktop and mobile browsers.</div>
<div>
Doing HTML5 makes it easy to target mobile platforms, but their specificity regarding screen size and input methods must be taken into account to produce a good experience. We'll try to find hardware for tests sooner in the project next time. Hopefully, we'll win an iPad from GitHub, and the problem will be solved.</div>
<div>
<br /></div>
</div>
</div>
</div>
Laurent Vaucherhttp://www.blogger.com/profile/13286811917069686050noreply@blogger.com0tag:blogger.com,1999:blog-5276958884676424644.post-5104555580284193682012-08-02T22:02:00.001+02:002012-08-02T22:14:44.825+02:00Chickenpix!<h2>
Long time, no post</h2>
<br />
I don't think anybody is really following this blog (except some of my most curious colleagues), but let's pretend for a second that I have an audience. I did not post anything for the last six months, mainly because I had nothing technical I considered worth sharing and I do not want this blog to become a diary of my breakfasts or other useless stuff. I does not mean I did nothing: just that the things I did were too small for me to talk about.<br />
<br />
For instance, I picked up <a href="http://www.puzzle-nurikabe.com/" target="_blank">nurikabe</a>. This is a puzzle game in the vein of sudoku, with rules that are, at first, a bit difficult to understand, but lead to an intersting way to waste one's time. There are parts that make it look like minesweeper (there are numbers that represent a count of something you have to find), others are more akin to the game of go (the black "stream" must be in one piece, so that you have to escape atari). It's nice to play "manually". And of course I wrote a solver, because that's what I do. But nothing exceptionnal to show: only a few heuristics bound with a brutish force search.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjifMavcVHzVqnzMwcOYz8WQYtpAOTrKNuet-_iq1RYYFtfefXVNNdSFz47K4lIwJ57BAaWfrqrHbnhK-FLdBSdmSWuIMSaRHcJp072FDPzjR1Rtz5sTqoYtimYfBGw0HXryMAOEmzLLFOH/s1600/nurikabe.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="191" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjifMavcVHzVqnzMwcOYz8WQYtpAOTrKNuet-_iq1RYYFtfefXVNNdSFz47K4lIwJ57BAaWfrqrHbnhK-FLdBSdmSWuIMSaRHcJp072FDPzjR1Rtz5sTqoYtimYfBGw0HXryMAOEmzLLFOH/s200/nurikabe.png" width="200" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Game of nurikabe in progress</td></tr>
</tbody></table>
<br />
At one point, I tried to switch views, and wondered how the site I referenced above could generate all those puzzles. I probably did not spend enough time on that task, and have not come to a working model of how to do that. Nothing to show again.<br />
<br />
I worked a bit on my other HTML5 game (a simple tower defense revolving around programmers and the SCRUM methodology, if you want to know). But I did not make enough progress to show it.<br />
<br />
<h2>
And then...</h2>
<br />
I spotted in the news that the <a href="http://opengameart.org/">OpenGameArt</a> site was hosting an art & game programming contest during the summer, with open source and free software sponsors (the FSF, Mozilla, Creative Commons). I thought it would be interesting, and I asked a few colleagues if they wanted to participate, to help create team motivation. And so, during the last two months, I spent all my spare time working on that project. We started with a team of about eight people, but we ended up being only two to push any code. I think we did not really succeed in creating enough momentum, and the end result is not really a game, just a technical prototype of what the game could have been. It's called <a href="https://github.com/slowfrog/chickenpix">Chickenpix</a> (hence the title of this post).<br />
<br />
At first, since most potential coders were fluent in C++, we decided to choose that language over JavaScript. Then we looked for a portable and open source low-level libary that could fit our needs. We kept two of them, <a href="http://www.clanlib.org/">ClanLib</a> and <a href="http://www.sfml-dev.org/">SFML</a>. Why didn't we stick with only one? It would have been simpler, but my fellow coder worked on OSX and he could not make ClanLib work on his machine. And on the other side, I worked mainly on Linux in a VirtualBox VM, and SFML was awfully slow when rendering. I also wanted to make a Windows build, but with Visual Studio Express 2010, SFML was a nightmare to link, and I eventually gave up.<br />
<br />
For the architecture, I wanted to experiment with the entity-component-system approach. Each game object (entity) is effectively nothing more than a container of components. Those components, in turn, are generally simple data structures containing state information. All the logic is then performed by the systems that are present. Any entity can contain any kind of components, and they can be added and removed dynamically.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjo5WQ9vXk5GvZRtG5_iXvBj5sUf1uFqxHkilrZ4-Rzkvqy_NywmXwfhHI9pPSagRChUWPr193pk6Wg6-lmsskncGRH95w2cKvnj_e-1IucRzY9wd1Y0XUmXnECG1dS3FCvgIo5Rh9V4UHc/s1600/chickenpix.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="249" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjo5WQ9vXk5GvZRtG5_iXvBj5sUf1uFqxHkilrZ4-Rzkvqy_NywmXwfhHI9pPSagRChUWPr193pk6Wg6-lmsskncGRH95w2cKvnj_e-1IucRzY9wd1Y0XUmXnECG1dS3FCvgIo5Rh9V4UHc/s320/chickenpix.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">The whole cast of characters</td></tr>
</tbody></table>
<br />
For instance, in chickenpix we have a dozen components, among which a Transform component holding the current position, a Mobile component for things that move, a Visual component for entities that need to be shown, and also Animated, Input, Audio, Camera, Scriptable, Collider. On the systems side, there is a Render system, that collects all entities with a Visual component, finds the Camera and displays everything accoding to their Transform. There is a Movement system that does the "physics" simulation, an Inputs system that gathers user input (keyboard and mouse) and calls contollers, a Scripting system that executes scripts.<br />
<br />
Talking of scripting, we quickly evaluated the usual open-source possibilities for embedding: JavaScript with V8, lua with luajit and Python. V8 was rejected because we could not find a binary release, we could not make it build on Windows and we simply did not persevere. lua was deemed too "low-level" and unknown to almost all participants. I was all for Python and some other people knew it a little, but I had never embedded it. It ended up easy enough, once the reference count scheme was understood.<br />
<br />
Technically, that's about all there is too say. And on the game design side, well... there was not really any time left for that.<br />
<br />
<h2>
Lessons learned</h2>
<br />
Working with other mildly motivated people, on a short schedule, in the middle of Summer is not the best way to build momentum. The human factor trumps the technical ones.<br />
<br />
C++ is not as bad as I anticipated. Mind you, I already knew C++, but it had been a long time since I did anything more than a toy program with it. I was afraid of manual memory management and the associated problems. Lots of logging and some gdb sessions to pinpoint the cause of segfaults was enough to cure those.<br />
<br />
Developing on the three main desktop platforms in parallel is not too hard, especially when each coder has a different preference and handles his platform himself. I have no other data point to really compare it to porting only after the first working version is done. I suspect there is a slight advantage with the multi-platform approach because the versions never have the possibility to diverge.<br />
<br />
Supporting several low-level libraries was not too difficult and probably had a good effect on the architecture of the code. It forced us to think on a higher level and to provide adequate interfaces.<br />
<br />
Entity-Component-System is interesting and has some good properties. But as all good things in life, you have to learn not to abuse it. Having the resource loading facility be a component of a <i>fake</i> entity seems like a hack, in retrospect. And having to switch between several modes of play led us to design transitions between distinct entity managers. I'm not sure it's the best way to do it.<br />
<br />
We're not going to compete with Unity just yet.<br />
<br />
Embedding Python for scripting is cool. The C API is easy enough to master and very well documented. No need to stress the benefit of scripting for games in general: it transforms part of the logic into "data" and data-driven programs are simply better (easier to test and reason about, no need to recompile for every change...)<br />
<br />
Working in a virtual machine is kind of nice (you can switch physical machines by just moving the image) but there are still limitations when developing a game. Graphics hardware acceleration does not seem to work out of the box just yet.<br />
<br />
<a href="http://www.google.com/webfonts/">Google webfonts</a> is a great resource for free (as in freedom) fonts, not limited to the web.<br />
<br />
github provides excellent tools for collaboration, that I had not yet tried when working alone: wiki, web pages, issue list, downloads. The code statistics and graphs are nice, but they give strange results sometimes (we did not code a single line of Objective-C!).<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhgV6qsoPH5OHJzFV82wMmZ9urIKfROW6lFzuG6M_rCsjuu2EHlz4hTX0c_cQs6RXlfTOCai_2rH-mDuZD59cgbR0Ql47kb9hhqtjVjYgSLgo_P5BFwz7OEzLjZ8M3uNWHc4aYVi4hKuMn7/s1600/lpc.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="161" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhgV6qsoPH5OHJzFV82wMmZ9urIKfROW6lFzuG6M_rCsjuu2EHlz4hTX0c_cQs6RXlfTOCai_2rH-mDuZD59cgbR0Ql47kb9hhqtjVjYgSLgo_P5BFwz7OEzLjZ8M3uNWHc4aYVi4hKuMn7/s320/lpc.png" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
To all other LPC participants: good luck! Chickenpix has been a nice experience, but the final game will not be an obstacle on your way to victory :)<br />
<br />
<br />Laurent Vaucherhttp://www.blogger.com/profile/13286811917069686050noreply@blogger.com1tag:blogger.com,1999:blog-5276958884676424644.post-1576240666674286582012-02-22T23:34:00.002+01:002012-02-22T23:43:14.435+01:00Hexiom, constraints and librariesAfter my own forays into constraints programming, I received a comment by Pierre Schaus who <a href="https://bitbucket.org/pschaus/scampi/src/51fc9203fb6f/src/main/scala/scampi/cp/examples/Hexiom.scala" target="_blank">solved the problem</a> with his own Scala CP library. The solution is very elegant, and once the boilerplate code is removed (file parsing...), is very short and to the point. The constraints are expressed very clearly using a kind of DSL that is made possible by Scala's flexible syntax. Really enlightening!<br />
<div>
<br />
<div>
This prodded me into looking at what were the available options in my preferred languages. I have learned a lot (but still have a long way to go) and I found two open-source libraries that are very powerful and quite performant, one for Java and the other for C++.<br />
<div>
<br /></div>
<div class="" style="clear: both; text-align: left;">
<span style="font-size: x-large;">JaCoP: Java Constraint Programming</span></div>
<div class="" style="clear: both; text-align: left;">
<span style="font-size: x-large;"><br /></span></div>
<div class="" style="clear: both; text-align: left;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhtDT5X_5yGRZrtZm6BFhv-lmiyYHKOD-4j7dD4W6_g-PQkaA06-jZcfo3IHJWB2caGgi18OEqDBFYiHKpAHqpWADdCu3LPHkkWO_S0NGWZglgyuvnOA2tNKFXgRKNvkOAyW93fc9WczyvL/s1600/mw_jacop.gif" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhtDT5X_5yGRZrtZm6BFhv-lmiyYHKOD-4j7dD4W6_g-PQkaA06-jZcfo3IHJWB2caGgi18OEqDBFYiHKpAHqpWADdCu3LPHkkWO_S0NGWZglgyuvnOA2tNKFXgRKNvkOAyW93fc9WczyvL/s1600/mw_jacop.gif" /></a><a href="http://jacop.eu/" target="_blank">JaCoP</a>, as its name implies, is a library for constraint programming in Java. It's been developed by two people from academia for more than ten years now. It's flexible, well documented and it ships with a wealth of good examples that are really helpful to get started.</div>
<div class="" style="clear: both; text-align: left;">
<span style="font-size: large;"><u>The pros</u></span></div>
<div class="" style="clear: both; text-align: left;">
<br /></div>
<div class="" style="clear: both; text-align: left;">
Java is a big pro for me. Also, the way boolean variables are defined is handy: they are integer variables whose values are restricted to 0 and 1, so they can be used in arithmetic constraints without conversion. In Hexiom, to count the number of actual neighbors of a cell, I only had to sum the boolean variable telling me if a tile was present on each side. And finally, I liked the way constraints can be composited from some primitive constraints. For instance, I found the IfThenElse constraint very helpful and intuitive to use.</div>
<div class="" style="clear: both; text-align: left;">
<br /></div>
<div class="" style="clear: both; text-align: left;">
<span style="font-size: large;"><u>The cons</u></span></div>
<div class="" style="clear: both; text-align: left;">
<br /></div>
<div class="" style="clear: both; text-align: left;">
Composition of constraints being so cool, I was a bit disappointed to realize that only <i>primitive</i> constraints could be used as building blocks. The algorithm for the propagation of constraints has probably very good reasons for that, but still. For instance, seeing that X+Y=Z (XplusYeqZ) was a primitive constraint, I hoped that the Sum could also be a primitive, but it's not. That's not too bad, because often the solution only requires to decompose the constraint and introduce one or a few auxiliary variables. You only have to learn this habit.</div>
<div class="" style="clear: both; text-align: left;">
<br /></div>
<div class="" style="clear: both; text-align: left;">
</div>
<div class="" style="clear: both;">
<span style="font-size: large;"><u>The result</u></span></div>
<div class="" style="clear: both;">
<br /></div>
<div class="" style="clear: both;">
The code can be found in: <a href="https://github.com/slowfrog/hexiom/blob/master/src/com/slowfrog/hexiom/Main3.java">https://github.com/slowfrog/hexiom/blob/master/src/com/slowfrog/hexiom/Main3.java</a></div>
<div class="" style="clear: both;">
It uses the same constraints as the one from Pierre Schaus, even though the way they are expressed is a bit less elegant:</div>
<div class="" style="clear: both;">
</div>
<ul>
<li>the variables to resolve represent cells and the values represent either a tile (0 to 6) or the <i>empty</i> value (7 here)</li>
<li>auxiliary boolean variables are used to model filled or empty cells</li>
<li>a GCC (Global Cardinality Constraint) ensures that the correct tiles are used</li>
<li>a local counting constraint is created for each cell, combined with a condition: if the cell is empty, its value is 7, if it's not empty, its value must be the count of filled neighboring cells</li>
</ul>
The code performs pretty well and solves all 40 levels in less that a minute. In fact, it solves 39 levels almost instantly, and the remaining one (level 38) in about a minute. However, I had to tweak the branching choice algorithm to get that result. As for my own constraint solver, the best result is obtained when solving variables in row-scan order, and choosing the most discriminating values first. Those values are 0 and 6, which impose respectively that all neighbors be empty or filled. The <i>empty </i> value must be considered last. The good point is that JaCoP makes it really easy to define that strategy by just listing all values in the required order.<br />
<div class="" style="clear: both;">
<br /></div>
<br />
<div class="" style="clear: both; text-align: left;">
<span style="font-size: x-large;">Gecode</span></div>
<div class="" style="clear: both; text-align: left;">
<br /></div>
<div class="" style="clear: both; text-align: left;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg2tTm4fTc3MW4VwAjUdwfHQdlC_dye4-R4Gg1uMACBMHGx5fYhJMIdtVnA7cs5N9RHrRf9SdWPptT1-rdxLh3om9eRwLfUnZC3a5IS0QgqnZj_ESKtMFPiANvOh-gEr8MiwluHQ-8EK_2U/s1600/gecode-logo-120.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg2tTm4fTc3MW4VwAjUdwfHQdlC_dye4-R4Gg1uMACBMHGx5fYhJMIdtVnA7cs5N9RHrRf9SdWPptT1-rdxLh3om9eRwLfUnZC3a5IS0QgqnZj_ESKtMFPiANvOh-gEr8MiwluHQ-8EK_2U/s1600/gecode-logo-120.png" /></a><a href="http://www.gecode.org/" target="_blank">Gecode</a> is a C++ library that has been in development for a bit more than five years. It's also very flexible and quite well documented. Being C++, it's also quite easier to shoot oneself in the foot with it, but I guess that's to be expected. It also comes with a pre-compiled solver that accepts the flatzinc syntax as input (but I am still evaluating that part). And the library has won constraint processing contests several years in a row.</div>
<div class="" style="clear: both; text-align: left;">
</div>
<div class="" style="clear: both;">
<span style="font-size: large;"><u><br /></u></span></div>
<div class="" style="clear: both;">
<span style="font-size: large;"><u>The pros</u></span></div>
<div class="" style="clear: both;">
<br /></div>
<div class="" style="clear: both;">
The performance of the program is excellent, with the right tweaks (same as always: the branching heuristics). One advertised advantage is that Gecode supports parallelism. I did not try it, but if it works, it's nice. So it's a virtual pro for me.</div>
<div class="" style="clear: both;">
<br /></div>
<div class="" style="clear: both;">
<span style="font-size: large;"><u>The cons</u></span></div>
<div class="" style="clear: both;">
<br /></div>
<div class="" style="clear: both;">
Compared to JaCoP, the variables and constraints seem more primitive and sometime more difficult to handle. Boolean variables cannot be used in arithmetic constraints: auxiliary integer constraints must be created. The difference between <i>variables</i> and <i>arguments</i> is not yet clear to me but seems to revolve around memory allocation. And I met several segfaults before the program ran successfully, because some functions allow nonsensical arguments. Maybe they could be checked better and meaningful exceptions could be raised. There is no obvious constraint composition mechanism, and the branching strategy seems less flexible. To implement the same one as with JaCoP, I had to change the <i>empty</i> value from 7 to -1, to make sure the values were tried in descending order starting at 6. In that case, zero is treated almost last, but it's not too problematic, because it does not appear in a lot of levels.</div>
<div class="" style="clear: both;">
<br /></div>
<div class="" style="clear: both;">
</div>
<div class="" style="clear: both;">
<span style="font-size: large;"><u>The result</u></span></div>
<div class="" style="clear: both;">
<br /></div>
<div class="" style="clear: both;">
The code can be found in: <a href="https://github.com/slowfrog/hexiom/tree/master/cpp">https://github.com/slowfrog/hexiom/tree/master/cpp</a></div>
<div class="" style="clear: both;">
I have only tested it on Windows 7, with VC++ 10 express and Gecode 32bit.</div>
<div class="" style="clear: both;">
It uses the same constraints as before, with a few more auxiliary variables and constraints to accommodate the library.</div>
<div class="" style="clear: both;">
<br /></div>
As already said, performance is awesome: all 40 levels are solved in less than half a second, including the dreaded level 38. I can officially call that <i>fast</i>!<br />
<br />
<br />
<div class="" style="clear: both; text-align: left;">
<br /></div>
<div class="" style="clear: both; text-align: left;">
<span style="font-size: x-large;">Conclusions</span></div>
<div class="" style="clear: both; text-align: left;">
<br /></div>
<div class="" style="clear: both; text-align: left;">
Both libraries are very good! Even for a beginner like me, it's possible to get impressive results with a few hours of work. In the future, I might try Gecode standalone solver, to get the performance without the C++ troubles. I'll see if I can find an equivalent Python library. </div>
<div class="" style="clear: both; text-align: left;">
<br /></div>
<div class="" style="clear: both; text-align: left;">
Overall, programming with constraints is fun, contrary to what the term might suggest.</div>
<div>
<br /></div>
</div>
</div>Laurent Vaucherhttp://www.blogger.com/profile/13286811917069686050noreply@blogger.com0tag:blogger.com,1999:blog-5276958884676424644.post-26745332709655014752012-02-12T18:49:00.001+01:002012-02-15T07:18:14.669+01:00Sikuli plays Hexiom for me<div class="separator" style="clear: both; text-align: left;">
[<b>Update</b>: with some tweaking, my script sometimes succeeds with size-6, see at the end]</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Yeah! Here is one of the first successful automatic runs of my Hexiom-playing bot. This is the combination of the solver<a href="http://slowfrog.blogspot.com/2012/02/solving-hexiom-using-constraints.html" target="_blank"> I wrote about recently</a>, and a bot coded with <a href="http://www.sikuli.org/" target="_blank">Sikuli</a>.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.youtube.com/embed/nzq63hm8sIU?feature=player_embedded' frameborder='0'></iframe></div>
<br />
Sikuli itself is a combination of <a href="http://opencv.willowgarage.com/wiki/" target="_blank">OpenCV</a> for the back-end, screen <i>vision</i> part, a Java middle layer and a scripting engine using Python as its language. It comes with an IDE that is quite easy to learn too.<br />
<br />
<span style="font-size: x-large;">What's great</span><br />
<br />
The scripting part of Sikuli being Jython (Python implemented on top of the JVM) is great. It allows to code quickly and to fall back to Java for more preformance-sensitive parts. In my case, all the screen reading and playing logic is implemented in pure Python, but the problems are handed to Java for resolution.<br />
<br />
OpenCV itself is great and fast enough.<br />
<br />
And as previously said, the IDE is easy to learn and loaded with helpful tools like the screen capture utility and above all the pattern testing screen. It is invaluable to tweak the parameters of image matching, because small patterns like the digits of Hexiom can sometime lead to misses or false positives.<br />
<br />
<span style="font-size: x-large;">What's not so great</span><br />
<br />
Sikuli, do no seem to offer a non-rectangular matching function. There's an <a href="https://bugs.launchpad.net/sikuli/+bug/673995" target="_blank">open request</a> for that on Launchpad, but from my quick investigation, it might be an OpenCV limitation. The only workaround is to match the biggest rectangular area that can fit in the preferred non-rectangular pattern. That is quite annoying: first, in Hexiom's case, all the patterns I'd like to use are hexagonal and second, using a smaller patterns leads to worse detection. After some tweaking, I succeeded in making the bot work every time on a size-4 puzzle, but it's not yet working on a size-6 one, because the board reading procedure making too many mistakes.<br />
<br />
<span style="font-size: x-large;">Wanna try?</span><br />
<br />
Following these steps, you should be able to run the bot:<br />
<br />
<ul>
<li>Install Java, <a href="http://www.sikuli.org/" target="_blank">Sikuli</a> and Firefox</li>
<li>Fetch my code <a href="https://github.com/slowfrog/hexiom" target="_blank">from github</a></li>
<li>Compile java sources (in src/main/java to build/main/classes) or use Eclipse</li>
<li>Open a Firefox window</li>
<li>Set JAVA_HOME and SIKULI_HOME environment variables in a terminal</li>
<li>Run <span style="font-family: 'Courier New', Courier, monospace;">./autorun.sh 4</span> to solve a size-4 puzzle</li>
</ul>
You can also try with 6 instead of 4, but the results will probably be disappointing. Don't try 3 or 5: I haven't captured the appropriate digits yet.<br />
<br />
<span style="font-size: x-large;">Breaking news!</span><br />
<br />
Sometimes, it works with size-6.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.youtube.com/embed/w4GSm0OtTeU?feature=player_embedded' frameborder='0'></iframe></div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Daniel Hartmeier on his site with a somewhat different approach also succeeded, with a fully functional C program, see: <a href="http://www.benzedrine.cx/hexiom.html">http://www.benzedrine.cx/hexiom.html</a>
</div>
<br />Laurent Vaucherhttp://www.blogger.com/profile/13286811917069686050noreply@blogger.com0tag:blogger.com,1999:blog-5276958884676424644.post-28335559318970800052012-02-10T22:34:00.000+01:002012-02-11T11:14:46.062+01:00Solving Hexiom using constraintsAfter <a href="http://slowfrog.blogspot.com/2012/01/solving-hexiom-perhaps-you-can-help.html" target="_blank">my first try</a> using brute force search to solve the <a href="http://www.kongregate.com/games/Moonkey/hexiom" target="_blank">Hexiom</a> puzzler, and following recommandations I received <a href="http://www.reddit.com/r/programming/comments/p54v2/solving_hexiom_perhaps_you_can_help/" target="_blank">in comments</a>, I switched to an approach using constraint solving principles. It's not yet finished (I can still think of new constraints to add), but it's already working more or less as efficiently as the search version. I will try to highlight my findings in this post.<br />
<br />
<span style="font-size: x-large;">Search algorithm</span><br />
<br />
My search algorithm was quite simple:<br />
<br />
<ol>
<li>choose an empty cell</li>
<li>look for all tiles that can possible fit and try each one in turn</li>
<li>decide if the resulting position is solved, still open, or impossible</li>
<li>if still open, continue at step 1.</li>
</ol>
That being said, the latest implementation already took the current position into account in step 2. and 3. For instance, when looking for possible tiles, I only tried tiles with available numbers (obviously), and in a range of values that would still be correct considering surrounding values. That last element is already a kind of constraint application, albeit a simple one.<br />
The third step is quite powerful too, in deciding whether a position is impossible to solve. It also computes possible values and detects mismatches. It can prune out a good deal of possiblities by finding violated constraints.<br />
<br />
<span style="font-size: x-large;">Constraint solving algorithm</span><br />
<br />
The algorithm is, in fact, an hybrid between constraint solving and search.<br />
<br />
<ol>
<li>When reading the input file, each cell is filled with the list of possible tiles, depending on available numbers, number of neighboring cells and locked tiles</li>
<li>A set of constraints is used to remove possibilities from cells. This step is repeated until nothing moves any longer.</li>
<li>Then we fall back on search, as before:</li>
<li>choose a cell</li>
<li>find all possible tiles and try each one in turn</li>
<li>decide if the resulting position is solved, still open, or impossible</li>
<li>if still open, repeat a step 2.</li>
</ol>
The tricky parts are number 2. and number 4.<br />
<div>
<br /></div>
<div>
Regarding constraints (step 2.), some are easy to find, some require a bit more work. I currently use three constraints, but I have thought of some more. The first constraint I use is the same as was implemented in the search algorithm: remove values that are outside the range of possible neighbors. For instance on the following figure, black cells have not been solved yet and we are trying to find which values are still possible in the blue cell. The minimum value is two, because we already have two neighbors. The maximum value is five, because we already have one empty cell as neighbor and the other ones are either filled or could be filled.</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhe4GBpMXa8erUg6Ct5K_zqiiihVN1jcCNi7ILV9PLhc0EU0KSxq3ejnL1q-gx4GAfBCT_BmgllYMzWMVvlMoZzX61meHGlPkKVX1FxuLY7rnvnjpqKHaWuzLnXsWjHHY-R0TGs2GjK-Tos/s1600/hexiom_range.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhe4GBpMXa8erUg6Ct5K_zqiiihVN1jcCNi7ILV9PLhc0EU0KSxq3ejnL1q-gx4GAfBCT_BmgllYMzWMVvlMoZzX61meHGlPkKVX1FxuLY7rnvnjpqKHaWuzLnXsWjHHY-R0TGs2GjK-Tos/s1600/hexiom_range.png" /></a></div>
<div>
<br /></div>
<div>
The second and the third constraints are mostly like the ones used in sudoku: when all tiles of a current value have been used, remove that possibility from all other cells, and when the number of cells that can host a given value is exactly the same as the number of available tiles with that value, fill all the cells with that value.
</div>
<div>
<br /></div>
<div>
Step 4. is where heuristic is important: I have to decide which cell to try first and in which order to try the possible tiles. I have implemented four strategies to choose the next cell. One finds the cell with the fewest choices, the second finds the cell with the most choices, the third finds the cell with the highest possible value and the last just scans cells linearly, from top to bottom (like the search algorithm).</div>
<div>
<br /></div>
<div>
<span style="font-size: x-large;">Results</span></div>
<div>
<br /></div>
<div>
The current results are good but not perfect. On the one hand, with the good heuristic, I can now solve level 40 in under a second and level 38 in two hours, whereas they completely resisted the search algorithm. On the other hand, solving the 38 other <i>easy</i> levels is a little slower than with the search. The code is available as usual <a href="https://github.com/slowfrog/hexiom" target="_blank">on github</a>. The java version could probably do with some low level optimization, like minimizing the number of instanciated objects.</div>
<div>
Among heuristics, the one that chooses cells linearly does globally better than others. I does not fit my immediate intuition. I was inclined to choose cells with the least choices, thinking I would get better chances. It seems intuition is not always the friend of science.<br />
<br />
<br />
<span style="font-size: x-large;">What's next</span><br />
<br />
This puzzle is a suprisingly rich field of exploration. I have a few more directions to go.<br />
<br />
The first is expanding the set of constraints. I'm thinking of one constraint that could help remove the "empty" possibility from cells, when it's mandatory to fill remaining cells with tiles in order to reach a given count. Another one, or the same in reverse, could force empty cells when the correct number of neighbors is already present.<br />
<br />
The second is around heuristics. What bothers me is that several of the ones I have implemented are perfect in some situation and awful in others. I can try to find new ones. Or I can try to take advantage of multiple cores by running several solvers in parallel, with different heuristics, and hope that one of them finishes quickly.<br />
<br />
The third is another approach to the problem. Only choosing which cells to leave empty is sufficient to determine the complete board. Then it's only a question of matching the resulting board with the set of available tiles to see if it works. I'll describe that approach later, but I'm not sure it can lead to a workable solver. I'm afraid I won't be able to prune out branches as effectively.<br />
<br />
The fourth is about automation. If you remember, my goal was to get the 60 Kongergate points granted for solving a random size-6 board in less than three minutes. To reach that goal, I have started using <a href="http://sikuli.org/">http://sikuli.org/</a> to play for me. It's not yet done, but it can almost <i>read</i> a size-4 board. After that, it will only need to launch the solver, read the results, and move the tiles accordingly. Should be fun to watch...<br />
<br />
<br />
<span style="font-size: x-large;">Credits</span><br />
<br />
Thanks to fellow redditor julesjacob who described the general principles of constraint propagation that I implemented here and gave invaluable advice and pointers to good resources. And also to leonardo_m who piqued my curiosity for the D language by porting the Java version of the search algorithm.<br />
<br />
You can also comment <a href="http://www.reddit.com/r/programming/comments/pjx99/solving_hexiom_using_constraints/" target="_blank">on reddit.</a> </div>Laurent Vaucherhttp://www.blogger.com/profile/13286811917069686050noreply@blogger.com1tag:blogger.com,1999:blog-5276958884676424644.post-29525175066974623112012-01-31T22:54:00.000+01:002012-02-10T22:35:08.122+01:00Solving Hexiom (perhaps you can help)<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiwkwFUKi8n7ElB2r_-y7WXt40iQl9BPqxOXFzG4Jf5JiYIs8qc_4TV3VWJ1cQoH6Son-JXYuwJm9RemdaGxnq4kqslPSH-nt2TJj-a2iGUss6GRNBTcYaQEn1I47mhyphenhyphen3cMaMTck8NA3Hyn/s1600/hexiom_lvl18.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><br /><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiwkwFUKi8n7ElB2r_-y7WXt40iQl9BPqxOXFzG4Jf5JiYIs8qc_4TV3VWJ1cQoH6Son-JXYuwJm9RemdaGxnq4kqslPSH-nt2TJj-a2iGUss6GRNBTcYaQEn1I47mhyphenhyphen3cMaMTck8NA3Hyn/s320/hexiom_lvl18.png" width="320" /></a></div>
<br />
<br />
Recently, when killing time on Kongregate and looking for achievements to boost my level, I discovered <a href="http://www.kongregate.com/games/Moonkey/hexiom" target="_blank">Hexiom</a>, a puzzle game by a guy called Moonkey. As all good puzzlers, this one features a very small set of rules and gives birth to a large range of problems, with varying degrees of difficulty. The game comes with forty pre-defined levels and a "random-level" feature. To obtain 60 points on Kongregate, you need to beat the "impossible" challenge: complete a random level of size six in less than three minutes. Well, that might not be impossible, but it's darn tough. So my immediate thought was: "Ok, let's just write a solver for this thing, and pocket the 60 points!" But as of today, I still don't have those points.<br />
<br />
<span style="font-size: x-large;">The rules</span><br />
<br />
So, what exactly are the rules of this game? As you can see, you have a board of hexagonal 'squares' (I call them cells), and you have hexagonal tiles in some of those cells. The tiles have a number on them, ranging from zero to six. They also have a color, but this one is changing. It's not a characteristic of the tile, as I will explain shortly. The goal is to put all tiles in cells such that each tile has a number of neighbors that exactly matches the number on the tile, as you can see below.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgiCLX6vcvBFF3429U9-tNswaQoUP_kJPRrze69ic1ZJ4Uv3idI-NuNiNkd_uiBBHw5xpZHr2t36u-jpbz_Dd7TkSxPcXLgNCi3M91zz6eETi4u-mMDHndSWLvpAPxs5INfeHgnaJaEYXhP/s1600/hexiom_lvl18_solved.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgiCLX6vcvBFF3429U9-tNswaQoUP_kJPRrze69ic1ZJ4Uv3idI-NuNiNkd_uiBBHw5xpZHr2t36u-jpbz_Dd7TkSxPcXLgNCi3M91zz6eETi4u-mMDHndSWLvpAPxs5INfeHgnaJaEYXhP/s320/hexiom_lvl18_solved.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">The number on the tile must match the number of neighbors</td></tr>
</tbody></table>
The color of each tile changes, just to give you a hint about its current status. If it's yellow, the number of neighbors is correct. If green, the tile does not have enough neighbors, if red, it has too many of them. A solved level is, therefore, filled with yellow tiles.<br />
<br />
In some level, there are additional constraints. Some cells might be simply unavailable: they appear completely flat. Some other cells might have a tile already locked in, with grey 'claws'.<br />
<br />
And that's all! You can move any free tiles to any free cell, until you come up with a correct combination.<br />
<br />
<span style="font-size: x-large;">Modeling the problem</span><br />
<br />
I first defined some structures for the puzzle and a way to describe the levels in text files and to read them. A level is:<br />
<br />
<ul>
<li>a board containing cells</li>
<li>a list of tiles (just the count of tiles for each possible number)</li>
<li>a set of fixed tiles, if any.</li>
</ul>
The board is initially built just knowing its size. In fact in my model, all cells are created, even those where no tile can be put. The "is neighbor of" relation is precomputed to speed up the search.<br />
The list of tiles is filled from all the tiles present on the board at startup. I just count the number of tiles for each possible value, because tiles don't have individual identity. I have also added a special value to mean "no number." Each cell that has no tile on it at startup counts as one "no number" tile. That way, when doing the search, it's always possible to chose a tile to fill a cell, even though it's not a real visible tile.<br />
The set of fixed tiles is simply modeled as a partial solution: some of the tiles already have a destination. Something I noticed is that unavailable cells can simply be modeled as cells filled with a "no number" tile. Since there is already a tile in the cell, it's impossible to put another one: the cell is really unavailable. And since the tile is a "no number", it does not impose any constraint on neighboring cells. It's nice that it fits in the general model, without needing a special case: it makes the algorithm simpler.<br />
<br />
<span style="font-size: x-large;">The current solution</span><br />
<br />
My current solver is a simple "search and backtrack". I examine each cell in turn, look for all possible tiles that could fit (determining what is the current minimum and maximum value possible), try them all, one after the other, and do the same on the next cell, if the current position is still acceptable.<br />
At first, I programed in Python, for the ease of iterative testing. It was enough for the first batch of levels, but it quickly became too long. I did some micro-optimizations first: changing some data structures, and some loops. It went a little faster. I tried using the excellent <a href="http://pypy.org/" target="_blank">PyPy</a> instead of the standard CPython: it cut the runtime by about two.<br />
The next not-so-logical step was to port the algorithm to Java. The performance got somewhat better and I could solve a few more levels. After profiling, I realized that a lot of time was spent creating and deleting short-lived objects, and using HashMaps. So I converted most HashMaps to arrays and found ways to drastically reduce object management. Another good speed gain.<br />
<br />
And then I did what I should have done from the start: focus on improving the algorithm itself! The main bottleneck was the function that tested if a working position was solved or not. I changed it to return a status telling if the position was solved, still open, or impossible because of some failed constraint. That small change made it possible to prune out some search branches really early and solve all but two of the forty levels in no time. The current Java program solves 38 levels in about 3.5 seconds on my machine. After backporting that change to the Python code and when run with PyPy, it takes 46 seconds to solve the same levels.<br />
<br />
<br />
<br />
<span style="font-size: x-large;">The current limitations</span><br />
<br />
But still, level 38 and level 40 resist the brutish-force search. So I ported the code again, to C this time. Since the Java code had already been mostly 'de-objectized', it was quite an easy translation. But the result is disappointing. Compiled with full optimization, either with Cygwin-GCC or with Visual C++ 2010 Express, the runtime is about the same as the Java version. It's even a bit slower, actually: 4.7 seconds vs 3.5 for Java.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiXJ_LFDzrslQ0FJNmkrL516-0LaWMr9dVSFXQ4IDOJtJf1BBifXBe3udAyyUO5grwCHEjGLy3oLt5f3rMKRs3-FXViT52WNjjABE-j-GyoRYXQwfQy_kkdW84pBxb73A7vbsksRPPSGC5O/s1600/hexiom_lvl39_solved.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiXJ_LFDzrslQ0FJNmkrL516-0LaWMr9dVSFXQ4IDOJtJf1BBifXBe3udAyyUO5grwCHEjGLy3oLt5f3rMKRs3-FXViT52WNjjABE-j-GyoRYXQwfQy_kkdW84pBxb73A7vbsksRPPSGC5O/s1600/hexiom_lvl39_solved.png" /></a></div>
<br />
Another limitation, if I were to try to grab the 60 points, is that all my solvers need a text file as input, and currently, typing the data for a size-6 level already takes a good part of the available three minutes. And even if the solver was instantaneous, I would still have to read the result and move all the tiles manually to their destination. If I really want those 60 points, I will have to resort to my old game-solving tricks: read the screen, solve the problem, and automate the displacement of tiles by simulating mouse events.<br />
<br />
<br />
<span style="font-size: x-large;">Where you can help</span><br />
<br />
All my code is freely available <a href="https://github.com/slowfrog/hexiom" target="_blank">on github</a>. If you find a flaw in my algorithm, a problem with my code or think of something different that might run faster, just tell me.<br />
<br />
<br />
Comments available also <a href="http://www.reddit.com/r/programming/comments/p54v2/solving_hexiom_perhaps_you_can_help/" target="_blank">on reddit</a>.<br />
<span style="font-size: x-large;"><br class="Apple-interchange-newline" /></span><br />
<br />
<br />
<br />Laurent Vaucherhttp://www.blogger.com/profile/13286811917069686050noreply@blogger.com1tag:blogger.com,1999:blog-5276958884676424644.post-82593153911939730132011-11-24T21:59:00.001+01:002011-11-24T22:15:56.433+01:00New sticker-art sightings<div class="separator" style="clear: both; text-align: left;">
This time it's Pokemon Mienfu (Kungfouine in French) and Muttley (aka Diabolo) that have been stickerized.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEimWhGjtpkVQD52OtccmBBDejoiovJh8g0geZrgHt1sYV6BvgTx6J0wg5WZddpocKk7XJECRz_-wHtQAIMXy1jIno3DejmfdW2ECVfzlbd35rtEMd4ejZHy9YlaFPi6Gt5_uZODpS8tYbWu/s1600/KungFouineSmall.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="239" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEimWhGjtpkVQD52OtccmBBDejoiovJh8g0geZrgHt1sYV6BvgTx6J0wg5WZddpocKk7XJECRz_-wHtQAIMXy1jIno3DejmfdW2ECVfzlbd35rtEMd4ejZHy9YlaFPi6Gt5_uZODpS8tYbWu/s320/KungFouineSmall.jpg" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
</div>
<div class="separator" style="clear: both; text-align: left;">
Mienfu is a standard conversion of an official bitmap.</div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEge3ejdeYcNRiQo4B7-3yPkQCI4N0scaLTdtNoecPbzoK9wa5afgmyDB9gIEO2DItU2BJwOYB4_u0D03FdQmw7iZN7lk-vzZX3JoWjwR6MqztpA9oQthFtyySUxgrE5I-XOTpIp1XQIDhGO/s1600/DiaboloPorteSmall.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEge3ejdeYcNRiQo4B7-3yPkQCI4N0scaLTdtNoecPbzoK9wa5afgmyDB9gIEO2DItU2BJwOYB4_u0D03FdQmw7iZN7lk-vzZX3JoWjwR6MqztpA9oQthFtyySUxgrE5I-XOTpIp1XQIDhGO/s320/DiaboloPorteSmall.jpg" width="239" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
For Muttley, on the other hand, I doctored the original image and used an hexagonal grid to obtain a "crisp" result, with 7,200 stickers.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi4hgMCBIJkGtB63N5smm55TSRbeKztfTpp3I4_OYWwhN_0O-W8yF0BkOJ8YQPTxG1cNYnBth_0rgazS3SUqVms4cVJBgpOYhs6NFjYfqm4MbhyLQRJQOuRbGU4kY13ojFTN3AxJoK80N15/s1600/DiaboloFenetreSmall.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi4hgMCBIJkGtB63N5smm55TSRbeKztfTpp3I4_OYWwhN_0O-W8yF0BkOJ8YQPTxG1cNYnBth_0rgazS3SUqVms4cVJBgpOYhs6NFjYfqm4MbhyLQRJQOuRbGU4kY13ojFTN3AxJoK80N15/s320/DiaboloFenetreSmall.jpg" width="245" /></a></div>
<br />
He's now on my office's window, making fun of the neighbors who are still doing lo-def drawings with Post-It notes.<br />
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<br />Laurent Vaucherhttp://www.blogger.com/profile/13286811917069686050noreply@blogger.com0tag:blogger.com,1999:blog-5276958884676424644.post-11948828681195217032011-11-18T18:12:00.001+01:002011-11-20T00:00:59.548+01:00The making of Web Desktop DungeonsAs promised in the previous post, I will explain how I made the <a href="http://www.desktopdungeons.net/HTML5/" target="_blank">web version of Desktop Dungeons</a>. I already told <a href="http://slowfrog.blogspot.com/2011/11/desktop-dungeons-in-your-browser.html" target="_blank">why I embarked</a> on that project; here is the <i>how</i>.<br />
<br />
When I first got the idea to port the game to the browser, I looked at what kind of game libraries were available. Back in April, nothing seemed to fit what I was looking for. Lots of libraries and frameworks, both free and proprietary, have appeared or blossomed only last summer. And most of the ones I browsed focused on fast-paced shooters and platformers, with animations, collision detection, particle systems, physics simulation and other features that were clearly not needed for Desktop Dungeons. So I quickly decided that I would code everything myself. It did not seem too big too handle.<br />
<br />
The other thing that I decided immediately at start (I don't even know if I should call it a decision) was to use only HTML and CSS for rendering: no canvas drawing. I thought that I would be able to ensure compatibility with older browsers that way. And since the game is tile-based, it was a very natural choice. I did not need real drawing capabilities. I only wanted to show images at predefined positions, rectangular buttons and areas, all things possible with <img>s, <div>s, <a>s and a bit of CSS styling. I abandoned compatibility with older browsers (yes, IE 7 and 8, I'm talking of you) along the way, but for other reasons.<br />
<br />
<span style="font-size: x-large;">The early days</span><br />
<br />
On the first day, I was able to display the 20x20 board with a predefined maze, a yellow placeholder for all the status information, a hero sprite that I could control with the keyboard and move even through walls, and a mouse-following 'cursor'. And all that with one HTML file, two JavaScript (one for utilities/compatibility layer and one for the game itself) and all the bitmaps from the original game. I used git immediately to track my changes and backup my work. I made five revisions on that first day.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgilAbyxOQFWSgZsLIUh0F-e1svreD6kJW7np26PYlMzU1tLwIw9qsI18wV4mTveRmMlGl85ytQWlgzK6TRbdFgWAI0PrSxHuaaWJbdguC06njWcjzmzs6B1FAq8POctPewI26sNDQPAmib/s1600/webd_shot1.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="227" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgilAbyxOQFWSgZsLIUh0F-e1svreD6kJW7np26PYlMzU1tLwIw9qsI18wV4mTveRmMlGl85ytQWlgzK6TRbdFgWAI0PrSxHuaaWJbdguC06njWcjzmzs6B1FAq8POctPewI26sNDQPAmib/s320/webd_shot1.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Web Desktop Dungeons at one day</td></tr>
</tbody></table>
<br />
After three weeks of (after hours) work, the game started to look a bit better: the info panel at the right was a bit more fleshed out, moving the hero worked both with the keyboard and the mouse, thanks to the pathfinding algorithm, the maze (still fixed) was filled with lots of intersting stuff and the combat system was in place, somewhat. Except it was not yet possible to die. The JavaScript code had now expanded to four files, totaling 1.200 lines. Three refactorings had already taken place, one of them labelled as "big" in the change log.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh7YkyaeGB0jjt2uoX7dGSH1UxcrTe0Oy3-9jcyh3R5VRcXVP9SndoI10iDnI56kJTsDbgxshrh5R4fYP86uluZQkDBoIY33VV584HcokHZzimL4M7gZ_lxRGQn0BiYJYrdN44xM3B4ce-M/s1600/webd_shot2.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="229" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh7YkyaeGB0jjt2uoX7dGSH1UxcrTe0Oy3-9jcyh3R5VRcXVP9SndoI10iDnI56kJTsDbgxshrh5R4fYP86uluZQkDBoIY33VV584HcokHZzimL4M7gZ_lxRGQn0BiYJYrdN44xM3B4ce-M/s320/webd_shot2.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Web Desktop Dungeons at three weeks</td></tr>
</tbody></table>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Then, I reorganized the code in true MVC fashion, began to develop individual widgets (buttons, gauges, images, tooltips, dialogs), continued to improve support of game mechanics (magic spells, special states, regeneration, power ups), added the basic logic of the menu screen and mid-June, I contacted QCF Design to present my creation. Danny (Day aka Dislekcia) answered me and has always been very positive and supportive. At that time, I wanted to open-source the whole thing and publish it on Github, with permission. Danny convinced me it was not a good idea: the project was still far from finished or even playable. Had I gone public at that time, I would probably have received only negative reactions.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
So I resumed work on implementing all the "content": hero classes and races with their unique abilities, monsters, bosses, gods (oh! boy!) and items. I was guided by the content of <a href="http://www.qcfdesign.com/wiki/DesktopDungeons/index.php?title=Main_Page" target="_blank">the wiki</a> and by personal experiments with the desktop version. I contributed a few elements back to the wiki. But after three months, I began to realize that play-testing was not going to be enough to ensure correct implementation of all the details and prevent regressions. I was now at 4.000 lines of JavaScript and I needed an automated test system. Otherwise, it was impossible to manually reproduce rare situations, like finding an altar to Jehora Jeheyu while being immune to poison. </div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
<span style="font-size: x-large;">Growing up, gathering tools</span></div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
I chose <a href="http://code.google.com/p/js-test-driver/" target="_blank">JsTestDriver</a> as my unit testing library. It's mature. It can be added to an automated build. It runs the tests in real browsers, not in some kind of virtual JavaScript environment. It can drive several browsers at once. It produces reports that are compatible with JUnit. Sometimes the server gets stuck and needs a restart, but that's really bearable. I started with version 1.3.2 and later migrated to 1.3.3 when it became available. I chose to only write unit tests with it for the game mechanics. I did not invest in automated UI testing. I thought the return on investment for those kinds of tests was not worth it. Breaking something at the UI level would become obvious quickly with some play tests: that could not be said of subtle game logic regression. In hindsight, it was a good choice.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
The test suite started with 75 lines of JavaScript in July. At the begginning of August, the code base was 5.600 lines and the test suite more that 600, mainly focusing on hero classes and beasts. In September, 7.800 lines of game code, 1.700 lines of test code, more than half for all the exquisitely detailed behaviour of divine entities.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiyEzM3BgAYtVT8pPG9pvGYf6oDC7FSsQBHH69Qtq6y2S0EHG2Bs0jCaR3uXdTn0SalYmNUljQlklYGWb1bi58StLw02qimQYgUTEAxIHJEtjHxxdAI3XQ3KBpB6puRBBnTgZy8zEi0y5tG/s1600/webd_shot3.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="270" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiyEzM3BgAYtVT8pPG9pvGYf6oDC7FSsQBHH69Qtq6y2S0EHG2Bs0jCaR3uXdTn0SalYmNUljQlklYGWb1bi58StLw02qimQYgUTEAxIHJEtjHxxdAI3XQ3KBpB6puRBBnTgZy8zEi0y5tG/s320/webd_shot3.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Yeah! Tests ok across five browsers!</td></tr>
</tbody></table>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Mid-August I got interested in JavaScript minification or compilation. I found two possible tools: <a href="http://www.crockford.com/javascript/jsmin.html" target="_blank">Doug Crockford's jsmin</a> minifier and <a href="http://code.google.com/closure/compiler/" target="_blank">Google closure</a> compiler. closure being written in Java was a better fit for my environment and promised more than just minification, with its advanced compilation mode. However, trying to apply it to the project at that time, with several thousands lines of existing code proved too hard. The advanced compiler made wrong assumptions that broke the game and needed me to explain everything and possibly apply deep refactorings, ultimately ruining some of my JavaScript techniques. I gave up on the advanced compilation mode and kept only the basic one. It's still very useful for two reasons. The first is that it packs all the JavaScript code into one single file. It means I can structure my code any way I want, for easy development and still end up with one compact file, better for deployment. The second advantage of compilation is size reduction: closure manages to shave off a good third of the initial size with whitespace and comment elimination and local variable reduction.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
On my next project, still in a very early phase, I used closure from the start, and took precautions to keep advanced compilation working. I don't know if it enhances runtime performance, but size reduction is still more impressive. My 50kB of JavaScript become 22kB with standard compilation and a mere 13kB with advanced mode. After all, maybe it's only useless optimization, when the complete JavaScript code is smaller than the image for the splash screen...</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
<span style="font-size: x-large;">Original sources and HTML5</span></div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
In early September, probably bored at answering my nitpicking questions, QCF Design agreed to send me the GameMaker project of the original game. I discovered both the tool and the game source with mixed reactions. First, <a href="http://www.yoyogames.com/make" target="_blank">GameMaker</a> is primarily targeted at hobbyists and not at programmers or software engineers. Versioning source code is impossible up to version 8.1. Code is scattered all around the place: sometimes as real code, sometimes as graphical constructions. The design screens have somewhat inconsistent conventions of interaction. From a software engineer point of view, it's ugly.</div>
<div class="separator" style="clear: both; text-align: left;">
But after doing the tutorials, I began to appreciate its philosophy. I am now convinced that it's a great tool for either hobbyists or rapid prototyping. In each case, it makes it possible to focus on the game itself and not on technical issues (How do I display an animation? How do I play a sound? How do I code collision detection?) It's also probably a great way to introduce children to programming. It's easy and quick to have something working. Afterwards, it's open to experiment.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjHtvXLVUE5UVdJsB_XNGtSlo3KAMjasyiIL__rmeeXK-CmOmMtvmV6HKENxPP4Jr7kKGP0MQwjm-_15iZlIssyR4VOwFv2kQoFjT3Bs5Y59ftHzD5m6drvXviZyAZu4fBByJEuRh5sdOBd/s1600/webd_shot4.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="173" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjHtvXLVUE5UVdJsB_XNGtSlo3KAMjasyiIL__rmeeXK-CmOmMtvmV6HKENxPP4Jr7kKGP0MQwjm-_15iZlIssyR4VOwFv2kQoFjT3Bs5Y59ftHzD5m6drvXviZyAZu4fBByJEuRh5sdOBd/s320/webd_shot4.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Is that code??</td></tr>
</tbody></table>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Overall, the game source became my source of answers, and I shamelessly copied the maze generation algorithm.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
During the summer, I added a few things that required HTML5 features and definitively lost any hope of supporting older browsers. The first one is anecdotal. I need to use a <canvas> element behind the scenes in Chrome and Opera to scale up bitmaps and keep the pixellated look. The second one is central to the game: saving progress using localStorage. You could argue that it would be better if progress was saved on the server side. But that was not the point. I wanted to provide saved games on the client side, to allow deploying the game anywhere, without server support over simple HTTP transfer, much like what Flash games do. The third HTML5 feature has been added later: sound support. It was a bit tricky (different browsers support different encodings, Safari requires QuickTime before it can play anything, Firefox 3.6 requires <audio> tags to be part of the DOM tree) but otherwise quiet easy to add.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
<span style="font-size: x-large;">Finishing touches</span></div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
That's definitely the hard part. At least for me. Most of the interesting bits of code were done. Most of the tools had lost their shine. What helped me was my moral commitment towards Danny and QCF Design. Some psychological studies - yes, I read some of them - suggest that great achievers always have a mental picture of the goal they are targetting and focus on it, whereas under-achievers keep looking in the past at all the work they have already done... and generally stop their effort before finishing, when they consider they have done a lot. I am often guilty of that sort of behaviour. That time at least I finished. The fact that it was a port of an existing game, with a clearly defined goal that I could use to estimate the path left must have played a role in helping me succeed. I must keep that in mind for my future projects.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
On the 2nd of October, after exactly six months of work, 9.800 lines of game code and 3.100 lines of unit tests, I told Danny that I was ready for deployment. It still took about a month to add a splash screen to monitor the loading progress over slow connections and iron out a few bugs. And on the 5th of November the game was finally uploaded to the official Desktop Dungeons web site and <a href="http://www.desktopdungeons.net/?p=152" target="_blank">announced in the news</a>. I took two weeks of vacations in the Bahamas to celebrate and write this account of the complete journey ;)</div>
<div class="separator" style="clear: both; text-align: left;">
</div>
<div class="separator" style="clear: both;">
<br /></div>
<div class="separator" style="clear: both;">
<span style="font-size: x-large;">Bonus</span></div>
<div class="separator" style="clear: both;">
<br /></div>
<div class="separator" style="clear: both;">
I made <a href="http://slowfrog.com/sourcetree/sourcetree.html" target="_blank">a visualization of the development</a> history, if you're curious. It represents the tree structure of the project at each commit. Each type of file has a distinct color. The size of the file is show as the width of the segment (at logarithmic scale). Enjoy! And don't forget to <a href="http://www.desktopdungeons.net/HTML5/" target="_blank">play the game</a>.</div>
<div class="separator" style="clear: both;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgh9905u5s8ObdJ47UA5kXs31JP9iv8kUBGTOmZ2nX34niLuQ8LB7vLKoyFAXxlFZLU1B_h1qSQxDxaek2DHSBMrHxKXSeA2U-KoVQvSgGwAi3TEHxuQv3pE29sGuEw0rDV9U5qnTVLzWHX/s1600/webd_shot5.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="190" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgh9905u5s8ObdJ47UA5kXs31JP9iv8kUBGTOmZ2nX34niLuQ8LB7vLKoyFAXxlFZLU1B_h1qSQxDxaek2DHSBMrHxKXSeA2U-KoVQvSgGwAi3TEHxuQv3pE29sGuEw0rDV9U5qnTVLzWHX/s320/webd_shot5.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="font-size: 10px;">The final project structure</td></tr>
</tbody></table>
<div class="separator" style="clear: both;">
<br /></div>
<br class="Apple-interchange-newline" />Laurent Vaucherhttp://www.blogger.com/profile/13286811917069686050noreply@blogger.com5tag:blogger.com,1999:blog-5276958884676424644.post-4757221300695080092011-11-06T09:36:00.000+01:002011-11-09T22:47:58.277+01:00Desktop Dungeons in your browser!Here it is! My <a href="http://www.desktopdungeons.net/HTML5" target="_blank">HTML port of Desktop Dungeons</a> alpha is done and available on the site of the original <a href="http://desktopdungeons.net/" target="_blank">Desktop Dungeons</a>. It's free, fully playable, up to the Lothlorien campaign, and works on all recent browsers (Chrome, Firefox 3.6 & over, Safari, Opera and even IE9).<br />
<div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh80Y-AKbJzbDrg4bOhrteOeXJ2oXVZCQQfPlO64QmPxJsd-iFzCqRs4bXJNEd2DGEggXlEXDGLfJbCrrzA_rhXNf72hfomBP7rHU_5VdyfLDGYoi4iSnP4mMLP2qmSp6oZ5qmQ1BcbH1OH/s1600/webdungeon.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="249" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh80Y-AKbJzbDrg4bOhrteOeXJ2oXVZCQQfPlO64QmPxJsd-iFzCqRs4bXJNEd2DGEggXlEXDGLfJbCrrzA_rhXNf72hfomBP7rHU_5VdyfLDGYoi4iSnP4mMLP2qmSp6oZ5qmQ1BcbH1OH/s320/webdungeon.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Desktop Dungeons on the web</td></tr>
</tbody></table>
I started working on porting the free alpha version in April. At that time, only that version was available. QCF Design, the creators, were busy working on their own port (to Unity3D) that they quickly showed during E3. They then published the new version as private beta, open to people pre-ordering the full game. Of course, their goal is to make a polished game, exploiting all the possibilities of the design, that can be played on a large array of devices. The alpha was done with GameMaker and could only be run on Windows and MacOSX. And that's why I did the port: I wanted to make it available to a larger public (for instance Linux users).<br />
<br />
After a few months of after-work coding, I showed my progress to the nice people of QCF Design, and they agreed to send me the GameMaker code, so that I could make the port as faithful as possible. And they even agreed to deploy it on their site once finished. How cool is that!<br />
<br />
I did all the coding with JavaScript and mostly HTML4 (using DOM for graphics), but a few features need HTML5: audio support and localstorage to save your progress across levels and classes. For the record, the whole game is about 10k lines of JavaScript and took me six months to code. It might seem long for a simple game like that, but as I said, I could only put a few hours in it now and then. And the mechanics and contents are quite rich: almost twenty hero classes with strange powers, ten gods with different tempers, ten spells and lots of possible items available in shops.<br />
<br />
<a href="http://www.desktopdungeons.net/HTML5/" target="_blank">Go play it</a> and tell me or <a href="http://www.qcfdesign.com/forum/index.php" target="_blank">the forums</a> what you think!<br />
<br />
In a future post, I'll cover my development tools, just in case someone is interested.</div>Laurent Vaucherhttp://www.blogger.com/profile/13286811917069686050noreply@blogger.com1tag:blogger.com,1999:blog-5276958884676424644.post-14572349137399364152011-11-04T00:36:00.000+01:002011-11-04T00:36:28.572+01:00Cool kids are doing itYes, seven and nine year old kids can do really nice pieces. The size must be carefully selected: not too small for a nice looking drawing, not too big, so that it can be done in an hour or two. And here are the results:<br /><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiY_Uxcjnzq2SVNec9OD-WhVnrM8oZqIGx5-BQqYGnRF9X7UBoUSkoCzA59albmMXBXTuqjL_7VB9MYosd86Wr5jngtb6rmXtEIabWTBbi1RwfwFG4FT1VUyx0iUl84iBMURmEhi-k20goz/s1600/pichu.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiY_Uxcjnzq2SVNec9OD-WhVnrM8oZqIGx5-BQqYGnRF9X7UBoUSkoCzA59albmMXBXTuqjL_7VB9MYosd86Wr5jngtb6rmXtEIabWTBbi1RwfwFG4FT1VUyx0iUl84iBMURmEhi-k20goz/s320/pichu.jpg" width="300" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">The cute Pichu<br /><br /></td></tr>
</tbody></table>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhTWF82Zran8oe6EQOKlmmhd6HQ2T_q95LdjquUVDD-rlSZtCjmUcenXKUBEGk4J_ne3c7Q0sD4RZdKRtXC2bgzDruSxJtoHJKV82KatXIjdcVMCdjkf_AIuwFpJyS-gisJUIQaFcL5u7Do/s1600/riolu.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhTWF82Zran8oe6EQOKlmmhd6HQ2T_q95LdjquUVDD-rlSZtCjmUcenXKUBEGk4J_ne3c7Q0sD4RZdKRtXC2bgzDruSxJtoHJKV82KatXIjdcVMCdjkf_AIuwFpJyS-gisJUIQaFcL5u7Do/s320/riolu.jpg" width="284" /></a></td></tr>
<tr><td class="tr-caption" style="font-size: 10px;">The cunning Riolu</td></tr>
</tbody></table>Laurent Vaucherhttp://www.blogger.com/profile/13286811917069686050noreply@blogger.com0tag:blogger.com,1999:blog-5276958884676424644.post-14333258798114612642011-10-26T23:17:00.000+02:002011-11-04T00:19:27.623+01:00Does it scale?After my small experiment with the Firefox logo (about 800 stickers), I wanted to see if the technique could scale. The first step was to order a bunch of 25,000 stickers, because office supply was too short for my ambitions. I got all those packs for about 75 euros, VAT and shipping included, which amounts to 0.003 euros per sticker.<br />
<br />
Then I searched for an appropriate image to render. I wanted something that made good use of the five basic colors I had (red, green, blue, yellow and black). I settled on an old image of Lucky Lucke, ready to draw his guns. It's easily recognizable (at least in France), has nice primary colors and is quite big and thin.<br />
<br />
Using <a href="http://www.slowfrog.com/polychrome/polychrome.html">my JS tool</a>, I made the template I needed, and computed that it would require just under 5,000 stickers and would be 1 meter wide and 1.6 meter high. Almost life-size. It's a big step forward from my previous creation, but it still felt manageable. I also prepared <a href="http://slowfrog.com/polychrome/gommettes.svg">a "grid"</a> at the correct scale to put under the transparent film, to help me place the stickers at their right positions. Since my roll of film is only 50 cm wide, I had to split the drawing in two.<br />
<br />
And I started the sticking phase. All in all, it probably took me about ten hours to complete, and I was quite happy with the result. Here it is, hung on a door.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjwi-MMF5Tz96GOkuv0svmCSgP1WgQmxpHyOOTN1YNMk3LtzH-hDufV9AkZTSV_NRLRy5e0DHlEiydrKzoDQ2yA86f_9p_srQn_1QTb500LXfE3s0XZzfayLHY8EGcc89CKnQ3K9Yyr-v0_/s1600/lucky_door.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjwi-MMF5Tz96GOkuv0svmCSgP1WgQmxpHyOOTN1YNMk3LtzH-hDufV9AkZTSV_NRLRy5e0DHlEiydrKzoDQ2yA86f_9p_srQn_1QTb500LXfE3s0XZzfayLHY8EGcc89CKnQ3K9Yyr-v0_/s320/lucky_door.jpg" width="240" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Lucky Luke on door</td></tr>
</tbody></table>
<br />
After that, I rolled it up and brought it to my workplace, and put it on a window for the whole world to see. Or at least for the whole parking lot. You can see that our windows are a bit small: the boots have been lost. And you can also see that I have a pretty bad camera...<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh_5n8YgbGDp7v2tI9SgmWQtOPa_uM-azY7Llo0N6LM8wPEAWSZ3k5ROR1WYiyGsbw7SYSjMCUdZQAaMAyDnHJUZgrErSq9pJzz3Uc-ojwkq1AexAczaFvDCO6DWygXMrPYs1CEKXgtUowf/s1600/lucky_window.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="296" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh_5n8YgbGDp7v2tI9SgmWQtOPa_uM-azY7Llo0N6LM8wPEAWSZ3k5ROR1WYiyGsbw7SYSjMCUdZQAaMAyDnHJUZgrErSq9pJzz3Uc-ojwkq1AexAczaFvDCO6DWygXMrPYs1CEKXgtUowf/s320/lucky_window.jpg" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Lucky Luke in situ</td></tr>
</tbody></table>
With the blinds closed, it looks ok. Without, the background looks black and the parts that should appear white (the hat and the hems of the trousers, the cigarette) don't look good, because I have no white stickers. A possible solution is to stick any kind of stickers on the other side of the transparent film: their back is white! I don't know yet if I will try to fix Lucky Luke or not. The solution with the blinds is working nicely and I don't want to waste more stickers. I'd rather keep them for my next opus...<br />
<br />Laurent Vaucherhttp://www.blogger.com/profile/13286811917069686050noreply@blogger.com0tag:blogger.com,1999:blog-5276958884676424644.post-15794358604164314112011-10-12T22:22:00.000+02:002011-11-04T00:19:27.627+01:00Real world sticker artHere it is! The first real-world implementation of my <a href="http://www.slowfrog.com/polychrome/polychrome.html">sticker art concept</a>. It's quite a bit more work to do than Post-Itâ„¢ art, but the resolution is better.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiS-al1LiqZi4KYwYp1g9upRIBpRrWb5AA1-85k_EAPiZmE4Q5GRr6dcgCF1otw_guPaWea_8xeMZejf3KD9eMxqydjUrpPbcK4jjQSbuofw5KGe4SgohO2zTV6Zpj59rfQvoVjnJ-93KP1/s1600/firefox_gommettes_blanc.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="312" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiS-al1LiqZi4KYwYp1g9upRIBpRrWb5AA1-85k_EAPiZmE4Q5GRr6dcgCF1otw_guPaWea_8xeMZejf3KD9eMxqydjUrpPbcK4jjQSbuofw5KGe4SgohO2zTV6Zpj59rfQvoVjnJ-93KP1/s320/firefox_gommettes_blanc.jpg" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Firefox logo with stickers on white background</td></tr>
</tbody></table>Those stickers being really sticky, I did not want to put them directly on a window or on office furniture. So I chose to use transparent book cover film, the kind used to protect the books and notebooks of children. It's cheap, readily available, and I was able put a grid model underneath to help me not deviate too much. I'll see tomorrow if I can find a place for it in my office.<br />
<div><br />
</div><div>This relatively small piece used the standard 16x16 pixel Firefox logo as a model. I did the "polychromation" with white background, using the 7-color palette. It needed a total of 788 stickers: about one and a half pack of multi-colored stickers (8 sheets of 11 stickers of the 7 different colors per pack). I did not use a stopwatch, but I would say it took me between one and two hours of meticulous work to finish.</div><div><br />
</div><div>In fact, it's only after doing it and trying to gauge the result on different places that I added the "background" option to the application. I realized that the result looked quite different when viewed on a dark background than on a light background. From the start, I had assumed that the missing dots would represent white, but it's not always the case. If you put the piece on a window and look at it from the outside, everything around the stickers will probably look darker (at least in the daylight). On the contrary, looking at it from the inside, the outdoor will make the background appear light. On the Firefox logo, it does not make a big difference, but on other images, with large white or black regions, it can change everything.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgwd3-dnBYzE7M2w1ROsnaoQ-sbky2c8R-ux3gksII_UWXGyILVY2938YEyD7R7KDF01QC8qoMfVgk7ZZp3lGTxPw_mLcymMnA4iRtCrtgUNIK8LRRNv5_Ik2TzJE91sMYGJROgqondaARR/s1600/firefox_gommettes_noir.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="240" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgwd3-dnBYzE7M2w1ROsnaoQ-sbky2c8R-ux3gksII_UWXGyILVY2938YEyD7R7KDF01QC8qoMfVgk7ZZp3lGTxPw_mLcymMnA4iRtCrtgUNIK8LRRNv5_Ik2TzJE91sMYGJROgqondaARR/s320/firefox_gommettes_noir.jpg" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Firefox logo with stickers on black background</td></tr>
</tbody></table>You might also have noticed that I added a "Sticker unit price" input box. This will help you estimate your cost, in case you want an quote beforehand. I found a provider in France that sells monochromatic packs of 462 stickers for 1.20€, VAT excluded, when buying more than five packs. That makes the VAT-included unit price 0.0031 €. So my Firefox logo cost a bit less than 2.50€ in stickers.<br />
<br />
That's all for the cold hard facts. I'm still pondering what I'll do next. If you want to join the new office-supply-abuse-revolution, you're all welcome!</div>Laurent Vaucherhttp://www.blogger.com/profile/13286811917069686050noreply@blogger.com0tag:blogger.com,1999:blog-5276958884676424644.post-55207511619252657092011-10-04T23:31:00.000+02:002011-11-04T00:19:27.630+01:00Improvements on the sticker art creatorThe previous version of <a href="http://www.slowfrog.com/polychrome/polychrome.html">polychrome</a>, my nifty tool for wasting your company's stickers, only supported a limited set of embedded images. And even though those images had been carefully chosen, there comes a time when you want to experiment with more personal pictures. Enter the new version: you can now <i>upload</i> your images and have them converted.<br />
<br />
You might have noticed that I emphasized the word upload. That's because when you do that, you don't really upload anything anywhere. I'm just using that particular interface to allow the browser to get access to a local file that you choose. If you don't trust me, just disconnect from the network after loading the page: the application will run unaffected.<br />
<br />
Also, you will now see the number of stickers that will be needed for your creation (lots of them) and you can automatically apply a zoom to shrink your image to more realistic dimensions.<br />
<br />
<br />
Oh, and sorry Internet Explorer and Safari users, but the File API is not supported by your favorite browser: you will still be limited to the selection of embedded images. Everything works fine with Chrome, Firefox and Opera on Windows. If you have tested other combinations, either working or not, just let me know.<br />
<br />
<br />
<span style="font-size: large;">Technical details</span><br />
<span style="font-size: large;"><br />
</span><br />
The reason I used the upload/FileReader API from HTML5 is simple. I first thought that just allowing the user to type in a URL would be enough. The application would load the image into the page, draw it, do some computation, and display a nice sticker chart. Except that does not work, because of security limitations. The "Same Origin" rule makes that impossible. When you try it, you end up with an image that you can display, but JavaScript cannot get access to its individual pixels and cannot do anything with them. It's essentially a write-only image. Useless.<br />
<br />
So I crawled the web, looking for an online HTML5 Photoshop-like application where it was possible to upload images, willing to learn how that magic was possible. I finally found <a href="http://evanw.github.com/webgl-filter/">http://evanw.github.com/webgl-filter/</a>. It's basically a WebGL effects demo, but what interested me was the upload function. It turned out it was quite easy. Just an old <span style="color: #3d85c6; font-family: 'Courier New', Courier, monospace;"><input type="file"></span>, then a FileReader plugged on the selected file, and with readAsDataURL() and putting the result as the source of my image, everything worked perfectly.<br />
<br />
All in all, this small experiment taught me a few new tricks of HTML5. It's really becoming a nice platform for all sorts of applications.<br />
<br />
If you are interested in code, have a look at <a href="https://github.com/slowfrog/polychrome">the source on github</a>.Laurent Vaucherhttp://www.blogger.com/profile/13286811917069686050noreply@blogger.com0tag:blogger.com,1999:blog-5276958884676424644.post-65238075361429639582011-09-23T23:17:00.000+02:002011-11-04T00:21:29.980+01:00Post-it art is sooo old!Why not waste your company's money on stickers instead. You know, the small round ones universally used by any self-respecting "agile" team:<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjthV7_njLwS8EIVFd59CNuLWAyPRKB0Wh2vUXYgJORxvr5DEHZ3aOY7s77Rj-0SvkLf1QKNCE6eqoH1TOvXZipjqKgJ-vOX7Yp28Ys5jOgKGd2xHS5KVIh39cFqOIrh9vSYReTY0M2iokx/s1600/gommettes.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="312" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjthV7_njLwS8EIVFd59CNuLWAyPRKB0Wh2vUXYgJORxvr5DEHZ3aOY7s77Rj-0SvkLf1QKNCE6eqoH1TOvXZipjqKgJ-vOX7Yp28Ys5jOgKGd2xHS5KVIh39cFqOIrh9vSYReTY0M2iokx/s320/gommettes.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Stickers (gommettes in French) about to be misused</td></tr>
</tbody></table><div class="separator" style="clear: both; text-align: center;"><br />
</div><div class="separator" style="clear: both; text-align: center;"><br />
</div>Well, now it's easy! Just go to <a href="http://slowfrog.com/polychrome/polychrome.html">polychrome</a> and try the options. The application is a small and quick hack and does not look like much for now, but it will improve. The next things to be built are image upload, and parallel processing using webworkers.<br />
<br />
In the meantime, you can still display a few sample models, ready to be used.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhapxm27yMa_srSnLh7h9jbY1XjgJ2Lf0gTEE7lJQwd5YhyphenhyphenmN2Kdo5q1fVQYXjlfS-12_laWh39tW632RFG9jBDTCiuyWMoSrocNDld4lOIbT7KfVxVwX1gVN09Xk1Kv0FGwoBuMv6hFC9D/s1600/polyfox.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhapxm27yMa_srSnLh7h9jbY1XjgJ2Lf0gTEE7lJQwd5YhyphenhyphenmN2Kdo5q1fVQYXjlfS-12_laWh39tW632RFG9jBDTCiuyWMoSrocNDld4lOIbT7KfVxVwX1gVN09Xk1Kv0FGwoBuMv6hFC9D/s1600/polyfox.png" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Model for the Firefox logo made from 7-color stickers</td></tr>
</tbody></table>Laurent Vaucherhttp://www.blogger.com/profile/13286811917069686050noreply@blogger.com0tag:blogger.com,1999:blog-5276958884676424644.post-89732899234013327352011-08-15T15:07:00.000+02:002011-11-04T00:21:29.983+01:00Grunt work going onFor the last four months, I've been using almost all my free time writing a web port of a free game. That's why I did not post any new inflammatory benchmark or computer-aided game solution.<br />
<br />
It might seem strange, but the game I'm porting, whose name I will not reveal yet, is only available as a Windows or OSX binary. I like the game very much and wanted to share it with some of my Linuxy friends, so I thought: "Rebuilding the game based on HTML/JS should not be that hard, and then, everybody with an Internet access and a modern browser could enjoy the game, without OS dependency or installation."<br />
<br />
I'm making good progress on the game itself. It's not a graphics-heavy game, but more of a content-rich game and although the main game mechanics have been in place for a good time now, I'm still adding all the content, and that takes time. It doubly takes time, because I have to do research on the original game, to discover what needs to be implemented, and after that, I have to replicate it into the new game.<br />
<br />
So what's the game? Sorry, but I will not reveal it just now. I have been in touch with the original developers because it's a free game, but not an open source one. I don't want to steal anything from them, and I hope we can reach some kind of agreement. They are currently trying to transform the original free game into a commercial one, far richer both in terms of graphics and content. I only want to replicate the free one, without killing their sales. Maybe it could even help their sales: like the current free version, it acts as a free appetizer.Laurent Vaucherhttp://www.blogger.com/profile/13286811917069686050noreply@blogger.com0tag:blogger.com,1999:blog-5276958884676424644.post-39365480169350561512011-05-29T17:11:00.000+02:002011-11-04T00:22:21.325+01:00Web Workers faster than (naive) C++ [edited]<style>
* {
font-family: sans-serif;
font-size: 12px;
}
table {
border-collapse: collapse;
}
th, td {
border: 1px solid grey;
padding: 3px;
}
th {
font-size: 130%;
background-color: #e0e0e0;
}
td {
text-align: right;
}
.best {
background-color: #d0ffd0;
}
.worst {
background-color: #ffd0d0;
}
.crash {
background-color: black;
color: white;
}
</style><br />
<div style="font-style: italic">[EDIT] The main problem with the C++ version was probably the platform (Cygwin). So I re-ran the same program on Linux inside VirtualBox on the same machine and the results are not so catastrophic. I also ran the Python program with PyPy and it's twice as fast as CPython on that problem (Thanks to Alex Gaynor for trying it first).<br />
</div><div><br />
</div><div>I don't mean that to stir the controversy. If someone with great C++ skills could explain what I did wrong, I'd be glad to learn. So here is the story.</div><div><br />
</div><div><span class="Apple-style-span" style="font-size: x-large;">Multi-language parallel processing comparisons</span><br />
<div><br />
</div>It all began last week with Google Code Jam <a href="http://code.google.com/codejam/contest/dashboard?c=1145485#s=p1">problem B in round 1A.</a> The problem is the following. Two guys are playing hangman. They have a common dictionary of allowed words. The guy who tries to guess has a very simple strategy. He has a fixed list of letters that he will propose in order. However, he will skip letters that cannot appear in the word in the current state of the game. Each time he proposes a letter that does not appear in the word, the other guy makes one point. Your goal is to find the word that will make the most points, knowing the dictionary and the ordered list of letters of the guy who guesses.</div><div>I have written a solution with the same algorithm in four languages: Python, Java, C++ and JavaScript. I also wanted to get some knowledge of the parallel processing capabilities of those languages. In Python, I used the multiprocessing module, in Java, package java.util.concurrent with ExecutorService, in C++, OpenMP and in JavaScript HTML5 web workers. Here are the running times.</div><div></div><br />
<table cellpadding="0" cellspacing="0"><tbody>
<tr> <th rowspan="2" style="background-color: white; border: none;"></th> <th rowspan="2">Single</th> <td rowspan="7" style="border-bottom: none; padding: 1px;"><br />
</td><th colspan="3">Multi</th> </tr>
<tr> <th>1 worker</th> <th>4 workers</th> <th>6 workers</th> </tr>
<tr> <th>Java</th> <td class="best">26"</td> <td class="best">27"</td> <td>18.5"</td> <td>17.5"</td> </tr>
<tr> <th>C++ Linux</th> <td>33"</td> <td>33"</td> <td>20"</td> <td>21"</td> </tr>
<tr> <th>C++ Cygwin</th> <td>58"</td> <td>59"</td> <td class="worst">30'00"</td> <td class="worst">28'00"</td> </tr>
<tr> <th>PyPy</th> <td>1'04"</td> <td>1'08"</td> <td>27"</td> <td>26.5"</td> </tr>
<tr> <th>Python</th> <td class="worst">2'30"</td> <td class="worst">2'35"</td> <td>50"</td> <td>44"</td> </tr>
<tr><td colspan="6" style="border-bottom: none; border-top: none; font-size: 1px; padding: 0px;"></td></tr>
<tr> <th>JS Chrome</th> <td>44"</td> <td rowspan="4" style="border-top: none; padding: 1px;"></td> <td>45"</td> <td class="best">15.3"</td> <td class="best">14"</td> </tr>
<tr> <th>JS Opera</th> <td>1'17"</td> <td>1'17"</td> <td>1'21"</td> <td>1'35"</td> </tr>
<tr> <th>JS IE</th> <td>1'30"</td> <td class="crash" colspan="3" style="text-align: center;">No web workers</td> </tr>
<tr> <th>JS Firefox</th> <td>1'34"</td> <td class="crash">crash<br />
1'14" for 9</td> <td class="crash">crash</td> <td class="crash">crash</td> </tr>
</tbody> </table><br />
<div>Best times are highlighted in green in each column, worst times in red, crashing or unavailable solutions in black.<br />
<br />
The code is available <a href="https://github.com/slowfrog/hangman">in github</a>, with extensive explanations on how to build and run it. The HTML5 web workers solution can be tested right <a href="http://www.slowfrog.com/hangman/hangman.html">in your browser.</a> To run the program in non-web worker mode, just click the "Run without workers" button. Be aware that the browser will probably tell you every few seconds that a script is making the page unresponsive. You need to allow it to continue if you want it to finish.</div><div>To run the program with web workers, you need to create a pool first. When you do that, a row of green squares will appear, to track the activity of allocated workers. Then, launch the computation with "Run". The "Queue size" will move briefly to 10, workers will turn red when busy. The result will appear once the queue is empty and all workers have finished.</div><div><br />
</div><div><span class="Apple-style-span" style="font-size: x-large;">Observations</span></div><div><br />
</div><div><span class="Apple-style-span" style="font-size: large;">About the C++ program</span><br />
<br />
My first surprise is that I could not make my C++ program run as fast as the Java solution. My C++ skills are rusty, for sure, but when I wrote some numerical things not too long ago, I had no problem making them go two or three times faster than Java. This time, there is a lot of string and map handling and I guess my performance problems might come from too much memory allocation. I used gprof to locate potential hotspots, but nothing meaningful appears. I would genuinely be interested if some C++ wizard could explain how to fix that. <span style="font-style: italic">[At least on Linux it's better than with Cygwin]</span><br />
</div><div><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="border-collapse: collapse; font-family: sans-serif; font-size: 12px; margin-bottom: 0.5em; margin-left: auto; margin-right: auto; padding-bottom: 6px; padding-left: 6px; padding-right: 6px; padding-top: 6px; text-align: center;"><tbody style="font-family: sans-serif; font-size: 12px;">
<tr style="font-family: sans-serif; font-size: 12px;"><td style="border-bottom-color: grey; border-bottom-style: solid; border-bottom-width: 1px; border-left-color: grey; border-left-style: solid; border-left-width: 1px; border-right-color: grey; border-right-style: solid; border-right-width: 1px; border-top-color: grey; border-top-style: solid; border-top-width: 1px; font-family: sans-serif; font-size: 12px; padding-bottom: 3px; padding-left: 3px; padding-right: 3px; padding-top: 3px; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjOIyoCy7BTWf5lRYUSluYiOGF2A-AaPVzdimhQOJzXPDYJHZUXutOiQRyGVmu4m2y1Jj2S8MZcGlbSKAkIgwUGMqTt48hj5UrLNdCemlrZ4E5eXdDWWM9h7u2dzzy3ipYXts64bE5YMfl6/s1600/cpp_cpu.png" imageanchor="1" style="font-family: sans-serif; font-size: 12px; margin-left: auto; margin-right: auto;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjOIyoCy7BTWf5lRYUSluYiOGF2A-AaPVzdimhQOJzXPDYJHZUXutOiQRyGVmu4m2y1Jj2S8MZcGlbSKAkIgwUGMqTt48hj5UrLNdCemlrZ4E5eXdDWWM9h7u2dzzy3ipYXts64bE5YMfl6/s1600/cpp_cpu.png" style="cursor: move; font-family: sans-serif; font-size: 12px;" /></a></td></tr>
<tr style="font-family: sans-serif; font-size: 12px;"><td class="tr-caption" style="border-bottom-color: grey; border-bottom-style: solid; border-bottom-width: 1px; border-left-color: grey; border-left-style: solid; border-left-width: 1px; border-right-color: grey; border-right-style: solid; border-right-width: 1px; border-top-color: grey; border-top-style: solid; border-top-width: 1px; font-family: sans-serif; font-size: 10px; padding-bottom: 3px; padding-left: 3px; padding-right: 3px; padding-top: 4px; text-align: center;">C++ 4-workers CPU profile</td></tr>
</tbody></table><br />
The second suprise is that using parallel processing actually made things worse, much much worse! Read the numbers: 30 <i>minutes</i> for the 4-workers C++ when Chrome takes 15 seconds. Actually it reinforces the hypothesis that my performance problems come from memory allocation. The multiple threads of execution are fighting each other for memory and provoke contention. That would explain the fact that the program only consumes 25% CPU, a big part of which is system time. <span style="font-style: italic">[Yet again, on Linux the multi-threaded version sees a good increase in performance. Cygwin probably has to do much more work.]</span><br />
<br />
<span class="Apple-style-span" style="font-size: large;">About Firefox 4</span><br />
<br />
The sequential solution, using only the main JavaScript thread, has a very curious memory profile.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjqdmoGr0vvepJNWxuJLO8MS1iMHTJNT9Aqh-3rapOwWo8XNJBo34LPu64h2J8yXTS9U1nHt_hmItAtzdiXaYu0IF0dgiAFVEY_bjpTIbA1RfxztrrKi61cLPI4thNYQt-NRaQEmNwZEhli/s1600/firefox_cpu.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjqdmoGr0vvepJNWxuJLO8MS1iMHTJNT9Aqh-3rapOwWo8XNJBo34LPu64h2J8yXTS9U1nHt_hmItAtzdiXaYu0IF0dgiAFVEY_bjpTIbA1RfxztrrKi61cLPI4thNYQt-NRaQEmNwZEhli/s1600/firefox_cpu.png" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Firefox non-worker solution</td></tr>
</tbody></table><br />
It looks like memory is never reclaimed during the execution, only after the function has finished running.<br />
<br />
When running the 4-worker solution, Firefox CPU profile is similar to the C++ one: only 40% used and at least three quarters of that is system time. Using Process Explorer, I would conclude that Firefox uses threads for workers and probably meets memory contention too.<br />
<br />
What is more troublesome is that Firefox cannot reliably compute the solution using web workers. Firebug catches some exceptions during execution. But those exceptions never occur in other browsers, or even in Firefox when running without workers. Among the ten tasks that workers have to process, there is generally one or two that produce an exception. It is sometimes possible to solve nine of the ten cases with one worker, but not always. And with four workers, it cannot even finish four cases. I have really no idea what is wrong.<br />
<br />
<span class="Apple-style-span" style="font-size: large;">About Opera 11</span><br />
<br />
Opera performs quite well without workers. With workers, it performs the same. In fact, the more workers you add, the worse it performs. I guess that it uses "green threads", not native ones. No new threads appear in Process Explorer when launching workers and CPU use is always around 25%. With more workers, there is more work for the internal scheduler and some more seralization of data to do. That's what explains the slight degradation of running times.<br />
<br />
<span class="Apple-style-span" style="font-size: large;">About Internet Explorer 9</span><br />
<br />
IE9 does not support web workers, so I only tested the standard solution. The performance is reasonable. It is worse than Chrome and Opera, but a bit better than Firefox.<br />
<br />
<span class="Apple-style-span" style="font-size: large;">About Chrome 13</span><br />
<br />
Chrome is impressive, no doubt about that. The standard JavaScript solution is already the fastest of the browser pack (twice faster than Firefox and IE), and it benefits greatly from added workers. Using separate OS processes (like Python multiprocessing module) makes it immune to memory contention.<br />
<br />
<span class="Apple-style-span" style="font-size: large;">About Java</span><br />
<br />
Java is a still a bit faster than Chrome V8 JavaScript in single-threaded mode. However, the gain when using multiple workers is not as big as expected: only 1.5 times faster with four workers when Python or Chrome go three times faster with four processes. I don't know why this is so and I don't have a precise idea how to diagnose. It might be a kind of memory contention, as with other multi-threaded implementations, except it does not appear as system time, because the JVM manages memory by itself.<br />
<br />
<span class="Apple-style-span" style="font-size: large;">About Python</span><br />
<br />
I initially wrote my solution in Python, because the language feels so good. When ran with PyPy (1.5.0-alpha0) it can perform twice as fast as with CPython. That's great news!<br />
<br />
<span class="Apple-style-span" style="font-size: x-large;">Conclusions and open questions</span><br />
<br />
I welcome all comments, on why my C++ solution is so slow, why Firefox fails with workers, and anything else. In the meantime, I will finish and release my micro-library to provide a Python-like Pool API above web workers, knowing that today, only Chrome can use it for heavy lifting.<br />
<br />
</div>Laurent Vaucherhttp://www.blogger.com/profile/13286811917069686050noreply@blogger.com3tag:blogger.com,1999:blog-5276958884676424644.post-37838462480002467692011-05-26T01:37:00.000+02:002011-11-04T00:21:29.971+01:00Taking advantage of multiple cores with JavaScript web workers<span class="Apple-style-span" style="font-size: x-large;">I'm at it again! </span><div><br />
</div><div>This time, I wanted to test the performance of JavaScript for solving the same problem I already described previously. And I chose to jump at the chance to perfect my knowledge of HTML5 web workers.</div><div><br />
</div><div>My main resource for learning how to use web workers was <a href="http://www.html5rocks.com/tutorials/workers/basics/">this introduction on HTML5Rocks</a>. I used Chrome v13 for my tests. If you try this at home and point to local filesystem files, don't forget to launch a fresh Chrome instance with the <span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">--allow-file-access-from-files</span> command-line switch, otherwise you will receive some strange security errors. The other possiblity is to run from a local web server.</div><div><br />
</div><div>At first, I couldn't seem to start a worker correctly. Or at least, my worker did not seem to receive messages. I was calling:</div><div><span class="Apple-style-span" style="background-color: black; color: lime; font-family: 'Courier New', Courier, monospace;">self.addEventListener('message', handleMessageFunction, false);</span></div><div><span class="Apple-style-span" style="background-color: black; color: lime; font-family: 'Courier New', Courier, monospace;"><br />
</span></div><div>I had to change it to the following form to make it work:</div><div><div><span class="Apple-style-span" style="background-color: black; color: lime; font-family: 'Courier New', Courier, monospace;">self.addEventListener('message', function(e) { slave.handleMessage(e); }, false);</span></div></div><div><span class="Apple-style-span" style="background-color: black; color: lime; font-family: 'Courier New', Courier, monospace;"><br />
</span></div><div>So, passing just a function reference as second argument did not seem to work, even though the function existed, was valid, was not a prototype method and had the right signature.</div><div><br />
</div><div>Once I had overcome that "glitch", everything went smoothly. I re-implemented my Python algorithm in pure JavaScript. I tried it directly (without workers). I had to acknowledge a few times that, indeed, a script on the page was taking some time to complete. And it finished in about 45". Nice performance for JavaScript!</div><div><br />
</div><div><span class="Apple-style-span" style="font-size: x-large;">To the core(s)</span></div><div><br />
</div><div>Having been spoilt by the nice Pool API from Python multiprocessing package, I embarked upon a journey to implement something similar with web workers. Basically, I created a protocol of messages to be exchanged between the workers and the pool driver. It is not polished, but it works well already. You can see the result <a href="http://www.slowfrog.com/workers/problemB.html">here.</a> Quick explanation:</div><div><ul><li><b>"Create pool"</b> creates the worker pool with the requested number of workers. Workers are materialized by colored squares with a number. When the square is red, the worker is busy; when green, it's idle.</li>
<li><b>"Run"</b> sends all problem cases to the pool. The size of the queue should increase. It is the number of tasks not yet taken by a worker.</li>
<li><b>"Kill"</b> kills all workers and drops the pool, so that you can create a new one with a different number of workers.</li>
</ul></div><div><br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi25KdogJE2VinBWHOqXg7df0zN_u9NaHA6vw2JZR60EBNGbhB84udLQCxSIWvdqsLB0IcEOlI2aTDcsJ7WWmI85FpKiErIapOpuaI-Mrrd-SV4KgptOcqSHJ24VbvPJ0XZ7nj9fLCvYG0b/s1600/workers.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="296" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi25KdogJE2VinBWHOqXg7df0zN_u9NaHA6vw2JZR60EBNGbhB84udLQCxSIWvdqsLB0IcEOlI2aTDcsJ7WWmI85FpKiErIapOpuaI-Mrrd-SV4KgptOcqSHJ24VbvPJ0XZ7nj9fLCvYG0b/s400/workers.png" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Web worker pool demo</td></tr>
</tbody></table>The input field is preloaded with the large problem set. On Chrome with four workers, the runtime is divided by three, compared to the single-threaded version: the problem is solved in about 15". Chrome does not seem to impose limitations on the number of workers that can be started. I tried with ten, and the results was almost identical. My machine was, of course, 100% busy.</div><div><br />
</div><div>Opera performs nicely on this one too, with the same code. Single-threaded solution in 75", four-worker solution in 75". Opera correcly creates the requested number of workers, but it probably does not use OS-level threads. They might only be "green-threads", with an internal scheduler, which would explain why only 25% of the CPU is consumed.</div><div><br />
</div><div>Firefox 4 gives me some problems, maybe because of memory limits or the size of the input value. The program runs unmodified, but you have to change the first input line from 10 to 8. I don't know why it chokes on the ninth and tenth cases. The single-worker version runs in 76". The four-worker one does not consume all available CPU. It's stuck at about 50% and consumes a lot of system time. Only three workers are busy simultaneously. And it runs in 230". So much for the performance gain.</div><div><br />
</div><div>And IE9, with its native HTML5 support... just kidding.</div><div><br />
</div><div><span class="Apple-style-span" style="font-size: x-large;">tl;dr</span></div><div><br />
</div><div>Chrome is fast, has great support for web workers. <a href="http://www.slowfrog.com/workers/problemB.html">Demo here.</a></div>Laurent Vaucherhttp://www.blogger.com/profile/13286811917069686050noreply@blogger.com0tag:blogger.com,1999:blog-5276958884676424644.post-77400409936290388562011-05-23T21:46:00.000+02:002011-11-04T00:22:21.328+01:00C++ slower than Java and Python!<span class="Apple-style-span" style="font-size: x-large;">... when badly programmed</span><br />
<br />
I was still trying to squeeze the most performance out of my solution to <a href="http://code.google.com/codejam/contest/dashboard?c=1145485#s=p1">the hangman problem</a> from round 1A of <a href="http://code.google.com/codejam/">Google Code Jam 2011</a> and so I decided to give C++ a try. C++ is like a long forgotten friend to me. I started my paid carreer with it, almost twenty years ago. I learned some tricks with the STL, template methods and other fun things. I already had a humble background in C, so pointers, memory manipulation and the like were still fresh in my head.<br />
<br />
Today I simply tried to port my Python algorithm to C++, as straightforwardly as possible - I don't know if "straightforwardly" is a very usual adverb, but I'm French, so please excuse me if it isn't. With some vague memories about memory allocation I tried to use reference types as much as possible, to avoid unnecessary copying. I used <span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">string</span>, <span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">vector<></span>, <span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">map<></span> quite easily. I wrote very simple input and output with <span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">cin </span>and <span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">cout</span>. I had a valid C++ program in no time. I ran it on the small input set. It was immediate and gave the right result. <a href="http://en.wikiquote.org/wiki/Wallace_and_Gromit">"Everything's under control"</a> I thought.<br />
<br />
Then I ran it over the large set, and it took 3'30": one minute longer than the Python version! Can you imagine?!<br />
<br />
gprof to the rescue. I tweaked one heavily used string manipulation function. 3'. Still not fantastic. I realized that <span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">map<></span> was based on ordering and offered log(n) access time: I switched to <span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">unordered_map<></span> to get a hashmap implementation. Around 2'30". Now it was as fast as Python (but still five times slower than the Java version). And now gprof did not give my anything interesting. A few mangled symbols appeared on top, especially with <span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">-O3</span> compilation. I tried to reduce the number of string allocations, using <span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">string const &</span> as much as possible, but to no avail. I started to think that C++ was definitely not good at string handling. I thought that maybe using Cygwin g++ was suboptimal. I tried g++ on Linux. Still the same order of performance.<br />
<br />
<span class="Apple-style-span" style="font-size: x-large;">And then I saw the light</span><br />
<br />
In the middle of my main algorithm loop, I was swapping big maps. Real map objects, not references. So each iteration of the loop would do a complete copy of the previous map. Arghh! C++ memory allocation is quirky, coming from managed languages like Java, Python or JavaScript. Replacing those maps by references gave the top rank back to C++: 17" for the single-threaded version, running on a single core and not even compiled with optimization. L'honneur est sauf.<br />
<br />
<span class="Apple-style-span" style="font-size: x-large;">Lessons learned</span><br />
<br />
<ul><li>It's far less difficult to work with C++ and the STL than I expected, for problems like those from Code Jam.</li>
<li>However, manual memory management is something you always have to keep in mind.</li>
<li>My newbie usage of gprof did not allow me to track superfluous data structure copying. If you have any suggestions in that domain, I'll be glad to hear them.</li>
</ul>Laurent Vaucherhttp://www.blogger.com/profile/13286811917069686050noreply@blogger.com0tag:blogger.com,1999:blog-5276958884676424644.post-1380838964033388522011-05-22T20:03:00.000+02:002011-11-04T00:22:21.321+01:00Taking advantage of multiple cores with Python and JavaThe first round of <a href="http://code.google.com/codejam/">Google Code Jam 2011</a> has just ended. I participated in round 1A, waking up at 3AM on a week-end day (to tell you how motivated I was). The first problem was not too difficult, but it still took me a good 45 minutes to solve. Then came the second one, <a href="http://code.google.com/codejam/contest/dashboard?c=1145485#s=p1">The Killer Word</a>: the one where you have to find the hardest word for your opponent to guess in a game of hangman. I implemented the solution the way it was described, but my first small attempt failed.<br />
<br />
I dug into the code again, and found a rule I had not implemented. Alas, my next attempt was also a failure. I had to try harder. Another bug fix later, my third submission was still not right. Time was running low. About twenty minutes before the end my rank was around 900th and falling. If I could not submit another valid solution, I would probably fall behind the qualifying 1000th rank.<br />
<br />
After another pass over the code, I found yet another subtlety that I had not taken into account. Clickety-clickety-click (I have a "Das Keyboard" that really clicks, if you want to know). Another submission. Fingers crossed. And... yes! Now it was right. The small problem set was now solved. My rank raised to 500th. I was saved. Time to download a large problem set and run the program over it. Eight minutes should be plenty. The dictionary size was multiplied by 100 and the list of letters by 10, but it should be ok... Except it was not. Not at all, by a long shot.<br />
<br />
<span class="Apple-style-span" style="font-size: x-large;">Sleeping over it</span><br />
<br />
With the knowledge of my qualification and still the problems in my head, I went to bed. When I woke up, I thought that perhaps a multithreaded implementation could have saved my attempt at solving the large problem set. As a first step, to speed up the program, I rewrote it from Python to Java. Straightforward, if a little dull. It ran faster, but still it was impossible for that algorithm to succeed in less than eight minutes on the large set. So: back to thinking.<br />
<br />
I implemented a solution another way: instead of computing the score of each dictionary word in turn, I processed all words at once, keeping only the best one at the end. I programmed that new algorithm in Python again, because I really love its "runnable pseudo-code" feeling: no need to write types, literal syntax for everyday structures (tuples, arrays, dictionaries). I ended up with a valid solution that managed to solve the large set in about 2'30". Not too bad for Python.<br />
<br />
<span class="Apple-style-span" style="font-size: x-large;">Going multicore</span><br />
<br />
The Python solution was now adequate, but the idea to take advantage of the mutiple cores of my machines was still in my head. So I decided to crawl the web and the excellent reference documentation for Python. My first reflex was to look at the <a href="http://docs.python.org/library/thread.html">thread</a> and <a href="http://docs.python.org/library/threading.html">threading</a> modules. But, as you probably know, the standard CPython implementation relies on a Global Interpreter Lock (the GIL) that practically makes multithreading useless, except for handling concurrent blocking I/O. Fortunately, the documentation pointed me to the <a href="http://docs.python.org/library/multiprocessing.html">multiprocessing</a> module. The basic principle is that instead of creating thread inside the Python VM, that module allows to create OS-level processes, each one running a distinct Python VM, but with communication channels established between them, so that you don't have to leave the comfy Python environment. And of course, it's as platform-independent as possible.<br />
<br />
For my needs, I looked at the Process class, but rapidly learned about the Pool class. The API is perfect, almost magic. You create a Pool object (Python guesses the number of CPU for you). You assign it all the functions you want to run asynchronously. You close it, which means you have no more work for it to do. You join it (you wait for all workers to process the functions). And you only have to get the results and sort them. That's all. In code, it looks like that:<br />
<br />
<pre style="background: #f0f0f0; border: 1px dashed #CCCCCC; color: black; font-family: arial; font-size: 12px; height: auto; line-height: 20px; overflow: auto; padding: 0px; text-align: left; width: 99%;"><code style="color: black; word-wrap: normal;"> def solve_with_pool(cases):
from multiprocessing import Pool
pool = Pool()
async_results = [pool.apply_async(solve_case, args=(case,))
for case in cases]
pool.close()
pool.join()
results = [ar.get() for ar in async_results]
results.sort()
return results
</code></pre><br />
It's difficult to get easier than that. <span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">solve_case()</span> is the function that, as the name implies, solves a case and returns the result as a tuple whose first element is the case index. That's why the simple call to <span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">results.sort()</span> works: it sorts all results by index. In fact, it's probably useless, because the results list is built in the right order... Anyway, with that in place, the program runs now in 50", which is three times faster than the single-threaded version, on my quad-core machine. The speedup factor is not four, because the division of work I have made is coarse-grained and there are only ten cases in the large set. So one of the processes probably got to work on two large cases and ended some time after the others had finished. Still, not too bad for ten lines of code.<br />
<br />
<span class="Apple-style-span" style="font-size: x-large;">And Java?</span><br />
<br />
If you read the title of this post thoroughly, you've seen Java in there. So. I remembered Java 1.6 standard library included a part of Doug Lea fork-join framework that was previously distributed as a separate package. Except it does not. It's planned to be included in the upcoming JDK 1.7. So in the meantime, I'll have to resort to simpler constructs. But at least, I think <a href="http://download.oracle.com/javase/6/docs/api/java/util/concurrent/package-summary.html">java.util.concurrent</a> will give me a higher level interface than direct use of Thread and synchronization.<br />
<br />
The principles are the same as the Python version, but of course, Java is a bit more verbose, mainly because of explicit typing and also because it lacks first-class functions. So I have to create a <span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">FutureTask</span>, built from an anonymous class derived from <span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">Callable</span>. Otherwise, the API is at the same level: a pool of executors, each one is executed, the pool is shut down, we wait for all computations to end (for one day, because we are forced to provide a timeout value), and then we collect all results. The managed exceptions also add a bit to the verbosity: both <span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">awaitTermination()</span><span class="Apple-style-span" style="font-family: inherit;"> and </span><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">get()</span> can raise some exceptions that are of no interest in our case.<br />
<br />
<pre style="background: #f0f0f0; border: 1px dashed #CCCCCC; color: black; font-family: arial; font-size: 12px; height: auto; line-height: 20px; overflow: auto; padding: 0px; text-align: left; width: 99%;"><code style="color: black; word-wrap: normal;">
public static Result[] solve_with_pool(Case[] cases) {
ExecutorService pool = Executors.newFixedThreadPool(4);
FutureTask<Result>[] fresults = new FutureTask[cases.length];
for (int i = 0; i < cases.length; ++i) {
final Case c = cases[i];
fresults[i] = new FutureTask<result>(new Callable<Result>() {
public Result call() {
return solve_case(c);
}
});
pool.execute(fresults[i]);
}
pool.shutdown();
try {
pool.awaitTermination(1, TimeUnit.DAYS);
Result[] results = new Result[cases.length];
for (int i = 0; i < cases.length; ++i) {
results[i] = fresults[i].get();
}
return results;
} catch (InterruptedException e) {
} catch (ExecutionException e) {
}
return null;
}
</result></code></pre><br />
The net gain from going multithread in my case is less impressive than in Python. The single-threaded program solved the large input set in 25" while the multi-threaded one took 18". I have not investigated why.<br />
<br />
<span class="Apple-style-span" style="font-size: x-large;">Conclusion</span><br />
<br />
Well, turning a single-threaded problem solving program into a multi-process or multi-threaded version is not too difficult. The available APIs sit at the right level of abstraction, both in Python and Java. The runtime gains are significant. Of note, the Java program, when running full steam on all four cores tended to make the whole PC sluggish, with the mouse pointer moving less smoothly than it should.<br />
<br />
Now I know. And hopefully you do too.Laurent Vaucherhttp://www.blogger.com/profile/13286811917069686050noreply@blogger.com0tag:blogger.com,1999:blog-5276958884676424644.post-76302099594440151242011-03-31T22:45:00.000+02:002011-11-04T00:22:06.552+01:00Genetically engineered Qwop (part 1)<div style="text-align: justify;">You might have heard about QWOP. I didn't. That's a comment on Reddit that made me discover "the hardest game ever." I believe the original home page for the game is at <a href="http://www.foddy.net/Athletics.html">foddy.net</a>. Go try to play it before reading on. You might end up very frustrated, or alternatively rolling on the floor laughing (while Qwop is in fact creeping on the ground, doing negative scores).</div><div style="text-align: justify;"><br />
</div><div class="separator" style="clear: both; text-align: justify;"></div><div style="text-align: justify;"><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEglezsbip376hY8sTqJFZu_4DTFNo-rH2-lfujzrvUwjWLzIENocFQ4shLgeBHL18zxx9GyyWneUWwf_x-mg96IaGzHOEe-ewBp9lqwh2kkb6UhbDIq-dyS-8iBYAJOJVc9movcI4HStE__/s1600/play.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="200" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEglezsbip376hY8sTqJFZu_4DTFNo-rH2-lfujzrvUwjWLzIENocFQ4shLgeBHL18zxx9GyyWneUWwf_x-mg96IaGzHOEe-ewBp9lqwh2kkb6UhbDIq-dyS-8iBYAJOJVc9movcI4HStE__/s320/play.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Wrong way...</td></tr>
</tbody></table><br />
</div><div style="text-align: justify;">After some time trying hopelessly to master the limbs of the athlete, I wondered what the best way to make a playing bot would be. That's a game without an obvious solution. There is not even a way to know what to do to run better. But at least, the inputs are quite simple. That's the perfect test case for some genetic programming!</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;"><br />
<b><span class="Apple-style-span" style="font-size: large;"># The idea</span></b><br />
<br />
Ok, so what is needed for genetic programming? A form of DNA encoding, from which individual entities can be built and a fitness function telling us if the algorithm is going in the right direction. Generally, there is also a simulated environment where the entities "live."</div><div style="text-align: justify;">In my case, the simulated environment is the Flash game itself. I will only drive it with synthesized key strokes. The advantage is that it's the real thing. But there are two main drawbacks. The first is that the simulation is real-time, which is quite slow and will have to run for long hours. The second is that while running, I cannot use the computer, because the simulator is moving the mouse and generating keystrokes. Hopefully, we have virtual machines to solve the second one. I used a VirtualBox Ubuntu GNU/Linux environment to drive the game. On a standard quad-core desktop machine, it appears to run at the same speed as the non-virtual game.</div><div style="text-align: justify;"><br />
The fitness function is easy to find: it's the distance reached by Qwop before falling down, possibly combined with the time it took, to have a rough idea of speed. The interesting part is finding a DNA that generates a population vast and rich enough to host a possible winner. So what's the idea? I think that Qwop can run correctly with a repeating sequence of key strokes, at least once he reaches his cruising speed. So my DNA should produce a series of key events at some given time intervals, plus a repetition period. Let's try to formalize that.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">I will write an uppercase letter for a key down, a lowercase letter for a key up, a plus sign for a unit pause. So for instance the string "Q+qW+wO+oP+p" means "Press Q for one unit of time, then simultaneously release Q and press W for one unit of time, release W and press O for one unit of time, and the same again for P." By the way, that sequence is not so bad. Qwop can reach 100 metres with it, but quite slowly, so, we'll try to find something better.<br />
<br />
</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;"><span class="Apple-style-span" style="font-size: large;"><b># Down to the code</b></span></div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">Last time I chose to program in Python, because I love the language. But I used some Windows-specific libraries and some people were frustrated they could not see the program run on their machine. So this time I'm going to use Java. It's arguably less expressive than Python, but I know that the GUI and window interface is quite portable: my code for capturing the screen and sending synthesized key events should run unmodified on Window, Linux, Mac OSX and probably Solaris. I could even run Jython on top of the low-level calls. Or clojure for the lisp-lovers around here... For now I will start with pure Java. I will also include a functional, if rudimentary GUI to pilot the simulation.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">The main class for interacting with the desktop is java.awt.Robot. It does everything I need: capture one pixel, or a rectangle on the screen and send mouse and key events. Let's start with screen capture. I will do as with Papa's Pizzeria: take some reference screenshots and search the screen for the reference patterns. I'll try to locate the game area by finding the light blue border around the message that appears on the opening screen. It has an homogeneous color (#9dbcd0), is four pixel wide, starts at 124,103 and goes to 505,306. But as you might have noticed, almost the same message box appears when a run is finished, except it's not exactly at the same position. It's at 129,99. So, in order to make it as easy as possible to run the program, and not force you to reload the game each time, I compute the real location of the game depending on which message box is shown. And how do I know? Easy! I try to find the two bright yellow ribbons that appear on the finishing screen. That's also the way I detect when the run has ended.</div><div style="text-align: justify;"><br />
<br />
</div><div style="text-align: justify;"><span class="Apple-style-span" style="font-size: large;"><b># Going the distance</b></span></div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">The other thing I need is a way to read the current distance reached. That's the tricky part. I first thought I could apply some mathematical morphology to detect shapes, lines and characteristic points (end of lines, crossings...). That's certainly a valuable approach and I should work a little more on the theoretical part, but I finally decided to go for the easy route. I grab the part of the screen where the distance is displayed. I apply a very simple thresholding function to turn the image to black and white. Then I segment the text by finding fully empty pixel columns. And once each box is found, I match it with the reference images I have taken for all digits. The comparison sums the number of equals pixels and computes the percentage of identical pixels over the comparison area, so that small digits don't give overly low scores (like 1 or the decimal point). When the result of a comparison is over 90 % I consider it a match. Below that value, I drop the result. That way, I don't have to make a special case for letters, which don't match anything: they are naturally eliminated.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;"><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg5SWYv5jr-f2sfr2VLokUEN-9frn1-grmMdhnRnzn5nVRwAPpBX9k0fAET7IjjSAOSklA106qa6XTRnVj_u2TLTIQOL1MY0TC7TcCw-WlK5MASoVI6_eduxB95J0exWifpquWljil9rzbW/s1600/reading_digits.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg5SWYv5jr-f2sfr2VLokUEN-9frn1-grmMdhnRnzn5nVRwAPpBX9k0fAET7IjjSAOSklA106qa6XTRnVj_u2TLTIQOL1MY0TC7TcCw-WlK5MASoVI6_eduxB95J0exWifpquWljil9rzbW/s1600/reading_digits.png" /></a></div>You can see from the screenshots that my segmentation algorithm is not perfect: the letters e and t are stuck in the same box, because there is no clear column between them. Hopefully, I don't want to read the text and it seems digits are always cleanly separated on screen. Would I need to read letters, I would probably try to segment using connex parts. That would probably work here because the threshold function has done a good job, but it's close...<br />
<br />
<br />
<span class="Apple-style-span" style="font-size: large;"><b># Hurdles</b></span><br />
<br />
If you have played the game long enough, you have seen the hurdle at 50 meters. It's the only one in the game, but not in my project: I have faced several big issues, and I don't know yet if my approach will yield any good runner. The biggest trouble is that the real-time keystroke playing is not perfectly stable. The same string of key presses and pauses does not always give the same result in the game. I tried my best to send keystrokes at regular intervals, but even then, our poor athlete sometimes behaves differently. It forces me to run candidates several times and to consider statistically significant results only.<br />
<br />
Another problem I found when trying to make the simulator run for several hours is that the game probably has memory leaks. After a few hours of uninterrupted play (something no human would ever do, I have to admit), the memory consumption of the Flash player is really slowing down the whole machine. I had to code a small workaround that simulates a F5 key press at regular intervals to reload the browser page and start with a fresh Flash player.<br />
<br />
<br />
<div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span class="Apple-style-span" style="font-size: large;"><b># Going genetic</b></span></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><br />
</div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;">After the first few tries, it's obvious that the task is going to be tough. Most of my random athletes fall on their head, or fold their limbs in very unnatural ways. So, the first step is to generate enough healthy candidates to initiate the genetic pool. Let's say that the first generation should contain only runners that can reach 5 meters in less that a minute and not crash at least 50% of the time. That's the condition I will set for them to be able to "reproduce". It might seem easy. I assure you it is not. I've had to run hundreds of random Qwops to get a handful of valid ones.<br />
<br />
And that's where I am today, still running batches of random guys, hoping to generate some acceptable ones. There is no genetic programming yet. I still need to figure out what kind of mutation and reproduction I will do to try to produce better sprinters from the early cripples. I accept any good ideas you might have. I will need them, I think.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjAg3UqVUjpTlOtk6lz9Ptmc-ZCnLOZPR9iEP6bRm25MBmTOjVi-cu-AB2yPT1Y01MDbKG543QfInu-dOuHfXOQgtck-ZimcVXwG4yH9voYZcKiyHadaxCYyNKrvC5lrl7m8_1SMWm56FtN/s1600/that_hurts.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="173" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjAg3UqVUjpTlOtk6lz9Ptmc-ZCnLOZPR9iEP6bRm25MBmTOjVi-cu-AB2yPT1Y01MDbKG543QfInu-dOuHfXOQgtck-ZimcVXwG4yH9voYZcKiyHadaxCYyNKrvC5lrl7m8_1SMWm56FtN/s400/that_hurts.png" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Ouch! That really hurts!</td></tr>
</tbody></table><br />
<br />
<span class="Apple-style-span" style="font-size: large;"><b># If you want to try</b></span><br />
<br />
The code is hosted at gihub <a href="https://github.com/slowfrog/qwopper">https://github.com/slowfrog/qwopper</a>. Running '<span class="Apple-style-span" style="background-color: black; color: lime; font-family: 'Courier New', Courier, monospace;">ant package</span>' in the top-level directory should produce a jar file in the dist/ directory. Running the jar directly will open a small UI where you can launch some runs. The simulation can also be run from the command line like '<span class="Apple-style-span" style="background-color: black; color: lime; font-family: 'Courier New', Courier, monospace;">java -cp dist/qwopper.jar com.slowfrog.qwop.ui.Main 10 5</span>'. That will run five different random athletes, each one for ten tries. Currently, that simulation automatically stops the runner after one minute, to avoid wasting too much time on the first batch.<br />
<br />
</div></div>Laurent Vaucherhttp://www.blogger.com/profile/13286811917069686050noreply@blogger.com8tag:blogger.com,1999:blog-5276958884676424644.post-8695909579248848712011-02-10T00:06:00.001+01:002022-04-08T17:23:20.185+02:00Making Pizza with Python<div style="text-align: justify;"> I read a post on Reddit recently from a guy who wrote a Python program to play Bejeweled automatically. Since I've always be interested in the concept of programs driving other programs, I decided to try to write a program to play a more sophisticated game. I chose Papa's Pizzeria, by Flipline Studios. You can find the game at <a href="http://www.kongregate.com/games/FliplineStudios/papas-pizzeria">Kongregate</a>. In the game, you are Roy, the delivery boy of the pizzeria. You come to work one day, and Papa is missing. He left you a note to tell you he is gone and asks you to run the pizzeria yourself. Customers are already arriving at the door, so you have no choice but to try to measure up.<br />
<br />
</div><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjZmoUrOdYCg4cTkn0dw_krM_NQ4q49n9bhPBeWBNS-XrBc4gDAQ2Mrhj4fbknrYFIZWFT5bag6Z3LoNjjFL1Y2v1rwiKV5a058wn8UMNFTVAytkDIL6ChlbAtWlO3A0GMNJACyfmQRuL1u/s1600/customers.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="240" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjZmoUrOdYCg4cTkn0dw_krM_NQ4q49n9bhPBeWBNS-XrBc4gDAQ2Mrhj4fbknrYFIZWFT5bag6Z3LoNjjFL1Y2v1rwiKV5a058wn8UMNFTVAytkDIL6ChlbAtWlO3A0GMNJACyfmQRuL1u/s320/customers.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Roy running the shop</td></tr>
</tbody></table><div style="text-align: justify;"><br />
</div><div style="text-align: justify;"> To play the game, you have to juggle between different tasks: take orders from customers, make the pizzas by putting the right toppings at the right places, bake them for the right amount of time and finally cut them in the correct number of slices. Customers will then rate you on those four activities. The game starts easy with only two customers to serve in one day, using only one topping and very short baking times. Then it becomes more and more difficult with up to ten customers a day, each one with several different toppings at different places, with different cutting and baking times.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;"> To be successful, you must be able to multi-task. If you do each pizza in turn, customers will wait too long and give you bad rates on that criterion. But doing several things in parallel is tricky, especially since you run the risk of missing the right baking time. Imagine you have a pizza in the oven that's just about right. If you go take another order, it might take ten seconds, and when you are back at the oven, your lovely pizza will be too baked and you will receive a mediocre baking rate. So, you have to keep things in mind, organize your order tickets the best you can in the limited space that is available, be quick when placing toppings and cutting the pies. After some time, you begin to get the knack of it and you can run a ten-customer day in around ten minutes. And that's when it starts to feel repetitive. Time to write a bot!</div><div style="text-align: justify;"><br />
</div><b><span class="Apple-style-span" style="font-size: large;">Python to the Rescue</span></b><br />
<div style="text-align: justify;"><br />
</div><div style="text-align: justify;"> What is needed to write a pizza baking bot? At the most basic level, three things: a way to recognize what happens on the screen, a way to act in the game, and some thinking between those two. I won't dare to call it AI, at least in my implementation. It sure won't pass the Turing test!<br />
If you want to jump right in and see the bot in action, skip the boring explanations and go to the last section.<br />
<br />
</div><b><span class="Apple-style-span" style="font-size: large;">Reading the screen</span></b><br />
<br />
<div style="text-align: justify;"> So, how does my pizzabot know what's on screen? Well, I'm not ashamed to tell you there is no complex image recognition in play. The program takes screenshots of portions of the screen and compares the pixels with some expected values. It probably makes the bot more fragile and less flexible, but a hell of a lot easier to program and faster to run. It also helps that the game is somewhat slow: it's not an action game where you have to react in a tenth of a second.<br />
<br />
</div><div style="text-align: justify;"> I used two main methods to read the screen. The first one is simply to compare one precise pixel with its expected color. For instance on the image below, what you can see is a close-up of the bottom left corner of an order ticket, where the baking time appears. I manually took screenshots of all possible values, blended everything on one image, chose a set of very significant pixels (pointed by the blue arrows) and read the expected RGB values of those pixels. When trying to determine baking time, the bot makes a small screenshot (the blue rectangle) and compares each significant pixel with its expected value. When there is a match under a given tolerance, it's done.<br />
<br />
</div><div class="separator" style="clear: both; text-align: center;"></div><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi94QHUyVdNWu8h-hRwqYgnMGz6lwAjY125R2Tt5boNRawv1A7ufgyW2cXHX0b_wAvFlY7F65J2-lJKLh-G-R9DhYNy2qMX8Y9EBceSacY6QYEqodgDcl-QO8CcDt8-P6e5jf4hrula85y3/s1600/baking_times.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi94QHUyVdNWu8h-hRwqYgnMGz6lwAjY125R2Tt5boNRawv1A7ufgyW2cXHX0b_wAvFlY7F65J2-lJKLh-G-R9DhYNy2qMX8Y9EBceSacY6QYEqodgDcl-QO8CcDt8-P6e5jf4hrula85y3/s1600/baking_times.png" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Reading baking time</td></tr>
</tbody></table><br />
<div style="text-align: justify;"> That's how the bot sees most game elements: button presence, beginning and end of order by a customer, baking time, number of slices, topping positions. Also, to determine the exact position of the game on the screen at startup the same technique is used, but not with one pixel, with an array of nine pixels that must match the green chequered background at the top left of the game area. Actually several positions can match, so the bot scans the screen in 5-pixel increments (which makes the scan 25 times quicker than on the whole screen) and once a possible match is found, it tries to gently slide to the top left as long as the new position is still a match.<br />
<br />
</div><div style="text-align: justify;"> The other technique, used for reading toppings and topping counts is a simple comparison with reference images. Here, comparing only one pixel with one expected value would be too error prone. So I took screenshots of all possible toppings and all possible counts, cut small images, painted in pure blue the background portions of the images. The bot loads those images and computes a distance between what he sees on screen and the reference images. Blue pixels are not part of the comparison. I could probably have used some alpha channel, but I only had experimented with loading opaque PNG files with PIL and I figured out that blue was not too common in toppings (when was the last time you ordered a pizza with something <i>that</i> blue on it?).<br />
<br />
</div><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhq7hS25ZK1xEvJNWjYrNpCDwe0w430phUp6mzSyqlIRZG93CF8pzXSxpBrJzbtx6fDuBv-1pGxr7_ohO-I4tYdXerhBjWfUV2HGgrCq8rP4lfXNXus7EV3gViEzVaqS2AYTEo5LFRUH8YN/s1600/onion12.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhq7hS25ZK1xEvJNWjYrNpCDwe0w430phUp6mzSyqlIRZG93CF8pzXSxpBrJzbtx6fDuBv-1pGxr7_ohO-I4tYdXerhBjWfUV2HGgrCq8rP4lfXNXus7EV3gViEzVaqS2AYTEo5LFRUH8YN/s1600/onion12.png" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Comparison of toppings from screenshot with reference images</td></tr>
</tbody></table><br />
<b><span class="Apple-style-span" style="font-size: large;">Acting</span></b><br />
<div style="text-align: justify;"><br />
<div style="text-align: justify;"> That's probably the least interesting part. Most of the work was to take reference screenshots of the different screens and do some measurement to find the location of actionable items: buttons, toppings, order ticket, cutting lines. All the coordinates are stored in dictionaries or constants or even used directly in the code. I know, I know, that's dirty... But the bot is not supposed to be a big enterprise project shared among tens of people and maintained over decades. It's supposed to be fun for me to write and for you to run. Nothing more. Hopefully the functions where those magic coordinates live have meaningful names like <span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">goto_topping_station()</span> or <span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">click_save_for_later()</span>.<br />
<br />
</div><b><span class="Apple-style-span" style="font-size: large;">Thinking tactically</span></b><br />
<div style="text-align: justify;"><br />
</div><div style="text-align: justify;"> During a game, the bot keeps a record of the current status: how many orders have been taken, in which state they are, are there customers waiting in the line, what's in the oven, for how long it's been there and how much time is left before it is perfectly baked... With all that information, it regularly makes a list of possible actions, assigns some priority to all of them and picks the top one to execute. That's all very simple. The priority is just a combination of static preferences and waiting time (I prefer putting quickly in the oven an already prepared pizza when a slot is available, then taking orders or serving customers). That way, the longer an order has been in a given state, the more likely it is to be chosen as the next to be processed.<br />
There is one subtlety: taking pizzas out of the oven must always have the highest priority. That is because if you miss the ideal baking time, you risk losing a lot of points. So the "out of oven" action is managed completely out of the priority queue. When evaluating possible actions, if a pizza is about to be cooked in less than a few seconds, the bot goes to the oven and waits for the perfect time. I felt it was needed because most other actions can take for 2 to 10 seconds and they cannot be interrupted. What is also helpful is that the game seems perfectly timed. There is actually no need to read the baking indicators in the oven: one step on the scale (one eighth of a turn) is exactly 22.5 seconds long. So the bot records the time when each order is put into the oven and computes the perfect time when it will be baked. Pretty easy stuff. Thanks again to Flipline Studio, that made it easier. Actually reading moving "needles" would have been more tricky.<br />
<br />
</div><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjuaPMbg4BcjxfKj9eElj4F3l8_9LRc4pd3U5qg-IUW6HD32DPKZNyZOshIqAhyphenhyphenk-skGOXTokbX6eLeH9L4qNrC6f-EeHlj8bGKYmt_E5zgWz0hadFSntKa3jmE_zsHJ2bycjelSZINtLm_/s1600/oven.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="240" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjuaPMbg4BcjxfKj9eElj4F3l8_9LRc4pd3U5qg-IUW6HD32DPKZNyZOshIqAhyphenhyphenk-skGOXTokbX6eLeH9L4qNrC6f-EeHlj8bGKYmt_E5zgWz0hadFSntKa3jmE_zsHJ2bycjelSZINtLm_/s320/oven.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">No need to read the baking timers</td></tr>
</tbody></table><br />
<b><span class="Apple-style-span" style="font-size: large;">Putting it all together</span></b><br />
<div style="text-align: justify;"><br />
</div><div style="text-align: justify;"> That's almost all there is to say. The complete scenario of the driving function is the following:<br />
<ul><li>find the offset of the game area</li>
<li>click on "Start game"</li>
<li>choose a saved game</li>
<li>then, for as many games as asked:</li>
<ul><li>look for possible actions (take order, make pizza, put prepared pizza into oven, get pizza out of oven, cut and serve pizza)</li>
<li>execute the one that is deemed the most important</li>
<li>until the shop is closed and all orders have been processed</li>
<li>look at the results for five seconds</li>
<li>look at the tips for five seconds</li>
</ul><li> If anything goes wrong during a game (it sometimes happens), the bot exits.</li>
</ul> The five seconds waits at the end of each round is there so you have a chance to stop the program without losing your score. You can cleanly kill python and close the game.</div><div style="text-align: justify;"><br />
</div><b><span class="Apple-style-span" style="font-size: large;">Wanna try it?</span></b><br />
<div style="text-align: justify;"><br />
</div><div style="text-align: justify;"> The whole source is hosted on <a href="https://github.com/slowfrog/pizzabot">github</a>. Get it, and follow the directions:<br />
<br />
Prerequisites:<br />
<ul><li>Python 2.x. Works at least with 2.6 and 2.7. Don't know about Python 3.</li>
<li>Windows (sorry about that!) Can probably be easily adapted. Only a few functions do win32 calls (event generation only)</li>
<li>PIL for screen capture and image file loading</li>
<li>You should also have played the first day of the game: that one is special because of the intro but mainly because the tutorial is a bit intrusive.</li>
</ul><br />
</div><div>Run the bot:</div><ol><li>launch your favorite Python shell. I really like IPython, but the standard shell works the same.</li>
<li><span class="Apple-style-span" style="background-color: #ffe599; font-family: 'Courier New', Courier, monospace;">import botutil</span>, that's the only source file</li>
<li>open a browser window on the game (here's <a href="http://www.kongregate.com/games/FliplineStudios/papas-pizzeria">the address</a> again on Kongregate)</li>
<li>make sure the whole game area is visible, especially the top left corner: that's where the bot looks first. Also make sure you are on the title page (with Papa's Pizzeria title and the three yellow buttons)</li>
<li>launch the bot using a given save game for a number of rounds with <span class="Apple-style-span" style="background-color: #ffe599; font-family: 'Courier New', Courier, monospace;">botutil.start_game(save, rounds)</span>. save should be 0, 1 or 2. rounds could be anything more than zero</li>
<li>watch the bot making perfect pizzas. It always gets 100% on toppings and cutting. It gets 100% most of the time on baking, and between 90% and 100% on waiting time, which usually gives a general score around 99%.</li>
</ol><br />
<div style="text-align: justify;"> If it doesn't work for you, just ask me: maybe I forgot something. And if it works for you, you can tell me too.</div><div style="text-align: justify;">Also, I'm not a very experienced Pythonista yet, so feel free to tell me where I'm using the wrong idioms or where I have used over-complicated code.<br />
<br />
</div><div style="text-align: justify;">And enjoy your lovely baked Python pizzas!<br />
<br />
P.S. <a href="http://www.youtube.com/watch?v=oQNkTCY6tkQ">Video now available.</a><br />
<br />
</div></div>Laurent Vaucherhttp://www.blogger.com/profile/13286811917069686050noreply@blogger.com15