next »

[a-k-]

To be continued...

[a-k-]

Coming soon as part of a mini-game:


(a solution reduced to blocks)

This view partitions the commands to blocks that highlight the control flow. It's a refinement of basic blocks in which conditions start new blocks (in orange).

Currently I naively assign colors to blocks in a cycle, which can produce blocks that have the same color as their predecessors (e.g. 1 and 14). I guess I'll leave fixing that to a future iteration.

[a-k-]

Inspired by Pony Island, the game now includes a fill-in-the-blanks mini-game, where the player is tasked with recovering keywords of up to 10 languages to reconstruct the flow of a representative sample of their solutions to the levels:


(screenshot of me playing the game. this is the 3rd puzzle so the toolbox already contains a few keywords that have nothing to do with BASIC.)

The actual number of puzzles in a game depends on how many languages and keywords the player has unlocked. As the game progresses, more complex solutions (in terms of control flow) are presented, and more superfluous keywords (both from the correct language and others) are made available.

Unlike the main game, there's a lot of randomization here, and that each player gets a distinct set of puzzles (all drawn from their level solutions) made it somewhat tricky to determine a proper progression while keeping the fun. One way to do it was demonstrated in the second-to-last post - the puzzles are selected so as to minimize the # of keywords that the player needs to fill in (very helpful if you have gigantic solutions like me...)


Future work:
- Make more discoverable (currently the mini-game is accessible only from Records > Words, not from Level Select)
- Animations, game complete screen etc.
- Global histograms

[JobLeonard]

Nice!

[a-k-]

Nice!

Thanks!
Here's a gameplay video of completing the minigame (~5 min).

[bayersglassey]

The amount of love for programming languages on display here is staggering. :D
The game's page actually has random programming language names floating across it: https://2020.itch.io/graphomata
And after "proving that I was human", I was treated to an animation of a sqlite console. With someone creating a graph using SQL. And hovering the mouse over rows in the SQL output also highlighted the corresponding nodes of the graph, shown to the right.

Even trying to describe these things with words is difficult. I'm blown away.

[bayersglassey]

This system is super robust... and even simple things like an infinite loop are very satisfying.

[JobLeonard]

That looks really good

[a-k-]

The amount of love for programming languages on display here is staggering. :D
The game's page actually has random programming language names floating across it: https://2020.itch.io/graphomata
And after "proving that I was human", I was treated to an animation of a sqlite console. With someone creating a graph using SQL. And hovering the mouse over rows in the SQL output also highlighted the corresponding nodes of the graph, shown to the right.

Even trying to describe these things with words is difficult. I'm blown away.

Thank you for the kind words!

