(nettipäiväkirja 19.10.2019) My son often makes games with Löve (https://love2d.org/wiki/Main_Page). We are on a trip together, and I had an idea that I wanted to implement.
The idea is a game where the players try to guess what the others are guessing. The guesses are any strings whatsoever, and the better similarity your string has with other strings, the better you fare. There are actually two algorithms I wanted to try out / demonstrate with this toy game: the calculation of similarities between two strings, and an automatic (nonlinear) 2d projection of the feature space that the contents of the string create.
The similarity between two strings is calculated as percentage of the strings that does not need to be edited to make them into each other. It relies on edit distance (the number of changes between two strings) which is an indeterministic algorithm that can very efficiently be optimised with memoization. Löve is based on lua, and of course lua has no facilities for memoization, so we write both:
function memoize(f) local memory = {} return function(a, b) local val = memory[a .. '/' .. b] if val then return val end val = f(a, b) memory[a .. '/' .. b] = val return val end end function real_edit_dist(s1, s2) if s1 == '' then return s2:len() end if s2 == '' then return s1:len() end if s1:sub(1,1) == s2:sub(1,1) then return edit_dist(s1:sub(2), s2:sub(2)) end return 1 + math.min(edit_dist(s1, s2:sub(2)), edit_dist(s1:sub(2), s2)) end edit_dist = memoize(real_edit_dist) function similarity(s1, s2) local max_distance = s1:len() + s2:len() local correct = max_distance - edit_dist(s1, s2) return correct / (max_distance + 1) end
The max_distance + 1 scaling is to make longer strings more self-similar (which is kinda intuitive) and also to make similarity("", "") defined. You will see a lot of division-by-zero corner cases in this code covered by this simple increment. The handling of strings is nice and functional, thanks to Lua; the handling of two indices is very bad, thanks to me.
The 2d layout of words is done by iterating a displacement algorithm where all words try to get away from each other but similar words attract each other. The repulsion is defined as so; I've usually used tihs formula for games that have objects that shy away / cling to the player:
function repulse(p1, p2) local xdiff = p1.x - p2.x local ydiff = p1.y - p2.y local dist_nz = xdiff * xdiff + ydiff * ydiff + 1 return {x = p1.x + 7 * xdiff / dist_nz, y = p1.y + 7 * ydiff / dist_nz} end
As you can see, Lua (which Löve uses as its glue language) has quite nice syntax for creating new records; I don't have to update the points in-place. But it turns out that Lua has no facilities whatsoever for making a partially updated record out of another, so I build that:
function merge_bang(t1, t2) for k, v in pairs(t2) do t1[k] = v end return t1 end function merge(t1, t2) return merge_bang(merge_bang({}, t1), t2) end function associate(t, k, v) return merge(t, {[k] = v}) end
It also turns out that Lua doesn't have any facilities for creating values out of lists, either. So I'll have to write at least map and reduce; I was going to write map() so that it uses reduce(), but then I found out that Lua doesn't offer an applicative array insertion / appending primitive either, so I wrote map() in the imperative way.
function reduce(f, acc, vals) for k, v in ipairs(vals) do acc = f(acc, v) end return acc end function map(f, vals) local result = {} for k, v in ipairs(vals) do table.insert(result, f(v)) end return result end
When you have higher order functions such as map and reduce, you'll usually also want function creators to make functions for them. Here are the two that I ended up needing:
function sum(x, y) return x + y end function field(key) return function(table) return table[key] end end
Here's one algorithm they're used for (that is used later for laying out the words so that they center at the middle of screen).
function avg_position(words) local locs = map(field('loc'), words) local xsum = reduce(sum, 0, map(field('x'), locs)) local ysum = reduce(sum, 0, map(field('y'), locs)) return xsum / #words, ysum / #words end
Here's how all words make a repulsion for each other. This code is quite neatly functional and uses persistent data structures; you could save a history of word positions if you wanted.
function repulse_word(w, points) local loc = reduce(repulse, w.loc, points) return associate(w, 'loc', loc) end function repulse_words(words) local locs = map(field('loc'), words) function rp_word(w) return repulse_word(w, locs) end return map(rp_word, words) end
At this point, I want to test all of this out. But turns out that the Lua repl doesn't print records properly, making it really hard to try out different values by hand. So we build that, too.
function indent(n) local result = '' for i = 1, n do result = result .. ' ' end return result end function deep_tostr(obj, lev) if type(obj) ~= 'table' then return indent(lev) .. tostring(obj) end local result = indent(lev) .. '{\n' for k, v in pairs(obj) do local ks = ' (@ ' .. tostring(k) .. '),\n' result = result .. deep_tostr(v, lev+1) .. ks end return result .. indent(lev) .. '}' end function pp(obj) print(deep_tostr(obj, 0)) end
Now we can test out things in lua repl like this:
atehwa@manyuk:~/proj/guesser$ lua Lua 5.2.4 Copyright (C) 1994-2015 Lua.org, PUC-Rio > dofile 'algo.lua' > pp(repulse_words({{w='foo',loc={x=1,y=2}},{w='root',loc={x=3,y=7}} })) { { { 0.53333333333333 (@ x), 0.83333333333333 (@ y), } (@ loc), foo (@ w), } (@ 1), { { 4.7333620565848 (@ x), 11.333405141462 (@ y), } (@ loc), root (@ w), } (@ 2), }
Then there's the attraction part. Here we cannot ditch the information about the actual words, because how much they attract each other depends on which words they are. But on the other hand, we don't need to cache it either, since the memoization of edit_dist already takes care of that.
function attract(w1, w2) local xdiff = w2.loc.x - w1.loc.x local ydiff = w2.loc.y - w1.loc.y local dist_nz = math.sqrt(xdiff * xdiff + ydiff * ydiff) + 1 local sc = similarity(w1.w, w2.w) / dist_nz local new_loc = {x = w1.loc.x + xdiff * sc, y = w1.loc.y + ydiff * sc} return associate(w1, 'loc', new_loc) end function attract_all(words) return map(function (w) return reduce(attract, w, words) end, words) end
You've probably noticed that all words attract and repulse themselves, too. It's okay because we have the magical "+ 1" everywhere. "dist_nz" stands for "distance, non-zero" :)
Okay, time to make something display in Löve. Here my son helped me a lot. It's a little bit too hard to reconstruct how it went, but I'll show the pieces in approximately the order we wrote them.
require 'algo' local words = {} local current_word = 'type in some handsome text and press enter' local state = 'inputting' local nodes = {} function love.draw() if state == 'inputting' then love.graphics.print(current_word) return end end
There's no point in trying to make this user interaction in the functional way - Löve doesn't allow me to. So I add keyboard handlers:
function love.load() love.keyboard.setKeyRepeat(true) end function love.textinput(text) current_word = current_word .. text end function love.keypressed(key) if key == 'return' then table.insert(words, current_word) current_word = '' return end if key == 'backspace' then current_word = current_word:sub(1, -2) return end end
Of course, UTF8 makes everything go ka-boom. Since why would Lua support such a concept? Strings are byte vectors by the will of God and Satan alike.
How to go into rendering mode? We use two enters as the end condition for input mode, and initialise words to start with random positions and random colors:
function jitter(n, variance) return n + love.math.random(variance) - love.math.random(variance) end function rand_comp() return jitter(100, 50) end function word_to_bubble(w) return {w = w, loc = {x = jitter(0, 150), y = jitter(0, 100)}, color = {rand_comp(), rand_comp(), rand_comp()}} end function love.keypressed(key) if key == 'return' and current_word == '' then state = 'iterating' nodes = map(word_to_bubble, words) return end if key == 'return' then table.insert(words, current_word) current_word = '' return end if key == 'backspace' then current_word = current_word:sub(1, -2) return end end
Then we need to make them draw to the screen:
function love.draw() if state == 'inputting' then love.graphics.print(current_word) return end local xw, yw = love.graphics.getDimensions() local xc, yc = avg_position(nodes) love.graphics.print(xc .. '/' .. yc) for k, v in ipairs(nodes) do local r,g,b = v.color local x = v.loc.x - xc + xw/2 local y = v.loc.y - yc + yw/2 love.graphics.setColor(r,g,b) love.graphics.circle('fill', x, y, 30) love.graphics.setColor(255,255,255) love.graphics.print(v.w, x, y) end end
Now we get the initial words bubbles on the screen. The last touch is to make them update with our layout algorithm.
function love.update(dt) nodes = attract_all(repulse_words(nodes)) end
If I was cool, I'd use the dt variable to scale the amounts of movement. But I don't really care how fast the animation goes.
The game is published at https://github.com/pkalliok/guesser-game .