Register a SA Forums Account here!
JOINING THE SA FORUMS WILL REMOVE THIS BIG AD, THE ANNOYING UNDERLINED ADS, AND STUPID INTERSTITIAL ADS!!!

You can: log in, read the tech support FAQ, or request your lost password. This dumb message (and those ads) will appear on every screen until you register! Get rid of this crap by registering your own SA Forums Account and joining roughly 150,000 Goons, for the one-time price of $9.95! We charge money because it costs us money per month for bills, and since we don't believe in showing ads to our users, we try to make the money back through forum registrations.
 
  • Post
  • Reply
Mr Shiny Pants
Nov 12, 2012
So is Verlet Integration amazing or what?

I need a ropesystem for Unity and all the one's I know of use physx which is unstable quite a lot of the time, so after doing some searching I come across a blog post about the rope system in Unreal, which casually says " the well known Verlet Integration" method.
So I've been watching some videos about Verlet Integration and it looks really, really useful. And better yet, I seem to understand it.

Is this something you learn in school? Because I've known about Euler, but all the other one's are new to me.

Adbot
ADBOT LOVES YOU

Suspicious Dish
Sep 24, 2011

2020 is the year of linux on the desktop, bro
Fun Shoe
Verlet Integration is basically a hack that relies on the difference between the past frames being somewhat near the assumed velocity. It works super well for springs or anything else that has a high "rubber band" factor and isn't influenced by external constraints, and for visuals only. It has issues when running at high/low frame rates and during "real" simulation. Super easy and looks super neat, though!

Wolfsbane
Jul 29, 2009

What time is it, Eccles?

The hardest thing about rope simulation is dealing with the rope wrapping around a sharp/thin point. If you can design the game or level so that never happens, I would strongly recommend it.

But yeah, verlet integration is pretty great for ropes.

Mr Shiny Pants
Nov 12, 2012
Well, I need to simulate a crane and hoisting stuff. I use the Ultimate Rope Editor for now, and it works but becomes quite unstable at certain points especially when the rope interacts with itself.
The Verlet stuff seems to do away with all weird physx glitches.

OneEightHundred
Feb 28, 2008

Soon, we will be unstoppable!
I might be confusing it with something else, but IIRC one of the big problems with Verlet integration is that it can't represent orientation without using 4+ points to form a 3D structure (i.e. pyramids), but if the handedness of the structure becomes inverted for any reason, it's totally incapable of recovering because the inverted configuration is stable. So, it's only really suitable for cases that stabilize in a 2D or 1D configuration (i.e. cloth, ropes, etc.).

OneEightHundred fucked around with this message at 17:27 on May 29, 2018

Elentor
Dec 14, 2004

by Jeffrey of YOSPOS

Veni Vidi Ameche! posted:

Because I want to generate them, not draw them. I’m trying to find out if there is established math or algorithms for this purpose. If not, I’m curious what approaches occur to others.

None of the examples are very hard to recreate procedurally, but as far as "expandable" goes you'd have to be a lot more specific as to how different from a simple capped cylinder you want, because these things can range from trivially easy to unfathomably complicated. But in general what you want seems to be:

1) Create a cylinder of a certain length with X sides.
2) Have the option to cut the cylinder halfway and control the height of the cut.
3) Be able to perform boolean operations, at the very least a boolean merge, though a subtraction would be useful as well.
4) Have at least these controls/references on the API:
* Power over the vertices pertaining to the cylinder's body.
* Power over the vertices pertaining to the caps.
* Power over the vertex of the tip.
* Power over the vertices of the central cut.
* Same as all the above, but with edges instead of vertices.
5) If you want to expand, the ability to create classic diamond cuts:
* The ability to create bevels from an edge (so you can create an Old Single Cut)
* The ability to create bevels from a point connecting two edges (so you can create a Mazarin Cut+)
* The ability to cut an edge on an arbitrary position and have it automatically triangulated (so you can create a Mazarin Cut+)
* The ability to connect two arbitrary points and have it automatically triangulated (so you can create any other relevant cut)

None of the examples given seem to need an L-system but if you absolutely must, you can add a simple tree reference and the ability for the spawn position of an n crystal be the body of an n-1 crystal and limit the width of the crystal to the size of the polygon or adjacent polygons you're spawning the crystal on though that all seems incredibly overkill especially if you want to make it not suck.

With 1 through 4 you can create all the examples given in an extremely simple manner. Most of the crystals in the first image and second are 6 sided cylinders with random offsets. The diamond in the first image can be created by creating an n-sided cylinder, scaling down the top cap triangles, then rotating their vertices 180/n degrees around the center where n = the amount of sides of the cylinder you're using. Move the vertices of the bottom cap except for the tip up. For example, this operation on cylinders of 4, 6 and 8 sides, notice how the shape is the same as the crystal in the first image you posted when n=4:





