How Do You Build 4D Worlds? - 4D Golf Devlog #3
Вставка
- Опубліковано 21 гру 2022
- Modeling 4D objects and drawing them to the screen is obviously one of the hardest problems with making a 4D game. In this Devlog, I go into the implementation detail of how I achieved this in my project and some of the amazing algorithms that got me there.
Wishlist 4D Golf on Steam: store.steampowered.com/app/21...
#4dgolf
Great video about 4D shapes: • I visualized 4D shapes...
Miratope (GitHub): github.com/galoomba1/miratope-rs
Devlog #1: • So I Guess I'm Making ...
Trailer: • 4D Golf | Release Date...
Support me and innovative projects like these!
Patreon: / codeparade
Ko-fi: ko-fi.com/codeparade
Merch: crowdmade.com/collections/cod...
Music (CC0 1.0)
Koi-discovery - Chromatismus
koi-discovery.lescigales.org/
So many problems in life can be solved by using a lookup texture instead of real-time calculations
Wife left you and took the kids? Lookup texture.
Anyone have one for your Dad getting milk but never coming back?
I could really use it right now
Technically, any algorithm that you can prove terminates can be a lookup table...
@@zyansheep Only so long as there is a finite number of allowable input combinations.
@@plopsmcgee9672 haven't seen an infinite chunk of data yet :D
I'm really glad Miratope was of some use. When I started coding it almost 3 years ago I honestly had very little idea of what I was even doing. I haven't been actively working on it for a while now, but I believe it's currently in good hands.
turn it all into audio oscillators and transduce EVP
At 2:47, the "vertex that can reach every other vertex," that's a property of star-shaped polygons/regions. Every star-shaped polygon has an internal region that can see the entire boundary of the polygon; this region is called the kernel of the polygon. In 2D, it's the intersection of all half-planes defined by the edges; it generalizes to any dimension.
en.wikipedia.org/wiki/Star_domain
Yeah I know it as a star-like region
Ahhhh that's so cool. Is kernel the same as nullspace?
@@michaelearnest1983 ah yes, the only kind of link you can follow without the comment having extra text.
@@FLMKane probably not. It's a coincidence that the word kernel is also used in linear algebra for something else
"Hmmm yes, fascinating," I say as I stroke my chin thoughtfully, completely and utterly failing to comprehend anything that's being shown or said
I think the property you migh be refering to at 2:56 is called star-convexity.
It is! Thanks a bunch, I couldn't find it in any search I did.
I learned it as “star-shaped”, but yes, that’s it.
The kernel (set of points which can see the entire boundary) of a star-shaped domain is convex. Is there any benefit to triangulating the kernel, then using the points on the boundary of the kernel to generate a triangulation of the domain? Intuitively this splits the domain into a simple(ish) centre and some boundary polytopes which feels like a nice decomposition if nothing else.
@@henryseg I learned it as 'star-like domain', basically the same lol.
Precomputed data in textures. Gotta love it.
It's a common trick. Everytime I see it I love just how silly but ingenious it feels. Yeah all this position data? Just colors in a texture. It's cracks me up
@@hamondorf9355 Why is it a texture and not a generic array? Can't GPUs work with generic arrays?
@matj1 it's texture because the data works better stored in GPU memory (VRAM) Generic arrays, if I understand what you're asking, are stored in CPU memory (RAM). This means the data would have to keep being sent to the GPU from the CPU, instead of just being always ready for use on the GPU. It's like keeping the tools you use most closer to you.
@@hamondorf9355 If I understand it correctly, a texture is an array in the GPU memory representing a raster image. Then, is every array in the GPU memory a texture? I expect that textures are special arrays, and every array in the GPU memory is a sequence of numbers, but not necessarily a texture.
@matj1 @matj1 Iirc VRAM has specialized memory that works best for certain usage patterns. I can't say for sure why. I'd assume it has to do with more hardware level stuff.
It's like asking if every thing stored in ram is an array cause the memory is contiguous. Sure, in a way, yes. But, how the memory is interpreted is up to the program. It's all just a bunch of 1s and 0s the programmer gives them meaning
The fact that you’ve wrapped your head around this stuff to not only think, but also code and optimize, in four dimensions is seriously so impressive. That optimization with the lookup texture was sick as hell
The optimization doesn't really have anything to do with the fact that it's 4D. It's just realising that there's a small number of possible inputs to this function so you can just precalculate it.
2:55 in my analysis class, we called a subset of a vector space with that property "star shaped".
That's the name I've heard for it too
Holy shit that optimization into a 64 bit table encoded to RGB values is FUCKING BRILLIANT!!! I adore your projects so much!!
I came in here thinking, "He's going to explain it!!! I can't wait to finally understand 4D world", I came out still confused but motivated. Idk how he casually just talks about 4d like it's nothing, but it made me motivated and happy to know that it is achievable to get to that level.
It's not 4d. Thats all 3d. The 4th dimension in this case isn't independent.
@@FLMKane You’re painfully wrong and have no idea how the game works.
@@aprilschauer2545 prove it
the video he links to about envisaging 4d shapes is really good
@FLMKane what do you mean? There are four degrees of freedom for position.
3:01
it is called a Star Domain!
In geometry, a set S in the Euclidean space R^n is called a star domain (or star-convex set, star-shaped set or radially convex set) if there exists an s0 in S such that for all p in S, the line segments from s0 to p lies in S. This definition is immediately generalizable to any real, or complex, vector space. (wikipedia)
I don’t understand most of this but it makes me feel good that someone does 😂 keep up the good work!
Even if someone "understands" the 4th dimension, he or she still just understands the simulation and projection of it into the 3rd or onto the 2nd dimension. Actually being in a/the 4th dimension and perceiving it for yourself would probably be like staring into an infinity; which would let our brains implode.
@@jumpander You are staring into infinity every time you look at sky.
@@madcio But that's an understandable infinity. I can also only see so far. A forth dimension is an infinity of infinities.
@@jumpander my brain hurts stop 😆
@@jumpander El aleph??
When i was doing 4d rendering, i did consider building meshes to render, but eventually i just thought back on your videos and the work of inigo quilez and raymarched it instead. super simple and ran decently well, mostly. though sending the primitives to the GPU was an interesting experience
Do you have the code posted somewhere?
@@durnsidh6483 I don't think so. And it was awful anyway. If you look up inigo quilez on UA-cam, he explains rasrching really well, and has a website with lots of code examples. I recommend starting with the one about the sdf of a box, it will explain how I came to the realisation that you can use raymarching for 4d. If you're not sure what raymarching is, there's some videos on this channel too
@@amyshaw893 Well, thanks anyways!
Nice optimization with the lookup table! Getting more and more pumped to experience all this in its final form.
love 4d stuff bruh
I'm deeply fascinated by your projects! They always fiddle with mathematics in depth.
Watching these videos is a crashcourse to visualising a 4D world which i’ve wanted for some time now, sick coding on top of that and this is a nerds dream walkthrough, great work!
You are a huge inspiration! Loved Hyperbolica, especially the farm level. The art gallery platforming was insane as well. Hyped for this!
This is endlessly cool. Well done. Been watching your videos for years and always look forward to the next one - but I always appreciate why they take time. Never compromise your quality for clout.
That truly is such a beautiful optimization, and i feel second hand pride for it, cause I'm so excited about all things 4d gaming
Oh, by the way: the property you’re looking for, beyond convex, is called **stellar convex**. Just learned about it in my topology class!
That lookup table should be the games icon/logo
Man, I can't even remotely follow this anymore. You have a truly impressive sense of visualization. I'm not giving up or anything, I'll get it one day. But you're trying to toss the ball as gently as you can and It's still flying miles over my head. LOL
If you encounter a problem in life that appears to have no solution, try throwing a lookup table at it.
-Sun Tzu-
Considering sending this to my computer graphics professor. It's really cool taking his class and then coming back to this video and actually _understanding_ what you're talking about. Feel like this is something he might find interesting. I didn't understand the brilliance of the lookup texture when I first saw this video, but that's actually really clever.
Yay! I'm always glad to see you posting.
Incredible work, these ideas are great, can't wait for the game.
I love clever optimizations like textures. Love how this is turning out so far!
I freakin love this channel. Please consider making longer and more detailed videos. 8min leaves me craving more!
You clever dog, you! Love listening about your dev adventures man! Thanks
The lookup table idea is so good it has me even more excited than most of the rest of the video
Really appreciate the technical details. It's rare to learn about both math and coding from one video!
This is inspiring! I'd love to hear your thought process when it comes to designing a 4d level, like, conceptually, because I can't imagine how you'd even begin doing that.
There is even going to be a level editor too
0:30 me when i see a honkin pair
I think this game concept is very, very unique! I've got the game wishlisted on Steam, and I can't wait to play it when it comes out!
Well, wait only some longer for the 22nd of March
Fascinating to see how you've made the lookup table for this!
2:58 It's called star convexity! (A set with that property is a star-convex set or just a star domain)
That music is really good!!! Thanks for leaving the source!
That was an amazing way to take Super Nintendo programming theory into the modern era. Tip of the hat to you sir.
Can you elaborate on what that is? I’m kinda curious
True 4d is all of the different views combined and more that we can’t comprehend
No?
@@drdca8263 No their right, a 4d creature would see a 3d image out of their eyes, just like how us 3d creatures see a 2d image out of our eyes. However we are not 4 dimensional creatures, and we can only see a max of 2(for our 2 eyes) 2d images at a time, and to comprehend 4d, you would need just as many "depth pixels" or separate images as you would pixels wide and tall. So it would be impossible to get a true 4d view.
@@Izzythemaker127 I’m not sure that makes it “all the views combined”
@@drdca8263 fair enough, but Its just the 3d -> 4d equivalent of 2d -> 3d combining many 2d planes to make a 3d space. So, you're right, the wording is a bit confusing, but also the original commenter isn't wrong.
@@Izzythemaker127 4D spaces are perhaps things we can’t *properly* visualize, on account of our brains being hard-coded for 3D spaces, but I still think it isn’t right to say that true 4D is “all the views combined” nor really that 4D spaces are “incomprehensible”.
I don't know if you read sci-fi but the chapter detailing how being in four dimensional space looks and behaves in Cixin Liu's "Death's End", the third novel in the Three Body Problem trilogy, it's just so coherent and believeable and I think you'd love it. Absolutely blew my mind.
For instance, it explains via analogy how us looking at a two dimensional world with 2d creatures from above would see their bones organs and muscles, how when you're observing from above there is not concept of "inside" in 2d. The application one dim higher is that there is no "inside" of objects in 3d, looking at someone's hand you could see the bones and muscles as easily as the skin. looking at a rock means seeing every cross section at once, it is described as "one hundred million times the visual information you see in normal space". It explains how you had to move your body carefully, because it is impossible for 3d beings to locate their hands with four coordinates, there is always one dimension you can't quite figure out how to move in, and as such you can easily touch someone's bones instead of their hand, or poke their organs by mistake. It goes into so much detail and it's all so believable, with analogies and explanations letting you actually understand the foundations of this fabricated reality and letting you play around and figure out narratives that work with them.
That trilogy is the best sci-fi I had ever read watched or experienced, possibly that I will ever experience. I highly recommend you go read that chapter, around the middle of the book. It doesn't spoil much of the plot. After that, just read the books. So good.
Love your channel, cheers!
Superb video as always!
Genius ideas you have got. Even though I didn't understand the last part about slicing, I hope at some point in the future I will understand it well.
3:01 it's called a star shaped region! I had this in my analysis course.
Bravo
2:57 That's called the "star-convexity" of a polyhedron. If a polyhedron is star-convex, "there exists a point within the polyhedron (called the "star center") that can be connected to every point on the surface of the polyhedron by a line segment that is entirely contained within the polyhedron"
Ngl, i know nothing about coding, and what i know about 4d space is thanks to you, and my brain is melting, but you have a relaxing voice and good pace with explaining, so even if i understand less than a fish understanding trigonometry, i enjoy your videos
Okay, i consider myself relatively acquainted with multidimensional spaces but you blew my brains out xD This is worthy of at least a few scientific papers!
There are some really interesting symmetries in that texture you generated. Some combination of shift, rotational, and reflective symmetries, that it took me a few moments to realize are only apparent if you wrap both the edges.
Wow dude. That's amazing!
Your explination is great but my 3 dimensional brain can't comprehend the complexities of the 4th dimension. I admire your courage to pursue the 4th Dimension!
How smart a mans gotta be to come up with his own 4d render optimizations
This is so insane. This man is pushing new territory for rendering, it's like if you made 3d meshes by writing the coordinates out in a list, except you can't even reference real life to think about the positions of those coordinates. And then he even optimised it for modern gpus.
Very impressing work ! 🙂
That lookup grid is a fantastic idea to save on processing power!
They say the creator of Roller Coaster Tycoon is the goat. Huge game by 1 developer, written completly in assembly, runs even on the lowest end pcs beautifully.
CodeParade: Yeah rendering millions of tetraheadrons (I don't even know how to write this) in 4D should do the trick.
The moment I heard “we could get the cpu to slice it and then send it to the gpu” a very loud ‘blaring wrong buzzer’ sound went off in my head. Your solution for it was incredible though! Love ur stuff
Not sure if anyone else has mentioned it, but tetrahedral meshing is something done very commonly in fluid simulation codes, you may be able to use one of those software packages to make your tet meshes more robust and less skewed.
That's interesting to know! But I think the problems are different. You generally try to minimize the tet count in 4D rather than have them distributed in a specific way. But maybe it could be useful for subdivision.
Dude! You are on the frontier of 4D rendering and pushing it further! Amazing
This video has so much math and/or coding knowledge it hurts my brain to try to think about it.
2:55 it should be a "star domain", see related description on Wikipedia.
You are a true inspiration my guy
first code parade video to officially lose me. great work man
Alright. That's brilliant. I can't wait to play!
Then just you wait
until the 22nd of March to play
Dude your solution to build the look up table is so fucking smart
I honestly can't wrap my head around the 4d concept of tetrahedras. But I'm stoked that someone else can, and that he's willing to try and explain it to us.
I love hearing about the crazy rending techniques. Can't wait for 4d windmill obstacles.
Hopefully this will be a warmup for a 4D fractal marble marcher
Absolutely beautiful
Nice use of Rhino !🎉 for the visuals
Singlehandedly making amazing mathematical fantasticals accessible like this and marble marcher AND giving great insight into their creation.
Would love to see what would happen if you had the budget etc of a massive game dev company. Excluding all complications of multiple minds etc.
this is super impressive!
What would happen if you combine 4D and hyperbolic geometry?
They're each hard enough to understand on their own 😅 but you could.
that would probably be completely incomprehensible for anyone playing it
@@packediceisthebestminecraf9007 So the next Big Indie Title.
Perhaps for a Hyperbolica sequel 👀
I believe after we have games like this we'll have people acquiring a yet unseen intuition for Einstein's Relativity
Ain't afraid to admit that I need the assistance of Google to get through these videos. But you keep putting out great stuff so I'll keep at it
Replacing logic with a data structure is one of my favorite things. When I made a Rubik's cube simulator/solver in Javascript with three.js, I had trouble knowing exactly which way to rotate a face to move a piece; like, which way should I rotate the right (R) face to move a piece from the top (U) to the front (F). Ended up manually typing a nested dictionary so that I could look up
Move[R][U][F] to get R'. That was the most productive 10 minutes of typing in the whole project.
The rendering is by far the most interesting thing so far
On 6:59 I remember making a lookup table for a ray tracing on shadertoy, also it calculated the bounding boxes too.
I think I would die working on this game. But I'm glad you're doing it.
Excited to play this game.
Then be excited for the 22nd of March
That's optimisation was awesome, it reminds me of marching cube geometry lookup tables.
I wonder if using the shared memory instead of a lookup texture wouldn't be more efficient for just a 8x8.
You are an absolute legend :D
If you are a new developer looking at this and thinking "I'll never be able to code like that!" don't despair... I've been a software engineer for a few years now and this magic still baffles me and likely always will.
This sounds like "DO despair" to me.
@@AllenKnutson LOL
(6:59) That actually looks like some very good pixel art of a plant.
2:55 The property is called star-shape (or I'm horribly mistaken). If I remember correctly, a shape is star-shape if there is a point (called the center point) such that every point in the shape is connected to the center point by a straight line (or a geodesic, for a non-Euclidean topology).
Sir you are on a whole other level
I have been to a conferece recently, on cognitive linguistics and one of the talks had your game in the title. There are researchers that are interested in how players of impossible geometry games come up with words to describe locations and directions. They have a "VR gaming lab" in Berlin and play your games.
I do work with 3- and 4-manifolds, and love these videos. There's so much good concrete stuff to know beyond academic research programs!! Do you have any thoughts as to why your lookup table looked like that? I was surprised it wasn't symmetric in any way.
I think it's partially because the lookup table is really a 2x2x2x2x4 image that has been squashed to fit into 2D. Although it's possible it's not symmetric even in that higher dimensional space as well.
It might have had more visible patterns if he'd used a different indexing scheme. The video shows bits 0-2 used for the X and 3-5 used for Y. It's hard to work backwards and figure out which configurations each pixel corresponds to.
I think if the image was organized with X = (ID&1)
It's not symmetric because of the way I brute forced it. One of the slice triangles gets priority over the other for the 1-triangle solution, and I sometimes have to flip the winding order of the triangles to match the 4D normal orientation. So it all gets kind of messy.
Suspect it would show more of a pattern if you used a k map.
Code parade making his 5048498484937th video on 4d games/worlds
you are more than a magician. sir.
This is wild.
Awesomeness!
Only one person is actually playing 4D chess, and it's this man.
This was definitely an update where I didn't understand the maths. But glad to see it's going well!
2:36 my first thought was parametric equation spam with the third parameter going perpendicular to the other 2
I love it, could you do a deeper episode on how the table lookup works ??? Because going from the table to getting millions of tetrahidron displayed was a bit of a shortcut for me and don't get how it works at all !
I'd love to give a hand with motion design if it helps :)
basically, the logic of figuring out how to display the tetrahedra is really complicated, and therefore expensive. So if you tried to compute that logic for every single tetrahedra in your scene, it is not fast enough to be able to display millions of tetrahedra. However, despite the complicated logic, the number of things that determine how to display the tetrahedra is actaully small, as there is only 64 different cases that there can be. With a lookup table, you just have to calculate those 64 different cases once, which isn't that expensive, and since its really easy to determine what case the tetrahedra are, you can just look up how to draw it in the lookup table, which is much much faster than calculating it from scratch,
When the tetrahedron is sliced, three or four points are expected. Each of those four points needs to know what edge of the tetrahedron they're on. Before, the calculation used math to determine whether each edge passed through the cut plane then tried to place the points as crossing edges were found.
You can see this in the old code as it tries to place point 0 between vertices A and B by checking whether their depths multiply to a negative number (because they're on opposite sides of the cut), then repeating point by point, vertex pair by vertex pair.
In the new lookup, it's kind of actually four lookup tables combined, one for each point 0-3. They seem to be arranged something like below:
Case 15 Case 16
Case 13 Case 14
Case 11 Case 12
Case 09 Case 10
Case 07 Case 08
Case 05 Case 06
Case 03 Case 04
Case 01 Case 02
Each case is one pixel tall and four pixels wide, with the first pixel for Point 0, the second for Point 1, third for Point 2, and fourth for Point 3. Rather than multiplying all the vertex depths together to check whether their products are less than 0 over and over and over again for every single point, you just look at their signs.
In Cases 1 and 16, for example, they were all + or all -, so the cut actually misses the tetrahedron, so all four pixels are blue to tell all four points immediately that there is nothing to draw there without doing any of that repeated multiplication at runtime. In Cases 2, 3, 5, 8, 9, 12, 14, and 15, only one vertex was different from the others, which meant the slice would be a triangle, which meant only three points are needed, which is why the fourth pixel in those cases is blue, telling the fourth point that it doesn't need to do anything.
@@Thelothuo THANKS A LOT for your explainations !! I'd love to see that explained in a video with motion graphics !
I'm not sure to get it all but it seems more understandable now :)
If you'd like to try to make a video on that with me I'd love to make one :)
impressive & elegant
What if, uhh, non-Euclidean 4D game?!
The LUT solution is mind blowing man
Doing this in all in the vertex shader or using the geometry shader? This seems like the text book use case for the geometry shader, if it ever gets used.
A good lookup table solves so many problems.
I saw 3d golf at game stop and thought of your game. I thought wow 3d golf that so last generation we have 4d golf now