A bunch of questions :)

hey, First of all, I just wanted to say thanks so much for this project -- 2d character controllers (especially collision response) is something I've always been obsessed with, and it's nice to see other people are obsessed with it too. <3

I've got a few questions, and I suspect some of them might be answerable if I could build the code, but I don't actually use C/C++ (and, every time I try to compile something, it never works), so please bear with me if I'm asking totally stupid questions!

a) I may have found a bug on lines 309-311 of main.cpp: if (iters == 1 && t == 0) { player.pos = player.vel * dt; }

There are two potential issues (I may be imagining both!): 1) I'm pretty sure you want to use += since otherwise this is going to warp the player to near the origin 2) you're using player.vel (which is the raw/uncorrected velocity) and not the temporary "vel" vector which has been nicely clamped to lie on the tangent plane... is that correct? (it might be, since if t=0 then presumably the TOI solver failed and it didn't return a useful normal. Unless GJK does actually handle this better than the root-solving methods I've been using.)

I also wanted to ask: what's the purpose of this code? I'm assuming that this is "handle the case where we start in penetration so the TOI solver can't give us a result", ie to avoid being stuck infinitely if you start the frame in penetration, but I don't really see how this code should fix that. (In the past I've tried projecting onto the previous frame's surface normal and then stepping along the tangent.)

b) Another maybe-bug (or at least, something I don't understand): in lines 95-105 of crate.h, you're depenetrating a crate out of the player by using 10 iterations of under-relaxed projection (fixing 20% of the error each iteration): couldn't you just use 1 iteration which solves 100% of the error in this case? Since nothing else is moving the crate, and the crate is always moving along the contact normal (which shouldn't change if all you're doing is translating the crate along the normal), there doesn't seem to be any reason to under-relax here. But I might be missing something! :)

c) Have you ever had any issue with seams between solid tiles? Your character controller looks fine (you sweep to find a normal, which means it should always be correct), but the crate-vs-tile code is only using NGS, which definitely does have issues with seams, so I'm curious if this just hasn't happened to you in practice. (I'm still trying to find a good solution for AABB characters (because, in degenerate situations, they can sweep exactly into the corner where two solid tiles meet and thus have seam problems), which doesn't rely on pre-processing (ie welding parallel segments together) or adjacency info (like Box2d's chain shapes).)

d) I've been trying to find a good way to support smooth movement (circles are good) and standing-on-cliffs (AABBs are good), and your example seems to work, however: doesn't this still have issues when the character lands on the corner of a solid tile? (ie your approach to keep it standing on a cliff is to use an AABB proxy to check below for collision when it's in the grounded state, but since this only applies when it's already on the ground, if the player jumps and then lands on the corner of a tile, aren't they going to be in the awkward "sort of halfway slid down the corner" case that capsules typically produce?) I'm sorry I'm not able to compile this on my own to answer this one. Figuring out a nice way to combine "character shouldn't overlap solid tiles when standing next to them" and "character is a vertical line when colliding with slopes" is something I'm still trying to figure out, it's pretty annoying! :)

Anyway, thanks again for such an edifying project. I'm currently working on a more direct depen solver -- like Erin hints in his slides, in 2D you can pretty easily directly solve for the case where the player is touching one or two planes; we've been experimenting with big worlds (think: 10,000 goombas in a giant procgen space) where doing many iterations to depen a character isn't really practical. (Then again: maybe we just need to move to C/C++ and we won't have performance problems! But it still feels like a big waste of effort to solve iteratively, when we know (thanks to the initial sweep) that we're starting very close to the correct solution.)

Cheers, Raigan

Hey Raigan!

Nice to see you around again. This whole project was a big experiment of mine. I think the underlying TOI solver was decent, but since then Erin has posted his implementation of a more optimized/stable version. I've been just using that one ever since. I believe the algorithm originally came from Gino and is documented in that Game Physics Pearls book.

In my code: https://github.com/RandyGaul/cute_headers/blob/master/cute_c2.h#L1087 From Box2D: https://github.com/erincatto/box2d/blob/main/src/collision/b2_distance.cpp#L601

To your direction question: I also wanted to ask: what's the purpose of this code? -- I was struggling at the time to figure out a way to generate a good surface normal from my simple implementation, and as a result had sort of hacked in some checks there. I do think you spotted a bug about += instead of +. I believe that if-case was rarely hit, so I didn't notice it at the time.

b) You're definitely right, in a simple case you can do just one solve and it will work. In the case of crates with nice orthogonal edges, I think you can usually get away with this, no problem. I beefed up the solves since in 2D games I make lately, it's negligible perf cost. If shapes happen to get into a penetrating case with more than one wall the soft-solve with iterations helps to converge. Basically like a band-aid over the geometric problem of low convergence situations with high horsepower.

c) Seams -- yes definitely lots of problems. I think the best solution, like you mentioned, is something like Box2D's chain shape. This way the collision routines understand the voronoi regions between different shapes, completely removing the possibility for a seam to generate bad manifold data. What I did here was a bit simpler of a solution, simply make the player have a rounded surface. When walking over seams the error in the manifolds becomes negligible until you penetrate deeply, but since the whole setup is swept you pretty much never end up in a deep intersection.

