Dialog

I want to be able to let the user input a four-digit hexadecimal number and use that number, after some bitwise manipulation, to procedurally generate a room description.

…Ghost of Mike Singleton, is that you?!

:slight_smile:

I know who that is, thanks to Wikipedia, but I don’t get the joke.

Singleton did a lot of procedurally-generated-world games for 8-bits (Lords of Midnight, Star Trek: Rebel Universe, etc.)

Interesting! There are a number of problems.

First, you’d have to convert the player’s input from a word to a number. A feature that has already been suggested is the abity to convert a dictionary word to a list of characters. That would solve the problem partially. But if all four hexadecimal characters are 9 or less, the word of input would be represented as an integer instead, and you’d have to deal with that somehow.

Then there’s the problem of being limited to 14-bit numbers, as you’ve pointed out.

Next, there are no bitwise operations. You could use multiplication, addition, and modulo to implement a crude PRNG, but you would have to rely on undefined behaviour (when multiplication overflows) and deal with the fact that addition fails on overflow.

I think it would be better to have a way to seed the built-in random generator of Dialog in a predictable way, that works the same on every backend, platform, and interpreter. That way, players could communicate out-of-game and exchange interesting random seed values. And it would be possible to use e.g. (select) ... (at random) when setting up room properties.

The question is then, what would the API look like for seeding the randomizer? A single number contains too little entropy, so perhaps a list of numbers? In that case, the player’s input could be converted to a list of four numbers in the range 0–15, and that list could be used as a seed. Additionally, this would support a use case where coordinates are used as a seed value.

1 Like

If I remember correctly, multiple recursive generators (like L’Ecuyer’s MRG32k) do the job with only basic arithmetic ops. But I don’t think you’d get much done in 14 bits (I guess it would have a very small period).

Another way to seed it would be to hash each character in the input string, and modify all parts of the internal state based on each hash. That way you could accept any string for the seed. (I don’t know what kind of RNG you use, but supposing your kernel values were all between 0 and 1, and your hash function returns values in the same range, you could just subtract each hash value from all kernel values, having them wrap around if they go negative, after setting up initial kernel state).

A 16 bit Xorshift* generator should be adequate. I’m assuming you could use the full 16 bits for internal code.

Whoops, my last comment might not have been very clear. I meant to suggest CMRGs as a family of PRNGs that might be appropriate for environments where you only have ints and don’t have bitwise ops (that was more for @FredMSloniker). I’m facing a similar situation here, due to an ungodly decision to use unary math somewhere, so I’ve had to think about this lately (otherwise I probably would have gone for xorshift).

Second paragraph was for @lft; it sounds like he already has a good PRNG and is just thinking about how to seed it. I’ve seen that method of hashing each character in a string used before across multiple different PRNG families and it seems to work well for just about everything.

Hi all! Due to the overwhelming demand on this thread, we’ve created a Dialog category under Authoring. If you have questions or discussion about writing using Dialog, feel free to start a topic there!

The discussion under “development systems” can be used for discussing the system itself. So “how does it do tail calls in the Z-Machine?” and status updates can go in the development systems discussion, but now you can make Authoring posts for things like “how do you teleport a player to a new room/location.”

I’m not going to try to move any of the discussion here yet to the Authoring category, because it seems kind of complicated to unpick the threads of what would go in what separate Authoring posts, but if anyone has ideas for something to move to a separate Authoring thread let me or the other mods know.

Hopefully this will make the discussion easier to follow, and congratulations Linus on such an enthusiastically received system.

9 Likes

Given that Dialog is a logic-programming language, it would be cool if you could “run games backwards.” In the same way that an interpreter running backwards can synthesize programs, running a game backwards might let you synthesize possible player input from actions or test winnability by automatically playing through a game.

With the way the language is now, though, that can’t be done, since constructs like (just), (stop), (select), dynamic predicates, etc. are impure (and likely for good reason–performance, practicality, or otherwise). But if you could write an entire game as a relation (maybe in miniKanren or pure Prolog), it would be neat to see what you could do with it.


