Game Programming in Prolog | Hacker News Reader

Game Programming in Prolog

thingspool.net

283 pointsfebin62 comments

Open articleView on HN

Normally we downweight posts that just have a Part 1 and then stop, but this one actually delivers the goods:

https://thingspool.net/morsels/page-11.html (part 2)

https://thingspool.net/morsels/page-12.html (part 3)

https://thingspool.net/morsels/page-13.html (part 4)

https://thingspool.net/morsels/page-14.html (part 5)

(and keeps going!)

you should consider the opposite to push the author's website and force them to continue ;)

We optimize for reader satisfaction, not author satisfaction—but that's probably in the author's best interest too!

(Will be continued in Part 13)

It will take me to read this book, but I love it! I'll be following along in https://github.com/mthom/scryer-prolog (written in Rust) so one should be able to take these techniques into Rust game programming.

Assume you are the author, I found your website is such a treasure. I couldn't believe your website wasn't listed on HN before. Next time please post on HN when you write.

I am not, just a huge fan of prolog and works of passion like this.

+1, this entire website is a fascinating find. Interestingly, in terms of formatting, all the long-form texts on the site are centered (as opposed to left align). I wonder what's the logic behind this decision (surprisingly, it is not at all annoying to read, though).

Maybe change the link to the index?: https://thingspool.net/morsels/list.html

It's better for the linked article to have substantive, interesting information on it, not just a list of links. HN is already a list of links, so that's too much indirection.

The Breath of the Wild game design has a concept called the "Chemistry Engine". In that game engines usually have a physics engine to figure out how things interact in a motion sense. The chemistry engine figures out how materials interact in an alchemy sense. It's kinda like a rules-based engine to figure out how different things interact with different other things, so you get surprising interactions between everything in the world, like being able to light arrows on fire, because arrows are a "wood" material.

The Youtube link is here: https://www.youtube.com/watch?v=QyMsF31NdNc&t=2354s

It seems like most rule-based stuff in games is just hand-coded, as it's relatively simple and doesn't need to be general. When I asked the author of Baba is You, if he implemented a datalog engine for it, he said 'no'. I suspect it's the same for Breath of the Wild.

But still, I've often wondered if that sort of chemistry engine would be best implemented in a logic language like Prolog or Datalog, for fast experimentation. Just like how we use SQL to keep the flexibility of our queries, and we end up just shipping that. I'm sure, back in the day, lots of people lamented how slow SQL queries were. The flexibility was useful enough that we ended up pouring man-centuries into making them fast. Now, we think that's just the way you ship things, and (almost) never think, "I can hand-roll imperative code that will be faster than this query".

Noita is a game based around the concept of a chemistry engine running at the pixel level. It uses a custom rules engine written in C++.

It's one of the more interesting games I have ever played.

https://store.steampowered.com/app/881100/Noita/

https://www.youtube.com/watch?v=prXuyMCgbTc

Noita is an amazingly complex game, from the alchemy reactions, to the cryptographic secrets [1], to the wand building mechanic -- which is itself like a small programming language.

Here is someone using a (really complex) wand to beat the game in 2 seconds (some spoilers): https://youtu.be/YYTB5_zBANg?feature=shared&t=309

[1] https://noita.wiki.gg/wiki/Eye_Messages

Man, I wish I was good enough after 110 hours to experience the other half of this game's content. I'm still stuck dying in Hiisi base... Still fun tho!

That object system it's the literal design of the ZMachine. Objects can atributes the same way objects and methods in OOP programming.

Also, probably, MUDs.

