# Penance

Member

255

190 Neutral

• Rank
Member
1. ## Simulating many dice rolls

Quote:Original post by no such user Quote:Original post by Penance If I generalized this, it would be input%d + input/d + n for n d-sided dice with input [0, d^n - 1] right? No, see the code sample directly above your post. Thanks =)
2. ## Simulating many dice rolls

Quote:Original post by alvaro Also, if you are rolling 20D6, is it that important that you get the exact distribution? You start running pretty quickly into the law of large numbers, which tells you that a normal distribution is a very good approximation to your roll. Then just use an algorithm that samples a normal distribution. In the case of rolling 20D6, you can use N(70,7.63762615825973334425) as a very good approximation. Then round the result, or something (I am not sure what these numbers are being used for). I suppose it doesn't need to be a perfect distribution, just a fair one. Basically, each player will get to roll a certain kind of dice for every X points they have in a skill, then those scores get compared and a modifier is computed. So, maybe for every 8 defense you get to roll 1d4, and for every point difference between the players' scores you get a certain % damage reduction.
3. ## Simulating many dice rolls

Quote:Original post by Sneftel Quote:Original post by Penance 16%6 + 16/6 + 2 = 8, not 7What's your point? Iterate through the inputs 0-35, and you will get the correct number of 2s output, the correct number of 3s ouptut, and so on up to the correct number of 12s output. I appreciate your response, but I think you're overestimating my ability to understand what's going on. ;) Can you explain what your solution is actually doing and why it produces the correct distribution? If I generalized this, it would be input%d + input/d + n for n d-sided dice with input [0, d^n - 1] right?
4. ## Simulating many dice rolls