Other things:

  • Typing ({0}) into the debugger causes a crash.
  • It’s (non-empty $X) in the quick reference but (nonempty $X) in the standard library.
  • In this output from split:
    > *(split [a b c] by [a b c] into $Left and $Right)   
    Query succeeded: (split [a b c] by [b c] into [] and [b c])
    Query succeeded: (split [a b c] by [c] into [a] and [c])
    Query succeeded: (split [a b c] by [] into [a b] and [])
    
    it looks like second argument is unified with $Right. I guess it doesn’t matter since that argument must be bound, but it is a bit strange to see it changing values.
1 Like

Backward-chaining, goals-based evaluation is something I’ve been wondering about lately too (not specifically in Dialog). One application where it could be immediately useful would be auto-travel / “go to” command, so it’s an interesting case to consider. That is, the “facts” are you are in location A, and what the room connections are, and the “goal” is you want to be in location B.

The thing is, I think even in a pure system you’d run into issues of practicality here. Consider four locations, each with a connection to the other three, in an undirected graph (no one-way doors). Asking how to get from location A to location D has infinitely many solutions, because of loops. There is one best solution, straight from A to D. Two 2-step solutions, A-B-D and A-C-D. Two three-step solutions, with no loops.

So even in this simple case, there’s a lot more that needs to happen to get some useful behavior out of backward-chaining, where forward-chaining is really pretty straightforward.


A few other considerations about the pathfinding thing. Consider this room layout:

  B
 / \
A-C-E
 \ /
  D

There are 3 paths from A to E that just take 2 moves, but we’d probably want to prefer the A-C-E path. Could do it by preferring cardinals to diagonals, but that has to be done carefully.

A-B-C
|\  |
D E F
|  \|
G-H-I

If we always prefer cardinals, that layout would be solved in 4 moves instead of 2. So we can’t prefer cardinals unless we have a situation like for example where we’ve calculated a Dijkstra map and are just deciding between two next-steps that have the same value.

So I guess what I’m saying is you can’t just take an existing rule set and start backward-chaining it to do much of anything useful, you need new rules that help the backward-chaining figure out what to do. It’s definitely an intriguing idea, though.

@Pluie, thanks for the bug reports! I’ll take a look.

As for synthesizing input from output, I agree with your list of obstacles, and would like to add the fact that most queries only return the first match. This is such a central design element of the language that it’s hard for me to imagine a Dialog program that avoids it entirely.

That being said, the language is very amenable to opportunistic static analysis, as one would use in an optimizing compiler. For instance, traits like (item $) or (openable $) tend to be defined using simple, straightforward rules, and the compiler is generally able to reduce them to per-object flags.

Here’s an example of opportunistically “running the program backwards”: The compiler analyzes the (dict $) predicate for each object, and figures out what words can come out. The result is inverted into a word-to-object lookup table, which speeds up the in-game parser. To do this, the compiler must explore every branch of the decision tree, and e.g. look at what happens both if a dynamic predicate succeeds and if it fails.

But the whole operation needs to be approximate. It needs to stop recursion early, for instance, because the base case could depend on a dynamic predicate. And words like “open” and “closed” would both show up as potential output from the dict rules of every openable object. So words like these have to be eliminated from the result, to prevent the table from growing ridiculously large. Therefore, if the player types “open closed”, the game would still have to enumerate every object in scope, and weed out all but the openable, closed ones. But in most cases, like “open safe”, the game only needs to consider a handful of objects, and then weed out the ones that are out of scope.

That optimization improves parsing speed significantly on old hardware, and it wouldn’t be possible in a language where everything by default is stored dynamically on the heap, and updated imperatively. Dialog still allows the programmer to put everything in dynamic storage, in which case the optimization doesn’t work. But because the language encourages a declarative programming style, most programs end up being transparent enough for this kind of analysis.

