Mikä on WikiWiki?
nettipäiväkirja
koko wiki (etsi)
viime muutokset
(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 .