For the other examples you just perform random rotations and offsets on vertices. For the base you spawn a bunch of 4 or 5 sided, scale them down and perform huge offsets on random polygons, then boolean add them. For the crystals with rhombus-shaped tips in the second image you offset every odd cap vertex of an even-sided cylinder:





For the final result you just stick a bunch of them together around a small area with higher rotations the further away they spawn from center.

Edit: Also, just to make sure, don't forget to add the ability to split triangles, to harden/soften edges (Maya) or smooth groups (Max). You can have a smooth transition by sharing a vertex between n triangles and having that vertex face towards the average of the normal of the triangles. You harden the edges by have each triangle have its own set of vertices all facing towards the normal. Most of the crystals you showed would be better having every triangle split, though you can make a single quadrangle made of two conjoined triangles for each side of the cylinder to preserve that quadrangular facet look.

Elentor fucked around with this message at 15:48 on May 29, 2018

Love Stole the Day
Nov 4, 2012
Please give me free quality professional advice so I can be a baby about it and insult you

I especially love this image. It gives me some strong Rainbow Brite vibes.

KillHour
Oct 28, 2007



Man, you are a procedural math monster.

Rocko Bonaparte
Mar 12, 2002

Every day is Friday!

I'm assuming you've actually used this. I'm wondering if you know if it can make this interaction even simpler:

code:
                        waitForSelection = gameObject.AddComponent<RingMenu.RingMenuSelectionCoro>();
                        yield return StartCoroutine(waitForSelection.TheCoroutineWithoutPromises(shopkeeper.ringMenu));
                        selectedIndex = waitForSelection.SelectedIndex;
I'm trying to make this smaller. Svelto.Tasks can take away the need to add a MonoBehaviour just to run the coroutine, but in terms of LOC, I still have to declare it, right?

One of the more frustrating things with working with coroutines that rely on overloading iterator syntax is they take over the return value, so I don't think I can ever go below two lines with them. I still aspire to try.

It probably sounds dumb for me to fixate on this, but the above code is going to show up four times in my shopkeeper script alone, and in very similar ways that I can't really wrap up into a single-line helper due to the yielding.

Edit: Well, I encapsulated the coroutine in shopkeeper.ringMenu and it already had the selection index so I just use that value afterwards. So I didn't have to create a special coroutine-related MonoBehaviour any more. It involves putting a little bit of extra state in the ring menu object so that a WaitUntil() call works correctly, but I can live with that.

Rocko Bonaparte fucked around with this message at 21:07 on May 29, 2018

suction
Jul 17, 2009
Noob needs some advice:

I have a Unity nav mesh with waypoints on it. The waypoints are added/removed/modified during game play. Between the waypoints I would like to to have footprints connected like so


Is my only option is to use projector for each print? Do I have other options?

Also the nav mesh is not flat plane.

roomforthetuna
Mar 22, 2005

I don't need to know anything about virii! My CUSTOM PROGRAM keeps me protected! It's not like they'll try to come in through the Internet or something!
I made a Mahjong solitaire game with Facebook integration (which doesn't work for invites yet because they direct people to the facebook app page, which won't load unless either the user has already approved the app elsewhere, or Facebook has approved the app, which review apparently has like a month long waiting list at the moment).

Just made with raw HTML5, drawing using canvas instructions (no bitmaps at all except for Facebook-imported faces), and super lazy; I don't pre-render to bitmaps and I don't skip drawing hidden faces, because the performance didn't seem bad enough to merit making the effort, even on a Chromebook. I did the scripts with ES6 and built it with parceljs.

It's here if anyone wants to take a look. (Doesn't require Facebook permissions, you can just play solo non-challenge.)

Fun bug - if you leave it on the menu for a while, in Chrome, the font of the challenge button changes size. This only happens with the 'compiled' javascript, and seems to be only in Chrome. It seems like measureText starts returning a different size after some number of repetitions.

Comfy Fleece Sweater
Apr 2, 2013

You see, but you do not observe.

roomforthetuna posted:

I made a Mahjong solitaire game with Facebook integration (which doesn't work for invites yet because they direct people to the facebook app page, which won't load unless either the user has already approved the app elsewhere, or Facebook has approved the app, which review apparently has like a month long waiting list at the moment).

Just made with raw HTML5, drawing using canvas instructions (no bitmaps at all except for Facebook-imported faces), and super lazy; I don't pre-render to bitmaps and I don't skip drawing hidden faces, because the performance didn't seem bad enough to merit making the effort, even on a Chromebook. I did the scripts with ES6 and built it with parceljs.