What graphical games are trying do to at something 'revolutionary' text games did that before 40 years ago with interactive fiction (more in the 90's with the reinassance of astounding amatur games such as Curses/Jigsaw/Anchorhead/Devours/Spider and Werb than the former Infocom games); roguelikes like Nethack/Slashem and CDDA:Bright Nights and online MUDs far beyond the usual fantasy settings, such as cyberpunk or scifi settings with weird materials and interactions.

The best game creators such as Warren Spector surely played with libre games/indie/geeky games too to bring new ideas to the gameplay.

I think referencing Nethack in the original Deus Ex wasn't just a happy easter egg, but a homage to the emergent gameplay probably inspired by it.

The best about Deus Ex weren't neither the graphics or lore, but what you could do in-game, breaking the linear settings on FPS' and making them accesible unlike System Shock 1 and 2, where they tried and failed because the game difficulty didn't scaled well and the gameplay wasn't as polished. Ditto with Arx Fatalix (now Libertatis) and Ultima Underworld.

(With the caveat I haven't read OP article yet) I was enamored of using relational programming for a games engine for many years. Ultimately I concluded it would be better to code such an engine in C++ and write custom solvers for just the aspects you want to be relational, rather than do the whole game in a general purpose relational language.

The resolution algorithm(s) implemented by a general purpose logic programming or relational language are not the only ones possible, and being more general may not be efficient for the type of problem you want the game engine to solve efficiently. Conversely extending a logic programming language to natively include these features may invalidate simplifying assumptions or require a change in evaluation order that makes the language impossible to implement as simply or efficiently.

A concrete example (of extending logic programming with game specific features):

I wanted to both use logic programming relations and also linear constraints, so that you could say something like "A <= (B-10.0) .OR. B <= (A-10.0)" which you could picture as constraining the position of the centers of two width=10.0 game objects so that their boundaries do not overlap, but you don't care which is in front of the other. (Statements like this would be used to build up a scene or more complex game object qualitatively, without pinning down exact coordinates rather letting the linear constraint solver pick them.)

Since running the linear constraint solver to resolve something like "f(A) <= g(B)" actually (potentially) updates all of the interrelated variables (A or B might also have constraints against C,D,E,F), running it as soon as you pick the LHS or RHS of the logic expression "prop(X) .OR. prop(Y)" could potentially invalidate propositions elsewhere previously committed to. So what you probably want to do is, rather than interpreting the "<=" on linear variables as a test with a boolean result, interpret it as a command to add "f(A) <= g(B)" to the global store of linear constraints, and then at some later time run the solver on the complete matrix of linear variables.

That leads to design questions like how does the language know when it's done adding constraints and time to solve, what if we really do need a logic clause to depend on testing a value not constraining it, etc. But all of that's just a distraction from the real issue, which is that for the case of BOTH the linear constraint solving and the logic programming, in the context of a game engine we really need to have more control over both when lengthy computation is run and how long it runs.

That is, even if we design a good way for the extension features to run from the POV of the logic language, from the POV of the outer system we still have the problem of sometimes the search time to resolve part of a logic program blows up and it's difficult for the programmer to always predict when/where that will happen. In this sense it's not even required that hand-rolled imperative code be faster, it can be slower - as long as it's predictable.

And in reality you wouldn't even necessarily be hand-rolling it; what I'm talking about is whether the rules engine is a solver that is externally driven (and pre-emptible) by imperative game code, or the whole game runs within the "solver" (i.e. relational language). As tempting as it is to imagine what could be done if literally "the whole" game were relational, the fact is using that technology for a whole game implies a magic relation solver that doesn't actually exist.

Reminds me of dwarf fortress. Silver hammers make more damage because silver is heavier. Wooden furniture will burn. Liquids will deposit in your clothes from rain or blood, which you can then drink. So much interesting complexity arises from simple mechanics.

This is an interesting take on Prolog game programming in that it's going straight to "action games" with a realtime, timeline, 3D, ECS, and event aspect. When most introductory texts on Prolog game development start with adventure games, in particular classic text adventures, since those build directly on Prolog constructs such as facts and rules for eg. mazes and inventory puzzles, and also DSLs. Or card and board games, the rules of which can be expressed so conveniently using Prolog, and can then almost trivially be extended into basic combinatorical general-purpose game opponents, not dissimilar to Prolog planners in robotics, logistics, finance, industry, etc.

When I took an AI class, the first thing they taught was Prolog and for exercises we all had to write adventure/colossal cave style games in it. Prolog turned out be well suited to the task. The variety of simple games made in the class was astounding and I wish I could have collected the all the games made by the other students. We only spent a couple of weeks before moving on to other topics, like CLIPS and Lisp. In my own assignment, I made a Bureaucratic Maze [1], again, fairly straightforward in Prolog.

[1]. http://logicmazes.com/bureau/index.htm

https://amzi.com/AdventureInProlog/ teaches prolog the same way.

With Common Lisp you literally write one in Land of Lisp as a beginners' exercise.

But with Inform6, the OOP applied to game design and literal ingame objects' relation (as the ZMachine) states it's when the difficulty plummets down to the point to be trivial.

@JoeDaDude -- on macOS using recent Chrome/FireFox the puzzles linked from the top-level page yield terminal JavaScript errors. It'd be great to see them in action.

http://logicmazes.com/alice.html

  alice.html:353 Uncaught TypeError: Cannot read properties of undefined (reading 'play')
      at playSound (alice.html:353:30)
      at finalize2 (alice.html:347:1)
      at <anonymous>:1:1

I skimmed through all 12 posts, and while it seems like it might be a good introduction to using Prolog, it seems a stretch to claim this has anything to do with game programming. Maybe that will develop later, but so far after 12 lessons, it's been mostly concerned with trying to model a few OOP concepts in Prolog.

Not sure if I'm missing anything, but nothing yet has been concerned with any kind of user interaction which would seem to be a pre-requisite for a game, although there was a brief discussion about sending messages so maybe that's what he was intending.

In the same vein, I had a lot of fun reading a game programming book with logic programming, but instead of Prolog it used CLIPS:

Adventures in Rule-Based Programming: A CLIPS Tutorial https://a.co/d/7wVOcZp

I was going to mention that one as well. I was exploring using CLIPS (or something like it) for a system at work and after digging through the free documentation I picked it up. It was an enjoyable read.

https://www.clipsrules.net/

https://ryjo.codes/ has a lot of good material on CLIPS.

Huh that sounds fascinating. Any idea if the kindle version is any good? Most programming books are awful on kindle (though I do have a Fire tablet which it might be fine for).

I read it on Kindle. It was good enough. The code formatting was normal.

Note, I read it on kindle as well, and like many kindle editions sometimes the '-' character is replaced by some weird thing that isn't a dash. I had a hell of a time figuring out what was going on when I copy and pasted code from the book... :]

There's an interesting (to me at least) overlap between gamestate as a set of facts and relations(Prolog), and the point of ECS("This is a database"[1]).

I personally experiment in Datascript as a gamestate db, but it's still quite an early attempt to conclude if it's a success. It's great seeing how ideas in this tutorial map 1-to-1 to that idea.

1. https://www.gamedevs.org/uploads/data-driven-game-object-sys...

To me the interesting thing is the logic programming "rules" and their overlap with game rules. Inspired by work at Stanford on the logic programming based Game Description Language [1] I implemented Tic Tac Toe in Datascript yesterday: https://github.com/kasbah/datascript-games/blob/e06a37025bf9...

I am still not clear whether there isn't a more succinct rule definition than what I have there. In the Stanford paper you have rules like:

   (<= (column ?n ?x)
     (true (cell 1 ?n ?x))
     (true (cell 2 ?n ?x))
     (true (cell 3 ?n ?x)))

But in Datascript I have to do much more rigmarole around shuffling the data around:

  [(column ?n ?x) 
    [?current "ident" "current"] 
    [?coord0 "type" "coord"] 
    [?coord1 "type" "coord"] 
    [?coord2 "type" "coord"]
    [?coord0 "m" 0] 
    [?coord1 "m" 1] 
    [?coord2 "m" 2] 
    [?coord0 "n" ?n] 
    [?coord1 "n" ?n] 
    [?coord2 "n" ?n] 
    [?coord0 "name" ?key0] [?current ?key0 ?x]
    [?coord1 "name" ?key1] [?current ?key1 ?x]
    [?coord2 "name" ?key2] [?current ?key2 ?x]]

I don't know if this is down to Datascript/Datomic Datalog limitations or more the limitations of my understanding.

How do you approach your experiments? If you have any of your work to share or some tips on what I am doing I'd be very interested.

[1]: https://www.cs.uic.edu/~hinrichs/papers/love2006general.pdf

This is a consequence of the Datomic information model which is focused on handling a single universe of triples (to facilitate natural schema growth) instead of independent n-ary relations. However unlike when building serious business applications, for most simple games you probably won't ever care about the ease of handling the schema growth of persisted data. You would likely care more once you think about supporting long-lived multiplayer environments or introducing played-defined concepts within the game.

Interesting, thanks. I am especially interested in the idea of introducing player-defined concepts.

Would you be able to recommend a Datalog implementation that allows independant n-ary relations. Ideally one I can use from Python or Javascript in a sort of sandboxed way, as I am doing with Datascript, but if you have any recommendation at all it would be helpful to me.

DataScript already supports processing n-ary relations, it's just not how the data is naturally stored when you use `d/transact!`. Even though it's all in-memory anyway (ignoring the recent addition of durable storage on the JVM) the main benefit you get when 'storing' data is the suite of persistent B-Tree EAVT indexes. DataScript also let's you store plain vectors (and most other objects) as values, which you can access from the Datalog, so it's very flexible really. And learning Clojure is good fun.

If you want to try something more exotic I would be tempted by https://logica.dev/ + some flavour of SQLite (potentially in-memory/WASM).

You'd probably be interested by this approach of chaining the DataScript rules to derive the next frame if you haven't seen it already: https://frankiesardo.github.io/minikusari/#!/minikusari.tuto...

This is such a breath of fresh air on tackling the state machine issue in games with heavy logic (city simulation, for instance). I never thought about using Prolog for this.

Bravo!

From the causality and relativity discussion, it seems like you could do some really neat stuff. Like for instance, you could generate a random encounter with an NPC, and a history of events for that NPC that includes causal chains initiated by the player in the past. Because everything is relations, and you know that the NPC is present now, and we have a history of all observed world state and actions, we can work backwards to get an entirely consistent history for the NPC without having simulated it in advance.

I'd never considered how the commonplace actor-world/entity-trait model is a neat fit for Prolog's whole relational deal. Though predictable and efficient run-time is also critical, and Prolog typically brute-forces its way through matching terms to satisfy the query. I haven't finished reading the series though - maybe they address it?

Naïve question, but doesn't amount of brute-force search depend on the particular solver used? I'm vaguely aware of finite domain something or other but curious about the affordances prolog has for using different solvers over different parts of your codebase.

At first guess, I would imagine this could look like writing down known constraints on the solution as a kind of "type declaration".

Prolog's clpfd (constrained logic programming over finite domains) is actually just a library - albeit one with very ergonomic bindings that mesh almost invisibly into the language.

Prolog's evaluator backtracks when it hits a conflict while trying to expand a predicate. It evaluates queries top-down, and tries predicate definitions/clauses in order. It's basically eager. This isn't a good fit for math, so CLPFD fixed this by making arithmetic constraints lazy. This works really well, but you're ultimately using Prolog to build a model, then (invisibly) solving the model separately.

Ultimately, the problem is that Prolog looks like a DSL but is Turing-complete. You can weave other solvers into the language, but there's a seam between the evaluators. I like the alternative, which is to sacrifice Prolog's Turing-completeness for a ridiculously powerful DSL. Answer Set Programming (clasp) and Datalog are fine examples of this.

Brute force search is just the naive way of finding solutions. Just like you can index a SQL table, you can index a Prolog predicate for better performance.

You can index, but iirc Prolog's indexing isn't powerful enough to efficiently handle SQL-like queries. Like, iirc `WHERE Id > 500` still requires trying all the Id values, you can't binary search on keys like that. And clause order matters a lot for perf. Doesn't Datalog use a different sort of evaluator that makes such queries more tractable?

There's no inherent reason you couldn't do that. That's another similarity to SQL: the underlying features of the language will depend on which runtime you're using.

SQL: Postgres, SQLite, MySql, etc. all have different features. Prolog: SWI-Prolog, GNU Prolog, Scryer Prolog, etc. same thing.

It's true that Datalog is better for pure data querying. But there's no theoretical reason it couldn't be implemented in Prolog as well.

I admit to not having that much experience in prolog, but I'm having a hard time translating the time parameter `[n]` into executable prolog. Anyone got a clue?

that is prolog pseudocode. You would probably use the lists:nth/3 predicate.

https://www.scryer.pl/lists

Markus Triska has probably the best resources on modern Prolog.

Just search for "Power of Prolog" on YouTube or the internets.

Interesting note: I believe the scripting language that larian (creators of the highly dynamic divinity titles and baldurs gate 3) is a prolog variant.

It's called Osiris and they state it "is a mostly declarative programming language, similar to Prolog" [1]

I think you get access to their engine if you buy one of their games through steam and you can mess with Osiris (not sure if that's still true for BG3, but it was the case for Divinity: Original Sin).

[1] https://docs.larian.game/Osiris_Overview

I believe you have Osiris access at least since Patch 7, when they opened things up to modders.

I'm thoroughly enjoying the philosophy side of these posts (like the how of representing various common abstractions in prolog), but I would love to see an actual game implemented in prolog! Does anyone know of any examples that are more complex than simple text adventures?

Or any anecdotes from more experienced prologgers about the experience of writing a real game? At face value it looks like it would be very easy to accidentally tie yourself up in a knot of logical contradictions, but I guess there are tools in prolog land for debugging this kind of thing?

A bit of OT, but if one would like to pick up a bit of Prolog, what's the recommended book?

And what prolog implementation should one pick?

There's very little that's modern and most modern resources teach you bad habits and non-idiomatic code.

For good habits and a good introduction: https://www.metalevel.at/prolog

I like "Prolog Programming for Artificial Intelligence" as a great print book with interesting projects that is fairly modern but be warned that much of the code is not idiomatic, so please refer to the first resource if you are looking to write too quality stuff.

https://a.co/d/5NGr6KS

Is there a embeddable Prolog implementation (à la Lua) that can be linked in to an application as a scripting language?

https://www.swi-prolog.org/pldoc/man?section=embedded - I've never used this myself so can't comment on how good it is. There are probably others, too.

http://minikanren.org/ - MiniKanren, a different language in the same vein, small and embedded into lots of host languages.

https://microsoft.github.io/z3guide/docs/logic/intro/ - Z3, again a different language but hits many of the same areas and use cases along with plenty of others. Also usable as a library (probably how most people access it, often through Python).

Thanks, MiniKanren implemented in C and Lua seems like the right way.

SWI Prolog seems to use global state, which becomes no-no without using GILs and whatnot. Z3 I've use before in college, but it wasn't really a scripting tool, unless something changed in the meantime.

I'll leave this here since it is useful: https://github.com/emacstheviking/gnuprolog-libsdl2

The centered monospace text is quite hard to read on mobile, but reader mode seems to work well. Back to reading it now...

I haven't quite finished reading this yet, but it's really quite interesting! Seeing how entity "components", interactions and relations come for free as a result of logic programming is fascinating.

That being said, it seems to get quite convoluted when trying to introduce dynamism (i.e. time) to the system. I was about to wonder if a hybrid of functional and logic programming could address this, and then I remembered Verse [0] exists ;-)

[0]: https://github.com/UnrealVerseGuru/VerseProgrammingLanguage

I'm so curious to see how Verse ends up, since last I knew it was not even 1.0 yet but have not kept up in a while. But I recall being interested in the set of design decisions SPJ

I’m not too dumb but my brain is not wired sufficiently enough to be willing to try to understand what’s happening. I can only understand it on a high level, but not I’m not going down this rabbit hole.

Is there a variant of Prolog that is less dynamic with AoT compilation?

Imagine if you can be in "dynamic mode" where you can add rules, facts, etc. in an adhoc way.

Then, once your game is better defined, you can compile the Prolog to native code so that it is highly optimized, executed in parallel, etc. The compiler could apply all sorts of optimizations we see in commercial game engines automatically.

This compiled object could then be embedded into a game engine with native performance.

Done right, this could even outperform imperative game engines, but be very easy to debug and modify.

The most similar thing to a "static" Prolog would be Mercury[0] or Turbo Prolog[1]. OTOH, if you want an embed-able logic programming library there is the mini/microKanren family[2].

[0] https://en.wikipedia.org/wiki/Mercury_(programming_language)

[1] https://en.wikipedia.org/wiki/Visual_Prolog

[2] https://en.wikipedia.org/wiki/MiniKanren

So much of the "magic" with Prolog and similar relational languages necessarily happens with dynamic data at runtime (especially in a game engine where entities move around, etc so the state of relations changes significantly) I'm not sure how much static you could get with it.

That said, there's plenty of research in the DB world on precompiled and JITted query execution plans. All of that would apply to a Prolog or Datalog engine as well.

Also, a personal interest of mine I keep wanting to come back to is how much one can make use of GPU and TPU hardware to accelerate the joins that go on in these systems. There are people working in this space already: https://arxiv.org/html/2311.02206v3 but I believe their emphasis is on large scale data sets (e.g. big data graphs) whereas I'm curious to see if there's a way that an approach using HW acceleration could make low latency "OLTP" type applications possible for applications like robotics/vehicle autonomy/games, using complex rule sets.

I watch my son play Dwarf Fortress and I'm like... it needs a Prolog.

Now, to put this on a cartridge for the Prolog-powered Sega AI:

https://news.ycombinator.com/item?id=39206529

Reply on news.ycombinator.com