Welcome, Guest. Please login or register.

Login with username, password and session length

 
Advanced search

1411283 Posts in 69325 Topics- by 58380 Members - Latest Member: bob1029

March 29, 2024, 02:04:50 AM

Need hosting? Check out Digital Ocean
(more details in this thread)
TIGSource ForumsCommunityDevLogs5N²+6N-4 . . . . . . (codename)
Pages: 1 ... 5 6 [7] 8 9 ... 14
Print
Author Topic: 5N²+6N-4 . . . . . . (codename)  (Read 47527 times)
JobLeonard
Level 10
*****



View Profile
« Reply #120 on: August 31, 2020, 01:58:21 AM »

A very cryptic game :p
Yeah, I'm currently just playing with algorithms, but in the end, creating the UI that will make this more accessible to the player is going to be the real challenge.


(a map, with colors in the form HSL(60°K, 1.0, ...))
Are you sure that isn't a Piet program? Cheesy

https://www.dangermouse.net/esoteric/piet.html
Logged
a-k-
Level 2
**


View Profile
« Reply #121 on: September 06, 2020, 01:04:54 PM »

Are you sure that isn't a Piet program? Cheesy

https://www.dangermouse.net/esoteric/piet.html

Was it? Who, Me? Let me check this one:



Pure coincidence!
Logged

JobLeonard
Level 10
*****



View Profile
« Reply #122 on: September 07, 2020, 03:57:20 AM »

 Hand Thumbs Up Left Kiss Hand Thumbs Up Right
 Hand ClapCheesy
Logged
a-k-
Level 2
**


View Profile
« Reply #123 on: September 27, 2020, 01:10:40 AM »

Piet is finally integrated in the game. I've cut a lot of corners to get it out the door, so some features of the textual languages are missing, but the essentials are here. Most importantly, players can hover areas of the image and see the underlying opcodes at the bottom:


(pushing -13 to the stack. when it makes sense, a pair or triplet of opcodes are displayed as one unit.)

This also provides an equivalent for the collection of "keywords" in the other languages, except that here, the player needs to be more active in hunting them.

A related change: the setting that overrides the language of a level, which was previously enabled only for players that unlocked all languages as well as the Lexical achievement, is now available for all players from the start.
Logged

JobLeonard
Level 10
*****



View Profile
« Reply #124 on: September 27, 2020, 05:56:09 AM »

Damn, I didn't expect you to actually add it!  Hand ClapGrin
Logged
JobLeonard
Level 10
*****



View Profile
« Reply #125 on: September 28, 2020, 02:12:29 AM »

I tweeted your addition to the creator of the language:

https://twitter.com/JobvdZwan/status/1310212278910947335

He replied and added it to the (delightfully low-fi) webpage of Piet:

https://www.dangermouse.net/esoteric/piet.html

https://www.dangermouse.net/esoteric/piet/tools.html <- this one

I realize that maybe I should have asked first, I don't know if you're trying to keep a low profile or not
Logged
a-k-
Level 2
**


View Profile
« Reply #126 on: September 28, 2020, 12:04:05 PM »

Damn, I didn't expect you to actually add it!  Hand ClapGrin
Yeah, I did try to be tentative about this in the first posts. I only had a Python prototype that encodes random numbers, and no clue how I would integrate such a thing into a game that assumes that code is, well, textual. But once you identified the language, I had no choice but to follow through... Wink


I tweeted your addition to the creator of the language:

https://twitter.com/JobvdZwan/status/1310212278910947335

He replied and added it to the (delightfully low-fi) webpage of Piet:

https://www.dangermouse.net/esoteric/piet.html

https://www.dangermouse.net/esoteric/piet/tools.html <- this one

That's so cool! Thank you!
Logged

a-k-
Level 2
**


View Profile
« Reply #127 on: October 03, 2020, 04:32:10 AM »

A little juicing, for program editing in the case of Piet:


(replacing a "link" command with "unlink", and later undoing the change)

As you can see, some pixels change color in-place while other pixels move, possibly also changing their color in the process.

In order to calculate this animation, I examine the blocks in the image in order (a block consists of 4-connected same-color pixels), and reduce each block to a single number - its size (# of pixels). This is done for the old image and the new image, so we end up with two sequences of numbers. By comparing these sequences with a standard "diff" algorithm, we get a matching of common blocks between the images (the "longest common subsequence") - common not necessarily in color, location or shape, but at least in terms of size. Then, the individual pixels in each pair of blocks are matched naively, just by enumerating them (that is, according to an arbitrary flood-fill order).

This produces a partial matching between the pixels in the old image and the new one. These matched pixels move if needed; others can only change color.

And that's how I used the same "diff" algorithm that I employ for animating transitions between text to animate transitions between images...
Logged

JobLeonard
Level 10
*****



View Profile
« Reply #128 on: October 03, 2020, 08:56:28 AM »

Surely this must be the fanciest Piet IDE ever Cheesy

But actually seriously, that's really cool
Logged
a-k-
Level 2
**


View Profile
« Reply #129 on: October 08, 2020, 08:41:22 AM »

Surely this must be the fanciest Piet IDE ever Cheesy
A pseudo-IDE, if you will. And there are 8 more in the demo version! (though not as fancy)

But actually seriously, that's really cool
Thanks! Just after posting I noticed that it would be better to match the left side separately from the rest of the image, and that the GIF wasn't a good example of the algorithm since it didn't explain why I ignored colors in the matching (which is, because modifying/inserting an opcode in the middle may change the colors of subsequent opcodes).

Anyway, I have a brand-new algorithm from today to describe in a post, haven't implemented anything yet but it looks promising. Hopefully I'll do better this time!
« Last Edit: October 08, 2020, 08:50:09 AM by a-k- » Logged

a-k-
Level 2
**


View Profile
« Reply #130 on: October 08, 2020, 01:46:41 PM »

When compilers generate machine code, they translate the source language's control flow constructs to jumps:


(popular constructs and the emitted jumps. dash = conditional jump.)

Decompilers do the opposite: they take an executable and produce an equivalent source code that's more readable than assembly. An important part of this process is representing the jumps using familiar structured programming facilities:


(a bunch of jumps and a possible translation. the decompilers i'm talking about usually generate C, though.)

Called control flow structuring, this step has typically been very complicated, employing many algorithms and ad-hoc trickery to get a faithful program. But that complexity is not really necessary! In this post I'm presenting an almost-trivial algorithm that solves this problem once and for all.

The algorithm

1. We're starting with the example above. Initially, we ignore the direction and type of jumps, so let's replace the arrows with arcs:


(for the sake of presentation, we split the rightmost point to 3 points, ordered so as to minimize crossings)

2. Imagine that we have a stack (last-in-first-out), and that we scan the 8 points from left to right.

The first time that we visit an arc (i.e. its left point), we push a random value to the stack. Once we arrive at an arc's right point, we pop from the stack and expect to get the same value that was pushed when we visited the left side of the arc.

Clearly, this can work only if the arcs don't cross each other, which unfortunately is not our case. To support crossings, we will allow pushing a value to the stack in arbitrary depths. In order to determine the proper depth for a value, we'll calculate the number of other arcs that cross each arc to its left:


(push_0 = push to top of stack, push_1 = push right below the top element, etc.)

3. Let's convert our arcs back to arrows, and refine the push's and pop's according to the directions and types of the arrows and the following mapping...


(we won't go into the specifics of the terms used here.)

... to get the final list of words:


(words from left to right: push_0-dest, C1, push_1-orig-cond, C2, ... )

4. Now, all that remains to be done is to translate the words one by one to the keywords and symbols of the target programming language.

The best option for our algorithm is the structured-programming-language-that-doesn't-support-break-continue-or-goto-but-does-allow-modifying-the-internal-stack-that-the-compiler-uses-for-emitting-jumps, so that we immediately get the program:


(the jumps and the final translation. a similar program appears in the programming language's manual (and that's why this example was chosen.))
« Last Edit: October 08, 2020, 01:52:21 PM by a-k- » Logged

JobLeonard
Level 10
*****



View Profile
« Reply #131 on: October 09, 2020, 12:22:52 AM »

Come for the game dev log, stay for the compiler design class Smiley
Logged
a-k-
Level 2
**


View Profile
« Reply #132 on: October 18, 2020, 11:55:20 AM »

Come for the game dev log, stay for the compiler design class Smiley
You never know when you'll need to transpile one esoteric language to another, better be prepared!


(translation of a program that resembles the example from the previous post)

Control flow and translation of commands are mostly ready. A few gaps remain:

  • Indentation - when 'break/continue/goto' jumps are present, indentation is off.

    That would be easy to fix if I could differentiate these jumps from the ones that structure loops and 'if' statements, but that is not something that the present algorithm is capable of. In fact, not detecting loops and conditions is an inherent quality of the algorithm that contributes a lot to its simplicity.

  • Early exits vs. structured programming - the quality of the translation depends on the jumps that are input to the algorithm. Forth has a 'return' statement, so per case, we can choose whether to generate a jump to the end of the function or just emit 'return' as if no jump is involved.

    Problem is, since the current algorithm is oblivious to loops and conditions, it doesn't provide the necessary information for making such a decision. So for simplicity, I currently always use 'return', which helps in the complex cases but tends to produce unstructured code in the trivial ones. Like, instead of generating the Forth-equivalent of "if (C) { A; } else { B; }", it produces "if (C) { A; return; } B;". It actually doesn't look so bad in Forth, and I don't know, maybe no player will notice?
Logged

JobLeonard
Level 10
*****



View Profile
« Reply #133 on: October 19, 2020, 01:01:54 AM »

> You never know when you'll need to transpile one esoteric language to another, better be prepared!

Honestly though, I bet you could make a really popular blog or video series on that topic!
Logged
a-k-
Level 2
**


View Profile
« Reply #134 on: November 07, 2020, 04:43:16 AM »

Forth is now integrated in the demo, for a total of 10 languages.

Handling indentation in the face of improperly-nested control structures turned out to be easy: just indent upon BEGIN (which starts a loop) and IF, and always use the maximum indentation over all "indentation contexts" that weren't closed yet. Forth doesn't appear to have any convention for those cases, so that will do for now. I did end up using a little bit of structural analysis to arrive at more intuitive translations in some cases (e.g. the "early exit" scenarios I talked about), and surprisingly, sometimes the results were more interesting than those of the other languages:


(one solution (mostly redacted), two translations: one loop in C++, two nested loops in Forth)

> You never know when you'll need to transpile one esoteric language to another, better be prepared!

Honestly though, I bet you could make a really popular blog or video series on that topic!

Hey, I'm not giving away my IP just like that! Still waiting for the right opportunity to commercialize this. When the world is prepared to move on from the complexities of the present-day SW ecosystems, I'll be ready with my 6-commands thingie...
Logged

JobLeonard
Level 10
*****



View Profile
« Reply #135 on: November 08, 2020, 05:44:33 AM »

If I recall correctly, Forth doesn't have any convention regarding indentation. The examples in "Understanding Forth" could look very weird at times.

Forth culture is one of "write once" and "build up everything from scratch and optimize it for the task at hand"
Logged
a-k-
Level 2
**


View Profile
« Reply #136 on: November 08, 2020, 01:35:52 PM »

If I recall correctly, Forth doesn't have any convention regarding indentation. The examples in "Understanding Forth" could look very weird at times.

Forth culture is one of "write once" and "build up everything from scratch and optimize it for the task at hand"

The ancient Forth scrolls seemed to assume that programs consisted of vocabularies of words with very short definitions, so I guess that one-liners could make sense, at least as examples. I can't attest to the culture, but in order to determine a style for the game, I reviewed two real-world projects - FFL (Forth Foundation Library) and 4tH (a compiler). I've found their coding standards no less than impressive.
Logged

a-k-
Level 2
**


View Profile
« Reply #137 on: December 05, 2020, 11:18:19 AM »

A new demo version is available, aiming mainly at making the game more accessible while providing more information to advanced players.

Names in leaderboards
I didn't originally plan to support this in the HTML5 version, but given that the desktop version will not support Mac, and that it's no longer so easy to lose the savefile due to the browser's clearing local storage (at least, I warn players of unsaved changes when they try to close the page), users of the demo can now provide a name that will appear in the leaderboards.

The UI for this is not very discoverable, but players will be subtly guided toward it with highlighted buttons once they are in the top 60.

New histogram
Previously, each level had 4 histograms: #commands, #conditions, cycles, and score, which is calculated from the other three. While "workers" (the game's term for registers) don't affect score, they're related to some achievements and in general can be interesting for players, so their distribution is now shown as a 5th histogram.

Histograms for uncompleted levels
The above-mentioned histograms used to be displayed only for levels that the player completed. This was intentional - I didn't want the histograms to hint at possible solutions before the player found at least one. I've recently changed my mind about that, and in the new version all histograms can be accessed from the Level Select screen.

More hint levels and extra workers
This was partially triggered by the results of the new #workers histograms, which suggested that I'd been too strict about the number of workers in some levels.

Encouraging "root"
Some levels disable command types and workers that were unlocked in preceding levels - either because they're not needed, or deliberately to impose a constraint. The game, however, provides an unlockable option (called "root") that re-enables everything that's currently disabled so that it can be used in solutions to a level.

In order to encourage the use of this mode - especially by players that get stuck in a level, I've removed the confirmation screen that was shown before submitting rooted solutions, and updated many tooltips to directly suggest root. Now I wonder whether the screen changing its background color from blue to red when root mode is activated plays a role in not many players' using it...
Logged

a-k-
Level 2
**


View Profile
« Reply #138 on: December 13, 2020, 12:48:24 PM »


(revised keywords screen, with empty rectangles for unexplored keywords and progress bars for partially-unlocked ones)

Lately I've been exploring the option of including some kind of narrative that's tied to the unlocking of keywords, so that once the player becomes (or has the potential to become) familiar with a language, something will pop up. The trigger for that could be, say, unlocking 80% of the keywords of a language.

Whereas the languages are distributed rather evenly across the levels, which keyword is unlocked when depends to a large extent on what the player is doing when a language is displayed. So I've went on to look at real data, and here's a representative example:


(% of keywords unlocked per language, and the order by which it crosses 80%)

As can be seen, the order of unlocking keywords is not aligned with the order by which languages are introduced (otherwise, we would have a diagonal). This is because only in later levels do solutions require more complex control flow that gets translated to more keywords. Consequently, the "interesting" keywords of the first languages, BASIC and Pascal, are usually unlocked only after those of the more advanced languages.

In general, even if I adapt the criteria for presenting a narrative for a language to my needs (e.g. by being flexible about the 80% threshold), the order will still have high degree of non-determinism and will vary across players. So I need to put more thought into this.

Ah, and a small leftover from the previous post - I've improved the accessibility of the online leaderboards:

Logged

JobLeonard
Level 10
*****



View Profile
« Reply #139 on: December 13, 2020, 01:27:30 PM »

Oh wow, the idea of having to unlock keywords in programming contexts never occurred to me before. That's one way to tackle the expression problem! Cheesy
Logged
Pages: 1 ... 5 6 [7] 8 9 ... 14
Print
Jump to:  

Theme orange-lt created by panic