It's here if anyone wants to take a look. (Doesn't require Facebook permissions, you can just play solo non-challenge.)

Fun bug - if you leave it on the menu for a while, in Chrome, the font of the challenge button changes size. This only happens with the 'compiled' javascript, and seems to be only in Chrome. It seems like measureText starts returning a different size after some number of repetitions.

Wow it runs surprisingly well on an iPhone, nice job. Would like it to fill the screen though, very small window on mobile.

roomforthetuna
Mar 22, 2005

I don't need to know anything about virii! My CUSTOM PROGRAM keeps me protected! It's not like they'll try to come in through the Internet or something!

Comfy Fleece Sweater posted:

Wow it runs surprisingly well on an iPhone, nice job. Would like it to fill the screen though, very small window on mobile.
Oh yeah, a full screen option is a thing I should do I suppose. (Though it does fill the available space as-is, so it's bigger on a landscape-view phone than on an upright phone, for example.)
I guess I could probably app-wrap it too.

Edit: now with full screen, but gently caress trying to turn anything into an app.

roomforthetuna fucked around with this message at 09:14 on Jun 2, 2018

ddiddles
Oct 21, 2008

Roses are red, violets are blue, I'm a schizophrenic and so am I
Anyone have any decent tutorials that go over more advanced Unity concepts, rather than the standard game dev version of "hello world", with simple movement?

I've been messing around with it for a bit, and I'm having a hard time imagining how any sort of complex game structures its GameObjects and code. I've been trying to wrap my head around composition based architecture, but I'm not really that sure how granular you should be getting, and how you should be sharing data and references between scripts.

For example, I have a LocalPlayerMovement script that needs the players rigidbody to run, as well as the ability to read player input. It calls a method on a PlayerInputManager script to get the current axis values to calculate the force needed to move, as well as a PlayerReferenceManager that is a central point to store all the components scripts need access to often.

In addition to that, I have a PlayerAbilityJump script that also requires the players rigidbody. It uses the same components as LocalPlayerMovement to get the jump button press to fire off the add force, and uses the reference manger to get the players rb.

I have no idea if this is the correct way do this as I think about more complex relationships, like storing the characters equipment and inventory, equipping weapons, etc. I feel like like I'm over complicating something I don't even understand yet.

Pixelboy
Sep 13, 2005

Now, I know what you're thinking...
Anyone here a mid-career services engineer, familiar with C#/Azure? Experience in web services and games?

We should chat.

Edit: I also need a senior (10+ years) PM... experience w/ advertising tech stack would be advantageous

Lork
Oct 15, 2007
Sticks to clorf

ddiddles posted:

Anyone have any decent tutorials that go over more advanced Unity concepts, rather than the standard game dev version of "hello world", with simple movement?

I've been messing around with it for a bit, and I'm having a hard time imagining how any sort of complex game structures its GameObjects and code. I've been trying to wrap my head around composition based architecture, but I'm not really that sure how granular you should be getting, and how you should be sharing data and references between scripts.

For example, I have a LocalPlayerMovement script that needs the players rigidbody to run, as well as the ability to read player input. It calls a method on a PlayerInputManager script to get the current axis values to calculate the force needed to move, as well as a PlayerReferenceManager that is a central point to store all the components scripts need access to often.

In addition to that, I have a PlayerAbilityJump script that also requires the players rigidbody. It uses the same components as LocalPlayerMovement to get the jump button press to fire off the add force, and uses the reference manger to get the players rb.

I have no idea if this is the correct way do this as I think about more complex relationships, like storing the characters equipment and inventory, equipping weapons, etc. I feel like like I'm over complicating something I don't even understand yet.
I don't think there is an established "right way" to do things, but for whatever it's worth, my instincts tell me that you're stratifying your code way too much. "Player Input" "Player Movement" and "Player Jump" are all interrelated enough that it would make much more sense to me for them to all fall under the domain of a single "Player Controls" component. Where does it end? PlayerAbilityAttack, PlayerAbilityStrongAttack, PlayerAbilityUsePotion, PlayerAbilitySwitchWeapon, and on and on... Each needing to be hooked up to who knows how many other components they need to do their job. I don't see any benefit to doing things that way.

ddiddles
Oct 21, 2008

Roses are red, violets are blue, I'm a schizophrenic and so am I

Lork posted:

I don't think there is an established "right way" to do things, but for whatever it's worth, my instincts tell me that you're stratifying your code way too much. "Player Input" "Player Movement" and "Player Jump" are all interrelated enough that it would make much more sense to me for them to all fall under the domain of a single "Player Controls" component. Where does it end? PlayerAbilityAttack, PlayerAbilityStrongAttack, PlayerAbilityUsePotion, PlayerAbilitySwitchWeapon, and on and on... Each needing to be hooked up to who knows how many other components they need to do their job. I don't see any benefit to doing things that way.

That was how I built it when I was first trying out Unity, but I came to the point where my PlayerController contained the code to manage the input, manage the rigidbody forces for moving, manage the raycasting that checks if the player is on the ground to handle jumping, managing the the vault raycasting to check for vaultable objects, and handling the animation flag changes. They all technically have to do with controlling the character. I guess I just need to pick a point of splitting up files to get a good reuseablity/ease of use balance.

I was thinking about having different weapons with different characteristics, and how having a large WeaponController script would require a bunch of switch or if/else statements to set up the weapon correctly.

This might be because my background is in JavaScript development living in MVC land, so I'm used to have a set way to separate data, logic and display.

OneEightHundred
Feb 28, 2008

Soon, we will be unstoppable!
The end begins: Apple has deprecated OpenGL on macOS.

Rocko Bonaparte
Mar 12, 2002

Every day is Friday!

ddiddles posted:

I was thinking about having different weapons with different characteristics, and how having a large WeaponController script would require a bunch of switch or if/else statements to set up the weapon correctly.

This might be because my background is in JavaScript development living in MVC land, so I'm used to have a set way to separate data, logic and display.
Ehh if you have a decent sense of code smell then you should just go willy-nilly, crashing through the drywall accidentally, and then refactor it when you've figured out what you're smelling.

Like you just mentioned a bunch of switch or if-else statements, and that should already get you thinking that maybe you want some abstraction for the weapon. Then you can just add a new weapon that implements some interface or whatever instead of having to dance around a bunch of logic blocks in your code.

If you're hung up on MVC and you're trying to use ECS, then treat components like models, and subsystems like controllers--possibly more appropriately like Angular services or whatever you're used to. Entities aren't anything but the pouch in which you cram some components together to describe something's capabilities and that is not even directly under your control.

Doc Block
Apr 15, 2003
Fun Shoe

OneEightHundred posted:

The end begins: Apple has deprecated OpenGL on macOS.

Meh. OpenGL has been dying for a long time across the board. It's been effectively dead on iOS since Metal was introduced. People should've seen the writing on the wall for OpenGL on macOS as soon as Metal was brought over from iOS. I mean, hell, Apple didn't update OpenGL at all for the previous macOS release, opting instead to leave it at OpenGL 4.1.

My main system, a 2011 iMac, is too old for Metal (and too old for the upcoming macOS 10.14) which is a real bummer, but even I'm not mad about it and knew this was coming sooner or later.

At least Metal is a nice API.

Jewel
May 2, 2009

For what it's worth, Celeste's had 2.5% of total sales on mac, and its most likely mirrored across the board . It doesn't seem worth it to take the time to port to metal. This is going to bite the game market bad I think.

96.3% of steam users are on windows, 3% on mac, 0.6% on linux.

Absurd Alhazred
Mar 27, 2010

by Athanatos

Doc Block posted:

Meh. OpenGL has been dying for a long time across the board. It's been effectively dead on iOS since Metal was introduced. People should've seen the writing on the wall for OpenGL on macOS as soon as Metal was brought over from iOS. I mean, hell, Apple didn't update OpenGL at all for the previous macOS release, opting instead to leave it at OpenGL 4.1.

My main system, a 2011 iMac, is too old for Metal (and too old for the upcoming macOS 10.14) which is a real bummer, but even I'm not mad about it and knew this was coming sooner or later.

At least Metal is a nice API.

4.1 is pretty decent as far as features go. Even if they decided they don't want to bother with OpenGL, though, I'm disappointed that there's no mention of Vulkan. I don't know that it's going to be worth it learning, supporting, and debugging a closed API solely for such a marginal market.

Edit: I should have done a tiny little bit of more research on this. The Khronos group will be the one maintaining Vulkan support on macOS/iOS, through the MoltenVK compatibility layer.

Absurd Alhazred fucked around with this message at 13:08 on Jun 6, 2018

Doc Block
Apr 15, 2003
Fun Shoe

Jewel posted:

For what it's worth, Celeste's had 2.5% of total sales on mac, and its most likely mirrored across the board . It doesn't seem worth it to take the time to port to metal. This is going to bite the game market bad I think.

96.3% of steam users are on windows, 3% on mac, 0.6% on linux.

If you already have support for multiple graphics APIs, adding a Metal backend isn’t an impossible amount of work.

edit: and games running on Unity and Unreal already have Metal support.

Doc Block fucked around with this message at 14:17 on Jun 6, 2018

xgalaxy
Jan 27, 2004
i write code
I don't have hands on experience with it myself so I can't really say but word in the street is that targetting Vulkan on MacOs (via MoltenVK) is kind of a pita.
Poor debugging support, etc.

It's still the early days with MoltenVK so hopefully things improve, especially now that there isn't much of a choice anymore.

Doc Block
Apr 15, 2003
Fun Shoe
Did anyone actually think Vulkan was ever going to come to macOS or iOS?

xgalaxy
Jan 27, 2004
i write code
Nah. I didn't. Apple wants to start developing their own graphics chips and they don't want to be hamstrung by supporting stuff that isn't their own.
I suspect we'll see graphics on a chip A* based cpu/gpu combos from Apple in the next few years. Once those things get powerful enough they will be dropping intel on their desktop platforms as well.
Deprecating OpenGL on their platforms is a precursor to that happening.

xgalaxy fucked around with this message at 15:59 on Jun 6, 2018

Doc Block
Apr 15, 2003
Fun Shoe
They’re already doing their own GPUs. The A11 used in the iPhone 8, iPhone X, etc, has an Apple-designed GPU.

Mr Shiny Pants
Nov 12, 2012

Doc Block posted:

They’re already doing their own GPUs. The A11 used in the iPhone 8, iPhone X, etc, has an Apple-designed GPU.

Aren't they PowerVR designs?

Doc Block
Apr 15, 2003
Fun Shoe
At first they used PowerVR designs, then they used customized PowerVR designs, and now they’re using their own GPU designs starting with the A11.

News that Apple would no longer be a PowerVR licensee hurt PowerVR’s owner pretty badly.

Suspicious Dish
Sep 24, 2011

2020 is the year of linux on the desktop, bro
Fun Shoe
they've been custom GPUs long before that, but this is the first time they told anybody

Rocko Bonaparte
Mar 12, 2002

Every day is Friday!

Doc Block posted:

At first they used PowerVR designs, then they used customized PowerVR designs, and now they’re using their own GPU designs starting with the A11.

News that Apple would no longer be a PowerVR licensee hurt PowerVR’s owner pretty badly.

Given I work in semiconductors (help me!):


(via Imgflip Meme Generator)

I mean, it's Apple, which is big now, but I half-expect a decade from now all these GPUs will be toast again and they'll be licensing GPU IP again from all the in-house people they started laying off.

rock2much
Feb 6, 2004

Grimey Drawer

Nude posted:

You should probably just start here; those posts are 11 years old, so a lot are probably outdated. Got any questions/particular resources you are interested in?

I'd like to make some card/board games for mobile and I'm not really sure where to start. I have an old version of Gamemaker Studio from a HumbleBundle and my job gives us a sub to lynda.com so I've started to watch some of the Unity 3D tutorials but I'm worried that I might be better off focusing on a specific set of lessons and tools instead of just doing their essentials training alone.

Veni Vidi Ameche!
Nov 2, 2017

by Fluffdaddy

Elentor posted:

None of the examples are very hard to recreate procedurally, but as far as "expandable" goes you'd have to be a lot more specific as to how different from a simple capped cylinder you want, because these things can range from trivially easy to unfathomably complicated. But in general what you want seems to be:

1) Create a cylinder of a certain length with X sides.
2) Have the option to cut the cylinder halfway and control the height of the cut.
3) Be able to perform boolean operations, at the very least a boolean merge, though a subtraction would be useful as well.
4) Have at least these controls/references on the API:
* Power over the vertices pertaining to the cylinder's body.
* Power over the vertices pertaining to the caps.
* Power over the vertex of the tip.
* Power over the vertices of the central cut.
* Same as all the above, but with edges instead of vertices.
5) If you want to expand, the ability to create classic diamond cuts:
* The ability to create bevels from an edge (so you can create an Old Single Cut)
* The ability to create bevels from a point connecting two edges (so you can create a Mazarin Cut+)
* The ability to cut an edge on an arbitrary position and have it automatically triangulated (so you can create a Mazarin Cut+)
* The ability to connect two arbitrary points and have it automatically triangulated (so you can create any other relevant cut)

