Understanding UI Layout Constraints (part 1)

This is the first in a series of posts where I attempt to understand and explain how UI layout constraints (such as Apple’s Auto Layout) work and are implemented. Along the way, we will learn about a field of mathematics known as “linear programming”.

This series is mainly targeted at software developers who want to understand how UI layout constraint algorithms work, but who don’t necessarily have a very strong or recent background in mathematics. I will assume you are familiar with basic algebra such as y ≤ 2x + 3. More advanced concepts will be explained as they are used.

Please be advised that I am not an expert on linear programming or these algorithms. I’m just a software developer who got curious. I will try to explain things as clearly and accurately as I can, but I might make some mistakes. If you have any questions, comments, feedback, or corrections, please email me: john (at) croisant (dot) net.

If you find this series interesting, enjoyable, or useful, please send me a little email to let me know. I spent a long time researching, writing, and polishing this series. It’s nice to hear that my efforts have made a positive difference (however small) in someone else’s life.

In this first post, I will introduce the concepts of UI layout constraints and linear programming. I will also convert a UI layout constraint example into a system of linear equations, graph the system visually, and prepare it to be solved with the simplex method. In future posts, I will explain the simplex method, the Cassowary algorithm, and how to implement the Cassowary algorithm as a computer program.

Update history:

  • 2016-02-27: Added link to Practical Optimization: A Gentle Introduction, in section “Series Introduction and Motivation”.
  • 2016-03-09: Added more accurate descriptions of artificial variables and surplus variables, in section “Preparing for the Simplex Method”.
  • 2016-04-19: Rewrote much of “Preparing for the Simplex Method” to use artificial variables and surplus variables.

Continue reading Understanding UI Layout Constraints (part 1)

chicken-sdl2 0.2.0 Released

Screenshot of a graphics demo showing waves, the moon, stars, and constellations.
Screenshot of “The Sea and the Stars”, a new demo program using chicken-sdl2 0.2.0.
Today I released version 0.2.0 of chicken-sdl2 (aka the sdl2 egg).

chicken-sdl2 provides CHICKEN Scheme bindings to version 2 of the Simple DirectMedia Layer (SDL) game development library.

Highlights of this release include:

  • Support for 2D accelerated rendering (renderer and texture)
  • Support for hints (configuration variables)
  • Support for most SDL 2.0.4 features
  • Efficient color, point, and rect operations
  • Performance improvements
  • Improved integer type checking
  • Miscellaneous other changes

For more details, please see the CHANGELOG.

Many thanks to Kooda Loutre and Kristian Lein-Mathisen for submitting suggestions which have been implemented in this release. :)

Lisp Game Jam Post-mortem

I recently participated in the 2016 Lisp Game Jam, an event where participants had 7 days (later extended to 10 days) to create a computer game using a dialect of Lisp, a family of programming languages. This is a “post-mortem” of that experience, in which I discuss what went well, what could have gone better, what I learned, and so on. Continue reading Lisp Game Jam Post-mortem

Lisp Game Jam Log #11

Today I wrapped up and submitted my entry to the January 2016 Lisp Game Jam. You can view my entry and download the source ZIP, or if you have Git you can clone the chicken-sdl2-examples repository. If I do future work on this game, the changes will probably only be pushed to the repository, not the entry page. I am considering trying to make compiled versions of the game so it is less hassle to download and play, but I don’t have the energy right now to figure out everything involved with that.

[Update: I have uploaded some videos of the game so you can see what it’s like without having to download and compile it. Video 1: Treasure Jumpers – Gameplay; Video 2: Treasure Jumpers – Gameplay 2 (Space Level)]

Screenshot of a game level with a black background, three players, and various coins and gems scattered around.I only made a few small changes to the game since my last post. I swapped the player colors around, I fixed a crash when loading a level with a non-integer gravity value, added support for players 3 through 5 (in case anyone wants to try making a level for that), and created a new level, shown here. This level has three players, and reduced gravity so you can jump higher. It is supposed to be set in space or on the moon or something, hence the black background.

I didn’t have the time/energy to add a display or update the window title to display the players’ scores, so you’ll just have to trust me that the game is indeed keeping track of every gem the players pick up.

I will write up a detailed post-mortem later this week, but now — I’m just going to get some rest!