Quote:Original post by Sneftel Quote:Original post by Penance Quote:Original post by Sneftel Waitasec. Quote:Original post by Penance Say I want to simulate 2d6. That means there are 6^2 = 36 possibilities that map to 11 buckets (2-12). I'd love to be able to call rand() once and get 0-35 as a result, and then map that back to the 2-12 range while preserving the proper probability distribution.You'd love to use a map to do addition for you? Not sure what you mean. =( output = input%6 + input/6 + 2 . It's just addition. I don't think that works though... 16%6 + 16/6 + 2 = 8, not 7
5. ## Simulating many dice rolls

Quote:Original post by alvaro A very low-tech solution that saves you lots of calls to rand() is to extract more than one die roll from each call to rand(). *** Source Snippet Removed *** Hmm interesting, thanks!
6. ## Simulating many dice rolls

Quote:Original post by Sneftel If the number of dice is far greater than the number of sides, then just sample successive binomial distribution, one for each side. That is, suppose you had to roll 1000d6. So first you sample the number of 1's, by sampling B(1000,1/6). Suppose it comes out to 120. So then the rest are between 2 and 6. So you sample the number of 2's, with B(880, 1/5). And so on, until you are left with just the 6's, all of which, of course, are six. Then just multiply each side by the number of successes for that side, and add the results. Of course, you'd have to call rand() millions of times per frame before it would actually matter for performance. Really cool idea, thank you!
7. ## Simulating many dice rolls

Quote:Original post by alvaro You could make a table of the partial sums of the probabilities, and use binary search to do your mapping. If that's not clear, I'll write an example. If you want to take the time to show me an example, it'd be much appreciated.
8. ## Simulating many dice rolls

Quote:Original post by Sneftel Waitasec. Quote:Original post by Penance Say I want to simulate 2d6. That means there are 6^2 = 36 possibilities that map to 11 buckets (2-12). I'd love to be able to call rand() once and get 0-35 as a result, and then map that back to the 2-12 range while preserving the proper probability distribution.You'd love to use a map to do addition for you? Not sure what you mean. =(
9. ## Simulating many dice rolls

Quote:Original post by Palidine Are you worried about linear performance cost because your app/game is running slow or because you just think it might. Implement it the straight forward way first then profile it if it's running slow so you can be sure you're optimizing the actually slow part. -me Just because I think it might. It's going to be for an online role-playing type game that needs to host as many game instances as possible on each box. So let's say I do a calculation between two players, and each requires 10d4, that's 20 calls to rand() just for that one interaction, and I might have multiple interactions per second per game instance. You're right, "premature optimization...root of all evil", but this problem just tweaked my curiosity, and I wondered if there was an established solution to it that I wasn't seeing.
10. ## Simulating many dice rolls

I am interested in simulating many dice rolls such as 10d4 or 20d6 efficiently. I could do it iteratively, but when rolling many dice, I'm worried about the linear performance cost. For instance, in the above examples, I'd have to call rand() 10 or 20 times, which I want to avoid. I think this is related to multinomial distributions, but I am a little lost at this point. Say I want to simulate 2d6. That means there are 6^2 = 36 possibilities that map to 11 buckets (2-12). I'd love to be able to call rand() once and get 0-35 as a result, and then map that back to the 2-12 range while preserving the proper probability distribution. 4^10 = 1048576 possibilities, so having a static look-up table could get very expensive for large numbers of dice rolls. I'm wondering if there is an efficient algorithm available to do that "reverse" mapping instead, so for 2d6 I could plug in 0 and get 2 back; or plug in 3, 4, or 5 and get 4 back; or plug in 15,16,17,18,19 or 20 and get 7 back, etc. Thanks for your time!
11. ## 2D squre to isometric formula

Using only 2D affine transformations, how do you transform a square into an isometric view? I found an article that shows using a 45 degree rotation and a 15 degree skew on both x and y, but I'm interested in the general formula for deriving how to do this. I'd also like to be able to rotate the isometric view (so if there's a square centered at the origin, rotating about that origin, I'd like to be able to fake that from an isometric view) Any ideas?
12. ## Dependency Graph + Flow

Thanks again for the responses guys. I believe your approach would work in the general case, jwezorek. One of the difficulties here is that this is being done in a functional language, so it's not as easy to "tag" nodes. I may have to end up just doing an incremental approach as opposed to trying to batch it. While it would be nice to accept an arbitrary set of nodes and have the server figure out if everything is legal, the overhead might be too much. A "you click it, you buy it" approach like Diablo seems less complex since all I need to do is check whether the required nodes have already been purchased and if the player can afford the new node.
13. ## Dependency Graph + Flow

Thanks for the response. Does that particular algorithm have a name, or did you think it up ad-hoc?
14. ## Dependency Graph + Flow

I've been researched all day and I can't find exactly what I need. Basically I want to have a skill tree in my game that is a DAG. Each edge has a cost and in order to "buy" a node, you have to be able to afford all dependent nodes. Is there anything similar to the maximum flow algorithms that returns the cumulative capacity/cost of *all* possible paths to multiple sinks? My game is client/server based, so the server needs to be able to handle forged commands, or redundant requests. For example, given this graph, whether the server is passed "buy C, D" or "buy D" it should compute the cost as 35. If passed "buy E" cost would be 45. If passed "buy E, F, A, B, C, D" or "buy E, F" cost would be 50 A -> B 10 A -> C 5 B -> D 5 C -> D 15 D -> E 10 D -> F 5
15. ## Matrix operation to do this?

I'm at a loss for the proper terminology to use here, so please bear with me. I want to update the world position of a vertex based on a velocity given in world space, but applied to a camera space basis. What I mean is, say my world space velocity is (0,100,0), I want to be able to transform my vertex along the "up" vector of my camera (given in world space) by 100. Or, if I pass in (100, 50, 0) in world space, I want to translate along my camera's "up" vector by 50 and along its "right" vector by 100, but the result should be in world space. This is the code I've come up with, and it seems to work, but I'm wondering if there is an existing operation to do this, or what this technique is called. //camera normalized Z this.cameraView.Normalize(); //normalized X Vector3 camNormalizedRight = Vector3.Cross(this.cameraView, this.cameraUp); camNormalizedRight.Normalize(); //normalized Y Vector3 camNormalizedUp = Vector3.Cross(camNormalizedRight, this.cameraView); camNormalizedUp.Normalize(); Vector3 upPart = cParticle.Velocity.Y * camNormalizedUp; Vector3 rightPart = cParticle.Velocity.X * camNormalizedRight; Vector3 zPart = cParticle.Velocity.Z * this.cameraView; Vector3 particleVel = upPart + rightPart + zPart;