None of the examples given seem to need an L-system but if you absolutely must, you can add a simple tree reference and the ability for the spawn position of an n crystal be the body of an n-1 crystal and limit the width of the crystal to the size of the polygon or adjacent polygons you're spawning the crystal on though that all seems incredibly overkill especially if you want to make it not suck.

With 1 through 4 you can create all the examples given in an extremely simple manner. Most of the crystals in the first image and second are 6 sided cylinders with random offsets. The diamond in the first image can be created by creating an n-sided cylinder, scaling down the top cap triangles, then rotating their vertices 180/n degrees around the center where n = the amount of sides of the cylinder you're using. Move the vertices of the bottom cap except for the tip up. For example, this operation on cylinders of 4, 6 and 8 sides, notice how the shape is the same as the crystal in the first image you posted when n=4:





For the other examples you just perform random rotations and offsets on vertices. For the base you spawn a bunch of 4 or 5 sided, scale them down and perform huge offsets on random polygons, then boolean add them. For the crystals with rhombus-shaped tips in the second image you offset every odd cap vertex of an even-sided cylinder:





For the final result you just stick a bunch of them together around a small area with higher rotations the further away they spawn from center.

Edit: Also, just to make sure, don't forget to add the ability to split triangles, to harden/soften edges (Maya) or smooth groups (Max). You can have a smooth transition by sharing a vertex between n triangles and having that vertex face towards the average of the normal of the triangles. You harden the edges by have each triangle have its own set of vertices all facing towards the normal. Most of the crystals you showed would be better having every triangle split, though you can make a single quadrangle made of two conjoined triangles for each side of the cylinder to preserve that quadrangular facet look.

