Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length

 
Advanced search

1368213 Posts in 64213 Topics- by 56155 Members - Latest Member: Filipe Ferreira

October 23, 2019, 11:42:52 AM

Need hosting? Check out Digital Ocean
(more details in this thread)
TIGSource ForumsCommunityDevLogs5N²+6N-4 . . . . . . (codename)
Pages: [1] 2 3 4
Print
Author Topic: 5N²+6N-4 . . . . . . (codename)  (Read 7331 times)
a-k-
Level 0
***


View Profile
« on: March 19, 2016, 05:40:41 AM »

  • Programming puzzle featuring an original undeterministic language:
    1  2  3  4  5  6    (actual commands redacted)
  • Play against adversarial RNGs by employing no more than 6 simple commands
  • Inspired by Manufactoria, Jahooma's LogicBox, Robot Unlock and SpaceChem
  • Developed for fun in spare time (C++, Python)

Looking for feedback!
« Last Edit: September 21, 2018, 09:20:51 AM by a-k- » Logged

a-k-
Level 0
***


View Profile
« Reply #1 on: March 19, 2016, 06:02:30 AM »

Editor & debugger (85% complete):
  • All functionality is available by mouse (drag & drop), by keyboard, or any combination
  • Unlimited undo & redo
  • Clipboard, rotation/flipping
  • Contextual tooltips for commands & GUI elements
  • Step forward & backwards
  • Unlimited program size, scrollbars

The commands shown in the GIF are not the actual commands of the game (obfuscated).

« Last Edit: August 20, 2016, 09:06:29 AM by a-k- » Logged

a-k-
Level 0
***


View Profile
« Reply #2 on: March 21, 2016, 01:50:19 PM »

Flow of screens (90% 100% complete):
  • 5 screens arranged linearly, two buttons per screen: Next and Back
  • Dedicated screen for comparing the user's output to the desired one, highlighting differences if exist


Flow of screens - levels with many inputs (80% 100% complete):

  • User's program will ultimately be tested against many inputs (up to 100)
  • User needs to demonstrate running his/her program successfully on 1 input (may choose which) in order to proceed to final testing
  • Final testing is done on all inputs automatically
  • In case of failure on an input, that input will become active so the user can debug the program on it

Still open:
  • Whether to have additional buttons beyond Next and Back
« Last Edit: March 25, 2016, 02:58:32 AM by a-k- » Logged

a-k-
Level 0
***


View Profile
« Reply #3 on: March 24, 2016, 10:05:17 AM »

Batch rendering engine (100% complete):
  • Except for text, everything is made up of untextured triangles (vector graphics)
  • Global/local coordinate system that automatically scales to window size
  • Multiple layers (opaque and transparent)

GUI system (100% complete):
  • "Screens" consisting of "views", one screen displayed at a time (two during transitions)
  • Except for views that require clipping, all views share the same rendering batch
  • Drag & drop between views, tooltips

GUI controls (60% complete):
  • Windows 95-style GUI controls
  • "Rich text" supporting embedding of views inline as part of the text
  • Multiline edit control (?)