@cpb, path-finding is already part of the standard library. It currently uses a variant of Dijkstra’s algorithm, although I’ve been meaning to replace it with a breadth-first search (because the edges don’t have weights). This can be done using ordinary forward-links. But in other places, the map-connection predicate is indeed queried “backwards”. To provide reasonable default behaviour for commands like “enter the red door”, the library needs to figure out in what direction there’s a link to the indicated door object, and then redirect to the action for going in that direction.

2 Likes

path-finding is already part of the standard library. It currently uses a variant of Dijkstra’s algorithm, although I’ve been meaning to replace it with a breadth-first search (because the edges don’t have weights).

Hmm, if the edges don’t have weights, isn’t Dijkstra essentially already a BFS? I’m curious to see that code now. Thinking about it, giving diagonals slightly more weight could be an easy way to prefer cardinal directions, but only in cases where they wouldn’t create more steps.

Was also thinking bidirectional search could work well for pathfinding, just need to go the “wrong way” down any one-way connections on the back half. Of course if a regular BFS is fast enough, might be more trouble than it’s worth.

This can be done using ordinary forward-links

Definitely, but auto travel could also be a “winnability test” for some hypothetical game where you just need to walk to the exit, so doing it “backwards” is an interesting thought experiment as far as what might be required for a game solver.

But in other places, the map-connection predicate is indeed queried “backwards”. To provide reasonable default behaviour for commands like “enter the red door”, the library needs to figure out in what direction there’s a link to the indicated door object, and then redirect to the action for going in that direction.

Interesting, never considered backwards-chaining for something like that. In the thing I’m working on, I might write something like this:

player is in bedroom.
closet is west of bedroom.
"red door" connects bedroom and closet.

$someone wants to enter $something,
$something connects $here and $there?
$someone is in $here? $there is $direction of $here?
    $someone wants to move $direction.

Actually there might be a few more rules for if player is “there” instead of “here,” or to assume that bedroom is east of closet, but you get the idea. A lot of backtracking surely needs to happen to resolve all the free variables, but it’s not a “reverse application” of the rules to achieve a goal, just a normal forward application (the rule matches existing facts, and a new fact is inferred).

Dialog version 0h/02 (library 0.30) is a minor upgrade to fix the bugs reported by @Pluie. It also generates slightly more efficient Å-machine code.

I wrote an extension for VS Code which provides some language support for Dialog:

https://marketplace.visualstudio.com/items?itemName=sideburns3000.dialog-language-support

Further information is in a neighbouring thread (I basically posted the readme file there, which I didn’t want to put into this thread here in its entirety, as it also includes several screenshots).

4 Likes

Version 0h/03 (library 0.30) fixes a bug that would crash the compiler if you tried to make a zblorb from a very small program (i.e. without the standard library).

There’s no pressing need to upgrade this time, but the bug was causing trouble for newcomers.

3 Likes

IFComp is around the corner, and I’ll participate with a Dialog game. Since I don’t want to bring undue attention to my entry during the judging period, I’ve decided to refrain from discussing Dialog in public. If you have urgent questions, please get in touch by private message.

This is perhaps an overly strict interpretation of the rules, but I’m going to have a limited amount of time for engine development anyway. I shall be reading stories.

2 Likes

Short of an AOT cross-compilation ala ClojureScript, I don’t think it would work that well, not just because strings are clumsy, but because all the other times people have hacked Clojure syntax to emit code for another language from within Clojure, it has failed. I had to work on Palette for a while, and it had a macro to emit Bash script from Clojure code. Bleeding from the eyes was a normal reaction.

I’m turning into a big fan of Dialog, but my current Inform project (still just starting even after several years of futzing around - I get a few minutes a month for personal coding due to kids and other responsibilities) uses Threaded Conversation heavily. I’d want to port that over I think.

1 Like

Please feel free to start separate new topics in the (relatively) new Dialog category instead of continuing this megathread. We’re glad there is so much interest in this new language and that is why many people requested it!

https://intfiction.org/c/authoring/dialog

2 Likes

New releases will be announced in this thread from now on.

1 Like