Whoa, I thought my post had fallen by the wayside, and haven't been back here in a while. Thanks for the reply. I don't insist on using an L-system, it just happens to be something I'm familiar with for growing complicated, fractal-like entities. I'm not hung up on that, and am perfectly happy to drop it completely.

Edit: One method I'd been considering was to start with a half-dome, select some number of points on that half-dome, and grow shaped pieces from those points, and then select some number of points on each of those pieces to serve as sprouting locations for another generation, and so on. I'm not sure if I'm getting the idea across without an illustration.

Veni Vidi Ameche! fucked around with this message at 23:18 on Jun 10, 2018

Khorne
May 1, 2002
Am I insane for thinking of using the 3rd dimension of an octree, or similar structure, to represent time for a discrete 2d grid? I had this idea while driving, and a quick look over literature and web articles doesn't seem to show anyone doing this. Or even thinking of doing this. When this happens, it usually means my idea is total garbage and I am overlooking why.

One thing that's messing with me a bit conceptually, without working through it at all, is that there are presumably situations where you'd want an irregular resolution, aka not a cube. Being able to look n steps forward without adjustingthe x,y boundary may be useful, or looking at a fixed or minimum depth x,y cell with a larger sized z-axis. I realize violating the cubic split would make it not an Octree and I also realize an octree can somewhat account for this at the cost of accuracy by just accepting you're increasing the search space. So let's look a bit at the octree side of things, there are useful applications (like pathfinding/AI) where the normal depth split of an octree trivializes some problems provided you modify the property you're propagating up the tree (think of dampening by some function of distance from the centerpoint, or reducing the value for each level of the tree it propagates up, kind of similar to FMM).