Open issues:
  • Speeding up rendering by creating textures on the fly for static/repeating elements?
  • Sprites? (if it's a game, why do I write it like an application?)

Logged

a-k-
Level 0
***


View Profile
« Reply #4 on: April 02, 2016, 01:54:51 AM »

This is a fresh new feature. I am currently leaning toward having a hint system for the first level two levels instead of a regular tutorial, mainly to encourage users to experiment, read tooltips etc.

Hint system (80-100% complete):
  • Can be toggled (off by default)
  • Hints such as drag from X to Y, click Z
  • User is not required to follow the hint: a new hint is generated upon any user action
  • Given the current user program and a set of predefined solutions, determines the next program edit toward a solution
  • Greedy algorithm with backtracking, foolproof (there is always some hint)

Open:
  • Alternative hints for editing by the keyboard? Click X or press Y?

Example: (actual commands have been replaced with numbers)

« Last Edit: May 14, 2016, 12:03:03 AM by a-k- » Logged

a-k-
Level 0
***


View Profile
« Reply #5 on: April 15, 2016, 11:13:46 PM »

Nondeterministic programming language:
  • Executing command C, under certain conditions, can yield any one of multiple outcomes (say, either X or Y)

For programs to produce reliable outputs, users can either:
  • Design their algorithms taking into account both possible outcomes X and Y, or
  • Manipulate the circumstances so that command C behaves deterministically

Approaches for testing user programs:
  • Random nondeterminism: command C will do X or Y with equal probability.
    Caveat: users may circumvent the nondeterminism by executing C repeatedly until it produces X not Y.
  • Adversarial nondeterminism: choose X/Y so as to make the program produce incorrect output, thereby failing the level.
    Caveat: forking the program whenever command C executes results in combinatorial explosion.
  • "Arbitrary nondeterminism" (selected approach): run the program against both random X/Y sequences and contrived ones (XXXXXXXXX...)
    Motivation: ensuring reliable program design by approximating the adversarial approach.

Problem is, this aspect of the language is not easily transformable into a consistent user experience.

Simple example in C:

« Last Edit: May 14, 2016, 12:02:04 AM by a-k- » Logged

a-k-
Level 0
***


View Profile
« Reply #6 on: April 23, 2016, 03:45:46 AM »

The pain of 1-based numbering...
How should I go about displaying a table so that the player can spot easily which numbers are marked by an 'X'?

?

?
Logged

a-k-
Level 0
***


View Profile
« Reply #7 on: July 30, 2016, 04:53:31 AM »

What:
As the player edits the program, she is presented with an equivalent program in C++ that clearly shows the control flow.

The challenge:
The source programming language has no structured control facilities (e.g. no while).
While transpiling to C++ with goto statements is trivial, the challenge is to discover the underlying control flow and output a C++ program that reflects it (e.g. shows loops explicitly).

Initial attempts:
Not having the time to reinvent the wheel, I had played with multiple non-commercial decompilers, as structural analysis is an important step towards legible C/C++. However, I hadn’t found anything that is not bugous and/or has impossible dependencies. Then I came across the Relooper algorithm that is part of Emscripten.

Relooper converts a given control flow graph into JavaScript. It is a real gem, but for my purpose it had two significant gaps:
  • It creates JavaScript that is optimized for browsers, not for human understanding.
  • In order to workaround over JavaScript’s absence of goto, it sometimes creates convoluted logic in the form of if (label==5) { do_something; } else if (label==12) { do_something_else; } else { yet_another_case; }

Final approach used:
In the end, I’ve rolled my own algorithms around Relooper’s ability to detect loops and output a reasonable ordering of the code blocks. This was more involved than initially anticipated, but I’ve had so much fun!

A simplified diagram of the overall algorithm that takes place on every edit to the program:


Simple example:

Source program (numbers specify basic blocks):



Resulting C++ code:



More complex examples can have if statements as well as break/continue/return, and as a last resort, also goto.
Logged

a-k-
Level 0
***


View Profile
« Reply #8 on: August 26, 2016, 03:11:23 AM »

So far I've created a few tens of programming puzzles to experiment with, ranging from introductory levels (without descriptions yet) to challenging ones. I guess that about half will get scrapped over time, but it's a good start.

Basically I'd like to target both programmers and non-programmers, players that always strive to find optimal solutions and those that just want to proceed and explore the next levels. So there are 3 or 4 quadrants of players, and the design challenge is to create an interesting experience for all, closing skill gaps with little overhead on the highly-skilled.

Level progression will certainly be non-linear, with multiple routes arriving at the same level. Beyond "prerequisite" relations between levels (or groups of levels), some kinds of levels that I'm considering include
  • "Hint levels" that appear only after the player fails to solve a level, presenting a simpler problem whose solution is related to the failed level
  • "Exempted levels" that can be skipped if the player already solved a more challenging level that employs equivalent tricks
  • "Optimization levels" that only accept solutions having optimal metrics
  • "Challenge levels" that are not mandatory for completing the game
  • "Milestone levels" that serve as a gate, giving a waiver from solving preceding levels and enabling subsequent ones

In addition, the following aspects will need to be handled:
  • Presenting the levels map clearly with all the inter-dependencies and optional routes
  • Presenting the relevant information gradually to the player according to the actual levels history and which level they choose next
    • New commands, new screens (e.g. choosing an input for multiple-input levels), etc.
    • Explanations of special behavior of commands (if not already noticed by the player)
    • Relevant programming practices (e.g. loops, if not already attempted by the player)
    • Unlocked GUI elements (e.g. clipboard)
    • Productivity tips (e.g. keyboard shortcuts)
    • Advanced facilities (e.g. C++ code)

I get the feeling that such a system may be complex for the regular player, but falling back to linear progression will be too limiting. Much work ahead...
Logged

Excy
Level 2
**



View Profile
« Reply #9 on: August 26, 2016, 04:09:34 AM »

Very interesting. Seems like the type of game I'd play through in one sitting. Looks pretty neat, keep it up.
Logged

a-k-
Level 0
***


View Profile
« Reply #10 on: September 03, 2016, 12:26:41 PM »

Currently I use zlib for compressing font files, with the standard Deflate (zip) algorithm. A Python script running as a pre-build step packs them into portable "resources files" (actually .cpp files) that are linked into the final executable, so that everything that's required is available by downloading a single file.

With Facebook's release of their new Zstandard compression algorithm a few days ago, I was compelled to benchmark it against zlib Deflate. For my purpose, only file sizes mattered (not speed), and only at the highest compression level possible.

Initially, running Zstandard on my use case (6 TrueType fonts) produced disappointing results - only 45% compression ratio, comparable to Deflate. However, since all font files are of the same family, I tried concatenating them all to one file, then run the benchmark again. While this didn't have any effect on Deflate (stayed at 46%), Zstandard succeeded to exploit the redundancies and achieve a compression ratio of 29% - much superior to Deflate:



Might be interesting for those of you using their own custom engine (of course, YMMV).


Very interesting. Seems like the type of game I'd play through in one sitting. Looks pretty neat, keep it up.
Thanks! Also for being the first TIG commenter Smiley
« Last Edit: September 03, 2016, 08:26:50 PM by a-k- » Logged

a-k-
Level 0
***


View Profile
« Reply #11 on: October 01, 2016, 04:54:32 AM »

Development status:



Settings screen (always accessible):



Anti-aliasing settings are as follows:
  • High - MSAA
  • Med - OpenGL polygon smoothing, no MSAA
  • Low - no AA + special optimizations for computers without GPU
Also experimented with Anti-Grain Geometry, but haven't seen much improvement over naive OpenGL in my case.

Adapting to different aspect ratios (16:9 is best) and arbitrary window sizes:


(Recorded without scaling - the window was 400 pixels wide.
 The programming model is not shown.)
« Last Edit: October 01, 2016, 05:11:44 AM by a-k- » Logged

a-k-
Level 0
***


View Profile
« Reply #12 on: October 16, 2016, 05:50:19 AM »

Portability to multiple PC platforms has always been on my mind, but only recently have I put it to the test. To my surprise, the transition from 32-bit Windows (VC++) to 64-bit Linux using gcc was quite easy, in the sense of getting something working fast. But packaging the result into a delivery that works across a variety of Linux distributions, new and old, was more involved.

As it turns out, the general advice for closed-source Linux applications is usually a combination of
(1) build the application on some old Linux distro,
(2) use specialized toolchains & build environments, and
(3) reduce/tweak application dependencies.

I should admit, I didn't like (1) and (2) too much, mostly due to security considerations and ease of use - I preferred to use an up-to-date Linux distribution with its standard gcc and libraries, all downloaded from their official repositories. But I had to start with something so I tried (1). In my case, at least, it didn't work - building on Ubuntu 12 LTS resulted in a binary that didn't load on Ubuntu 16 LTS (and neither did the opposite direction, of course).

To make a long story short, in the end, I relied solely on (3) and succeeded to follow my Windows approach, namely, have the entire game reside on one executable file that has all the needed software dependencies and game assets. So I have a stock Ubuntu 16 64-bit installation (in VirtualBox) with its standard libraries & tools, that builds one binary for 32-bit Linux and one for 64-bit Linux.

A few Linux tips for the interested (technical):
  • Libraries that must not be linked statically #1: GLIBC (libc, libm, libdl, librt, pthread)
  • Libraries that must not be linked statically #2: OpenGL and X11-related (libGL, libX*, ...)
  • Libraries that should be linked statically (assuming gnu not clang): stdlibc++ & libgcc
  • Libraries that are safe to link statically, if desired: handling of fonts/images/compression (FreeType, png12, etc.)
  • Libraries that had better not be linked at all (use dlopen()): device management (udev)
  • Dependency reduction (assuming gcc): use --wrap to selectively implement missing glibc functionality (e.g. __isoc99_sscanf in terms of vsscanf) so that any statically-linked library will use your version instead.

Now back to Windows, the game is not complete yet...
Logged

Pixel Noise
Level 10
*****



View Profile WWW
« Reply #13 on: October 16, 2016, 06:18:41 AM »

My only concern is that this seems like it requires some level of knowledge with how programming, etc, already works, or else the player is going to be completely lost?
Logged

Pixel Noise - professional composition/sound design studio.
 https://soundcloud.com/pixel-noise
 https://twitter.com/PixelNoiseMusic
 https://pixelnoisemusic.bandcamp.com/

Recently completed the ReallyGoodBattle OST!  https://www.youtube.com/watch?time_continue=2&v=vgf-4DjU5q
a-k-
Level 0
***


View Profile
« Reply #14 on: November 05, 2016, 02:04:54 AM »



My only concern is that this seems like it requires some level of knowledge with how programming, etc, already works, or else the player is going to be completely lost?
There are only 6 commands, how difficult could it get?  Wink

Seriously, this is a valid concern, thank you for raising it. Trying to put myself in shoes that have never programmed, one way to classify difficulty is as follows:
  • Currently, the "first" 15 levels (not necessarily first, it all depends on the player) do not require conditional logic or loops, so I believe everyone will be on the same playing field.
  • Following them are levels that require only simple loops (usually one).
  • Starting with Area N, nested loops may need to be employed (1 level of nesting at most, i.e. one loop inside another).

Sure, it will help to have prior experience with the genre or with programming. But the game should be challenging for everyone, since the underlying language demands the development of peculiar techniques for solving problems.

A note about the linear code presented in the last posts: it is optional and mainly oriented towards advanced players. Once I show the visual model that programs manipulate, it will become easier to discuss the accessibility of the game to novice players. This will take some time, though...
Logged

Pineapple
Level 10
*****


~♪


View Profile WWW
« Reply #15 on: November 05, 2016, 05:17:39 AM »

This looks awesome. I'm really interested to see where this goes!
Logged
a-k-
Level 0
***


View Profile
« Reply #16 on: November 25, 2016, 05:27:32 PM »



In order to support multiple resolutions, everything except text is drawn using vector graphics. This makes rendering depend on the OpenGL implementation and produces artifacts related to line widths and antialiasing (below, 'GL' rows, MSAA=4):



To solve this, I've been experimenting with turning this icon into a TTF and using FreeType's automatic font hinting. The result ('FT' rows) is more consistent but with the icon having two colors, I need to render two glyphs at the same position - a fill (from '2' inwards) and an outline (from '1' to '3'):



Oddly enough, sometimes the two glyphs are off by 1 pixel even though in FontForge they look perfectly-aligned. Making the bounding boxes of the two glyphs identical by adding small squares at the corners didn't seem to help. I will need to look further into this.

---
On another note, I've finally converged with a name for the game. The previous one I had in mind (two words, ending with '-arium') implied a scope that was beyond my plans (and graphic skills). The new name better reflects the abstractness of the game and can also serve as a name for the programming language itself. But I think I will keep the TIG title as is for now.

This looks awesome. I'm really interested to see where this goes!
Thanks! So much is still open...
Logged

a-k-
Level 0
***


View Profile
« Reply #17 on: January 07, 2017, 02:40:49 AM »

Imagine that you are debugging your game in your favourite IDE. In the middle of debugging, you decide to arrange the code a bit differently without changing the program's semantics - reorder the functions, move some to different files, add some comments with your insights and so on.

So you do the changes, and then you continue debugging the program from where it was. Since your IDE also supports stepping backwards in time, you try that and the "program counter" follows your code in its new location(s), as if the program had always been arranged like that since the start of your debugging session.

Now I don't know about the IDEs you use, those that I'm familiar with do not support anything like that. Luckily, I have implemented this functionality in my game so players can enjoy it. I did it mainly for fun (my fun, apparently) and it doesn't get the game any closer to an MVP, but it can serve as a basis for a more useful feature that I plan to implement in the future. To be discussed...

---
Mini-game --> Message --> Startup screen --> Level selection

As the player runs the game for the first time, they are presented with a mini-game where they are asked to complete some task with their mouse. Once done, a new screen opens, showing a message explaining that the mini-game was useless, and why. Only after that does the real startup screen appear, with the name of the game and so on.

For a long time I haven't felt I had a good way to describe a key aspect of the game for beginners, and I believe this new scheme should solve that. It's a bit risky, since the mini-game may make the actual game appear as a casual puzzle game (maybe there's already a similar game somewhere based on this mechanic!) and not as a programming puzzle. But I guess first-time players will not come across the game by chance, so they'll already know what this is all about. Time will tell...
Logged

a-k-
Level 0
***


View Profile
« Reply #18 on: January 28, 2017, 03:19:15 AM »



Every user solution is measured along two metrics:
  • Program cost - each command used is 1 unit of cost, except conditional commands which cost 10. The motivation for the difference is discouraging over-complicated logic and favoring elegant solutions.
  • Running time - basically, this is the number of steps till program completion. In practice it's more complex than that.

Due to the natural trade-off between the two, solutions are only partially-ordered so there may be several optimal ones. Right now I'm thinking about implementing the following scheme:
  • Solutions that are worse than mine - 2 or 1 stars
  • Solutions that are better than mine (if exist) - 4 stars
  • All the others - 3 stars (except 4 stars for special cases)

I find this scoring system compelling thanks to its simplicity. But it has two main drawbacks: I'd like to communicate the conditions for achieving 3 stars to the user, but I don't know yet how to best do that. In addition, I can't know in advance, for each level, whether 4 stars are possible or 3 stars are the max...
Logged

a-k-
Level 0
***


View Profile
« Reply #19 on: February 04, 2017, 06:23:33 AM »

It seems like I've been keeping the progress indicator here at for a year now - it's funny how every feature added gives room for yet more features to no end...

At least in terms of level progression, I had a lot of ideas but ultimately converged to introducing Cheat Mode as a means of easing the difficulty.


("cheat" indicates Cheat Mode is available, levels numbering is arbitrary)

  • When activated, Cheat Mode enables the player to use commands and facilities not normally available in the level.
  • This can make solving the level easier (sometimes much easier), providing a good starting point for a real solution.
  • Once solved using unpermitted commands, subsequent levels are unlocked as if the solution were real.
  • However, no credit is given for the level - only real solutions count.

I hope this mechanic will enable me to keep the levels as condensed as they are now. We'll see.
« Last Edit: February 24, 2017, 12:37:58 AM by a-k- » Logged

Pages: [1] 2 3 4
Print
Jump to:  

Theme orange-lt created by panic