Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 18 Jul 2002
Offline Last Active Jun 18 2013 08:57 PM

#5027010 Distance between parallel lines under transformation

Posted by Numsgil on 29 January 2013 - 06:15 PM

@clb: I don't think you can do h' = |M*H| because M*H is not guaranteed to be a shortest path between the two parallel lines after they're transformed by M.


That is, just because H is perpendicular to both lines before transformation doesn't mean it's perpendicular to both lines after transformation.  Consider the case of a sheering of a square in to a parallelogram.  One of those funny properties of affine transformations: closest point pairs on parallel lines aren't preserved.

#4961381 MMO and databases

Posted by Numsgil on 20 July 2012 - 11:38 AM

Thanks for the comments, everyone.

I'm looking at various NoSQL systems right now. They seem to fit closer to the mental model you have for how an MMO works. MongoDB especially seems promising. It has spatial queries and indexing, which you'd need if you want to have, say, large numbers of items floating freely in the world (ala Ultima Online, if anyone remembers that game). In the case of storing bags of items, it also has arrays natively supported. So you could have bags represented as documents in a collection (ie: as rows in a table), with items stuffed in to an array inside each bag document (row). It feels very similar to how tables work in Lua, actually. It seems to map pretty well to OOP. The primary downside is that it's not ACID compliant. So transactions (like moving an item from one bag to another) get tricky and you probably have to manage a two-phase commit manually.


To give a different usecase example, I'm trying to scope out how technically possible a "living world" MMO would be. For instance, I'm thinking of trees that spread seeds that grow more trees, with players allowed to chop the trees down or manually move seeds around. To handle it in a general way, I'm imagining that all entities that exist in the world can register themselves to run certain scripts at some future date. So on the server side you'd need to periodically query for entities that are due to run scripts and run them. The scripts can update the state of the entity, change behavior based on neighboring entities, spawn new entities, etc., and write the results back to the database. Clients could request spatial queries to get all the entities in a given area that they're playing to find all the visible entities so that the client can display them. The number of dynamic entites in a given area of the world could be quite large.

You'd probably want to cache highly active entities (like animals) in RAM, and only push changes to the database periodically. Or even treat things like animals totally differently from more static entities. But let's ignore that and just call the entire game state recording mechanism the "database".

As a single player game this wouldn't be so unusual, but making it work as an MMO would be quite difficult. I imagine a traditional RDBMS would quickly choke on something like ths.

#4961025 MMO and databases

Posted by Numsgil on 19 July 2012 - 12:34 PM

Are there any books or article series discussing database use in MMOs? For instance, there's a few one-off posts on various sites, but I'd be interested in a more comprehensive examination.

I've done a bit of SQL work, and my impression is that it would be a bit like a square-peg-in-a-round-hole situation trying to get the relational model to make sense for an MMO. If we take the simplified case of just inventory management, would you maintain a table of every item in the game universe, and have a field defining a UID for which container it lived in? Wouldn't that make a simple query like "what's in my inventory?" take forever? Many MMOs get around this by having a limited number of slots in your inventory, with few objects existing outside of players' inventories (or in banks) but if you wanted to really open that up and do an inventory system like the late Ultima games, or even something like Skyrim, where the player can have hundreds of unique items, and there are tens of thousands of unique items randomly placed throughout the world, I imagine things quickly get hairy. You'd probably also want a database model that lends itself to spatial queries (what items exist within a 20 meter bubble of some position in the world), which isn't something relational databases do very well.

I feel like there's enough domain-specific knowledge here that there must be a book or article series somewhere, either in getting relational databases to work well, or in some Non-SQL technology.

#4939436 Computing space travel

Posted by Numsgil on 11 May 2012 - 04:27 PM

If you succeed, you should probably be working at NASA. ;)

They were launching craft 50 years ago and doing the math. The computing power I have in my toaster is probably 1000 times what NASA had then. It'd still be a bit of a project to read up the academic papers and figure out how to approach the problem. But even a completely naive implementation would probably run more than fast enough. Especially if it's an autopilot feature for a proper simulation type game, there's nothing wrong with a "plotting autopilot course" wait dialog of a second or two.

#4939129 Realistic Fluid Simulation

Posted by Numsgil on 10 May 2012 - 03:04 PM

If you haven't yet you should read through this set of Intel articles on fluid sim. It specifically uses a hybrid approach where vortons and a static grid interact so you can (hopefully) get the best of both worlds. Importantly the article comes with source you can try out (though I haven't actually tried it out yet).

To your specific problem, I think at least part of the trick is to not put the vortons on the actual boundary. Instead you offest the vortons a bit from the boundary, but set them up so that they still cancel out the velocity at the boundary surface. This helps eliminate potential singularities, as I understand it. For the case of velocity flow exactly perpendicular to a flat surface, your vortons would happen to be on the surface, but to the left or right of the point on the boundary you're trying to cancel out. For non perpendicular flows, the vorton will be a bit ahead of the surface, at a glancing angle to the point you're trying to cancel out velocity at. Importantly the actual position of these new vortons change based on the relative angle of the incoming flow and the surface.

I'm curious if it's possible to construct something like a vorton, but with surfaces instead of just points.