Lisp Game Jam Log #10

Screenshot of the finished first game level. Yesterday I did quite a bit of performance tuning, implemented the ability for players to collect treasure, various gameplay improvements, and a command line flag to specify an alternate level file to load.

I wrote in my last post about how the game’s performance slowly degrades over time, probably due to pressure on the garbage collector from temporary rects created during collision detection. I did some basic performance profiling using CHICKEN Scheme’s built-in profiling support (the -profile compile flag and the chicken-profile utility program), which provides a table of each procedure that was called, how many times it was called, how much total time was spent in it, and an average time spent in it. This by itself didn’t definitively tell me that the performance issues were caused by creating too many temporary rects, but it did confirm that most of each frame was spent doing collision detection, and that make-rect was indeed being called many times. It also revealed a bug in chicken-sdl2 which impacted performance, the fix to which will be included in the next version.

I spent some time yesterday trying to improve the performance of the game, mainly by caching and reusing rects instead of allocating hundreds of temporary rects per second. This partially alleviated the issue, allowing the game to run much longer before degrading, but it hasn’t completely solved the problem. There is more work I could do to improve performance, but I am going to move on for the time being, and maybe come back to it at some future date.

Also yesterday, I added broad-phase entity/entity collision detection using bounding boxes, and the ability for players to collect treasure. The value for the treasure is added to the player’s score, although players’ scores are currently not displayed anywhere, so that is not apparent. When a player collects a treasure, a new treasure is spawned randomly. I tweaked the treasure spawning algorithm so that it won’t spawn on a tile that currently has a treasure or a player on it. I also made some tweaks and fixes to the balance and distribution of treasure.

Screenshot of a smaller, simpler game level. Also yesterday, I added a command line flag (-l FILE or --level=FILE) to specify an alternate level file to load. Shown here is the level template I included in the game to help users create their own levels.

The game window is sized to fit the level, so that levels can be different sizes. The number of treasures is also scaled to be 30% of the possible treasure spawn points, so that the gameplay balance doesn’t drastically change from level to level. Also, the game spawns the number of players specified by the level (default 2), so that hypothetically users could create a five player level and add key bindings for more players, although it would be rather difficult to fit five people around a single keyboard. Perhaps those programs that translate game controller input into keyboard presses would work here.

There is a lot more work that could be done on the game, but I’m pretty exhausted from over a week in game-jam mode. Tonight after work I might add a crude score display by updating the window title, but then I’m wrapping it up and submitting it. I might come back to it from time to time to update it and showcase more chicken-sdl2 features, but for now this is it.

Lisp Game Jam Log #9

My game jam entry is coming along nicely, and the deadline has been extended by 3 days, so I have some more time to polish it and write about it.

Screenshot of a game with five colored characters and many coins and gems scattered around the level.The “engine” parts of my game are mostly finished now, so I have been working on implementing and polishing the gameplay mechanics. I now have fairly satisfying player movement, random spawning of players (and respawning, if they fall off the screen), and random spawning of treasure. For demonstration purposes, I spawned all 5 players in this screenshot, although there are currently only controls available for two of them.

Player spawning is based on tile labels. Each tile in a level can have a 3-character label which assigns it some special behavior. In the case of player spawning, there are six labels: pl1 through pl5, which are specific to players 1 through 5, plus pl*, which can be used by any player. At the start of the game, the algorithm will try to put a player at a spawn point that is specific to that player, but if it can’t find a specific spawn point, it will fall back to selecting one of the general spawn points. (And, in the case that the level has no spawn points at all, the player will spawn in the center of the level.) If a player falls off the screen, they will be moved back to a random spawn point, either specific to that player or a general spawn point.

The treasure spawning system is similar, but more complex. There are five labels, tr1 through tr5, that can be applied to tiles to mark the tiles as treasure spawn points. The number specifies the “grade” of the spawn point, which affects what kinds of treasure appear there, and how often. Lower grade spawn points spawn mostly coins, but very often. Higher grade spawn points spawn mostly gems, but less often. The low-grade spawn points are meant to be scattered around the level in easy-to-reach places, with a few high grade spawn points in hard-to-reach places. You can see this in the screenshot, where the gold coins and green gem are in more difficult and perilous positions than the copper or silver coins. This follows the game design principle of balancing risk and reward — higher risks offer higher rewards.