d) Regarding landing on an edge, while not in ground state -- Yes you're totally right, that this case is not handled here. Landing onto a corner would require some more logic that I never implemented in this demo. I think it totally depends on the style of the game. If it's meant to be a bit more relaxing, then I would code in some state machine that helps you land on edges and sort of assists you there. Other times, perhaps bonking off of an edge could better (thinking about wet or slippery levels).

As time has went on (it's been a while since I worked on this demo) I find myself much more interested in simpler solvers. I really like how Celeste has chosen to do things. They have a smaller number of moving things (just one player) and the levels themselves are usually not too large. Plus, you can cut up 2D levels quite easily with a broadphase. That lets the narrow-phase take a more brute force approach. They simply move one pixel at a time and perform a check. This guarantees they don't ever intersect, and it's a perfect swept solution, albeit at the cost of computation. But computers these days are so fast, a well designed system can easily get away with this in 2D.

https://maddythorson.medium.com/celeste-and-towerfall-physics-d24bd2ae0fc5 https://github.com/NoelFB/Celeste/blob/master/Source/Player/Player.cs

Dang I think I left our copy of Game Physics Pearls behind the last time we moved! :/

About (b) and (c), I'm working on solving it more directly; this paper avoids seams by implicitly identifying the voronoi region that contains the circle's position -- it's a pretty cool idea! They test vs triangles first: if the sphere position projects onto the triangle interior, they generate the usual plane constraint and mark the triangle's verts; then when they test vs edges and verts, they skip any marked ones since the sphere can't be in an edge/vert voronoi region if it's in the adjacent face's vr: http://www.codercorner.com/MeshContacts.pdf

About (d), thanks -- yeah I agree that it depends, I noticed that Dead Cells does a ton of smoothing the player's movement around corners. :)

I appreciate Celeste, especially (as you mentioned) the power and beauty in the simplicity of working in pixel units and stepping pixel-by-pixel!

This paper runs the simulation at 1khz, essentially for the same reason: the smaller the timestep, the faster it converges (less error to solve, and also closer to the surface of the valid region so the gradients (which are linear approximations.. I think) are more accurate); they only do a single iteration of constraint solving per step!

In the case of Celeste, the problem is simplified analogously: each tick we only need to consider the 3x3 pixel region around the starting position, a tiny set of candidate solutions. I don't know if the analogy really holds though! :) Anyway I really love the Celeste idea of only processing collision at the display resolution (since, with bitmap graphics, that's all you can see).

I forgot to mention: I view the depen problem as fundamentally "find the point q on the surface of the Configuration Space Object which is closest to the desired position p". (The CSO is robotics jargon for a minkowki sum of the whole scene: shrink the query shape down to a point, and inflate the scene geometry by the query shape; points on and outside of the CSO surface represent non-overlapping positions for the query shape, and the signed distance+gradient from p to the surface of the CSO is what we want our depen query to answer.)