Like for a sphere, you construct something like a vorton, but instead of causing vorticity, it pushes velocity out in all directions uniformally. That, centered right on top of the sphere and tweaked so that velocity just ahead of the sphere is 0, and added to the background uniform flow, might produce a realistic flow pattern cheaply. I'm not sure exactly, I probably need to think it trough a bit more. At first glance it seems like it would violate some conservation laws, and it would probably only really make sense for a uniform background velocity field. The more chaotic the flow around the sphere, the more likely you'd need to use more than one primitive, no matter what your primitive is (vorton or something else).

#4864261 DrawPrimitive() Dilemma

Posted by Numsgil on 21 September 2011 - 10:45 AM

Found the answer: http://origin-develo...hBatchBatch.pdf.

Basically: batch calls per frame is CPU limited (all done in the driver), and so is independent of the graphics card or its speed. From some empirical testing, 25K is a mid to low estimate of how many draw calls a 1 Ghz processor can do per second. This exact number is dependent on drivers and other factors.

#4864027 DrawPrimitive() Dilemma

Posted by Numsgil on 20 September 2011 - 06:49 PM

An interesting rule of thumb, the source of which I forget:

25000 * CPU Speed in Ghz * percentage of frame time to spend on drawl calls * time per frame = draw calls per frame

So on a 2 Ghz machine running at 60 FPS and aiming at 40% time spent on graphics, you're looking at about 320 draw calls per frame. Useful way to theorycraft how much simplification you'll need to be doing to meet your target framerate.

Not sure where the magic number 25000 comes from. I'm sure it's batches per second for a given card, but I can never seem to find numbers on that anywhere.

#4498912 Erin Catto's Sequential Impulses with accumulation and coherence

Posted by Numsgil on 27 July 2009 - 07:46 AM

Ignore for the moment that it's an LCP. You have a 2x2 system of equations. You can solve it using cramer's rule. You'll get two solution impulses: one for each contact point.

Now remember that it's an LCP, so the answers must all be >0. Check your two impulses. If they're both > 0, you're done. If one of them is <0, you need to feed your problem into an LCP solver. Since the system is so small, you can basically brute force it (direct enumeration method).

So you take the impulse that was <0, and you set it to 0 (using the complementarity condition, you're basically setting a slack variable to some non zero, positive value instead). Then you solve for the remaining impulse term as if it were the only contact. If it's <0, you clamp it to 0 as well.

Here's a web book on LCP. If you understand section 1.1 you'll be in good shape. It's in postscript format, so you'll need to download and install ghostscript and ghostview. If the download links are broken (they are sometimes), look through the download mirrors they have listed.

But here's the crib notes for it: In LCP format, basically you have Iw - Mz = q. M is your 2x2 matrix that you found from the Jacobian. q is the vector of initial conditions (ie: each element is (1+e)*(delta V * n)). I is the identity matrix, and w is a "slack" variable. If you remove Iw from the equation, you basically have your system of equations Mz = -q. Which you can solve normally using Cramer's rule. (The M matrix here is your J * M-1 * JT matrix).

The LCP has a non negativity condition (which is what you want in this case for collision impulses). So elements in z must be >0. If any are <0, they get clamped to 0.

The LCP also has what's called a complementarity condition. Which means that if an element in z is 0, the corresponding element in w is >= 0. So when you have to clamp an element in z to 0, you increase the corresponding element in w so the system will still solve correctly.

Solving the system is basically a combinatorial problem. You want to find what elements in z can be >0, and which need to be clamped to 0 and have the slack vector w handle it.

At the end of the process, you just discard w and the z vector are your impulses. For larger problems, you have to use more sophisticated solvers than direct enumeration, since it has an exponential order of complexity. But since this is a simple 2x2 system, you can do the algorithm I outlined at the beginning of the post: solve the system normally, and if any of the impulses are <0, clamp it to 0 and solve the remaining contact point in isolation.

Using this method in my little homebrew engine I was able to stack over 200 boxes in real time (~55-60 FPS) and have them be stable. You have to add friction to keep them from slipping out laterally, though (imagine stacking wet soap). And you need Baumgarte stabilization, too, or the stack will start to sag (imagine stacking blocks of depleted uranium on top of blocks of styrofoam). But that was it in my engine. No sequential impulses, etc.

I'm not sure if you need to add friction to the LCP, though, or if you can just sort of fake it. I tried adding it to my LCP, but I had to hack it to get it to work right, and even then it only works when the two bodies have a two point contact manifold. If it's vertex vs. edge it won't apply any friction for some reason.

#2993404 Anyone have DirectX 8 SDK?

Posted by Numsgil on 06 April 2005 - 05:22 PM

If you can't find it, either send me a personal message or email me at numsgil2002@yahoo.com and I can upload it to my server for you to download. I probably won't be checking back on this topic...

EDIT: October 2007 I've received like half a dozen requests since I wrote this email. I've uploaded it to my personal site. Download the DirectX 8 SDK here. Please email me a thanks when you do, so I know people are appreciative of my efforts!

[Edited by - Numsgil on October 5, 2007 3:22:19 AM]