The algorithm for spawning treasure first finds all the tiles in the level that have a label indicating it is a treasure spawn point. Then it shuffles that list into a random order, and begins iterating through the list, separating it into two piles. If the tile passes a random check (based on the chance specified for its treasure grade), the tile is put into the “chosen” pile. If the tile fails the check, it is put into the “rejected” pile. The algorithm terminates if enough tiles are chosen, but if it gets to the end of the original list and doesn’t have enough tiles, it will repeat the process using the “rejected” pile, giving those tiles a second (or third, etc.) chance to spawn treasure.

It is possible that a level might not have any labelled treasure spawn points, so as a fallback the algorithm simply chooses tiles at random, and spawns low-grade treasure there.

It was not strictly necessary to make the algorithm so complex. Most levels should already have relatively few high-grade treasure spawn points, so high-grade treasure would naturally be more rare (fewer tiles = less chance of being selected in the shuffle). But, this algorithm will allow me to tweak the odds for gameplay balance, and it was fun to write the list traversal code.

I have not yet programmed entity/entity collision, so it is not yet possible for players to pick up treasure. That will be my next step. I was previously thinking that treasure would disappear after a few seconds, so that the treasure is constantly circulating, encouraging the players to move around the level. But for simplicity, I will probably make the treasures remain until a player picks them up, then immediately spawn another treasure to replace it.

Another thing I did yesterday was create a highly-commented template level, to help people get started making their own level. It is not yet possible to choose a different level, but I will definitely at least add a command line flag to choose the level. If I have time, I might add a GUI to select the level.

I noticed last night that there is a performance issue with my game. While you play, the game gradually uses more and more CPU, and its framerate gradually gets choppier and choppier. I suspect that this is caused by the app putting pressure on CHICKEN’s garbage collector, since many temporary rects are being allocated and thrown away during the collision detection, which occurs hundreds of times per second.

Unfortunately I’m not experienced with profiling CHICKEN code, so I am not completely sure that my intuition is correct. But, I’ll try to reduce and reuse the rects during collision detection, and see if that helps. If I can’t figure out what the problem is, then I guess I’ll make it part of the gameplay: see which player can collect the most treasure before the game’s framerate becomes completely unplayable! :P

Lisp Game Jam Log #8

Yesterday I got pretty far along with implementing user input. I spent more time on it than I should, but I’m fairly happy with the results. The system is much more complex than other demos, in order to be flexible enough to allow the user to customize their controls.

The way I ended up programming user input has several parts:

  • The event handling system, which passes each event to a series of handler procedures
  • The controls.scm file, which defines the user’s preferred control bindings
  • The user input event handlers, which translate input events into gameplay events
  • The gameplay event handlers, which cause changes to the game state

The event handling system consists of a procedure, handle-event!, which accepts a single event and a list of event handler procedures. Each event handler procedure is a procedure (lambda) which takes the event, inspects it, and decides what to do with it. The event handler procedure may return true or false to indicate whether it “consumed” the event. If the event was consumed, no further handling of that event is performed. If the event was not consumed, the event is passed to the next procedure in the list.

Each event handler is focused on a specific kind of event. For example, there is an event handler which specifically looks for the S key to be pressed while the Ctrl key is being held. If it sees such an event occur, it saves a screenshot to disk, and returns true to indicate that it consumed the event. If it is given an event that it does not care about, it returns false so that the next event handler can try.

The controls.scm file is a list of s-expressions, like so:

(action: p1-up     scancode: w)
(action: p1-left   scancode: a)
(action: p1-right  scancode: d)

This says that when the W key is pressed or released, the p1-up action should occur, with state true or false depending on whether the key was pressed or released. Likewise for the A key triggering p1-left, and the D key triggering p1-right. I am using scancodes (rather than keycodes) because it’s not the key letters that matter, only their physical positions on the keyboard. That means on an AZERTY keyboard, it is actually the Z key which triggers p1-up, and the Q key which triggers p1-left.

