Game2 W4/4

Well, It’s unfortunate, but I couldn’t make the game in these 4 weeks. August is just too much of a pain in terms of the amount of different events - maybe even the busiest month in the whole year, for me personally. Judging by the commit history, I was able to work only for 11 days out of the 28 days given to me by the challenge - and I tried to do at least some work every day and commit everything I did. I’m saying 11 days, but maybe 5 of these were in this last week.

This last week was all about level generation and, unfortunately, I failed at it. I was trying to implement the Wave Function Collapse algorithm in Lua and for some weird reason, it didn’t work. After three failed attempts, I decided to cheat. My idea was to go and port my ClojureScript version to Fennel form by form and compile it to Lua after it works. However, it didn’t work as well, no idea why. For some reason, some branches in my code are just never visited at all, although I did everything the same way, and implemented missing pieces from Clojure’s standard library for this code to work. At least it terminated, but instead generated a complete gibberish:

>> (wfc (gen_world 9 9) coast)
[["🟩" "🟩" "🟦" "🟦" "🟩" "🟩" "🟩" "🟦" "🟩"]
 ["🟩" "🟩" "🟫" "🟦" "🟫" "🟦" "🟦" "🟩" "🟦"]
 ["🟦" "🟩" "🟫" "🟫" "🟦" "🟫" "🟩" "🟫" "🟫"]
 ["🟫" "🟫" "🟩" "🟩" "🟩" "🟦" "🟫" "🟦" "🟦"]
 ["🟫" "🟫" "🟩" "🟫" "🟩" "🟦" "🟩" "🟩" "🟩"]
 ["🟦" "🟦" "🟩" "🟫" "🟦" "🟩" "🟦" "🟩" "🟫"]
 ["🟦" "🟫" "🟩" "🟦" "🟦" "🟩" "🟩" "🟩" "🟫"]
 ["🟦" "🟩" "🟦" "🟦" "🟩" "🟩" "🟩" "🟫" "🟩"]
 ["🟦" "🟩" "🟫" "🟦" "🟦" "🟩" "🟩" "🟦" "🟫"]]

It is supposed to look like this:

user> (wfc (gen-world 9 9) coast)
[["🟫" "🟫" "🟫" "🟫" "🟫" "🟫" "🟫" "🟫" "🟫"]
 ["🟩" "🟫" "🟫" "🟫" "🟫" "🟫" "🟫" "🟫" "🟫"]
 ["🟦" "🟩" "🟫" "🟫" "🟫" "🟫" "🟫" "🟫" "🟫"]
 ["🟦" "🟦" "🟩" "🟫" "🟫" "🟫" "🟫" "🟫" "🟩"]
 ["🟦" "🟦" "🟦" "🟩" "🟫" "🟫" "🟫" "🟩" "🟦"]
 ["🟦" "🟦" "🟦" "🟦" "🟩" "🟫" "🟩" "🟦" "🟦"]
 ["🟦" "🟦" "🟦" "🟦" "🟦" "🟩" "🟦" "🟦" "🟦"]
 ["🟦" "🟦" "🟦" "🟦" "🟦" "🟦" "🟦" "🟦" "🟦"]
 ["🟦" "🟦" "🟦" "🟦" "🟦" "🟦" "🟦" "🟦" "🟦"]]

This reminded me of the importance of data structures and their properties I keep forgetting when programming in Clojure. Because in Clojure it’s just the thing you have, so you don’t think much about it.

You see, Clojure has 4 main data structures, baked up with literals: list (a, b), map {k1 a, k2 b}, vector [a, b], and set #{a, b}. Each of these has its own set of properties, for example, lists are only fast to add elements at the front, and vectors are fast to add elements to the tail. Maps are mostly like Lua’s tables, and sets are like maps in the way that they can only store unique elements, and are indexed like a map but iterated like a list.

In my ClojureScript implementation of the WFC algorithm, I used all these data structures and relied on their behavior. For example, the superposition for a cell after the world’s initialization is a set of all possible values for the cell:

#{"🟦", "🟩", "🟫"}

