12 ms·
Is it possible to write games like Pac-Man in a functional language? (2008)
- rydgel 3y agoI remember making Flappy Bird in Haskell with FRP. It was a very different but pleasant experience.
- vogon_laureate 3y agoTIL that a 6502 didn’t have division and remainder instructions. Yikes.
- 082349872349872 3y agoI learned a lot from Chuck Moore's designs; for instance he assumes that you know how to build multiply given a multiplication step instruction, or the full set of logic ops given just and and xor. (which comes on top of the traditional forth punning of logical and bitwise booleans) > Before I studied the art, a binding was just a binding. After I learned the art, an assignment was an assignment but an application was an application. Now that I've understood the art, a binding is just a binding.
- flohofwoe 3y agoNone of the 8-bit CPUs had that, but you can get pretty far with left- and right-shift (which is the same as multiplication and division by 2), which allows to compose multiplication and division by constants quite easily (it's a bit more trouble and usually too slow for a universal runtime mul/div, but one simply tried to avoid that, or use precomputed lookup-tables instead).
- zabzonk 3y agonot division, but the 6809 8-bit processor did have a MUL(tiply) instruction.
- flohofwoe 3y agoI stand corrected and TIL :) That's pretty awesome actually, pity that the 6809 wasn't more popular in the home computer era (but looking at the price compared to the Z80 or even 6502 it's understandable - $37 versus $9 for Z80 and $6 for the 6502 in 1980 according to Wikipedia: https://en.wikipedia.org/wiki/Motorola_6809 https://en.wikipedia.org/wiki/Motorola_6809).
- zabzonk 3y agoi wasn't aware of the price difference, and at the time i owned a 6809-based system - a dragon32 (a sort of UK re-branded version of the tandy colco). i wasn't fussed about the MUL instruction, but i simply loved all of the addressing modes that thing had.
- dboreham 3y agoI worked in embedded systems design through this era. I don't remember ever hearing of a design using one 8-bit cpu vs another due to chip cost. Those Wikipedia numbers also seem suspect.
- paulsutter 3y agoZero page addressing was far more inconvenient than calling a library for division on the 6502 16 bit addresses didn’t fit into registers, so you keep pointers in the zero page (bytes 0-255). There was no 16 bit increment either, so to increment the pointer you incremented the low byte and on overflow increment the high byte
- IshKebab 3y agoThere are still modern CPUs that don't. Division/remainder is much much harder than all the other basic arithmetic operations.
- PhilipRoman 3y agoIt is quite rare to need an actual division instruction; for the majority of cases you would simply precompute the modular inverse and use that with multiplication. Non-constant modulo can often be computed by checking for roll-over when incrementing (or just computed in a similar way to division)
- TillE 3y agoGame consoles like the SNES (65816) had a coprocessor for multiplication, division, etc. You load the values into a certain address, wait a couple cycles, and retrieve the result. Not pretty, but those CPUs were designed to be really cheap.
- aputsiak 3y agoIn Conrad Barski's book, Land of Lisp, you are taught to do so. Check out the website: http://landoflisp.com http://landoflisp.com
- amouat 3y agoI loved this book! It's about much simpler, generally turn based games though
- asimpletune 3y agoYeah but to be fair Pac-Man is like a turn based game where the turns are taken 120 times a second (or whatever the frame rate is)
- tromp 3y agoA Quake clone written in Haskell [1] suggests that it is quite possible. That's just one of the games listed on [2], along with game engines and libraries. [1] https://wiki.haskell.org/Frag https://wiki.haskell.org/Frag [2] https://wiki.haskell.org/Applications_and_libraries/Games https://wiki.haskell.org/Applications_and_libraries/Games
- rwmj 3y agoMy Katamari Damacy in fairly pure functional OCaml: https://github.com/fccm/OCamlODE/blob/master/examples/katamari.ml https://github.com/fccm/OCamlODE/blob/master/examples/katama...
- mappu 3y agoThat's wonderful, Katamari is great and this code looks pretty readable. Do you have any screenshots?
- barbariangrunge 3y agoHow is performance compared to the ordinary implementation? Same, better, worse?
- draw_down 3y ago[dead]
- garethrowlands 3y agoI like this. He shows some of the basic ideas of functional reactive programming and of entity component systems. And then the thing about large objects not being efficient to update, well it's not efficient in C either, or in databases or in anything really. Understanding how data transforms and the dependencies between data is usually A Good Thing.
- raincole 3y agoIt's probably not the author trying to say, but at a higher level a game is just: new_game_state = simulate_a_frame(old_game_state, user_input, time_delta) So of course it's possible. Whether it's practical is another question.
- sph 3y agoMore generally, `new_state, framebuffer = update(old_state, input, time_delta)` How far away are we from being able to represent the GPU state and rendering instructions with simple datastructures ready to be submitted wholesale to the driver?
- tubs 3y agoThat’s pretty much what a command buffer is in any of the modern gpu apis. Recording it is still command driven but trying to give an entire app scene in one go is really messy. We tried this internally on our gpu before Vulkan.
- nottorp 3y agoI know it's harder, but can we please decouple state updates from rendering?
- nine_k 3y agoGPU could compute state separate from rendering, if such updates are simple and independent enough. (In many cases, they are not.)
- taneq 3y ago100%. This relatively small amount of extra work makes it SO much easier to debug both rendering and state update code.
- matsemann 3y agoEven better would probably be to run the state update X amount of times per second, not depending on framerate at all. Otherwise you mess with physics. And then render based on delta and interpolate movements.
- arunix 3y agoThe other parts: Part 2: https://prog21.dadgum.com/24.html https://prog21.dadgum.com/24.html Part 3: https://prog21.dadgum.com/25.html https://prog21.dadgum.com/25.html Part 4: https://prog21.dadgum.com/26.html https://prog21.dadgum.com/26.html Follow up: https://prog21.dadgum.com/37.html https://prog21.dadgum.com/37.html
- sph 3y agoMost of the criticism outlined in his follow-up is because of the state of functional programming in 2008 when this was written: - "Not being able to re-use names for values in functions". It's not a feature of functional languages, and thankfully many these days don't suffer from this limitation (see Erlang vs Elixir for example) - "The lack of a simple dictionary type". Again, blame the terrible functional ecosystems of 2008.
- deleted 3y ago[deleted]
- taeric 3y agoI'm curious what you mean? How can you re=use a name in a function? I've seen this problem even in Java code.
- asimpletune 3y agoIt’s called variable shadowing and it’s super common in these days. The rust book introduces it in like the 2nd chapter.
- taeric 3y agoOk. Shadowing has been a thing for a very long time. If you are in languages that use block scoping, yes, you could just build a new block and call it a day. No, that isn't ergonomic, though.
- 3y ago
- sph 3y agoShould add (2008) to the title.
- NikkiA 3y agoPretty sure I remember a FRP pacman being written in response to those post, way back then in 2008.
- giovannibonetti 3y agoI think the most fun and behinner-approachable way to build games with functional programming is with Elm [1]. See a few (small, demo) games built by the community in [2] . Notice Elm has abandoned the FRP approach in favor of Model-View-Update [3]. [1] https://elm-lang.org/ https://elm-lang.org/ [2] https://github.com/rofrol/elm-games https://github.com/rofrol/elm-games [3] https://elm-lang.org/news/farewell-to-frp https://elm-lang.org/news/farewell-to-frp
- megapoliss 3y agoFable [1] (F# to JS compiler) has pac-man game as one of samples [2] [1] https://fable.io/ https://fable.io/ [2] https://github.com/fable-compiler/repl/blob/master/public/samples/games/pacman.fs https://github.com/fable-compiler/repl/blob/master/public/sa...
- epolanski 3y agoFunctional core + imperative shell can describe any kind of problem. The biggest problem with the approach is that mainstream functional languages put most effort in the functional core rather than the imperative shell modeling. Effect systems (ZIO for Scala, effect-ts) are the only places where fibers allow composing, scheduling and managing "processes" in a functional way.
- deleted 3y ago[deleted]
- innocentoldguy 3y agoIt is both possible and relatively easy. I wrote a game similar to Pac-Man using Elixir, only I used characters from Firefly instead. I used it in several job interviews to prove I can code.
- deleted 3y ago[deleted]
- FrustratedMonky 3y agoIt is completely possible of course. I think questions like this are really getting at, is how do you update the 'huge-game-state' without mutating it, changing variables. People have a very ingrained feeling that the game state is updated by updating variables. But in functional languages, the state is immutable, so if you are new to functional languages you ask 'man how do I update this'. Then, if this new person takes next step and is told 'you make a copy of the game state', they are like 'man that must be a big performance hit to copy the whole thing'. So I think questions like this are really about how to handle a state with immutable data. How to make a copy efficiently, like in parts, or whatever. And then of course, you are down the rabbit whole of changing your brain thinking towards functional style.
- taneq 3y agoIt'd be good to hear some discussion of whether it's advisable and what the advantages and disadvantages are. Often discussions around functional programming are incredibly dogmatic, with it already taken as gospel that functional is superior in every way and purity is next to godliness.
- epgui 3y agoFor some reason, your skepticism looks a lot like dogmatism…
- taneq 3y agoFair enough, my dogma is "understand the problem, then apply the appropriate programming paradigm, methodology and approach in the context of the overall system that you're building." And yeah, I believe pretty hard in this. So when someone tells me "you MUST use [procedural / object oriented / functional / graphical / vegetable / ironic] structures in your code, or it's BAD CODE and you are bad too" I tend to immediately think they're full of crap. This response is raised to the n'th power when they start using terms like "purity" to rate the philosophical 'goodness' of code in any way unrelated to its correctness, performance, simplicity, or ease of writing, verification, or future modification.
- CJefferson 3y agoI’ve heard Edwin Brady, who made Idris (and Whitespace…) use the term “pac-man complete” when discussing languages, particularly functional ones.
- asimpletune 3y agoPart of me questions the old view that functional programming isn’t performant. If you think about it, 1.) most performance comes down to memory access. 2.) It is widely known that accessing memory off the stack is faster than allocating memory on the heap. 3.) calling a function pushes everything onto the stack, starts a new stack pointer, and when it’s done releases everything from the stack. So my thinking is if by definition functional programming is about organizing your program as a pure composition of functions, doesn’t that also imply an ideal memory access pattern? Can someone tell me where I'm wrong? I guess the one issue where this comes into doubt is with strings of unknown length, and other data types that must be heap allocated, but even in those cases it seems that problem would equally affect all other paradigms.
- taeric 3y agoI believe a lot of this boils down to so many data structures not being kind to state updates. And most ways of making that work out fine are by adding more data and indirection. Even the ways of making things a bit more "performant" typically do so by adding more data to the mix, not less. This is even harder if you work with data structures like threaded trees, where there are so many links that even the zipper approach basically falls flat. (And the zipper already has performance questions if you do a deep edit, if I am not mistaken. What could be a single value mutation is now a rewiring of every link down to the value that you wanted to change.)
- agumonkey 3y agoThen there's memory locality, and shared memory. if you keep bitbanging the same area, your processor might be very happy. FP will create temporary structures to derive the next computation and it may cost a bit much. I say may because I have no experience in this, just semi educated guess. Our processors are well made to hammer the same insts on the same memlocs. ps: of course FP shields you from having to manage correct state update seen in imperative programming, which might require a lot, a lot, of reads and writes to ensure things are not messed up.
- mrkeen 3y ago> 3.) calling a function pushes everything onto the stack This is a very C-centric view of it. In FP, sometimes they're functions, sometimes they're closures. Sometimes they're fully applied and sometimes they're partially applied. You're probably on the heap, not the stack for two reasons: tail recursion, and variables very often outliving the return.
- egonschiele 3y agoHey, it's my time to shine! I rewrote Chips Challenge in Haskell years ago: https://github.com/egonSchiele/chips https://github.com/egonSchiele/chips It's not better than using C, but worked just fine when I wrote it in 2014. I'd say, unless you're planning to sell it, write the game in whatever language you enjoy.
- opyate 3y agoJust to pitch in with a Clojurescript/Quill example, where the game loop takes a function that takes game state, modifies it, and returns it for the next iteration of the game loop. https://github.com/opyate/minild72/blob/master/src/pong/core.cljs#L59 https://github.com/opyate/minild72/blob/master/src/pong/core...
- dahart 3y agoIf there was one single thing I learned from my functional programming class in college, it’s that there exists a way to implement imperative programming in a pure functional language. I distinctly remember the aha that Turing complete means Turing complete, and functional vs imperative is a style that can be emulated in any Turing complete language. Now for the life of me I can’t remember what the exact trick or mechanism was, does anyone know what I’m talking about? I’m pretty sure it leveraged one of the named functional constructs, similar to a thunk or y-combinator or something. I’m old enough that use of “monad” wasn’t much of a thing at the time.
- Archelaos 3y agoThere may be a lot of different ways to do this, for example writting a BASIC interpreter in LISP, or a LISP interpreter in BASIC.
- zarakshR 3y agoContinuation-passing style?
- dahart 3y agoI think it’s something like this, yes. I should try to dig up the old assignment, it was in Scheme and I probably have the code buried somewhere.
- eesmith 3y agoAs I recall, if you have constant-time random access array with mutation then you can emulate that behavior in a functional language using balanced trees, with O(log(n)) time. This means any functional programming language can implement any imperative programming language with a factor of O(log(n)) overhead.
- dahart 3y agoI guess as soon as you have array mutation, you have assignment and thus it’s already imperative? The trick I’m thinking of definitely didn’t involve any algorithmic complexity overhead, it was just more of a trick to emulate assignment and imperative statements using pure functions. It was a neat observation at the time, but with the passage of time it starts to seem a little less surprising, though I guess it still is a little since the article asks the question.
- marcelr 3y agoIn university I had a mind bending experience writing snake in purely functional javascript, I was so proud of it and showed my friends and the reaction was “oh god” I can’t say they were wrong
- foobarbecue 3y agoI enjoyed this article. Is there source code to accompany it?
- bitwize 3y agoThere's Monadius, a clone of Gradius written in Haskell: https://github.com/tanakh/monadius https://github.com/tanakh/monadius
- hgsgm 3y agoA game as tiny as pacman is trivial to make run fast enough even with the most naive functional style like rebuilding the entire game state every frame.
- simonmic 3y agoSome Haskell pacmans: - https://github.com/EgorDm/fp-pacman https://github.com/EgorDm/fp-pacman (https://www.youtube.com/watch?v=DlifcJ4cexw https://www.youtube.com/watch?v=DlifcJ4cexw) - https://github.com/Jcklly/PacMan https://github.com/Jcklly/PacMan - https://github.com/ajkavanagh/pacman https://github.com/ajkavanagh/pacman and other games: - https://wiki.haskell.org/Applications_and_libraries/Games https://wiki.haskell.org/Applications_and_libraries/Games See also the #haskell-game chat on Matrix and Libera IRC.
- agentultra 3y agoTotally possible. Here’s a link to a game recently released on Steam that is written in Haskell and whose source is open: https://github.com/incoherentsoftware/defect-process https://github.com/incoherentsoftware/defect-process I recently hacked together an asteroids clone in Haskell with SDL2 and not much else. It’s not super pretty but it works. I’ve talked to folks who’ve been using the newer effects libraries taking advantage of the new delimited continuation primops in GHC 9.6 for their game dev. Even with very high level libraries their reporting acceptable performance. With enough dedication I’m certain anyone could make whatever game they wanted in an FP language.
- whateveracct 3y agoEven without delimited continuations, ReaderT IO-based effects libraries like cleff and effectful are plenty cheap for gamedev!
- eesmith 3y agoOr, as the link says: > I've spent enough time with functional languages to have figured out how to implement non-trivial, interactive applications like video games. My plan is to cover this information in a short series of entries.
- donaldbough 3y agoAwesome write up. Great seeing a talk on functional programming with more technical details and examples.
- ziml77 3y agoI want to know if it can be done such that it performs just as well as the original on the original hardware.
- joeld42 3y agoI've tried this a lot, and I will say no, it's not realistically possible if you're being a purist. The simple counterexample, take setpixel, which takes an image buffer, and returns an image buffer with one pixel changed. Now imagine having a large bitmap and using setpixel to draw a sprite to it. For every non-transparent pixel in the sprite you need a whole copy of the whole buffer. Obvs there are lots of improvements and cleverness but compared to the speed and simplicity of an imperative code just modifying an image buffer in-place it's vastly slower, more complicated or both. However you can manage to write "most" of your game in a functional way and if you're careful about it, and use tricks like copy-on-write to make some things act functional, you can do it. Writing your game in a functional mindset, and keeping data immutable when you can has a lot of benefits.
- kelseyfrog 3y agoWe might be getting into semantics, but if you're willing to agree that IO monad maintains functionality, then there's no reason a Bitmap monad couldn't do the same for pixel writing. In principle and practice, all effects can be pushed to the outside of all applications.
- pjmlp 3y agoNot every FP language is Haskell.
- mock-possum 3y ago… would it be presumptive of me to think that there are no games which could not be written in a functional language? I mean like… what’s stopping you?
- aask_ 3y agoI mean... I wrote OOP tetris in PowerShell, so I'd say yes? github.com/aask42/particleTetris