The game loads the controls.scm file at startup, and generates an event handler procedure for each s-expression in the file. For example, it generates a handler that looks for the W scancode to be pressed or released. If the handler sees that happen, it calls the process-user-input-action with the symbol p1-up. The process-user-input-action procedure then creates an instance of a custom event type which indicates that player1 started (or stopped, if the key was released) trying to move up.

There are five custom event types related to players, corresponding to the (hypothetical) five possible players: player1, player2, player3, player4, and player5. These types are registered with SDL using register-events!. They are sdl2:user-events, but I created several procedures to make them easier to work with. Aside from having different symbols, the event types are all the same. They hold an action (a symbol), and optionally one or two extra integer values. sdl2:user-event can’t directly store symbols, so I had to do some clever tricks. The action symbol is mapped to an integer using a lookup table, then stored in the event’s code integer field. The two extra integer values are stored in the pointer addresses of the event’s data1 and data2 fields. There are other ways I could have handled this (such as evicting a Scheme object and storing a pointer to it), but this way works well.

There are many player event actions, indicating the various things that can happen to a player, such as trying to move in various directions, jumping, falling, landing on a tile, collecting treasure, and so on. I created an event handler procedure which looks for a player event, finds the player entity that it belongs to, and calls the appropriate procedure, such as player-start-up or player-stop-up.

Those procedures then look at the player’s state, and modify the player accordingly. For example, player-start-up set’s the player’s holding-up? property to true, and if the player is currently standing on the ground, calls player-jump!. player-jump! set’s the player’s in-air? and jumping? properties to true, and gives the player some upward velocity so they jump into the air. It also nudges the player upwards a tiny amount so that they are no longer colliding with the tile they are standing on; otherwise, the collision detection would immediately think that the player had landed.

As I mentioned at the start of the post, I think I spent too much time on this system. It is very flexible, but I should have done something dead simple (like hardcoded key bindings) for the game jam, then made it more flexible later. Oh well, too late now!

I am now working on refining the player movement logic. In particular, the player’s acceleration should change depending on the player’s state. For example, if the player is on the ground and holding left or right, they should accelerate to the left or right to counteract friction. And the friction of the tile that the player is standing on should also affect their acceleration, so that slippery tiles are more challenging to walk on. Players should also probably accelerate a small amount while holding left or right in the air, so that the user has some control while in the air.

There are less than 30 hours left in the jam, so I better get cracking!

Lisp Game Jam Log #7

I made a lot of progress today. I finished narrow phase collision detection (NPCD) between entities and tiles, added support for partial-sized tiles, added collision resolution and friction for players (and ice tiles!), decoupled the physics simulation from the render framerate, and added support for a live REPL so I can type in commands to modify the game while it is running!

Screenshot of a game, with characters standing on top of floating platforms, and some floating ice platforms above them. I already wrote about NPCD in my last post, so I won’t say much more here, except that I finished implementing it. In the process, I added support for partial-sized tiles. Certain tiles only fill part of a grid cell. For example, the floating grass tile that the yellow character is standing on only fills the top half of its cell, and the thin wood tile that the pink alien is standing on only fills the bottom third of its cell. The shape of each tile is defined in its properties as a symbol, e.g. 'top-half or 'bottom-third, and the tile’s hitbox is generated based on the symbol.

I also added collision resolution for players. Resolution is the step after detection, when you resolve (i.e. react to) the collisions that were detected. In the case of the player, this means canceling their velocity on one axis (so they stop moving) and repositioning them so that they are no longer colliding with the tile. This is where having four hitboxes comes in handy. Depending on which hitbox is colliding with the tile, I can easily determine what to do. For example, if the player’s bottom hitbox is colliding with the tile, I need to cancel downward velocity and move them so they are above the tile. If the player’s left hitbox is colliding with the tile, I need to cancel leftward velocity and move them so they are to the right side of the tile.

After I implemented that, players would no longer move through solid tiles, but they would continue sliding along the ground, never slowing down or stopping until they ran into a wall or went off the side of the screen. So, I added a simple friction simulation. Basically, if a player is touching a tile, their velocity decreases by a certain percentage, depending on how much time passed since the last frame, and how slippery the tile is. The hitboxes are used here too: if the top or bottom hitbox is touching the tile, the player’s horizontal velocity is decreased; if the left or right hitbox is touching the tile, their vertical velocity is decreased.

