# Alrecenk

Members

503

400 Neutral

• Rank
1. ## Multiple Rotation Issues

I'm sorry if you've heard this before, but I think skeletal systems are one of the major areas where quaternions really excel: http://en.wikipedia.org/wiki/Quaternions_and_spatial_rotation If nothing else you could continue to store things in matrices or Euler angles and just convert into/out of quaternions when performing the operation which is causing problems. http://en.wikipedia.org/wiki/Conversion_between_quaternions_and_Euler_angles
2. ## splitting aabb with plane

Your problem could use a little clarification, but here's how I understand it: You have an AABB, and an arbitrary non axis aligned plane that passes through it. You need to split that AABB into two AABBs (hence with an axis aligned plane) such that you have the largest possible AABB completely behind the plane. So to start let's look at a single axis. What is the largest location you can split along the x axis? The Intersection of the plane with the axis aligned bounding box forms a quadrilateral, and the smallest x on this quadrilateral represents the largest x that would be completely behind(or just touching) the plane. Since it's a polygon that lies in a plane it's minimum or maximum value along any axis is required to be a corner point on the polygon (there's probably a name for this theorem but I couldn't find it in 30 seconds of searching). So, the actual method I would suggest would be to intersect the 4 edges of the AABB that go in the direction of the axis in question with the plane. Whichever one of those 4 points has the shortest expanse in the direction your trying to maximize is the maximum position on that axis that you could cut the box and have the box completely behind the plane. To clarify if you cut above any of these points then the box is not entirely behind the plane so it's invalid, so the best position to cut is right behind all of the intersection points. If you do that right you should get the best place to cut in one axis. Repeat that for the other two axis, and your absolute best cut will be one of these 3 planes. At that point you can just check the resulting volume of each and pick the best one. I get the feeling my explanation is a lot less clear than the idea was in my head, and even though I just made this up I'm pretty sure it will work. Let me know if you need more clarification.
3. ## Taylor expansion

The Taylor expansion will be piecewise. You'll have (1.) when x+y > 1 and x-y > 1, (2.) when x+y < 1 and x+y < x - 1) and (3.) otherwise. So you calculate the Taylor expansion of each piece separately and use whichever one your current input falls into. I'm not sure how much this will help you to invert the function though. You've got one constraint on 2 variables, so in general there will tend to be an infinite number of solutions for any given f. Also: min(x+y,x-y) = x + min(y,-y) = x - |y| so f(x,y) = x^2 + xy + y^2 + min(1,x-|y|) Most likely your problem is not well defined enough to come up with a meaningful solution, but I came up with this partial one. Assume x- |y| = 1 Then f(x,y) = x^2 + xy + y^2 + 1 x = 1 + |y| so f(x,y) = (1+|y|)^2 + (1+|y|)*y + y^2 + 1 Let y > 0 f(x,y) = (1+y)^2 + (1+y)*y + y^2 + 1 f(x,y) = 3y^2 + 3*y + 2 Since we assumed y > 0 , f(x,y) can never be below 2 but for any f(x,y) above 2 you could solve for y using the quadratic formula and then plug y into the added constraint to get x. There's probably some other clever constraints you could stick in there to generate a solution for f(x,y) < 2, but like I said before you'll probably want to rethink the question you're asking.
4. ## How much of a game-changer is CUDA?

Quote:Original post by Johan Gidlund Broadphase is hard to parallelize well. You could sort each axis separately I guess but it would give no huge gains. There are some parallel sorting algorithms, but I don't know how well they actually perform. Bitonic sort comes to mind.
5. ## Problem with connecting broad and narrow phases

For most game physics you can probably take every colliding pair separately and correct it as though there were no other collisions. Then if it's not accurate enough increase the frequency with which you run physics calculations(ie run it twice per frame instead of once). If there are going to be lots of little things stacked up then you can make a special case once movement gets so slow to stop the stacked object from moving. Then you can re-enable them later if there's a collision. Actually having an automatic set-up for disabling stationary objects is a good way to shave some cycles regardless.
6. ## Ray - Quadric sphere

Is your if statement actually catching the 0 cases? Using == on floats or doubles almost never works. You should do something like abs(coef) < epsilon where epsilon is some arbitrarily small number but big enough to catch rounding errors. A linear combination of zeroes is going to come out zero and acoef isn't dependent on k (the only nonzero element). You could be tracing a ray along the plane itself in which case there are infinitely many solutions.
7. ## Ray - Quadric sphere

(x-Cx)^2 + (y-Cy)^2 + (z-Cz)^2 = r^2 x^2 - 2Cx*x + Cx^2 + y^2 - 2Cy*y + Cy^2 + z^2 - 2Cz*z + Cz^2 - r^2 = 0 if F(x, y, z) = Ax^2 + By^2 + Cz^2 + Dxy+ Exz + Fyz + Gx + Hy + Iz + J = 0 A = 1 B = 1 C = 1 D = 0 E = 0 F = 0 G = -2Cx H = -2Cy I = -2Cz J = Cx^2 + Cy^2 + Cz^2 - r^2 It's pretty straight forward, but I did it quick so you may want to check my math.
8. ## Need suggestions for an Applied AI project