This makes it easier to understand what's so hard about shape-vs-tiles: the tiles look nice and simple and non-overlapping, but when you inflate them by the query shape, they all overlap messily, so finding true surface points isn't trivial. So really the problem is more or less CSG: you want to inflate all of the scene geometry, then find its union: that's the geometric surface you want to project onto. (Sadly using min() to union multiple distance fields doesn't generate correct internal distance fields, which is what we're after: https://iquilezles.org/articles/interiordistance/ )

So you don't want to explicitly have to perform CSG on the geometry, you just want a process which gets you to the same surface point as if you had done so. The under-relaxation approach is one method that does this, approximately.

One good insight is that the closest point on the surface will always be either (a) a point on the surface of an inflated scene element (the trivial/easy case), or (b) formed by the intersection of the surfaces of 2 inflated scene elements (eg if your moving object is a circle that's resting on two static circles, those two static circles (when inflated) intersect at a point which is where your moving circle's center is resting). (Or it's degenerate and you're stuck between 3+ contacts, in which case jacobi/under-relaxation is as good as you can do.)

In a polygonal world, this means you can solve by explicitly enumerating all possible combinations: if the query shape overlaps shapes A and B with normals nA and nB, first you project fully out of A along nA and check if you still overlap with B; if so, you rewind and project fully out of B along nB and check if you still overlap with A. If so, you solve the remaining overlap with A by sliding along perp(nB): this implicitly finds the point where the inflated surfaces of A and B intersect. The problem is, this only works nicely for a polygonal world where the CSO surface is only formed by planes! (Also I've left out a few details; you always want to check A and B since for convex corners both will be solutions but you want the shortest one.) If you want to support circles, you now have circular arcs in the CSO and you have to resort to explicitly intersecting arcs and planes to find candidate surface points (or at least, I couldn't find a better approach).