A lot of this is actually incidental - the languages thing started with adding a C++ translation just because I thought it would be cool, and now there are 14. The keywords started as mere animation for April fools' day (my take on particle effects), and now there's this whole mini-game. And the SQLite session, I think it was inspired by some visualization demo (can't find it at the moment so not 100% sure). I guess slow-cooking a project for so long does have some benefits

[a-k-]

This system is super robust... and even simple things like an infinite loop are very satisfying.

That looks really good

I'm glad that you're enjoying the garbage collection*! In more complex cases this dynamic layout system can really get in the way, I feel like there's still a lot of room for improvement.

* more precisely, automatic reference counting (because... performance!)

[bayersglassey]

Ah, that's true, it is garbage collection! :D That didn't occur to me.
The pseudocode is basically

Code:

while(true) { A = new Node(); B = new Node(); }

But yeah, I guess you're purposefully forgoing the possibility of puzzles involving unconnected nodes... because that probably wouldn't be so interesting.

But you don't "garbage collect" nodes with outgoing edges, it looks like:

So not quite the same as the garbage collection one might be used to...

(I was thinking maybe the "workers" Alice, Bob, etc were like the "roots" of the GC graph, but it looks like the GC algorithm here is just "remove nodes with no in/out going edges")

[a-k-]

Ah, that's true, it is garbage collection! :D That didn't occur to me.
The pseudocode is basically

Code:

while(true) { A = new Node(); B = new Node(); }

But yeah, I guess you're purposefully forgoing the possibility of puzzles involving unconnected nodes... because that probably wouldn't be so interesting.

But you don't "garbage collect" nodes with outgoing edges, it looks like:

So not quite the same as the garbage collection one might be used to...

(I was thinking maybe the "workers" Alice, Bob, etc were like the "roots" of the GC graph, but it looks like the GC algorithm here is just "remove nodes with no in/out going edges")

You're right, I assumed that you can navigate from a node also through incoming links, so that every link creates circular references that keep the structure in memory. That wouldn't fool a tracing GC (that could indeed start with the workers) but would do the trick for ARC...

[a-k-]

UI-related updates from the last 3 months:

View/edit past solutions


(top: clicking the pencil icon; bottom: the screen that opens, with 2 matching solutions)

You can recall any past solution by clicking the respective icon in score tables. The solution is displayed, it can be copied to the clipboard, and can also be selected if it still exists in the editor.
This makes it easier to optimize solutions when new cost-cycles thresholds render them obsolete, and it's not necessary to keep the best solutions (or the most interesting ones) in the editor.

Ctrl+X/C/V (previously supported only by mouse) - here Ctrl+V simply initiates the drag-and-drop operation from the in-game clipboard, so mouse is still needed for completing the paste. I display a large "Paste mode" banner when this mode is active, otherwise pressing Ctrl+V while the mouse pointer is outside the window could be rather confusing.

Exchange button (X) in the editor (previously supported only by keyboard)

Intro ("captcha") is skipped automatically for returning players, and it's now accessible from the main menu. Unless it's needed for escaping an <iframe> in the HTML5 version.

Profiles support (PC versions only) - the game always starts with the recently-used profile, and you can switch it in the main menu. Still haven't decided whether to implement Delete or just add a button that opens the savefiles folder.

[a-k-]

A few optimizations to improve performance on laptops running on battery power (following player feedback), make the game load faster and display level histograms earlier:

Game performance

Besides fixing a bug that made the game somewhat slower for players that had many (hundreds of) solutions, I've optimized the rendering, or more specifically, the memory management of dynamic arrays of vertices on the CPU (whose size is not known ahead of time):

• Reduced memory allocations - by attempting to reuse allocations done in the previous frame, exploiting the fact that consecutive frames usually allocate arrays of vertices in the same order and that those arrays usually end up having similar lengths. Heuristics is employed to discard previous allocations that are found to be too large for subsequent frames' needs.
• Faster/less copying on dynamic array growth - by replacing STL vector with a custom implementation that uses realloc() instead of the compiler-generated POD-move constructor for vertices

(~1000 FPS when taking the GPU out of the equation by running in a ~250x150 window)


Shorter loading time (HTML5 version) - moved from gzipped-WAV to FLAC (as in the PC versions). MP3 is still available as a fallback for old browsers. Total download size is back at ~4 MB.


Histograms server

• Reduced Python-->C++ overheads - the C++ processes that the server executes for sanitizing/canonicalizing potential solutions and verifying/scoring them now run as long-running HTTP servers so that process initialization is done only once per Python thread instead of every call
• Reduced server startup time to 2 sec - by optimizing the recalculation of scores that the server performs for all solutions in the DB on startup
• Faster histograms for new solutions - submitting an original solution and getting back updated histograms now requires only 1 round-trip to the server instead of 2+ (unless the server is busy verifying lots of other solutions)

Also, did some changes to enable future transition to an out-of-process DB and a multi-process (instead of multithreaded) Python server:

• Fewer DB queries and updates - by batching ("executemany") and other techniques (along the lines of querying a larger amount of data and filtering it in the code instead of running multiple queries only for the data that's needed)
• Achievement histograms - are now returned up-to-date from the DB instead of potentially out-of-date from a cache
• Server OS and HW upgrade

[JobLeonard]

How many people are playing it? Has this game founds its puzzle audience yet?

[a-k-]

How many people are playing it? Has this game founds its puzzle audience yet?

There are new players here and there that make their way to the leaderboard, and specifically in the last weeks there have been many contributions of new cost-cycles scoring thresholds. The multiprocessing initiative, if that's why you're asking, is not so much about scalability as opening up alternative options for hosting - the current setup is good enough for now and there are lots of server-side optimizations I can do if the game is plucked out of obscurity.

Anyway, I've added a graph to the website that shows the number of solutions in the DB, updated in real time. Right now there are over 10,000:



(ordered by level popularity; excluding hint levels)

[JobLeonard]

That's pretty impressive in a market saturated with puzzle games!

[a-k-]

A small peek into the internals of a new algorithm:



(I actually planned to show an output where the algorithm failed before I revised everything over the weekend - but I think I've just made it work with a simple fix...)

Edit: I haven't... this translation is completely bugous.

[a-k-]

There was a bug in the last post (the loop wouldn't work), so to set things straight, here's the control flow that the current version of the algorithm produces:



The key change is in the handling of backward jumps (back edges, i.e. cycles). For example, a loop 60-->70-->80-->60 will be translated to

60 defer (... && 80) 80
70 defer (60)
80 defer (70) 60,70

(The syntax in this specific example is roughly
statement-id defer (statements-that-postpone-the-execution-if-enabled) statements-to-enable-after-execution;
on startup, all statements are enabled; a statement gets disabled automatically once it gets executed.)

In general, a statement that jumps backwards to a target statement will enable all statements except itself that are reachable from the target without following backward jumps. In the example, 80 jumps to 60, so it enables 60 and 70 (in bold). The target of the jump, in its own turn, will enable the origin (60 enables 80, in bold).

After determining, for each location in the program (effectively, for each statement), which statements need to be enabled or disabled - i.e. the desired state, I run a data flow algorithm to determine the actual state of each statement in each location in the program (enabled, disabled or sometimes-enabled-sometimes-disabled). The final enable/disable clauses are generated based on the difference between the actual states and the desired states. This means in particular that if a statement is guaranteed to already be enabled, there's no need to re-enable it.

Finally, there's also an inlining phase that eliminates true/false branch statements that neither end the program nor jump backwards (in the last post, those were 11, 12 and 32 - now they're gone). This brings the result closer to something that a human being could write.

The next step is to re-number the statements (drop the BASIC-like numbering), and decide how to represent commands in the code. The language supports neither subroutines nor comments, but that won't be a blocker...

Edit: fixed line numbers in explanation

[bayersglassey]

I love how there is deep programming magic going on everywhere in this project... there's interesting stuff running on a server, there's interesting stuff running on the client side, and the player is somehow taking part in this by solving crazy puzzles by programming.
It's like performance art. :O