I added a 'friction tile property to define its friction scale, and added some frictionless ice tiles to try it out. A friction scale of 1 means normal friction, 0.5 means half friction (somewhat slippery), 0 means no friction (very slippery), 2 means double friction (very sticky), etc. A negative friction scale causes the player to accelerate, which is pretty funny and might be worth using in the gameplay somewhere.

Also today, I decoupled the physics simulation from the rendering framerate. Specifically, the physics simulation is always update with a fixed step, currently 0.005 seconds (5 ms). The rendering framerate is currently limited to a maximum of 100 FPS, or minimum of 0.010 seconds (10 ms) per frame. So, that means the physics simulation is updated at least twice for every time the scene is rendered. Updating the physics more often with smaller steps leads to more precise and stable simulations. For a game as simple as this, it is probably not really necessary, but it was really easy to implement, so I did it anyway just to show how to do it. (This is intended as an example game, after all.)

Finally, I added support for a live REPL (Read-Eval-Print Loop) while the game is running. If you run the make repl command, or compile the program or run the interpreter with the -D repl flag, the program will run the main loop in a background thread and start a REPL. This allows you to type in commands while the game is running. For example you can set one of the player’s velocity and watch them go flying. If you’re running in the interpreter, these even allows you to redefine procedures on the fly and see their effect immediately. Later I might play around with Geiser, which would let me update the code live from within Emacs, much like you can do with SLIME and Common Lisp.

One change I had to make in order to run the main loop in a background thread, is to use SRFI-18‘s thread-sleep! procedure instead of SDL_Delay for limiting framerate. CHICKEN Scheme uses “green threads“, which means that all of its threads are actually running inside a single native thread. SDL_Delay will cause the native thread to pause, and thus cause all CHICKEN threads to pause. This would make it very difficult to interact with the REPL. Fortunately, thread-sleep! causes only the current CHICKEN thread to pause, so the REPL thread can continue unhindered.

By the way, the fact that CHICKEN Scheme uses green threads has a nice side effect. When using SDL in C, only the thread that initialized SDL’s display system can interact with it, e.g. drawing to the window. But since every CHICKEN thread is running in one native thread, every CHICKEN thread can interact with the display system. This made it painless to run the main loop in a background thread.

So, there are 3 days left in the game jam, and I’m feeling pretty good about what I’ve accomplished so far. Even though the physics and collision detection took me longer than I hoped, and I had to postpone some features, it was a good exercise. Here are the remaining features I’d like to complete before the jam ends, in order of priority:

  • User input. Definitely keyboard support, and probably joystick as well. Customizable bindings by editing the settings file.
  • Collision detection between players and treasure, so players can pick up coins and gems.
  • Ability for tiles to spawn players and treasure.
  • Treasure disappears after some time.
  • Command line flag to specify a level file to load.
  • HUD interface to display players’ scores.
  • Countdown timer and “{COLOR} Player Wins!” text.
  • Simple GUI levels list so players can select a level from within the game.

We’ll see how far I can get!

P.S. Since this is probably the last post I will write about collision detection and resolution, I wanted to link to a couple resources that I found useful:

Lisp Game Jam Log #6

Screenshot of a game level with several characters. The characters have colored lines drawn around and over them. Today I started on narrow phase collision detection. I also made many “under the hood” improvements to the code. And, I decided to simplify the game in order to save time.

First I’ll write about narrow phase collision detection (NPCD). In my last post, I wrote about broad phase collision detection (BPCD), in which the goal is to quickly detect possible collisions between an entity and a tile, or between one entity and another entity. After BPCD has narrowed down the possible collisions, NPCD performs more precise mathematical checks to find out whether or not a collision is actually occurring.

Zoomed-in screenshot of a character with colored lines drawn around and over him. The approach I’m using for entity NPCD is for each entity to have four “hitboxes”, smaller rectangles that are positioned on each side: left, right, top, and bottom. (The hitboxes are drawn in green in this screenshot, and the overall bounding box is drawn in red.) I can then check each hitbox to see whether it is colliding with a tile or other entity. Depending on which of the four hitboxes is colliding, the program will be able to calculate in which direction the entity should move in order to stop colliding. This can also be used for gameplay purposes. In many platformer games, the player will be injured if she touches an enemy with her left, right, or top hitboxes, but she will defeat the enemy if she touches it with her bottom hitbox (i.e. her feet).