(Also it suffers from combinatorial explosion (ie if you're overlapping tiles A,B,C, and D, you need to test every possible pair using the above method to exhaustively look for the closest point on the CSO); still, this approach totally avoids seams even with a "convex soup" scene (no explicit surface/connectivity), and typically your moving shapes are small enough relative to tiles that you're never overlapping more than 2-3 at once (large rigid shapes are very awkward and ugly, making larger things by combining multiple small pieces seems like a better way to have large things).)

It's possible that, since computers are fast now, it would make sense to do this explicitly, ie use CSG to construct the geometric surface of the nearby CSO around each moving shape; IMO a better equivalent approach would be to use image operations (ie the signed distance transform) to build an explicit signed distance field of the scene; IIRC Pixeljunk Shooter used this approach. Especially in a tile-based world where the slopes are all integer-ratios, it might be possible to compute this signed distance field at very low resolution and use bilinear interpolation to reconstruct exact slopes so that the image-based field matches the tiles perfectly without being at display resolution... maybe I'm really wrong about this, I haven't yet tried it.

Casey Muratori had a pretty novel approach in Handmade Hero: he explicitly searches space to find any point external to the CSO, and then refines this to find the closest external point to the query point. He uses only boolean result point samples, I think it's inspired by his approach to character movement in The Witness (which similarly operated in a worldspace grid which was heavily sampled/refined). IMO, similar to 100 iterations of under-relaxation, this approach doesn't scale nicely to hundreds or thousands of characters though.

(His approach is sort of like Erin Catto's recent(ish) "find TOI by searching forward and backwards in time" approach, only searching in space instead of time: you don't just push out of the things you're overlapping, you also (if you started overlapping them) suck in towards them, since you know you want to end up on the surface. I haven't explored this properly yet, but it's possible that the relaxation-based solvers could be greatly accelerated by using this idea.)

The two high-level philosophies seem to be (1) "step freely and project onto the surface of the valid region", and (2) "don't ever cross the surface, always stay outside of it in the valid region". The problem with (1) is that it's a messy difficult geometrical problem as detailed above. The problem with (2) is that it requires game/logic design which by construction never forms loops of dependencies -- which, admittedly, is probably good enough for almost all 2D games! (IMO "physics" isn't particularly fun).

I've seen an arcade-style system which functions like Celeste but attempts to recursively move things (ie if shape A wants to move right but its blocked by shape B, it asks shape B if it can move right, etc.); this seems like it would have some serious issues with degenerate situations (loops) but probably in practice it's workable?

My problem is that I'm a bit obsessed with making a game inspired by Umihara Kawase, which has two-way interaction between moving objects via rope, and moving platforms which don't crush you (and which interact physically with the other objects and the rope). I don't want "physics" really, I just want a scene with lots of moving objects which don't overlap and which can push each other around to resolve pile-ups (instead of there being a priority system where interactions are only one-directional).

The other problem with (2) is that due to numerical problems, you're almost always going to have some overlap/crossing of the surface; so you do still need to be able to find your way back onto the surface (but, it's an easier problem since you know you'll be very close to the surface). Celeste's use of integer coordinates for position/collision totally side-steps this issue! Although, it makes sloped platforms a lot more weird/challenging to implement, I'm still working on that.

Anyway, sorry about the ramble! This is a problem I've revisited every few years and it's still really annoying to me that I don't know a good simple solution! There are so many factors (how things are represented, what sort of behaviours you want to support, etc.) that it's a bit overwhelming tbh. I'm just frustrated that after like 20 years, I still don't have a better solution than what we did in N (which was voronoi-region-based, and doesn't work with AABBs).

This makes it easier to understand what's so hard about shape-vs-tiles: the tiles look nice and simple and non-overlapping, but when you inflate them by the query shape, they all overlap messily, so finding true surface points isn't trivial.

Haha, I find the mental gymnastics required to say "it's easier to see in configuration space" quite amusing -- in a good way 😄

I'm glad you brought up iq's shaders. I recently used them at work! I see these shaders as leveraging better hardware with simpler algorithms. It's piggy-backing on hardware advances to brute-force calculate a distance value for each pixel. This reminds me a bit of the Celeste algorithm -- piggy-back on how fast CPUs are (if all your data is in the cache of course) and let it fly.

I checked out Umihara Kawase, I suspect something similar to Celeste is used, with explicit logic paths for handling platform interactions. From watching some videos I don't see any "piling up" scenario. This gets into physics land. I think Celeste still used floating point for all their collision interactions, not actual integers. They just don't move into a colliding configuration, so technically their character would always be numerically floating, and would "land" near surfaces at varying heights (and cease movement into the surface). It's just a very brute-force style, and works really well.

For E. Catto's bilateral advancement -- I believe he only searches forwards and backwards to try and help support rotations. Since players aren't rotating you can just advance time forward quite safely. The only thing that may happen in a non-rotating case is the closest voronoi regions may change, but their orientations are static.

For your game it doesn't sound like you need to support very many objects, maybe just a couple hundred static tiles at a time with a small number of dynamic objects. I would probably just do position based projections with a good number of iterations. Your piles of objects are likely going to be quite manageable. You don't need to worry about combinatorics or implausible scenarios. Jittering can be quite low or non-existent in small piles with low iterations.

It's totally possible to support tile-merging on-the-fly, since they're probably very easy to lookup when next to each other for near-zero cost. I do feel that merging on configuration-space is not really necessary unless you're searching the space (like GJK does). Understanding the geometry in cartesian space, especially for tiles, seems to be the simpler solution.

My favorite implementation for sloped tiles I've ever seen is in Ichigo's game, Leliani's Island: https://forums.tigsource.com/index.php?topic=46289.msg1416664#msg1416664

One more link https://maddymakesgames.com/articles/celeste_and_towerfall_physics/index.html

So yes it does look like under the hood there are integer movements.

Yeah, Lelani's devlog is definitely something I've pored over. :) The problem is that their approach uses the Mario Maker solution of side-stepping the problem: constrain the level data so that slopes always start/end on flat ground. Every old game with slopes does this too, since it makes the problem very tractable.. but I find it so unsatisfying! (Also it makes procgen slightly harder, and destruction is a bit awkward since you can't guarantee the slopes will be bounded with flat tiles (so explosions might need to alter adjacent-but-not-in-blast-radius tiles).)

Umihara is just a reference, we'd like to support a much more dynamic world (ie similar to Noita, but tile-based): think a 256x256-tile space of 8x8-pixel "tiles", each tile is more of a "chunk" -- analogous to a tile, but can be freely positioned and connects with adjacent chunks to form platforms. Here's a screenshot from one of our R&D projects showing chunks forming a surface: chunkworld

I've been trying to think about how to implement something like Celeste's model (positions/collisions happen on an integer grid) more generally -- so the grid you're stepping through isn't necessarily pixels, it could be sub-pixels, the idea is just that space is fundamentally discretized so that local search methods for finding the solution become much more useful: if you only step N pixels forward, you only need to search an NxN region to find the closest surface point.

About bilateral advancement, I meant more on an analogous hand-wavey level, speculating that something similar can be done for "find the closest point on the CSO surface": currently under-relaxation is only pushing out in one direction, because it can't deal with overshoot -- this is analogous to conservative advancement, which Erin showed you could improve by bracketing the solution from two directions instead of only pushing in one direction.

So maybe there's a similar series of in/out projections we can do for depen -- page 4 of this paper seems to describe such a method, which is similar to Erin's "sweep to collect planes, then solve planes" except they're alternating "sweep to find a plane then project onto it" and "find the new closest plane and project onto that": https://www.researchgate.net/profile/Changsoo-Je/publication/224839439_PolyDepth_Real-Time_Penetration_Depth_Computation_Using_Iterative_Contact-Space_Projection/links/00b7d51cad419d8fd8000000/PolyDepth-Real-Time-Penetration-Depth-Computation-Using-Iterative-Contact-Space-Projection.pdf

This thesis covers a bunch of related topics (in the context of some simulation paradigms I don't fully grasp, but they're analogous to stuff I've encountered -- eg generating speculative contacts for nearby stuff causes "ghost collisions" because you're extending linesegs into planes): https://foswiki.cs.rpi.edu/foswiki/pub/RoboticsWeb/LabPublications/Binh_thesis_final.pdf

IMO the requirements for platformers are actually a lot stricter than most 3D games where you don't notice a slight amount of error (because you're not looking at the ground edge-on, like you do with a side-view 2D game).

I admit I'm pretty obsessed with this problem -- a few years ago we tried Phaser and several other game frameworks, and discovered that they all had terrible tilemap collision: even with just squares, they were glitchy and awful! Since then I've really wanted to find a solution which didn't require any preprocessing, which worked on "convex soup" (or ideally "lineseg soup") ie no adjacency info, and which was simple and performant enough that you could just drop it in anywhere. Of course.. this is probably a pipe-dream! I have a very bad habit of being way to anal about some aspects of game development. ;-;

I do agree that just relaxing to depen is probably good enough, it's just very unsatisfying because in 2D the problem is so simple, it should admit to a more direct solution (I hope).

Also, some other context is that we're trying to run our game simulation at 1khz because we'd like to support variable framerates, but AFAICT there's just no nice way to do this: if you do the "sim at 100hz then interpolate between the two most recent frames" method then you're adding complexity (you need to keep around 2 frames of state and interpolate between them) and latency (okay, 10ms of latency is probably not a deal-breaker, it just annoys me that it's there); if you tick at 1khz then you can just render the most recent frame and the error is at most 1ms which (so far in our tests) seems imperceptible. (This is probably also very stupid/silly!) :)

(variable framerate meaning monitors with different refresh rates, the tick will be fixed-size steps of course! I'm not that crazy :) )

I still think your idea of “merging” shapes at runtime is completely doable, even with your nice big “tiles”. The core issue with soups is they are unsorted, but if you can lookup neighbors without much trouble then adding in those extra voronoi regions shouldn’t be too hard.

Of course in 3D things are messier as you have to deal with a 2D contact plane, but in 2D it’s simple enough to fully enumerate a voronoi region’s neighboring regions and construct the “adjacency info” on the fly. I’m imagining passing in two or three “tiles” to a single function, then let it figure out what the surface is like, and collide against a box2d-style chain shape. If you have integers underneath perhaps keeping it numerically robust won’t be too hard. An advantage here is the tiles can freely be altered, moved, destroyed since there’s no preprocess step.

RandyGaul / player2d

A bunch of questions :) #10