There's also the issue of time continually moving forward. It will represent a discrete 2d grid of at most 256x256 (or some other chosen constraint). This means if our z axis expands beyond 256, consider situations well beyond like say magnitudes further forward, things will get pretty "worst-case". I can think of some ways to combat this, mostly by not allowing it happen through some method (there are a few, one is if the time axis value would exceed a preset limit to make a new octree with the parent node being "now" and copying over all "now" and future nodes from the old tree). Heck, even looking at the base case (many objects in a 256x256x1 space) is perhaps not ideal for an octree. Then again, this may not even be a real issue because we know the x,y constraints and any entity added to the octree will have a known location at max depth from its known x,y,t values allowing for insert, traversal, and range optimizations.

I was hoping I'd find someone suggesting this on stack overflow and some big nerds telling him he's an idiot and to use this data structure or that there's no advantage. I'm recruiting you games dev posters, to be big nerds and tell me I'm an idiot. I mean, there's probably a better structure for this, right? I'm effectively creating a time-varied density function for a 2d grid that I can get a time-averaged value from for a subsection of the grid over a given time period. Doing it with an octree simplifies that a lot but also has some potentially undesirable constraints. Maybe there's a more ideal method or structure that I'm not familiar with.

Related note, the game this for has more "concrete" actions than most other games. Issuing a move command that traverses 20 tiles on the grid has a start point, end point, and pre-determined velocity. This allows for calculating quite far into the future with no interpolation, and it allows for calculating exact x,y,t intercepts using newton's equations of motion as well as knowing exactly where things will be until an object's old command ends or is interrupted for almost free provided you have an accurate object list to check. Nearly everything in the game is like this, so there is perhaps a larger advantage to using this method, or a similar one if I am a big dummy who's overlooking some other, better-suited approach, for this particular game than in a game where player motions and actions even half a second in the future are unknown or must be interpolated.

ps the procedural generation of crystal post is very good. It's accurate, brief, clear, and leaves little to the imagination.

Khorne fucked around with this message at 00:11 on Jun 11, 2018

Absurd Alhazred
Mar 27, 2010

by Athanatos

Khorne posted:

