(toiminnot)

hwechtla-tl: Experiences on writing a toy game with löve

Kierre.png

Mikä on WikiWiki?
nettipäiväkirja
koko wiki (etsi)
viime muutokset


iterated.png

(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 .


kommentoi (viimeksi muutettu 19.10.2019 18:08)