Also today, I made several improvements under the hood related to coordinate spaces. The biggest improvement is that I established a distinction between “worldspace” — the coordinate space in which the gameplay occurs — and “screenspace” — the pixels on the screen. (There is also “gridspace”, the rows and columns of the tile grid. One unit in gridspace equals 21 pixels in screenspace.)

Before, worldspace and screenspace were the same: one pixel on the screen was the same as one unit in the game world. In order to avoid choppy, imprecise movement, I implemented my own bounding box type that used floating point numbers, and I used floating point numbers for the position, velocity, and acceleration of entities.

But, my bounding box type was essentially the same as SDL’s rect type, except that my type used floats and SDL’s type strictly uses integers. I found myself duplicating a lot of the functionality of rects, as well as procedures for converting from one type to the other. I decided that it would be better to just use SDL’s rect and point types directly. This also has benefit of allowing me to easily use SDL’s rect and point intersection functions.

In order to work around the fact that SDL’s rects and points use integers, I decided to define worldspace as being 1000 times the scale of screenspace. In other words, one pixel on the screen is equal to 1000 units in the game world. That means I get milli-pixel precision for movement and collision detection, while be able to use SDL’s functions, and have better performance because integer math is faster than floating point math.

As a future optimization, I might change the scale to 1024, so that I can use bit-shifting to convert between worldspace and screenspace. But for now, having a round 1000 makes it easier for me to interpret worldspace coordinates in my head while debugging.

I wrote a bunch of procedures for working with SDL rects and points. These are generally useful, so I put them in a shared directory so that I can use them in future example games. I am thinking about maybe adding some of them to chicken-sdl2. The fixnum procedures could be implemented in C for efficiency.

Finally, I have decided to simplify the game concept, in order to save time. Physics and collision detection have already used up three days, and probably the next day or two as well. It would take even longer if I tried to implement slopes, ladders, and water. So, I have decided to postpone those elements of the game until after the jam. Instead, I’m only going to have solid rectangular platforms that you can jump around on. Rectangular platforms will make collision detection and resolution simpler.

Tomorrow I hope to finish up collision detection and resolution for entities and tiles. I probably will not have player-to-player collision detection for this jam, but will add it later, after the jam.

Lisp Game Jam Log #5

Screenshot showing a game with several items and characters. Each item and character has a colored box highlighting it. Not as much progress today, since I had to work. But I did managed to implement broad phase collision detection (BPCD) between entities and tiles. BPCD is a quick first pass to narrow down the number of possible collisions that need to be tested more carefully. In this case, I’m looking for tiles that are near enough to an entity that there might possibly be a collision.

Full-featured physics engines often use spatial hashing for BPCD, but since tiles are laid out in a fixed grid, I can find nearby tiles by converting the entity’s bounding box from worldspace coordinates (pixels) into tilespace coordinates (row/column).

I programmed a simple debug overlay to visualize the results. In the screenshot above, each entity’s bounding box is highlighted in red, and tiles that were detected during BPCD are highlighted in green. Empty air tiles are omitted from BPCD because they have their nonsolid property set to true, which means they don’t need to be considered at all during collision detection.

Eventually I will need to do collision detection between entities and other entities. I can’t use the tilespace coordinates trick for that, since entities aren’t arranged in a grid. But, I expect there to be fewer than 20 entities in the game simultaneously, so for BPCD I can probably get away with brute force, simply iterating through every entity. If that turns out to be too slow, I could do some crude spatial partioning, organizing the entities into 50-by-50-pixel bins.

There is still the matter of narrow phase collision detection, where I check each entity’s precise shape against the precise shape of the tiles. Because some tiles have different shapes (slopes, half-height, etc.), it is not enough just to check whether the bounding boxes intersect.

And after narrow phase collision detection, I’ll need to respond to the collision, by adjusting the entity’s position and velocity so it won’t pass through solid tiles. And, some collisions will need to trigger gameplay actions (e.g. a player colliding with a coin would cause the player to take the coin). As mentioned in the last post, I’m pretty sure I would have saved time by using a prebuilt physics engine, but at least I’m gaining experience!