Am I insane for thinking of using the 3rd dimension of an octree, or similar structure, to represent time for a discrete 2d grid? I had this idea while driving, and a quick look over literature and web articles doesn't seem to show anyone doing this. Or even thinking of doing this. When this happens, it usually means my idea is total garbage and I am overlooking why.

One thing that's messing with me a bit conceptually, without working through it at all, is that there are presumably situations where you'd want an irregular resolution, aka not a cube. Being able to look n steps forward without adjustingthe x,y boundary may be useful, or looking at a fixed or minimum depth x,y cell with a larger sized z-axis. I realize violating the cubic split would make it not an Octree and I also realize an octree can somewhat account for this at the cost of accuracy by just accepting you're increasing the search space. So let's look a bit at the octree side of things, there are useful applications (like pathfinding/AI) where the normal depth split of an octree trivializes some problems provided you modify the property you're propagating up the tree (think of dampening by some function of distance from the centerpoint, or reducing the value for each level of the tree it propagates up, kind of similar to FMM).

There's also the issue of time continually moving forward. It will represent a discrete 2d grid of at most 256x256 (or some other chosen constraint). This means if our z axis expands beyond 256, consider situations well beyond like say magnitudes further forward, things will get pretty "worst-case". I can think of some ways to combat this, mostly by not allowing it happen through some method (there are a few, one is if the time axis value would exceed a preset limit to make a new octree with the parent node being "now" and copying over all "now" and future nodes from the old tree). Heck, even looking at the base case (many objects in a 256x256x1 space) is perhaps not ideal for an octree. Then again, this may not even be a real issue because we know the x,y constraints and any entity added to the octree will have a known "location" from its known x,y,t values allowing for insert, traversal, and range optimizations.

I was hoping I'd find someone suggesting this on stack overflow and some big nerds telling him he's an idiot and to use this data structure or that there's no advantage. I'm recruiting you games dev posters, to be big nerds and tell me I'm an idiot. I mean, there's probably a better structure for this, right? I'm effectively creating a time-varied density function for a 2d grid that I can get a time-averaged value from for a subsection of the grid over a given time period. Doing it with an octree simplifies that a lot but also has some potentially undesirable constraints. Maybe there's a more ideal method or structure that I'm not familiar with.

Related note, the game this for has more "concrete" actions than most other games. Issuing a move command that traverses 20 tiles on the grid has a start point, end point, and pre-determined velocity. This allows for calculating quite far into the future with no interpolation, and it allows for calculating exact x,y,t intercepts using newton's equations of motion as well as knowing exactly where things will be until an object's old command ends or is interrupted for almost free provided you have an accurate object list to check. Nearly everything in the game is like this, so there is perhaps a larger advantage to using this method, or a similar one if I am a big dummy who's overlooking some other, better-suited approach, for this particular game than in a game where player motions and actions even half a second in the future are unknown or must be interpolated.

ps the procedural generation of crystal post is very good.

How about if you had the time dimension be a moving window? Within a reasonable physical framework your objects of interest are not going to be affected or affect things that are around too early or too late from where you are, and you can slowly disappear things that are in the past while generating things that are upcoming in the future. In cosmology you'd be talking about the conversion between space and time being the speed of light, but you can just decide on a reasonable speed of travel for most of your interactions that's closer to 1m/s.

roomforthetuna
Mar 22, 2005

I don't need to know anything about virii! My CUSTOM PROGRAM keeps me protected! It's not like they'll try to come in through the Internet or something!

Khorne posted:

Am I insane for thinking of using the 3rd dimension of an octree, or similar structure, to represent time for a discrete 2d grid? I had this idea while driving, and a quick look over literature and web articles doesn't seem to show anyone doing this. Or even thinking of doing this. When this happens, it usually means my idea is total garbage and I am overlooking why.
It seems like a pretty reasonable idea to me - though it's an optimization thing, so I would question whether you need to optimize, first. Do you actually have so many objects moving with newton's equations of motion that you couldn't just do the quartic solves for every pair of objects for their bounding circles colliding, without bothering with the octree-based pruning? I'd guess that for up to about 30 moving objects it would be faster to skip the overhead of populating and checking a 3D structure and just do pairwise collision detection.

I did the pairwise quartic thing in my physics engine whose purpose was colliding circular objects accurately - the tricky part is that the "timestep" of such a physics engine is a weird kind of thing where it only actually updates when things actually collide (or a user input changes something), and for rendering purposes you don't ask it "where are things now" but rather "where would things have got to with their velocities and accelerations from the last collision/input at time t=c, by time t=now". Which is another reason why it's more likely to be okay to just do pairwise collisions; even if it takes two or three times longer, you're only doing a recalculation on collision/input, not every frame.

Rocko Bonaparte
Mar 12, 2002

