Code center > Suggestions

Hyperspeed Mode

<< < (2/15) > >>

Numsgil:

--- Quote from: Houshalter ---
--- Quote ---Physics is a really really studied problem. Because it's a billion dollar industry for video games and other things.
--- End quote ---
But most video games run fast enough to work in real time and could probably run faster. Darwinbots is a bunch of circles moving past each other, sometimes running into each other or shooting at each other. Any chance any of that can be applyed to them?

--- End quote ---

Video games can't really run faster.  Trust me, games like Uncharted 2 are literally pushing the hardware as hard as it can be pushed.  Games might also look complex, but under the hood it's collisions between capsules and triangles and other primitives like that.  Not at all different from Darwinbots' collisions between circles.  So there's a lot of literature and resources available on physics that I've digested and will use for DB3, and even DB2 isn't doing it that inefficiently.


--- Quote ---
--- Quote ---The exception to that is that physics situations from one frame to the next are usually very similar. So most physics engines cache that information across frames (temporal locality).
--- End quote ---
Exactly. The bots can change course frequently but things like shots just move in a straight line. You know their direction and speed so you can accuratley calculate where they will be in x cycles. If a shot is drifting through space with no bots around it then why bother calculting its position every cycle. The thing is there are exceptions to this rule, like what if the user places a bot right in front of the shot, what if a teleporter moves another bot into its way. So hard coding all these individual short cuts, including their exeptions gets complicated.  A GA could find the optimal way to handle it. Remember where evolving an algorithm to create these heuristics, not the actual heuristics themselves. That way different simulations will have different heuristics. A large sim could easily do the shot thing i just mentioned because most shots just drift into space anyway, but a small sim where the shots are constantly moving and most hit bots anyways, could use a different heuristic to calculate the shots correctly, simmilar to but not the same as the first one. As i understand it, you've already put in shortcuts like these to speed up sim size in larger sims.

--- Quote ---This isn't something genetic algorithms are good at. The core of most physics engines is a "constraint solver", which is basically doing a sparse matrix inversion. Which is a well studied problem with very well studied answers. Genetic algorithms are more for situations where the problem is quite complex and there's a lot of data and a lot of noise in the data and you want to find a good best guess. That just doesn't describe physics.
--- End quote ---
Youre right. DB is essentially a GA, but without a fitness function. How many zerobots have evolved into perfect bots with intelligence and learning. However the problem is kind of complex as you mentioned and noise doesn't make a difference so long as the evolved program is errorless (wich is it's first fitness function.) Given enough time, it could come up with a very good system of speeding up db that a human never would've thought of, maybe couldn't even understand. Thats the beauty of GAs.

--- End quote ---

It's precisely because you can describe the position of a shot at cycle X that makes it inefficient for a genetic algorithm.  Collision detection resolves basically down to numerical root finding, which is a problem with well understood solutions.  Collision response is sparse linear algebra, which also has well studied solutions.  If there are any shortcuts, they come from making simplifying assumptions about the underlying math (eg: use a quadratic approximation to a sinusoidal curve).  So underlying all the physics is just a lot of algebra, calculus, and linear algebra, which humans and machines already know how to do very well.  All these problems have well established algorithms to find a solution.

Compare this with something like learning to fly a 747.  There are thousands of knobs and readouts, and it takes a human years of study to be able to use these to fly a plane.  There isn't even a rote solution to some problems, because they haven't ever come up before.  So being a pilot takes a strong combination of improvisation and experience.  It's these sorts of problems that genetic algorithms or neural nets are better at than algorithmic/rule-based approaches.  Genetic algorithms can sort of figure out how to improvise.

Last, just to clarify any confusion, the hashlife you linked to isn't using any genetic algorithms or anything to speed up the game of life.  It's using algorithmic approaches (specifically caching oft used patterns) to speed it up.

Houshalter:

--- Quote ---Video games can't really run faster. Trust me, games like Uncharted 2 are literally pushing the hardware as hard as it can be pushed. Games might also look complex, but under the hood it's collisions between capsules and triangles and other primitives like that. Not at all different from Darwinbots' collisions between circles. So there's a lot of literature and resources available on physics that I've digested and will use for DB3, and even DB2 isn't doing it that inefficiently.
--- End quote ---
I believe you. How many times have you played a game and half of your characters body gets stuck in a wall. Or worse the ai gets stuck in a wall and can shoot at you but you can't shoot at them. Actually thats kind of rarer now because most games are tested thouroughly before theyre released. Still happens to me sometimes though.

--- Quote ---It's precisely because you can describe the position of a shot at cycle X that makes it inefficient for a genetic algorithm. Collision detection resolves basically down to numerical root finding, which is a problem with well understood solutions. Collision response is sparse linear algebra, which also has well studied solutions. If there are any shortcuts, they come from making simplifying assumptions about the underlying math (eg: use a quadratic approximation to a sinusoidal curve). So underlying all the physics is just a lot of algebra, calculus, and linear algebra, which humans and machines already know how to do very well. All these problems have well established algorithms to find a solution.
--- End quote ---
What i meant by my example was that, why calculate the position of the shot every cycle when you only need to calculate it once, to see if it will colide with an object (of course this is if the graphics are turned off, otherwise you might still have to calculate it every cycle.) This may, however use more computing resources calculating the position of every object to see if its in or could be in the path of the shot, especially if the sim is full of objects. Anyways there may be algebraic solutions but you can still make a program go faster. What i mean is a + a = 2a. But which one runs faster on the computer. Also this doesn't nessacarily apply to soley the phyics in the game, other proccesses in db eat up resources to, like dna execution. Allright i might not be making sense here. Do you get what im trying to say, just cause a problem has one simplified algebraic solution, doesn't mean theres only way to run it on a computer and get the same results. Anyway this whole thing is prety much just hypothetical anyways.


--- Quote ---Last, just to clarify any confusion, the hashlife you linked to isn't using any genetic algorithms or anything to speed up the game of life. It's using algorithmic approaches (specifically caching oft used patterns) to speed it up.
--- End quote ---
Yes i figured it wasn't a GA, not that i understand it. I'll go back to the site and read some more about it.

jknilinux:
Is it possible to use a cellular automata as a basis for DB physics? See here and here .

Digital physics seems to bear a close resemblance to cellular automata, and as such should be easy to use the hashlife algorithm on...

I have always wanted to find a way to combine DB with cellular automata...

Houshalter:
You can make a universal turing machine in conways game and you can program any immaginable program on a turing machine so, theoretically you could program the whole of db into a turing program and then program that into a game of life seed. Then you can use hashlife on it. I just wonder if you would actually gain any speed doing that. Even if you could, have you ever tried to program anything into a turing machine. Have you ever created super complex patterns in the game of life. Now try combining both of them  .

jknilinux:
What I mean is using DB to simulate a cellular automata, not the other way around...
And the CA would only be for physics simulations.

Navigation

[0] Message Index

[#] Next page

[*] Previous page