If you're in school and taking other classes then building more than the simplest of 3D games is going to be hard to do in 3 months. Top down would be a lot easier and the AI parts will be roughly the same. If you want to focus on AI then I would suggest not writing the game at all, and instead write AI for a preexisting open source game such as Sauerbraten or BZflag. A friend and I once wrote AI for BZ Flag which would interpolate bullet (bullets are slow) and player movement and determine if a shot fired at the current position was likely to hit an enemy, firing automatically if a hit was detected. Using the same formulas bullets could be detected that you were likely to be hit by and dodged. I'm sure it thoroughly pissed off everyone we played with online, but it did provide a pretty good platform for playing with AI.
9. ## genetic programming or evolutionary algo for game AI

Quote:Original post by noppanit I'm just curious that has anybody used genetic programming for Game AI before? I mean I'm doing my project and I just need some experience. I'm not going to get into the genetic programming vs genetic algorithms vs gradient descent argument, but I will say that as I am typing this I am running genetic algorithms to learn strategies for the base set of the card game Dominion: http://en.wikipedia.org/wiki/Dominion_%28card_game%29 . The game has a lot of cards with varying effects and relatively simple effective combos. It would be quite a pain to write intelligent AI for every card, and doing it this way lets me generate multiple AI players that all play differently while still playing fairly well. In my experience genetic algorithm are not good at finding the "best" answer to a problem, but they are good at finding okay answers. What makes them fun is that they are good at finding unexpected answers.
10. ## Suggestions for AI technique

If the map is relatively clear then "steering behaviors" are the way to go, otherwise you'll need actual path finding. "A*" is the generally accepted best path-finding algorithm when you want the shortest path from A to B. Though there are faster things you can do if you have redundancy in your path-finding (like lots of guys going to the same place as discussed recently here: http://www.gamedev.net/community/forums/topic.asp?topic_id=579076) The behavior besides path-finding can be written exactly as you describe it. You just have to work out exactly what notices the player means. If you want sight to be blocked by objects then you'll want to look into "line of sight" checks, otherwise a simple distance check would be sufficient. If you want more complex behaviors like continuing to chase to last known position before giving up, then you'll want to look into "finite state machines". A lot of intelligent seeming behaviors can be written into an FSM pretty easily. That should be enough search terms to get your research started. My best advice for game AI is to not over-complicate things, but I'd be lying if I said I ever followed that advice.
11. ## when to recalculate path in td game?

Thanks alvaro. Your example is far superior to what I would have said.
12. ## Matrix transformation issue

If you just want translation from two translations then I believe it will be the difference in the translation section of the matrices for each object. Which is either the top 3 elements in the right column, or the left 3 elements in the bottom row depending on whether opengl uses colomn or row vectors (I don't know off the top of my head). If you're doing arbitrary transformations and then looking for the difference of transformations that reduces to solving a system of equations for the matrix multiplication. Given model matrices A and B, A*C = B solved for C. If you want to just pull translation from the differences of two matrices of arbitrary transformation then that's not really a well defined problem as it could be different for each point in space. You could just substitute a point of interest (such as the middle of the object) into both matrices and then take the difference, but the general problem has no meaningful solution
13. ## when to recalculate path in td game?

What he said, but also I don't think it is necessary to recalculate the whole field every time a tower is placed. A unit will only possibly travel into a square if there is a neighboring square whose distance from the goal is exactly one bigger. So you can start at where the tower is placed (or removed) and work your way out from there updating cells only if necessary, and you only need to ever check neighbors of updated cells potentially not touching large sections of the board. If it's still going too slow (which I doubt but I don't know anything about mobile capabilities) you could spread your updates over several frames as well. It might take the guys a fourth second to turn around, but I doubt that would bother the player much.
14. ## Have/Want List Matching Algorithm

The problem could be posed as a closest pair or collision detection type problem. Each user has a vector consisting of how much of each item they have and how much of each item they want. Then to detect a match for a user, take the user's vector, create a new vector by switching the haves with the wants, and look for points close to that new vector. kd-trees work pretty well for high dimensional spaces in my experience. Put all your people's points into the kd-tree every time they are edited and then when a user requests partners create a hyper sphere around the point described above and test that against the tree. Then sort the intersections returned by distance. As a disclaimer I haven't actually done this, so I can't say how well that meets your criteria, but I have written massive n-dimensional kd-trees and they can be pretty fast (much much faster than a naive search).
15. ## mass-spring baraff-witkin implicit solver

It looks like the non-diagonal parts are the derivatives. The derivative of a vector valued function on a vector input at a point is a non-diagonal matrix: http://en.wikipedia.org/wiki/Jacobian_matrix