Every day is Friday!
I have two inventory containers in Unity I need to reconcile. One is for shopkeepers. It has item prefab info, quantities, and costs. The other is the player inventory with actual items and quantities. The prefab business is separating them. I was about to beat them both over the head with abstraction magic to handle the common stuff but I wanted to check for ideas on reconciling prefabs of inventory items versus actual instances. I don't think there is a trick here though.

KillHour
Oct 28, 2007


Add a gameobject field to the inventory item and drag the actual item into it via the inspector? I think that still works with a prefab.

leper khan
Dec 28, 2010
Honest to god thinks Half Life 2 is a bad game. But at least he likes Monster Hunter.

KillHour posted:

Add a gameobject field to the inventory item and drag the actual item into it via the inspector? I think that still works with a prefab.

This will work with prefabs. You incur overhead equivalent to an additionally spawned prefab from the reference. It’s very likely you don’t care.

Adbot
ADBOT LOVES YOU

Xerophyte
Mar 17, 2008

This space intentionally left blank

Khorne posted:

Am I insane for thinking of using the 3rd dimension of an octree, or similar structure, to represent time for a discrete 2d grid? I had this idea while driving, and a quick look over literature and web articles doesn't seem to show anyone doing this. Or even thinking of doing this. When this happens, it usually means my idea is total garbage and I am overlooking why.

No, that's a perfectly sane idea and you're not the first person to have it.

I can't really speak for real time use cases very well, but temporal bounding volume hierarchies are pretty common to handle things like motion blur in ray tracing and collision detection for animation data in VFX. We generally use 2/4-wide AABB BVHs nowadays but it's all pretty agnostic to the hierarchy type: you can use octrees, BSPs, k-DOPs, kd-trees, etc. The rendering problem domain is slightly different in that light rays are instantaneous -- in most rendering use cases, anyhow -- which opens for a number of simplifications but there's nothing stopping you from doing a time-dependent path traversal, range query or whatever on a hierarchy with 2/3 spatial + 1 temporal dimensions that's built using the exact same techniques, it all works well enough.

I think there's a few problems you might run into that may or may not be relevant to your use case:
  • Queries on octrees are a little bit poo poo if you cross over a halfway split since then you have to traverse all the way back to the root. For spatial data that usually doesn't matter that much because most queries are local. For temporal data it will depend, but I'm guessing most traversals will be starting at t=0 or so and looking to the future so you're at least more at risk for having every traversal be an inefficient traversal.
  • It's difficult to incrementally update the octree, or any BVH, since the entire point is that you've coupled the temporal and spatial data. You will need to refit the entire tree every now and again, which will be more expensive than just updating a quadtree or other 2D structure. That might be fine, I dunno, but it's a tradeoff.
  • You'd need the motion to be sufficiently complex that you need a relatively fine-grained temporal resolution. If it's (approximately) linear motion then you can do simpler things like computing a bounding capsule from the motion and bounding sphere of the body and making a 2D hierarchy of those. Also note that you can make some cases of non-linear motion a lot more linear by changing the frame: there's nothing stopping you from building a BVH in spherical coordinates, or in a frame of reference that's being accelerated by gravity. They're bounding volumes after all, they don't have to be exact.
If you're always going to be checking for intersections some fixed number of seconds in the future then you should be able to use that limitation when building your acceleration structure. My semi-unfounded expectation is that you're going to be better off with a ring buffer of N quadtrees (or other 2D acceleration structure) evenly sliced over those seconds instead of an octree. That way you can choose to only incrementally refit a limited number of trees/update, and full-time traversals will be about as fast as an octree since you'd go back to the root either way.

If you need to handle a lot of queries or complex motion over a range of times and scales then you can get significantly better efficiency from a more complex acceleration structure than just time slices of a 2D one. I'm not sure that structure should be an octree necessarily since you probably want a lower temporal resolution than spatial resolution and octrees can't do that, but they'll work. Just be really sure that you really need to trade worse acceleration structure build speed for better query speed before you go there. There aren't a lot of use cases outside of "I'm making a relativistic ray tracer" and "I'm doing ballistics simulations for the military", far as I know.

For googlable terms, try: "dynamic bounding volume hierarchy", "temporal bounding volume hierarchy" or just "bounding volume hierarchy collision detection". Some of those terms are probably quite rendering-oriented since that's the domain I happen to know them from but hopefully there's something useful. There's also a "Real Time Collision Detection" book on the specific subject of acceleration structures for collision detection which is pretty good ... or at least it was when I bought it 8 years ago. It's a bit out of date now, especially on the GPU side. You can google the title and find a pdf of the entire thing on the first page results, which is probably not supposed to happen.

  • 1
  • 2
  • 3
  • 4
  • 5
  • Post
  • Reply