Gamedev in Lisp. Half 1: ECS and Metalinguistic Abstraction
On this sequence of tutorials, we’ll delve into creating easy 2D video games in Frequent Lisp. The results of the primary half shall be a growth surroundings setup and a primary simulation displaying a 2D scene with numerous bodily objects. It’s assumed that the reader is acquainted with some high-level programming language, has a basic concept of how graphics are displayed on a pc display screen, and is excited about increasing their horizons.
Frequent Lisp is a programming language with a wealthy historical past of offering efficient instruments for growing advanced, interactive functions equivalent to video video games. This sequence of tutorials goals as an example a spread of CL capabilities that match seamlessly into the context of recreation growth. A brief overview of those capabilities and the distinctive options of Frequent Lisp is supplied in Yukari Hafner’s article “Using a Highly Dynamic Language for Development”.
Many options first launched in Lisp, such because the if/then/else conditional assemble, features as first-class objects, rubbish assortment, and others have lengthy since made their manner into mainstream programming languages. Nevertheless, one distinctive characteristic that we’ll take a look at at this time is metalinguistic abstraction.
Metalinguistic abstraction
To grok this idea, let’s flip to the well-known elementary textbook “Structure and Interpretation of Computer Programs”:
Nevertheless, as we confront more and more advanced issues, we’ll discover that Lisp, or certainly any fastened programming language, isn’t ample for our wants. We should consistently flip to new languages to be able to categorical our concepts extra successfully. Establishing new languages is a strong technique for controlling complexity in engineering design; we will typically improve our capacity to take care of a fancy downside by adopting a brand new language that permits us to explain (and therefore to consider) the issue otherwise, utilizing primitives, technique of mixture, and technique of abstraction which might be notably nicely suited to the issue at hand.
Metalinguistic abstraction — establishing new languages — performs an necessary position in all branches of engineering design.
To understand this level is to vary our pictures of ourselves as programmers. We come to see ourselves as designers of languages, relatively than solely customers of languages designed by others.
So, an necessary mechanism supplied by nearly any Lisp dialect, together with after all some of the highly effective of them, Frequent Lisp, is the flexibility to create your personal language constructs inside the language itself. This idea is also referred to as DSL (Area Particular Languages), however solely Lisp dialects have it extremely tightly built-in into their core. In most of them, the mechanism of metalinguistic abstraction is constructed round so-called macros, particular features outlined by the programmer, that are known as at compile time and return small fragments of program code for the compiler to substitute wherever they happen. The distinctive characteristic of Lisps is that the code is actually an everyday nested checklist, which makes it straightforward and environment friendly to generate and course of program code fragments.
There are quite a few of various methods to creatively use and abuse this characteristic. I’d wish to introduce the cl-fast-ecs macro library I’ve created, which supplies a mini-language for describing recreation objects and their processing guidelines utilizing the Entity-Part-System sample typically utilized in recreation growth.
Entity Part System
ECS is a relatively simple sample for organizing information storage and processing in recreation functions that achieves two necessary conceptual targets without delay:
- Flexibility in defining and modifying the construction of recreation objects.
- Efficiency beneficial properties by means of environment friendly utilization of CPU caches.
Flexibility, interactivity, and the flexibility to redefine program habits on the fly are cornerstones of most Lisp-like languages. We’ll revisit this challenge later, however for now let’s focus a bit extra on the second purpose, which is commonly offered as the principle benefit of the ECS sample. Let’s begin from the start.
Within the Von Neumann structure at present utilized in most computing gadgets, there’s a elementary downside known as the “Von Neumann bottleneck”. Its essence is that regardless of how briskly the CPU processes information, its processing pace is proscribed by reminiscence efficiency. Furthermore, the efficiency of the “CPU-memory” system is proscribed by the bandwidth of the bus by means of which these nodes change data, and this worth can’t develop indefinitely or at the very least on the identical charge because the CPU efficiency grows. The issue is vividly illustrated by the next graph:
(supply: Aras Pranckevičius. “Entity Component Systems & Data Oriented Design”)
The curve labeled “Processor” represents the variety of reminiscence requests the CPU could make per unit of time; the curve labeled “Reminiscence” represents the variety of requests RAM can course of per unit of time (each values are normalized to the common values in 1980). Even superficially analyzing the graph, one can come to a disappointing conclusion — more often than not the CPU is idle ready for information from reminiscence, and over time the hole between CPU and reminiscence efficiency is getting bigger and bigger.
Already within the early Nineties, with the discharge of the Intel 486, a standard answer to this downside in shopper grade {hardware} was the cache positioned on the identical chip because the processor. The cache is a small however extraordinarily quick reminiscence that shops the info requested by the processor earlier, thus lowering the length of subsequent requests for a similar information by retrieving them from the cache as a substitute of the slower fundamental reminiscence. Towards the top of the nineties, the cache began to be divided into a number of ranges (L1, L2, and so forth.), every subsequent stage having a bigger capability, but in addition the next latency, though nonetheless considerably decrease than the latency of entry to the principle RAM. Typical reminiscence interplay timings of desktop {hardware} as of 2020 are as follows:
- processor register: <1 ns
- L1 cache: 1 ns
- L2 cache: 3 ns
- L3 cache: 13 ns
- RAM: 100 ns
(supply: dzone.com)
CPU cache helps lots in optimizing sequential entry to reminiscence cells. Even when the processor requests for a single byte from RAM, a whole cache line is returned to it and saved within the cache. On trendy x86 architectures, a cache line is 64 bytes (512 bits) lengthy.
So, if we sequentially course of parts of an array, for instance, single precision floating level numbers (32 bit floats), the primary entry to a component not solely retrieves the requested component but in addition (512 − 32) ∕ 32 = 15 subsequent parts. For the following 15 iterations of the loop, accessing the component will take 1 ns as a substitute of 100 ns. Thus, because of the cache, our loop operates roughly 16 × 100 ∕ (100 + 15 × 1) ≈ 14 occasions sooner whatever the array’s size! This instance illustrates how necessary it’s from the efficiency standpoint to course of information in such a manner that it stays “sizzling” in cache.
To know how the ECS architectural sample contributes to cache utilization, let’s look at its key elements:
- entity – a composite recreation object;
- part – information describing some logical aspect of an object;
- system – code that processes objects of a particular construction.
Let’s first take care of entities and parts with a concrete instance:
(supply: Mick West. “Cowboy Programming. Evolve Your Hierarchy”)
Horizontally, the parts Place, Motion, Render and so forth are represented by coloured rectangles. Notice that every of those parts could include a number of information fields, for instance, Place and Motion will nearly actually include x and y fields.
Vertically, the entities are labeled in parentheses — Alien, Participant, and so forth. Every entity has a particular set of parts. Extra importantly, we will add or take away some parts to any entity “on the fly”, in runtime, to vary its construction and, consequently, its habits and standing within the recreation world, all with out recompiling the sport code! This achieves the primary conceptual purpose of ECS talked about earlier — flexibility of the construction of recreation objects.
The illustration above, if you happen to squint a little bit, appears lots like an odd Excel spreadsheet. In essence, that’s what ECS is 😊
(supply: Maxim Zaks – Entity Component System – A Different Approach to Game / Application Development)
From a conceptual perspective, entities and parts kind the rows and columns of a desk whose cells maintain the part information or no values. This illustration of recreation information permits us to tug off a variety of tips associated to its reminiscence format. In flip, these tips allow probably the most environment friendly utilization of the CPU cache when processing information, just like the instance talked about earlier with a loop over floats, and thus squeeze most efficiency out of the “CPU-memory” system.
The processing of recreation information when utilizing the ECS sample is delegated to the so-called methods — loops that iterate over all entities which have sure parts and carry out operations on these entities in the identical uniform manner. For instance, a system that calculates the motion of objects will course of entities with Place and Motion parts, a system that attracts objects on the display screen shall be excited about entities with Place and Render parts, and so forth. This may be illustrated by the next instance:
(source)
On this instance, the MoveSystem is actually a loop that sequentially traverses all entities with Rework and Motion parts and calculates new place values for every entity in accordance with its velocity. Most implementations of the ECS sample are structured in order that the part discipline information (e.g., the x and y fields of the Motion part) are saved in flat one-dimensional arrays, and the entities are mainly integer indices in these arrays. Programs, in flip, merely iterate over arrays with part information, thus reaching spatial cache locality, similar to within the float loop instance talked about earlier.
This concludes the temporary overview of the Entity-Part-System architectural sample. For a deeper dive into the subject, the next assets are really useful:
Now we’re prepared to make use of the cl-fast-ecs library to create a minimal recreation undertaking with ECS structure. However earlier than that, we want a configured Frequent Lisp growth surroundings.
Improvement surroundings
The very first thing we have to construct a growth surroundings is a compiler, and the universally acknowledged chief amongst open-source Frequent Lisp compilers is Steel Bank Common Lisp, aka SBCL. You’ll be able to set up it utilizing your package deal supervisor with a command within the terminal like:
# for Ubuntu/Debian and their derivatives:
sudo apt-get set up sbcl
# for Fedora:
sudo dnf set up sbcl
# for MacOS with Homebrew:
brew set up sbcl
…or obtain a ready-made installer from the official website (you’ll want to select the CPU structure you want; generally, it’s AMD64).
After putting in the compiler, you will have to put in Quicklisp, which is the de facto normal package deal supervisor for Frequent Lisp. To do that, obtain the set up file at https://beta.quicklisp.org/quicklisp.lisp , after which load it by operating SBCL within the listing containing the file with the next command:
sbcl --load quicklisp.lisp
After loading this file, SBCL will enter the so-called REPL (Learn-Eval-Print Loop) mode, by which it would show an enter immediate consisting of a single asterisk and wait so that you can enter the code to be executed, and after executing it and displaying the outcome, it would return to ready for enter. Let’s give SBCL three code fragments to execute: to put in Quicklisp, to attach an extra LuckyLambda repository with the most recent variations of gamedev packages, and so as to add Quicklisp help to the SBCL config:
(quicklisp-quickstart:set up)
(ql-dist:install-dist "http://dist.luckylambda.technology/releases/lucky-lambda.txt" :immediate nil)
(ql:add-to-init-file)
After operating the final command and urgent Enter as prompted, you may exit SBCL by urgent Ctrl-D or typing (exit) on the REPL immediate.
To jot down Frequent Lisp code with consolation and nonetheless have the flexibility to work together with REPL, you may select your favourite IDE:
- VScode with the Alive extension put in; see the Common Lisp cookbook guide to utilizing it. To make it work accurately with the SBCL we’ve put in, it’s essential to put in a number of further packages by executing the next code line within the SBCL REPL:
(ql:quickload '(:bordeaux-threads :cl-json :flexi-streams :usocket))) - IntelliJ IDEA with the SLT plugin put in; see the user guide for it.
- Sublime Text with the Slyblime plugin put in (sadly, the plugin doesn’t work on Home windows in the meanwhile).
- For Vim and Neovim, there may be Vlime plugin.
- Nevertheless, the unmatched chief as an IDE for Lisp-like languages is Emacs. For those who’re already an skilled Emacs consumer, you may merely set up the Sly plugin. For those who don’t wish to hassle with configuring this surroundings, you need to use the ready-made cross-platform Emacs construct personalized for Frequent Lisp known as Portacle, and skim the Emacs introduction from the Common Lisp cookbook. To ensure that our undertaking to work in Portacle, you’ll must run the next code in its REPL:
(ql-dist:install-dist "http://dist.luckylambda.technology/releases/lucky-lambda.txt" :immediate nil) (ql:quickload :deploy)
In addition to, for such an unique OS as Home windows, you’ll want a instrument like MSYS2 for correct growth.
Frequent Lisp recreation undertaking template
To begin our undertaking, let’s use the cookiecutter-lisp-game template. For this you’ll want the cookiecutter Python instrument put in. Yow will discover set up directions here. Let’s run the next command within the terminal:
cookiecutter gh:lockie/cookiecutter-lisp-game
cookiecutter will immediate you with questions concerning the undertaking you’re creating. Reply them within the following method:
full_name (Your Identify): Alyssa P. Hacker
electronic mail (your@e.mail): alyssa@area.tld
project_name (The Recreation): ECS Tutorial 1
project_slug (ecs-tutorial-1):
project_short_description (A easy recreation.): cl-fast-ecs framework tutorial.
model (0.0.1):
Choose backend
1 - liballegro
2 - raylib
3 - SDL2
Select from [1/2/3] (1): 1
cookiecutter will create a undertaking skeleton within the ecs-tutorial-1 listing. You’ll want so as to add this listing to your native Quicklisp package deal repository with the next command:
# for UNIX-like OS:
ln -s $(pwd)/ecs-tutorial-1 $HOME/quicklisp/local-projects/
# for Home windows:
mklink /j %USERPROFILEpercentquicklisplocal-projectsecs-tutorial-1 ecs-tutorial-1
# for Home windows when utilizing Portacle:
mklink /j %USERPROFILEpercentportacleprojectsecs-tutorial-1 ecs-tutorial-1
As a backend, we selected the default possibility #1, liballegro, as a result of it’s at present probably the most hassle-free graphics framework to be used in Frequent Lisp. You’ll additionally want to put in it, both with the terminal command like
# for Ubuntu/Debian and their derivatives:
sudo apt-get set up liballegro-acodec5-dev
liballegro-audio5-dev liballegro-dialog5-dev
liballegro-image5-dev liballegro-physfs5-dev
liballegro-ttf5-dev liballegro-video5-dev
# for Fedora:
sudo dnf set up allegro5-addon-acodec-devel
allegro5-addon-audio-devel allegro5-addon-dialog-devel
allegro5-addon-image-devel allegro5-addon-physfs-devel
allegro5-addon-ttf-devel allegro5-addon-video-devel
# for MacOS with Homebrew:
brew set up allegro
# for Home windows with MSYS2:
pacman -S mingw-w64-x86_64-allegro
…or by downloading ready-made binaries from the official website. Moreover, due to the programming language liballegro is written in, which is pure C, you’ll want a working surroundings to compile the C code:
# for Ubuntu/Debian and their derivatives:
sudo apt-get set up gcc pkg-config make
# for Fedora:
sudo dnf set up gcc pkg-config make redhat-rpm-config
# for MacOS with Homebrew:
brew set up pkg-config
# for Home windows with MSYS2:
pacman -S mingw-w64-x86_64-gcc
mingw-w64-x86_64-pkg-config make
For Home windows with MSYS2, you’ll additionally must set the MSYS2_PATH_TYPE surroundings variable to the worth inherit and add the next paths to the start of the PATH surroundings variable: C:msys64usrbin;C:msys64mingw64bin;
Moreover, you’ll want the libffi library for Frequent Lisp to work together with C code. You’ll be able to set up it with a command like this:
# for Ubuntu/Debian and their derivatives:
sudo apt-get set up libffi-dev
# for Fedora:
sudo dnf set up libffi-devel
# for MacOS with Homebrew:
brew set up libffi
# for Home windows with MSYS2:
pacman -S mingw-w64-x86_64-libffi
Lastly, in spite of everything these preparations, you may run the undertaking by:
- Navigating to the
srcsubdirectory of the undertaking (that is necessary in order that the sport code can discover all of the useful resource information it wants, equivalent to fonts, pictures, and so forth.). - Launching
sbclinside this listing. - Loading the undertaking package deal with a code like
(ql:quickload :ecs-tutorial-1) - After ready for the enter immediate within the type of an asterisk after loading, name the undertaking entry level, the
fundamentalperform, by executing the next code:(ecs-tutorial-1:fundamental)
If every thing goes easily, you’ll see an empty window with an FPS counter:
To run the undertaking from an IDE, chances are you’ll must manually set the working listing by operating the code like (uiop:chdir "/path/to/src") in IDE REPL. On Home windows, be certain that to make use of ahead slashes, /, as a substitute of backslashes within the src listing path.
Now we will proceed so as to add the “meat” of parts and methods to the skeleton.
Including parts and methods
In the beginning, if you happen to’ve by no means handled Frequent Lisp or different Lisp-family languages, I like to recommend referring to a quick information, Learn X in Y minutes, Where X=Common Lisp (learning its first six sections must be ample). For a deeper dive, Practical Common Lisp is a superb useful resource.
The very first thing we have to do is to attach the cl-fast-ecs library to our undertaking. To do that, open the ecs-tutorial-1.asd file within the root listing of the undertaking. The .asd extension isn’t the results of a random chord on the keyboard; it stands for “One other System Definition”, and it’s the de facto normal for describing Frequent Lisp packages. On this file, it’s worthwhile to add a component #:cl-fast-ecs to the checklist that’s the worth of the key phrase parameter :depends-on, in order that it appears like this:
;; ...
:license "MIT"
:depends-on (#:alexandria
#:cl-fast-ecs
#:cl-liballegro
#:cl-liballegro-nuklear
#:livesupport)
:serial t
;; ...
After that, it is best to (re)load the package deal with the longer term recreation in REPL utilizing the acquainted command (ql:quickload :ecs-tutorial-1). Now we’re able to dive into the supply code.
So, let’s open the src/fundamental.lisp file. Don’t be frightened by the code inside the shape beginning with the symbols cffi:defcallback %fundamental. This can be a normal boilerplate, just like what will be present in any program utilizing liballegro. As an illustration, you will discover the same boilerplate within the code of the “skater” demo from the official library web site. This boilerplate offers with initialization and finalization of liballegro and its addons essential for the sport to perform, error dealing with and rendering of the FPS counter you’ve already seen. Nevertheless, its central half is the principle recreation loop, which sequentially attracts the sport frames on the display screen. You’ll be able to learn extra about what the principle recreation loop is here. We received’t intervene with the %fundamental callback code. As an alternative, we’ll lengthen the init and replace features which it calls to initialize the sport logic and replace the sport’s inside state on every body respectively.
Let’s begin enhancing the code by initializing the cl-fast-ecs framework. If we attempt to use its features with out initialization, for instance, run the code for creating a brand new entity (ecs:make-entity) in REPL proper now (attempt it!), we’ll get an error like The variable CL-FAST-ECS:*STORAGE* is unbound. It occurs not as a result of the writer forgot to outline the variable *storage* within the framework code, however as a result of it’s not sure to any worth but. To bind it to a newly created ECS information storage object, it’s worthwhile to name the bind-storage perform. Essentially the most logical place to do that within the recreation code is the init perform:
(defun init ()
(ecs:bind-storage)))
Having written this code, we should flip it into part of our program. Right here a necessary facet of Lisp we mentioned earlier, which is uncommon in different mainstream languages, comes into play: interactivity. It’s not essential to shut the at present operating SBCL course of. Simply put the cursor on the perform code and use the keyboard mixture of your IDE that sends the code to the operating REPL. For instance, in Emacs it’s double-press of Ctrl-C (or C-c C-c in its lingo). In different IDEs the corresponding context menu merchandise shall be known as “Inline eval”, “Consider This S-expression”, “Consider kind at cursor” or comparable. Moreover, when utilizing the livesupport library (which is included in our template), you may redefine code fragments or total features not solely when Lisp awaits your enter, however at any second of program execution. This characteristic opens up really limitless prospects for code modification and debugging “on the fly”. There’s a well-known example of how Lisp interactivity was used to convey to life a spacecraft 150 million miles away from the Earth.
Now we’re able to outline the parts that our recreation simulation will use. We’ll be modeling the Newtonian physics of numerous celestial our bodies. To do that, we will definitely want parts for the place and pace of objects structured in the same manner. Let’s add the next code that makes use of the define-component macro from the cl-fast-ecs framework simply earlier than the init perform on the prime stage:
(ecs:define-component place
"Determines the placement of the article, in pixels."
(x 0.0 :kind single-float :documentation "X coordinate")
(y 0.0 :kind single-float :documentation "Y coordinate"))
(ecs:define-component pace
"Determines the pace of the article, in pixels/second."
(x 0.0 :kind single-float :documentation "X coordinate")
(y 0.0 :kind single-float :documentation "Y coordinate"))
Every name to this macro takes as enter the identify of a part, an non-obligatory documentation string, and a set of part fields, or slots as structure fields are generally known as in CL. For every slot, similar to for construction slots, we specify in parentheses:
- identify,
- default worth,
- key phrase parameter
:kinddefining the kind of the sphere, - non-obligatory key phrase parameter
:documentationincluding a documentation string to the slot.
The define-component name comprises a minimal of redundant data and may be very simple. Nevertheless, truly the macro generates fairly a considerable quantity of code to help part operations. You’ll be able to take a look at it by passing the quoted macro name to the usual macroexpand perform in REPL:
(macroexpand
'(ecs:define-component place
"Determines the placement of the article, in pixels."
(x 0.0 :kind single-float :documentation "X coordinate")
(y 0.0 :kind single-float :documentation "Y coordinate")))))
I warn you straight away, the outcome can look overwhelming 😅 It may appear that the compiler is SCREAMING AT YOU as a result of the generated code is in uppercase, however in reality automated symbol-to-uppercase conversion is a historic characteristic that may be disabled by tweaking the readtable-case setting. Sometimes nobody bothers with that. You can too take a look on the generated code here.
The code generated by the macro consists of not solely an outline of the construction that shops place part information for all entities and is routinely added to the frequent object information storage, but in addition a set of auxiliary features and macros (sure, sure, macros can outline different macros 🤯). These permit:
- to get and set the
xandyslot values, - so as to add and take away a
placepart from a given entity, - to repeat
placepart information from one entity to a different, - to test if the
placepart exists for a given entity, - to simply entry slots by identify.
As a part of this tutorial sequence, we’ll ultimately attempt all of them.
Let’s add yet one more part earlier than init, which is able to permit us to attract pictures equivalent to our celestial our bodies on the display screen:
(ecs:define-component picture
"Shops ALLEGRO_BITMAP construction pointer, dimension and scaling data."
(bitmap (cffi:null-pointer) :kind cffi:foreign-pointer)
(width 0.0 :kind single-float)
(top 0.0 :kind single-float)
(scale 1.0 :kind single-float)))
Along with the C pointer to the ALLEGRO_BITMAP picture construction from liballegro, this part additionally shops the picture dimension and scaling data.
Now let’s implement our first system that can show objects on the display screen. Add the next code after the part definitions:
(ecs:define-system draw-images
(:components-ro (place picture)
:initially (al:hold-bitmap-drawing t)
:lastly (al:hold-bitmap-drawing nil)))
(let ((scaled-width (* image-scale image-width))
(scaled-height (* image-scale image-height))))
(al:draw-scaled-bitmap image-bitmap 0 0
image-width image-height
(- position-x (* 0.5 scaled-width))
(- position-y (* 0.5 scaled-height))
scaled-width scaled-height 0))))))
Defining a system is barely extra advanced than defining a part, because it includes the precise entity processing code. The arguments of the define-system macro are: the identify of the system, a set of named choices in parentheses, after which the types that make up the physique of the system — the code executed for every entity by which the system is . This curiosity is specified with the :components-ro possibility, the place “ro” stands for “read-only”: we’ll course of all entities which have place and picture parts, however we received’t modify them. Within the physique of the system, for every such entity, we calculate the scaled dimensions of the picture and put them into the scaled-width and scaled-height variables utilizing the particular kind let. We then name the al_draw_scaled_bitmap perform from liballegro to render the picture in accordance with the desired place and scale. Notice that to entry the slots of the parts of the processed entity, we use variables within the kind component-slot, like image-width or position-y. These variables are routinely generated for us to make use of by the define-system macro. Moreover, we use the :initially and :lastly system choices, just like the corresponding key phrases in the usual LISP loop assemble: expressions from these choices shall be executed on the very starting and on the very finish of the system, respectively. We name the al_hold_bitmap_drawing perform at these moments to activate liballegro’s built-in sprite batching, which ensures that each one the calls to the graphics APIs essential for drawing will happen solely after we’ve processed all of the objects, saving costly bus communications between CPU and GPU.
To see the outcomes of our work on the display screen, we want two issues:
- create some variety of objects with random positions,
- and name our system each body.
Let’s begin with the primary level.
First, we want pictures for our celestial our bodies. Obtain them from this page of the OpenGameArt web site (click on the “File(s)” hyperlink):
Let’s unpack the small listing from the downloaded archive into our Assets listing, in order that the PNG information can be found to our utility by paths like Assets/a10000.png. With a view to preserve issues easy, let’s simply hardcode the mandatory pictures as a relentless checklist earlier than the init perform:
(define-constant asteroid-images
'("../Assets/a10000.png" "../Assets/a10001.png"
"../Assets/a10002.png" "../Assets/a10003.png"
"../Assets/a10004.png" "../Assets/a10005.png"
"../Assets/a10006.png" "../Assets/a10007.png"
"../Assets/a10008.png" "../Assets/a10009.png"
"../Assets/a10010.png" "../Assets/a10011.png"
"../Assets/a10012.png" "../Assets/a10013.png"
"../Assets/a10014.png" "../Assets/a10015.png"
"../Assets/b10000.png" "../Assets/b10001.png"
"../Assets/b10002.png" "../Assets/b10003.png"
"../Assets/b10004.png" "../Assets/b10005.png"
"../Assets/b10006.png" "../Assets/b10007.png"
"../Assets/b10008.png" "../Assets/b10009.png"
"../Assets/b10010.png" "../Assets/b10011.png"
"../Assets/b10012.png" "../Assets/b10013.png"
"../Assets/b10014.png" "../Assets/b10015.png")
:take a look at #'equalp)
Notice for MacOS customers: there’s at present unresolved bug in liballegro, which causes it to incorrectly show PNG pictures with 16-bit coloration on MacOS. Thus beneath this OS you’ll must convert them to 8-bit format utilizing the command like
mogrify -depth 8 *.png
after putting in imagemagick from Homebrew. Due to Marcus for the bug report!
Then, add the next code to the init perform after the bind-storage name:
(let ((asteroid-bitmaps
(map 'checklist
#'(lambda (filename)
(al:ensure-loaded
#'al:load-bitmap filename))
asteroid-images)))
(dotimes (_ 1000)
(ecs:make-object `((:place
:x ,(float (random +window-width+))
:y ,(float (random +window-height+)))
(:picture
:bitmap ,(alexandria:random-elt
asteroid-bitmaps)
:width 64.0 :top 64.0)))))
On this code, we load all hardcoded pictures into the asteroid-bitmaps checklist utilizing the al_load_bitmap perform and the helper Lisp perform al:ensure-loaded. After that, we use the ECS framework perform make-object in a loop with a thousand iterations. This perform constructs an entity with parts outlined by the supplied specification — a listing of the shape
'((:component1 :slot1 "value1" :slot2 "value2")
(:component2 :slot "worth")
;; ...
)
Moreover, we use a particular characteristic of Frequent Lisp that blurs the skinny line between information and code, and is commonly encountered when writing macros, the so-called quasiquoting. It permits us to assemble lists of arbitrary nesting stage by inserting the outcomes of some code execution into the required locations within the checklist. In our case, this includes calls to the usual perform random, which returns a random quantity in a given vary, and float, which converts its argument to a floating-point quantity (since liballegro makes use of float as coordinate kind). Additionally, to randomly choose a picture, we use the random-elt perform from the alexandria library, which incorporates quite a lot of helpful features (mainly, this library is to Frequent Lisp what GLib is to C or enhance is to C++).
Now, the second level: calling the system. That is taken care of for us by the run-systems perform within the ECS framework, because it runs all methods registered through define-system. It’s attention-grabbing to notice that, though our template code separates the replace and render steps in the principle recreation loop, with ECS we don’t must explicitly outline separate features for world updates and on-screen rendering. With ECS, the sport code is concentrated inside methods, and we’ve the pliability to arbitrarily outline the execution order of methods relative to one another. So, we merely add a name to run-systems to the replace perform in our template, after the FPS calculation code:
(defun replace (dt)
(until (zerop dt)
(setf *fps* (spherical 1 dt)))
(ecs:run-systems))
Let’s go away the render perform as it’s, regardless of the TODO remark inviting to place the drawing code there. In our setup, this perform is barely chargeable for the FPS counter.
After sending the brand new code — the asteroid-images fixed, new our bodies of init and replace features, place, pace and picture part definitions, and the draw-images system — to a operating Lisp course of utilizing the C-c C-c keys (or the equal on your IDE) and operating (ecs-tutorial-1:fundamental), it is best to have the ability to observe the next outcome:
Physics
Now let’s add a little bit of Newtonian physics. We’ve got the pace part, so it is sensible to make use of it to calculate the present place of the article. Let’s create a separate system known as transfer for this function:
(ecs:define-system transfer
(:components-ro (pace)
:components-rw (place)
:arguments ((:dt single-float)))
(incf position-x (* dt speed-x))
(incf position-y (* dt speed-y)))
This time, we’ll modify the place part of the entities of curiosity, so we specify it within the checklist equivalent to the components-rw possibility. Moreover, our system will want the precise time elapsed for the reason that earlier body as an argument, to make sure the bodily correctness of what’s occurring on the display screen. For simplicity, this argument may even be a single-precision floating-point quantity, single-float. We name it dt and specify it together with its kind within the arguments system possibility. Lastly, the system code merely increments the place values utilizing the usual incf macro, just like the += operator from C-like languages, by the worth of dt multiplied by the corresponding pace part.
To ensure that this method to do its job, we additionally want so as to add the pace part to our objects. To do that, modify the snippet for creating the objects within the init perform as follows:
(let ((asteroid-bitmaps
(map 'checklist
#'(lambda (filename)
(al:ensure-loaded
#'al:load-bitmap filename))
asteroid-images)))
(dotimes (_ 1000)
(ecs:make-object `((:place
:x ,(float (random +window-width+))
:y ,(float (random +window-height+)))
(:pace :x ,(- (random 100.0) 50.0)
:y ,(- (random 100.0) 50.0))
(:picture
:bitmap ,(alexandria:random-elt
asteroid-bitmaps)
:width 64.0 :top 64.0)))))
Nevertheless, operating the ecs-tutorial-1:fundamental perform once more after sending the transfer system and the brand new init perform code to the Lisp course of by way of your IDE yields the next error proper within the move-system perform:
The worth
NIL
isn't of kind
NUMBER
[Condition of type TYPE-ERROR]
Let’s terminate the fundamental perform by choosing the default ABORT restart from the Restarts checklist and check out to determine what went flawed.
Upon nearer examination of the brand new code, chances are you’ll discover that we forgot to move the dt parameter to the brand new transfer system. It’s already computed for us within the template code and handed to the replace perform. All we’ve to do is convert it from double precision double-float to single precision and move it to the ecs:run-system perform known as in replace. run-systems accepts any variety of key phrase parameters and passes them to the methods by identify as wanted:
(defun replace (dt)
(until (zerop dt)
(setf *fps* (spherical 1 dt)))
(ecs:run-systems :dt (float dt 0.0)))
Working fundamental after sending a brand new definition of the replace perform to the Lisp course of, it is best to observe asteroids slowly drifting aside:
Notice that the demo nonetheless maintains affordable FPS values. Furthermore, out of curiosity, we will check out the machine code generated by the compiler for our final system, transfer, utilizing the usual CL disassemble perform:
(disassemble (relaxation (assoc :transfer ecs::*system-registry*)))
Because of this, we will see (for the discharge construct generated for us by the package deal.sh script from the template) one thing like this:
; disassembly for ECS-TUTORIAL-1::MOVE-SYSTEMG5
; Measurement: 210 bytes. Origin: #x538B2811 ; ECS-TUTORIAL-1::MOVE-SYSTEMG5
; 11: 488B0508FFFFFF MOV RAX, [RIP-248] ; 'CL-FAST-ECS:*STORAGE*
; 18: 8B48F5 MOV ECX, [RAX-11]
; 1B: 4A8B0C29 MOV RCX, [RCX+R13]
; 1F: 4883F9FF CMP RCX, -1
; 23: 480F444801 CMOVEQ RCX, [RAX+1]
; 28: 488B4125 MOV RAX, [RCX+37]
; 2C: 488B4801 MOV RCX, [RAX+1]
; 30: 488B712D MOV RSI, [RCX+45]
; 34: 488B5935 MOV RBX, [RCX+53]
; 38: 488B4009 MOV RAX, [RAX+9]
; 3C: 4C8B582D MOV R11, [RAX+45]
; 40: 4C8B7035 MOV R14, [RAX+53]
; 44: 498B42F9 MOV RAX, [R10-7]
; 48: 4C8B52F9 MOV R10, [RDX-7]
; 4C: 488BD0 MOV RDX, RAX
; 4F: EB35 JMP L2
; 51: 660F1F840000000000 NOP
; 5A: 660F1F440000 NOP
; 60: L0: 4D8B41F9 MOV R8, [R9-7]
; 64: 488BCA MOV RCX, RDX
; 67: 48D1F9 SAR RCX, 1
; 6A: 488BC1 MOV RAX, RCX
; 6D: 48C1E806 SHR RAX, 6
; 71: 498B44C001 MOV RAX, [R8+RAX*8+1]
; 76: 480FA3C8 BT RAX, RCX
; 7A: 7217 JB L3
; 7C: L1: 488BCA MOV RCX, RDX
; 7F: 4883C102 ADD RCX, 2
; 83: 488BD1 MOV RDX, RCX
; 86: L2: 4C39D2 CMP RDX, R10
; 89: 7ED5 JLE L0
; 8B: BA17010050 MOV EDX, #x50000117 ; NIL
; 90: C9 LEAVE
; 91: F8 CLC
; 92: C3 RET
; 93: L3: 488BC2 MOV RAX, RDX
; 96: F3410F10544301 MOVSS XMM2, [R11+RAX*2+1]
; 9D: 66480F6ECF MOVQ XMM1, RDI
; A2: 0FC6C9FD SHUFPS XMM1, XMM1, #4r3331
; A6: F30F59D1 MULSS XMM2, XMM1
; AA: F30F104C4601 MOVSS XMM1, [RSI+RAX*2+1]
; B0: F30F58CA ADDSS XMM1, XMM2
; B4: F30F114C4601 MOVSS [RSI+RAX*2+1], XMM1
; BA: 488BC2 MOV RAX, RDX
; BD: F3410F104C4601 MOVSS XMM1, [R14+RAX*2+1]
; C4: 66480F6EDF MOVQ XMM3, RDI
; C9: 0FC6DBFD SHUFPS XMM3, XMM3, #4r3331
; CD: F30F59D9 MULSS XMM3, XMM1
; D1: F30F10544301 MOVSS XMM2, [RBX+RAX*2+1]
; D7: F30F58DA ADDSS XMM3, XMM2
; DB: F30F115C4301 MOVSS [RBX+RAX*2+1], XMM3
; E1: EB99 JMP L1
And that is certainly a formidable outcome: the machine code that calculates the positions of an arbitrary variety of objects in accordance with bodily issues doesn’t name any exterior features and occupies solely 210 bytes! Furthermore, when you’ve got a primary talent of studying assembler, you may see the physique of the loop that processes our objects. It begins with the label L3 and consists of solely 17 (!) machine directions, which additionally float of CPU cache guaranteeing excessive efficiency.
Nevertheless, we digress. To make the simulation extra enjoyable than simply asteroids flying round, let’s add a large planetary physique to it, turning the demo right into a simulation of house particles orbiting a planet.
Let’s use the next content material from OpenGameArt: Space Background. In addition to a pleasant planet, the archive additionally comprises some charming house backgrounds. Unpack the layers listing from the downloaded archive into our Assets listing, in order that the PNG information can be found to our utility by the paths like Assets/parallax-space-big-planet.png.
With a view to see the planet on the display screen, we have to create a corresponding entity within the init perform. To begin with, earlier than definitions of all our ECS methods, let’s create world variables with the traits of the planet, we’ll want them later:
(declaim
(kind single-float
*planet-x* *planet-y* *planet-width* *planet-height* *planet-mass*))
(defvar *planet-x*)
(defvar *planet-y*)
(defvar *planet-width*)
(defvar *planet-height*)
(defvar *planet-mass* 500000.0)
Notice that in Frequent Lisp it’s customary so as to add “earmuffs” — asterisks at first and on the finish — to the names of worldwide variables, to emphasise that they’re special in a way that they use dynamic scoping guidelines as a substitute of lexical. Moreover, earlier than defining variables utilizing the usual defvar macro, we declare their kind, single-float, which is a floating-point quantity with single precision, utilizing the declaim macro with the kind parameter. That is non-obligatory, since Frequent Lisp has gradual typing, however it’ll positively have an effect on the efficiency of the code that makes use of these variables.
Now let’s create the planet entity with the next new code snippet within the init perform after the ecs:bind-storage name:
(let ((planet-bitmap
(al:ensure-loaded
#'al:load-bitmap
"../Assets/parallax-space-big-planet.png")))
(setf *planet-width*
(float (al:get-bitmap-width planet-bitmap))
*planet-height*
(float (al:get-bitmap-height planet-bitmap))
*planet-x* (/ +window-width+ 2.0)
*planet-y* (/ +window-height+ 2.0))
(ecs:make-object `((:place :x ,*planet-x*
:y ,*planet-y*)
(:picture :bitmap ,planet-bitmap
:width ,*planet-width*
:top ,*planet-height*))))
Right here we load a picture with the planet utilizing the already acquainted al_load_bitmap and al:ensure-loaded features. Then, utilizing simple arithmetic and the al_get_bitmap_width and al_get_bitmap_height features, we create an entity with the picture precisely in the midst of the display screen, storing its coordinates and dimensions within the corresponding world variables utilizing the setf macro.
After sending the brand new code to the Lisp course of — world variable definitions through defvar and the modified init perform — and restarting the fundamental perform, you will note the planet:
Extra physics
Now let’s add extra realism — let objects crash once they collide with the planet. For simplicity, we’ll think about the planet as an ellipse. Let’s implement one other system for collision detection, naming it crash-asteroids:
(ecs:define-system crash-asteroids
(:components-ro (place)
:with ((planet-half-width planet-half-height)
:of-type (single-float single-float)
:= (values (/ *planet-width* 2.0)
(/ *planet-height* 2.0))))
(when (<= (+
(expt
(/ (- position-x *planet-x*) planet-half-width)
2)
(expt
(/ (- position-y *planet-y*) planet-half-height)
2))
1.0)
(ecs:delete-entity entity)))
In its definition, we use the :with system possibility, which permits us to outline native variables as soon as at first of the system execution. These variables shall be accessible inside the system’s physique. We use this characteristic to calculate the semiaxes of the planet to plug them into the ellipse equation
to find out whether or not an object collides with the planet. If this situation is true, we delete the article by calling the delete-entity perform with the entity variable routinely created for us by the define-system macro for the at present processed entity.
Notice that you simply don’t even have to shut the simulation window and restart the fundamental perform! By sending the crash-asteroids system definition to the Lisp course of, you instantly change the habits of our simulation in accordance with the foundations encoded within the new system. Nevertheless, utilizing this chance, you’ll encounter an surprising impact — the planet disappears!
For those who look carefully on the new system, you may perceive the essence of the issue: the code in crash-asteroids doesn’t distinguish between asteroids and the planet. It simply processes all entities with the place part one after one other. For the reason that coordinates of the planet middle are fairly absolutely contained in the ellipse shaped by the width and top of its picture, it will get deleted on the very first run of the crash-asteroids system.
With a view to right this challenge, let’s use a method typically utilized in ECS-architecture functions, generally known as the tag part. We’ll create an empty part with no slots, which is able to function a sort of “tag” or “label”. When added to an entity, it would sign some boolean characteristic, on this case, whether or not the article is a planet:
(ecs:define-component planet
"Tag part to point that entity is a planet.")
Then modify the init perform in order that the newly created part is added to the planet entity:
(ecs:make-object `((:planet)
(:place :x ,*planet-x*
:y ,*planet-y*)
(:picture :bitmap ,planet-bitmap
:width ,*planet-width*
:top ,*planet-height*)))
Additionally, whereas we’re at it, let’s add a little bit c̶o̶s̶m̶i̶c̶ beauty contact by making the asteroids inside our 1000-iteration loop to have random sizes:
(ecs:make-object `((:place
:x ,(float (random +window-width+))
:y ,(float (random +window-height+)))
(:pace :x ,(- (random 100.0) 50.0)
:y ,(- (random 100.0) 50.0))
(:picture
:bitmap ,(alexandria:random-elt
asteroid-bitmaps)
:scale ,(+ 0.1 (random 0.9))
:width 64.0 :top 64.0)))
Lastly, let’s modify the crash-asteroids system to skip entities with the planet part. To do that, we use the :components-no choice to the define-system macro, by which we will specify a listing of parts that ought to not be had by entities processed by the system:
(ecs:define-system crash-asteroids
(:components-ro (place)
:components-no (planet)
:with ((planet-half-width planet-half-height)
:of-type (single-float single-float)
:= (values (/ *planet-width* 2.0)
(/ *planet-height* 2.0))))
(when (<= (+
(expt
(/ (- position-x *planet-x*) planet-half-width)
2)
(expt
(/ (- position-y *planet-y*) planet-half-height)
2))
1.0)
(ecs:delete-entity entity)))
By sending the brand new definitions (planet part, init perform and crash-asteroids system) to the Lisp course of and restarting ecs-tutorial-1:fundamental, we will observe the next digital snow globe:
Much more physics
Lastly, allow us to add the gravitational drive of the planet to the elements affecting the simulated objects. We’ll neglect the mutual attraction of asteroids for simplicity. To do that, we want a brand new part — acceleration:
(ecs:define-component acceleration
"Determines the acceleration of the article, in pixels/second^2."
(x 0.0 :kind single-float :documentation "X coordinate")
(y 0.0 :kind single-float :documentation "Y coordinate"))
Subsequent, let’s introduce a system that can use acceleration to affect the pace vector, and identify it speed up:
(ecs:define-system speed up
(:components-ro (acceleration)
:components-rw (pace)
:arguments ((:dt single-float)))
(incf speed-x (* dt acceleration-x))
(incf speed-y (* dt acceleration-y)))
Nevertheless, the principle character within the gravity story would be the impact of planet mass on our asteroids. We have already got a worldwide variable with the mass of the planet, *planet-mass*. By means of some easy algebraic manipulations, we derive expressions for acceleration from the legislation of common gravitation and Newton’s 2nd legislation:
the place
is the angle between the planet and the asteroid, and- is the space between them.
is the angle between the planet and the asteroid, and
is the space between them.
Assuming that the gravitational fixed G is already included as a multiplier within the *planet-mass* variable, allow us to create a brand new system named pull to calculate the asteroid acceleration utilizing the above formulation:
(ecs:define-system pull
(:components-ro (place)
:components-rw (acceleration))
(let* ((distance-x (- *planet-x* position-x))
(distance-y (- *planet-y* position-y))
(angle (atan distance-y distance-x))
(distance-squared (+ (expt distance-x 2)
(expt distance-y 2)))
(acceleration (/ *planet-mass* distance-squared)))
(setf acceleration-x (* acceleration (cos angle))
acceleration-y (* acceleration (sin angle)))))
Lastly, within the init perform, let’s add an acceleration part to our asteroids:
(ecs:make-object `((:place
:x ,(float (random +window-width+))
:y ,(float (random +window-height+)))
(:pace :x ,(- (random 100.0) 50.0)
:y ,(- (random 100.0) 50.0))
(:acceleration)
(:picture
:bitmap ,(alexandria:random-elt
asteroid-bitmaps)
:scale ,(+ 0.1 (random 0.9))
:width 64.0 :top 64.0)))))
By sending the definitions of the acceleration part, in addition to the init perform and the speed up and pull methods to the Lisp course of, we get the same image of a snow globe, solely now the asteroids swarm across the planet extra eagerly.
To make the simulation extra attention-grabbing, let’s set it up as if a satellite tv for pc close to the planet has been destroyed, and a considerable amount of its particles, attracted by the planet, types rings. Change the code for creating asteroids within the init perform to the next:
(let ((asteroid-bitmaps
(map 'checklist
#'(lambda (filename)
(al:ensure-loaded
#'al:load-bitmap filename))
asteroid-images)))
(dotimes (_ 5000)
(let ((r (random 20.0))
(angle (float (random (* 2 pi)) 0.0)))
(ecs:make-object
`((:place :x ,(+ 200.0 (* r (cos angle)))
:y ,(+ *planet-y* (* r (sin angle))))
(:pace :x ,(+ -5.0 (random 15.0))
:y ,(+ 30.0 (random 30.0)))
(:acceleration)
(:picture
:bitmap ,(alexandria:random-elt asteroid-bitmaps)
:scale ,(+ 0.1 (random 0.9))
:width 64.0 :top 64.0))))))
Additionally, as a last cosmic contact, let’s use the star backgrounds from our assets by including the next code to the init perform, proper after bind-storage name:
(let ((background-bitmap-1
(al:ensure-loaded
#'al:load-bitmap
"../Assets/parallax-space-stars.png"))
(background-bitmap-2
(al:ensure-loaded
#'al:load-bitmap
"../Assets/parallax-space-far-planets.png")))
(ecs:make-object
`((:place :x 400.0 :y 200.0)
(:picture
:bitmap ,background-bitmap-1
:width
,(float (al:get-bitmap-width background-bitmap-1))
:top
,(float (al:get-bitmap-height background-bitmap-1)))))
(ecs:make-object
`((:place :x 100.0 :y 100.0)
(:picture
:bitmap ,background-bitmap-2
:width
,(float (al:get-bitmap-width background-bitmap-2))
:top
,(float (al:get-bitmap-height background-bitmap-2))))))
These preliminary parameters will result in the next mesmerizing simulation habits:
Notice that the bodily simulation of 5 thousand objects simply matches inside the 60 frames per second restrict, additional confirming the effectivity of the code constructed utilizing the Entity-Part-System sample. And the quantity of code we wrote, totaling 250 traces (together with boilerplate and hardcode) confirms excessive expressiveness of the Lisp language and the ability of metalinguistic abstraction.
You’ll be able to change the simulation’s preliminary parameters within the init perform to create your personal visible masterpieces. Please share your leads to the feedback 😊
Conclusion
On this tutorial, we’ve constructed a 2D physics simulation in Frequent Lisp, and explored the principle options of the cl-fast-ecs framework. The total supply code will be discovered at github.
On the time of writing, the model of the cl-fast-ecs framework is 0.4.0, which signifies that it’s quickly evolving and there nonetheless could also be modifications breaking backward compatibility. Nevertheless, the performance we’ve coated at this time — macros for outlining parts and methods, features for creating entities — is key and is unlikely to bear main modifications sooner or later.
Within the subsequent half, we’ll add consumer interplay and swap from the house style to the fantasy style as we try and make a easy dungeon crawler. Comply with me on itch.io so that you received’t miss the following half.
I want to thank my buddy @ViruScD for help and assist in writing the article, and Artem from the Lisp Eternally Telegram neighborhood for assist with proofreading the textual content.