This is a position-based physics engine made all in C for portability and versatility.
It had many challenging moments when making it, such as triangle collisions, spatial partitioning, performance optimization, and more, but I had a lot of fun building it, showing it off to my friends and family, and learning more about physics.
I added edge detection for 3D triangles and other miscellaneous stuff, like improving the website, adding VSync to the demos, but that stuff’s boring so I’m just going to show off the new demo!
It might be the coolest one so far, but it was one of the easiest to make.
I’m planning on shipping real soon though, just wanna add a few things to the website and readme!
I added triangle-walls which vertices are 3 dynamic spheres, which can collide with other particles and have all 4 particles update with their own velocities!
This makes the engine a lot more flexible, so you don’t have to make big grids of spheres if you want to be able to have walls that can move, instead of being static. And it makes rigidbodies (probably) possible!
(Press enter to spawn balls)
Demo!
2D is, of course, simpler than 3D, and the length of the function for these walls definitely show that (~40 lines). I used the same algorithm to find the closest position on a line to another position as I used for detecting collisions on the edges of the static 3D walls a while ago. It gives you a lerpable value from from the first point to the second point of the line, and you can use that to find the point you are looking for. Comparing it to the circle you’re checking against, will give the distance and the normal of the collision. You can use that information to move the circle out of the wall, and push the wall away, using the value to lerp between as the ratio to push each of the points that the wall is made of away.
This function is a bit more complicated, being about 80 lines long, but a lot of the information in the 2D version is applicable here too.
Here, instead of trying to find the closest point, we are trying to find the barycentric coordinates of the point, which is similar to the value to lerp between the two points in 2D, but for 3D (It’s basically just 3 numbers which tell you how close you are to each vertex of a triangle, and can describe any point on the triangle). This involves find the triangle’s area that you are checking against using the cross product, getting the distance of the point inward to the triangle for each edge, and calculating some inverse areas, which magically (not really) give you the barycentric coordinates. We then use these coordinates, as long as the distance to the triangle face using the dot product, to figure out whether the ball is colliding with the face, and if so, moving the ball outside of the triangle and moving the 3 vertices away as well, of course using each barycentric coordinate as a weight for how much to move each individual vertex.
I haven’t implemented detections with the edges of the triangles exactly yet though, only the faces, but I will try to implement it soon!
I improved the website to include multiple demos, and I made a couple improvements to the performance of the spatial partitioning detection, but I’ve mostly just been doing tinkering and testing with the engine some more.
Finally made the snake thin so it doesn’t turn into a blob.
It should NOT have taken 9 hours, but it really does take a long time to program in assembly. In order to figure out how to bend the snake, it checks the segment in front of the snake, packs the info into 2 bits, and then does the same thing for the segment behind the snake. Then, it does a switch statement (At least, the closest thing to a switch statement in assembly) of the 16 possible values from those 4 bits packed together and then hardcodes drawing the segment. This implementation is definitely a bit strange and not the best way to do it, but it was the first one that worked and I didn’t want to keep trying different methods (doing anything in assembly isn’t very pleasant)
(If the video looks super blurry, that’s because I recorded it at the original 320*240 resolution)
The snake now has some food that appears on the screen. Not much to say here about the feature, it’s snake! But the implementation is a little bit more interesting. In computers, random numbers aren’t much of a thing, so you’ll usually have to settle for pseudo random numbers, but, CPUs today have an RDRAND instruction for generating random numbers from thermal noise and whatnot inside the CPU. but even though it’s on practically every chip today, I still opted not to use it, because
And we want this snake to be able to run on the original i386, don’t we?
So instead I decided to use a simple pseudo random number generator I just whipped up on the spot by multiply the seed by some big numbers and xor’ing it with itself a couple times. it’s definitely not cryptographically secure, but it’s snake, so whatever.
Now that the game is done, I’m gonna add a couple more features just so the game is a bit more more comfortable to play. I plan on adding:
Sadly there’s no apple yet so the snake is getting pretty hungry.
I made the snake finally able to get longer than 1 segment through a circular style array for keeping track of the head. This means that there is an array for all the segments that store the X and Y, and the head slithers through the array overwriting the tail segment so that you don’t need to copy the whole array forward every time the snake moves.
With this way of implementing the snake, you need to shift forward all the segments in front of the snake’s head in memory so that it creates a free space in front of the head, and so the head can move into the free space instead of overwriting the tail.
It’s a pretty simple concept, but I had a lot of trouble enacting this in assembly. Having to think about individual bytes isn’t something I’m used to from having data types handled automatically by higher level languages like C.
As I was writing more assembly, I noticed a moment when whenever I added any more instructions, the screen would just go black. I knew I might be scooching up to the 512 byte limit, so I ndisasm’d the binary and found out that, sure enough, I only had 2 more bytes left!
I was preparing to have use more than 512 bytes for my program, so I knew roughly what I needed to do.
You just need one bios interrupt to read a couple sectors (512 byte chunks) into memory, and moved some code around, and now I have practically unlimited (a couple thousand bytes) to work with!
I drew a grid for the snake to move on.
The code for the nested loop is not readable at all, but then again, it’s in assembly, no matter how you write it it’s unreadable.
I had an issue with the rectangle size being 0, because the size is passed to the drawing function through the DX register and I forgot that the MUL instruction doesn’t just store the result in AX, but also the DX register. This part sounds a bit weird but the stardance devlog guide says to “Include the friction”
I know these devlogs may seem uneventful or dull, but writing anything in assembly is a hard task. It took me over an hour to draw a grid!
This is my first devlog of making (or at least trying to make) snake without an operating system using BIOS interrupts and 16 bit x86 real mode assembly.
I’ve made my functions for clearing the screen and drawing a rectangle, and it only took 5 hours to do! A lot of was also researching calling conventions, which registers can do what, and wondering why you can’t access memory with the stack pointer register (???? why cant you it LITERALLY has the word pointer in its name)
Not a huge devlog, I’ve mostly been having fun with this little parachute demo I made!
I definitely spent too much time just playing with it.
I’ve also been experimenting a bit with multithreading, but it’s not in a stable or performant enough state right now to showcase.
mp4 compression will hate this
I ported the spatial partitioning to 3D! It’s definitely a lot laggier in the 3D environment, because it needs to check 3x the partitions per ball, but it’s still a lot better than having no spatial partitioning at all.
One of the problems I encountered when transitioning to 3D was lag, but not in the expected “It’s going to be laggy when you have a lot of balls” way. For some strange reason, the framerate was still below 60 even when there were no balls in the world! It turned out to be an issue with needing to calloc a big region of memory everytime it would sort the balls into their partitions, but I was able to fix it by keeping the allocation throughout the lifetime of the partition grid. I also fixed it in the 2D version, even though it wasn’t really a problem there, it also wasn’t really a problem to fix either.
(In the video you will notice the balls disappearing, the sample I whipped up for the devlog just automatically despawns balls when they leave the partitioning grid. Also some balls fly off when spawning, because sometimes the balls spawn inside one another)
I’m getting a bit burnt out from this project though, I might ship after maybe adding multithreading, creating the README, and maybe making some more demos.
I’ve been watching some videos on real rigidbody physics, and I want to try that out too!
I added spatial partitioning to the engine to speed up collisions when you have a lot of balls in a scene.
Spatial partitioning is an optimization that divides the world into a grid, so balls only check other balls that are in close cells, instead of every ball checking all others, which is O(n^2). It seems pretty simple, but I tried 4 different ways before getting a good result. Judging by the time logged, I struggled.
I first tried a naive implementation, which was making a big grid, with each cell having a list of pointers to balls that are in it. The problem is, each cell needs to have the total amount of balls that could be in it allocated.
For the best performance, each grid cell should be the same size as a ball, and for the size I use here, you need the grid dimensions to be in the 100s. with 1000 balls, and with 64 bit pointers, you could have 1000 * 8 * 300 * 300 bytes allocated total, ~720 MB. You can get away with a lot less pointers, but that still wasn’t satisfying, or flexible.
My second try was a grid, but you only store cells which have balls in them. This doesn’t solve the high number of pointers per cell, but it uses less cells overall. It should’ve been easier, but C doesn’t have any built in hashmaps. The physics code doesn’t use many libraries, and I didn’t want to rely on more, so I had the bright idea to make my own hashmap. It didn’t work and I gave up, and that was the end of the sparse grid.
The third attempt was like the first, but I decided to try allocating the memory on the fly, when balls moved around, but it didn’t work out.
The most successful attempt was a grid, every cell is allocated, and yet, uses the least memory. Instead of storing pointers, each cell only stores two things: An offset and a length. Just indices into the ball array, which sounds easy, but then you realize - the balls are in a random order. To fix this, when updating the grid, you sort the balls into the cell they’re in. You may think that going into the dark cave of sorting is a bad idea, but here, it’s just a counting sort. Then it sets each cell’s fields, and you have your partitions.
Collisions are easier than constructing the grid, you just check every ball, find its cell, check balls in close cells, then you’re done.
There was a lot of friction with memory errors. To fix them, I learned GDB, and learnt about sanitizers, which detect lots of hard to catch memory errors.
One time the program would randomly crash, and it was really hard to fix, but a sanitizer detected an easy out of bounds error when rendering. Not even a physics thing. :(
Sorry for the long post, and the time it took me to post it, The devlog guide says to keep it short and post often, but I fell down a rabbit hole with optimizing, and was putting off writing as I knew it would be unwieldy in length.
I haven’t implemented partitioning in 3d yet, but it should be easy to transfer over.
It’s hard to see the balls in the video, but I want to keep the video smaller.
It gets laggy in the video as well, but there are 7000 balls in the scene at the end, and I check collisions 15 times per frame, I am also recording too.
If you read all the way down here, you might want to try the engine. I have a build on my pages, but it’s kinda slow on web.
(at least until I change the demo). On some screens the simulation doesn’t show up until you click fullscreen.
Sorry for weird wording, max devlog size is 4k characters.
Finally added mass to the engine!
Before now all the particles had the same mass (just implicitly, so basically all of them had a mass of 1), making the small ones super dense.
Took so long because I had to migrate back to 2d in order to make sure the mass was working in 2d (everything was in 3d already so I actually added mass to 3d first), and had to update the 2d rendering for it to be able to render in 3d, but now everything (especially springs), is a lot cooler!
I added the shape generators back for 3d, now we have ✨ 3D cloth ✨!
Trying to move to 3D, finally got triangle-sphere collisions working
the edges were by far the hardest part, the sphere-face collision actually wasn’t too hard
the engine wasn’t built for walls to be able to move, but it can handle it semi fine (I’m just having rotating walls for the cool 3d showcase)
Added some functions that generate shapes for you, for example, cloth!
not that big but i migrated to the sdl callback system, so it works on emscripten now (can run in browser)
ignore my screen recorder quality
