tag:blogger.com,1999:blog-5052387.post5502058233813958214..comments2024-03-17T16:13:55.262-07:00Comments on Blobs in Games: Game Component: Spaceship editor, part 2Amithttp://www.blogger.com/profile/12159325271882018300noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-5052387.post-78026460609131912912009-01-28T18:50:00.000-08:002009-01-28T18:50:00.000-08:00Do note that I said matrix pseudo-inverse *if* you...Do note that I said matrix pseudo-inverse *if* you were okay with activating a thruster to a negative degree, and that you probably wouldn't be. I don't want to be blamed for a flat "Use matrix pseudo-inverse, it's what you want" statement.<BR/><BR/>One reason I like using a ready-made linear programming solver is that then you can add extra constraints to model other things as your problem becomes more complicated. That's quite hard to do if you're building a custom "like linear programming, but not really admitting that that's what it is" solver.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5052387.post-62312283218028534832009-01-23T08:56:00.000-08:002009-01-23T08:56:00.000-08:00Hi Darren,Yes, linear programming is the best matc...Hi Darren,<BR/><BR/>Yes, linear programming is the best match for this problem; I just didn't want to implement Simplex myself. The common cases are 2d planes and so I used convex hulls instead of Simplex for those, and then I use an approximation for the uncommon case (all 3 dimensions).<BR/><BR/>I think if you're using this for a real game, you'd probably want to use Simplex. For the quick prototype I am working on, the goal is to figure out whether this is a fun/interesting idea, and the approximation doesn't change that. I'm not even convinced it was worth spending the effort to find the intersections with zero planes, and convex hulls. I should do that after I figure out whether it's fun, and only if it turns to be fun. :)Amithttps://www.blogger.com/profile/12159325271882018300noreply@blogger.comtag:blogger.com,1999:blog-5052387.post-12104865946505656922009-01-20T21:10:00.000-08:002009-01-20T21:10:00.000-08:00Hi Amit,I have spent some time considering this pr...Hi Amit,<BR/>I have spent some time considering this problem since I read your blog yesterday. The idea seems to have great gaming potential. Considering Matthew Skala's comments, I disagree (as you have shown by example) that the pseudo-inverse is appropriate. There is just no way to add constraints such as 'no negative thrust' into linear algebra routines. I think that the simplex method is the way to go to provide quick mappings for your controller. <BR/>The key is to shape the constraints correctly. If we follow Wikipedia then this problem should probably take the form of a 'dual' problem, that is:<BR/><BR/>minimise THRUST<BR/>subject to M*T = F<BR/>and T >= 0<BR/><BR/>The key here is to recognise that the strict equality condition can be broken up into two parts:<BR/>M*T >= F<BR/>-(M*T <= F) i.e. -M*T >= -F<BR/><BR/>By including each of these constraints in the simplex tableau I think you will get the answer.<BR/><BR/>Of course this will take some time to implement unless you can find a simplex code on the webAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-5052387.post-86239292544789033852009-01-19T22:39:00.000-08:002009-01-19T22:39:00.000-08:00I've been considering this exact same concept, how...I've been considering this exact same concept, however I hadn't even started to chew on the specifics. I've been more interested in what implications it could have for gameplay. One thing that interests me is that the structure of the ship can be encoded as a genotype, and then you can apply genetic algorithms to create ships which meet certain parameters. For instance, you could have a game, maybe similar to geometry wars, which could slowly evolve better ships suited to your playing style. Or you could have a space RPG which spans many generations, and the ships in the galaxy evolve as the technology gets better.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5052387.post-86606342498563831702009-01-12T12:30:00.000-08:002009-01-12T12:30:00.000-08:00I took another look at pseudo-inverses and I think...I took another look at pseudo-inverses and I think I can't use them for this problem. For example, in test ship 1, the “best” way to slide left is thruster input [ 0.0625 0.1875 1 0 ]. But the pseudo-inverse tells me that I need [ -0.0625 0.0625 0.5 -0.5 ]. I'm not sure how to impose the non-negative thruster value constraint when using pseudo-inverses. Linear programming seems like a better fit.Amithttps://www.blogger.com/profile/12159325271882018300noreply@blogger.comtag:blogger.com,1999:blog-5052387.post-80039351029743230542009-01-12T10:11:00.000-08:002009-01-12T10:11:00.000-08:00Fusun: looks interesting! Especially the documents...Fusun: looks interesting! Especially the <A HREF="http://graphics.ethz.ch/twiki/bin/view/GameClass/TeamBattleTinker" REL="nofollow">documents page</A>.Amithttps://www.blogger.com/profile/12159325271882018300noreply@blogger.comtag:blogger.com,1999:blog-5052387.post-31394266212627987602009-01-12T06:04:00.000-08:002009-01-12T06:04:00.000-08:00HelloYou might be interested in http://fusun.ch/cm...Hello<BR/><BR/>You might be interested in http://fusun.ch/cms/index.php?id=78.<BR/><BR/>greetsAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-5052387.post-59880445636402538532009-01-11T18:03:00.000-08:002009-01-11T18:03:00.000-08:00Thanks Matthew! I hadn't made the connection to le...Thanks Matthew! I hadn't made the connection to least squares but that makes a lot of sense. My math is quite rusty and least squares hadn't come to mind.<BR/><BR/>Monte Carlo is cheap (~15 lines of code in this case), and it's quite useful for getting a quick sense of what the data looks like, especially when it may not be linear. I started with it and then looked for other approaches. Linear programming seemed like the best fit among the things I looked at. However, I didn't find any Simplex algorithm implementations in Actionscript, and I didn't want to implement it myself, which is why I went looking for something else. I disagree that convex hull will become simplex. Finding a convex hull in 2 dimensions seem quite a bit simpler than the simplex algorithm.<BR/><BR/>Whether you go for the computational approach or the analytical approach depends on how you value computer time and your time. I tend to start with approaches that make the computer do lots of work, and I then look for other approaches if it doesn't work well. My goal here isn't to solve the math or find the optimal solutions; it's to write a quick and dirty spaceship editor demo, to see whether it'd be interesting for a game. If Monte Carlo was satisfactory, I would've stuck with it. I had hoped to finish this project in a few days but it took a bit longer than that, because Monte Carlo didn't work out.Amithttps://www.blogger.com/profile/12159325271882018300noreply@blogger.comtag:blogger.com,1999:blog-5052387.post-86561114493236697602009-01-11T17:25:00.000-08:002009-01-11T17:25:00.000-08:00It seems to me that you're doing an awful lot of c...It seems to me that you're doing an awful lot of computational work to avoid a little bit of mathematics. The basic problem is that you have a matrix M representing the effects of the thrusters, and a vector t representing which thrusters you're going to activate, and you want to find a value of t such that M*t is of a certain form - usually, so that it's axis-aligned (has only one nonzero entry). Is that it?<BR/><BR/>Let's take this in steps. Suppose you had exactly as many thrusters as entries in your vector, so M is square, and you could activate any thruster in any amount, including negative. Then you just invert the matrix and you're *done*. You get a new matrix that contains a vector to produce each thrust pattern of the form [1 0 0], [0 1 0], ... It is possible for some matrices to not produce any answer, if your thrusters are in bad places; those would happen to be matrices of zero determinant, but it doesn't really matter what that means; you can just detect it and tell the designer "your design sucks!"<BR/><BR/>Next step: suppose you have more thrusters, for instance four thrusters and only three dimensions of output. That's kind of nice because it reduces the chance that your thrusters will turn out to be in bad places (you can probably use the extra thruster to break the "tie"); but it means that for any given output there may be multiple thruster activation patterns that all produce that output, so you don't get a unique solution. What people normally do in that kind of case is least-squares: they say "Because I have to choose among many different solutions, I will prefer the one that has the least sum of squares of the variables of my vectors." In your case that's much like saying "Among different thruster activation patterns that achieve the result, I will prefer the solution that minimizes the total amount of thruster fuel spent" which seems like a reasonable way of doing it. That's also easy to do mathematically - none of this Monte Carlo baloney. What you need to do is find the Moore-Penrose matrix inverse, which is one of the pseudo-inverses you were looking at. You can find a formula for computing that in Mathworld; note that the superscript H means "conjugate transpose", which is just transpose because you're not using complex numbers. Feed in your thruster matrix M, you get out an inverse matrix P, with the property that if M*t=x (say x=[0 1 0] or whatever), then P*x is the smallest value of t for which that holds, where "smallest" means "the sum of the squares of the elements is minimized".<BR/><BR/>Presumably the thrusters have a maximum activation level they can handle. The easy thing to do in that case is take one of the previous solutions, and then scale the result so that the most-activated thruster is activated to its maximum. Then you also get a nice result telling you just how much thrust you can get out of the system in each dimension of thrust - and the designer would probably like to know about that.<BR/><BR/>But what if you can't activate your thrusters to a negative degree, and what if they all have different limits on how much they can be activated and you don't want to fake that by scaling the input? Then I think you need to set up a linear programming problem for each dimension. It'll be along the lines of "Minimize total thruster activation (which could be weighted if some are more expensive than others) subject to M*t=[0 1 0], and no thruster activated less than zero, and no thruster activated more than its maximum." You can solve that with the simplex method, but DON'T implement it yourself. Go download a library or something. If you must implement it yourself, go get a copy of Numerical Recipes and follow the recipe; you shouldn't have to understand it to implement it, and you shouldn't try to reinvent it.<BR/><BR/>There are even better ways to solve linear programming problems (interior-point methods), but their advantages don't show up for the problem size you're looking at and so they aren't worth it.<BR/><BR/>I think almost any solution that requires you to test a large number of guesses at random or educated-random, is almost certainly the Wrong Answer. That's heavy computational artillery, suitable for cases where (for instance) there's a complicated nonlinear relationship among the different thrusters so that activating A and B is different from the sum of activating either alone. I don't think that heavy artillery can be justified for a simple linear problem like this one.<BR/><BR/>Note, also, that your "convex hull" solution is going to *be* the simplex method by the time you're done tinkering with it. How do you think the simplex method works? It pretty much exactly comes down to building a polytope representing the constraints (which you're calling the convex hull of the projected hypercube) and then exploring its vertices and surfaces to find the best solution. You're taking a long and unnecessarily complicated route to get to that.Anonymousnoreply@blogger.com