I used maps to store the recipe:

{"🟫" {:up #{"🟫"}
       :down #{"🟫" "🟩"}
       :left #{"🟩" "🟫"}
       :right #{"🟫" "🟩"}}
 "🟩" {:up #{"🟫"}
       :down #{"🟦"}
       :left #{"🟫" "🟦" "🟩"}
       :right #{"🟫" "🟦" "🟩"}}
 "🟦" {:up #{"🟩" "🟦"}
       :down #{"🟦"}
       :left #{"🟩" "🟦"}
       :right #{"🟦" "🟩"}}}

The map itself stores maps with sets that are later used in the algorithm. Other data structures are at play for other parts of the whole process, but I’m not going to touch them here.

Lua on the other hand has only one collection type - the table. It can serve as a vector, to which you can add elements at the tail, and you can use them as hash tables, where there can only be a single instance of a given key. Sets can also be represented if we just use a table where keys are elements and values are the same elements or something like true.

local superposition = {["🟦"]=true, ["🟩"]=true, ["🟫"]=true}

This is actually what the “Programming in Lua” book suggests. The recipe then looks like this:

-- Sorry, not sorry for formatting - all these brackets on separate
-- lines take a stupidly big amount of vertical space
{["🟫"]={up={["🟫"]=true},
         down={["🟫"]=true, ["🟩"]=true},
         left={["🟩"]=true, ["🟫"]=true},
         right={["🟫"]=true, ["🟩"]=true}},
 ["🟩"]={up={["🟫"]=true},
         down={["🟦"]=true},
         left={["🟫"]=true, ["🟦"]=true, ["🟩"]=true},
         right={["🟫"]=true, ["🟦"]=true, ["🟩"]=true}},
 ["🟦"]={up={["🟩"]=true, ["🟦"]=true},
         down={["🟦"]=true},
         left={["🟩"]=true, ["🟦"]=true},
         right={["🟦"]=true, ["🟩"]=true}}}
-- also, the table syntax is just horrible - why square brackets are
-- needed around strings for keys? Why can't we write {"foo bar"="baz"}?
-- And why can we write {foo="bar"}? Why variable foo is not the same
-- foo when used in the table? Why foo is now a string?  The syntax is
-- too smart for its own good.

Now, here’s the problem - how do we tell apart sets from key-value tables? We can write some predicates, like is_set that either check that all values are true, or create a constructor function that will add a hidden __index metatable with a is_set key set to true, but it’s all pretty janky, in my opinion at least. A proper data structure should have its own syntax literal and a set of functions to check the type. Lua doesn’t even give you the ability to distinguish sequential tables from associative ones¹. I don’t think that Clojure’s choice of #{} for sets is great, but it’s a lot better than nothing.

But there’s also another issue with our implementation of sets - iteration support. In Clojure, you can iterate over any type of data structure, and it will actually do it in a meaningful way.

If you try to iterate over a list, vector, or set - it will just iterate over the elements:

user> (map identity '(:a :b :c))
(:a :b :c)
user> (map identity [:a :b :c])
(:a :b :c)
user> (map identity #{:a :b :c})
(:b :c :a)

In the case of a set the order is not determined, so the order of results is arbitrary. If you try to iterate over a map though, it’s a bit different:

user> (map identity {:a "b", :c "d", :e "f"})
([:c "d"] [:a "b"] [:e "f"])

Same as for the set, the order is arbitrary, but you can see that the elements in the list are vectors. That’s right, when we iterate over the map we get back vectors, containing the key and its value, which we can then use in the function that we iterate with.

You may be thinking: “Well, that’s the same as what pairs does in Lua” but it’s not. Unlike what I have shown to you, pairs will always return the key and value, even for vectors. Yes, in the case of a vector, the key will be an index, and we can pretty much ignore it most of the time, but what about our sets? In the case of our set implementation, the key is actually the value we’re looking for, because the value is just true. So no, implementing sets as tables that store true as a value is a no-go for most use cases, we have to store the value both as a key and a value in a set:

local superposition = {["🟦"]="🟦", ["🟩"]="🟩", ["🟫"]="🟫"}

But I digress.

Another, very important property of Clojure’s data structures is that they’re both immutable and persistent. This means that whatever we do with the vector doesn’t actually change the vector - it returns a new vector that shares the unchanged part of the structure with the old one plus new stuff. Clojure author went to great lengths to make this process fast and reliable.

I used this heavily in the CLJS version of the algorithm. Perhaps too heavily, but it’s a different topic. What it gave me though is the ability to change the world without mutating the original world, so every step of the algorithm actually produced a new world, and I could trace it back to the very beginning if I wanted to. It is not as fast as the mutation-based approach but is much more sane to work with and debug.

My first implementation of the algorithm in Lua, however, was mutating the world. Not only it is hard to debug, Lua makes it harder because you can’t view the data structure you’re working with. You probably don’t remember it, but I made a complete rewrite of the pretty printer for the Fennel language, and I did it mostly because the original one produced the representation that was hard to read due to indentation going all over the place. Well, guess what, Lua doesn’t have its own pretty printer whatsoever. You have to write your own or import some library that does it for you, which is not feasible with TIC-80, as its screen resolution is too small to comfortably read anything, especially huge tables that contain lots of elements, like the world I was trying to generate. Can you feel my frustration?

Then I made a hacky deepcopy function (another part that lacks from Lua because tables²) to at least get a copy-on-write type of immutability in Lua. This slowed down things to the point that it was useless for the sizes of worlds I wanted to construct. And it didn’t fix the problem, so it was somewhere else. I wasn’t ready to re-implement the whole thing again, so I stopped here.

Another thing I keep forgetting is how great Clojure’s standard library for manipulating collections is. There are all sorts of operations on sets, you can transform maps, iterate on anything, rename keys, etc., etc. Lua has a very rudimentary library for tables, that can’t do almost anything. Sure, there are libraries like Penlight³, and lua-stdlib that could help with that, and I made a port of Clojure’s core namespace to Fennel (and therefore Lua) but again - TIC-80 makes it hard to use these libraries. So, no, Lua isn’t great at manipulating data structures, and porting Clojure code to it is a pain. What did I expect? Well, I’ve ported all the functions I used in my CLJS WFC implementation, things like map, keep, map-indexed, get-in, assoc-in, etc., but there were still problems with how to iterate over tables, as there is no sequence abstraction in Lua, and it’s hard to make it properly. I tried multiple times before, and the best I got was my lazy sequence library for Fennel, but even there I took some shortcuts regarding the situation with tables that have both associative and array parts. Sorry Lua fans, but combined data structures like that are stupid.

I’m writing this a bit early, as there are clearly some more days until the end of this week, but then again, I won’t have time to do any work neither this evening, nor tomorrow, or the day after that. It’s a shame though, I don’t want to abandon this roguelike idea, and maybe I’ll get back to it after the challenge ends. Or maybe not, I don’t know. I will have another chance to make a top-down game, but probably without an isometric projection.

Looking back on the development process for this game I can see that choosing the isometric projection was probably the wrong decision. First, I struggled with the projection itself, then with the projection of screen coordinates back to the world coordinates. Halfway through I ditched the isometric projection and started drawing stuff without it, in hopes that I will just enable it back when the world generation is ready. But then the world generation was a problem. I didn’t even get to work on enemies, items, menus, and so on. Well, a roguelike is a lot more involved than a simple platformer, so it is expected that it takes more time to do stuff, but I didn’t have that time unfortunately.

Lua isn’t the one to blame for all these problems though. While I did get some frustrations with its syntax, overall the experience wasn’t that bad. However, I will not probably use it for upcoming projects. The lua-mode package for Emacs is in a rough shape - there is no pairing support for do end keywords, like in sh-mode or ruby-mode. Indentation is extremely slow and often unpredictable.

The next game on the list is a Card game but I’m not in the mood for that at all, so I’m going to change this and make a side-scrolling shoot-em-up kind of game. It should be much easier, and with all of the frustration built up over the last month, this is probably just what I need.