61 lines
21 KiB
HTML
61 lines
21 KiB
HTML
<!DOCTYPE html PUBLIC ""
|
||
"">
|
||
<html><head><meta charset="UTF-8" /><title>Sketch for an algorithm for a pure-functional physics engine</title><link rel="stylesheet" type="text/css" href="css/default.css" /><link rel="stylesheet" type="text/css" href="css/highlight.css" /><script type="text/javascript" src="js/highlight.min.js"></script><script type="text/javascript" src="js/jquery.min.js"></script><script type="text/javascript" src="js/page_effects.js"></script><script>hljs.initHighlightingOnLoad();</script></head><body><div id="header"><h2>Generated by <a href="https://github.com/weavejester/codox">Codox</a></h2><h1><a href="index.html"><span class="project-title"><span class="project-name">The-great-game</span> <span class="project-version">0.1.3</span></span></a></h1></div><div class="sidebar primary"><h3 class="no-link"><span class="inner">Project</span></h3><ul class="index-link"><li class="depth-1"><a href="index.html"><div class="inner">Index</div></a></li></ul><h3 class="no-link"><span class="inner">Topics</span></h3><ul><li class="depth-1"><a href="3D-formats.html"><div class="inner"><span>3D file formats</span></div></a></li><li class="depth-1"><a href="A-generic-planning-algorithm-for-craftworker-npcs.html"><div class="inner"><span>A Generic Planning Algorithm for craftworker NPCs</span></div></a></li><li class="depth-1"><a href="API_Spec.html"><div class="inner"><span>API Spec (unfinished)</span></div></a></li><li class="depth-1"><a href="Appraisal.html"><div class="inner"><span>Appraisal (unfinished)</span></div></a></li><li class="depth-1"><a href="Architecture.html"><div class="inner"><span>Architecture</span></div></a></li><li class="depth-1"><a href="Baking-the-world.html"><div class="inner"><span>Baking the world</span></div></a></li><li class="depth-1"><a href="Building_on_microworld.html"><div class="inner"><span>Building on Microworld</span></div></a></li><li class="depth-1"><a href="Canonical-dictionary.html"><div class="inner"><span>Canonical dictionary for this documentation</span></div></a></li><li class="depth-1"><a href="Division_of_tasks_between_server_and_client.html"><div class="inner"><span>Division of tasks between server and client (unfinished)</span></div></a></li><li class="depth-1 current"><a href="Draft-algorithm-functional-physics-engine.html"><div class="inner"><span>Sketch for an algorithm for a pure-functional physics engine</span></div></a></li><li class="depth-1"><a href="Dynamic-consequences.html"><div class="inner"><span>On the consequences of a dynamic game environment for storytelling</span></div></a></li><li class="depth-1"><a href="Economy.html"><div class="inner"><span>Game world economy (unfinished)</span></div></a></li><li class="depth-1"><a href="Further-reading.html"><div class="inner"><span>Further Reading (and watching)</span></div></a></li><li class="depth-1"><a href="Game_Play.html"><div class="inner"><span>Game Play (unfinished)</span></div></a></li><li class="depth-1"><a href="Genetic-buildings.html"><div class="inner"><span>Genetic Buildings</span></div></a></li><li class="depth-1"><a href="Gossip_scripted_plot_and_Johnny_Silverhand.html"><div class="inner"><span>Gossip, scripted plot, and Johnny Silverhand</span></div></a></li><li class="depth-1"><a href="MVP-Roadmap.html"><div class="inner"><span>Minimum Viable Product, and a road map</span></div></a></li><li class="depth-1"><a href="Modelling_trading_cost_and_risk.html"><div class="inner"><span>Modelling trading cost and risk (unfinished)</span></div></a></li><li class="depth-1"><a href="Naming-of-characters.html"><div class="inner"><span>Naming of Characters</span></div></a></li><li class="depth-1"><a href="Not_my_problem.html"><div class="inner"><span>Not my problem</span></div></a></li><li class="depth-1"><a href="On-dying.html"><div class="inner"><span>On Dying, and Injury</span></div></a></li><li class="depth-1"><a href="On-sex-and-sexual-violence.html"><div class="inner"><span>On Sex, and Sexual Violence, in Games</span></div></a></li><li class="depth-1"><a href="Organic_Quests.html"><div class="inner"><span>Organic Quests</span></div></a></li><li class="depth-1"><a href="Pathmaking.html"><div class="inner"><span>Pathmaking</span></div></a></li><li class="depth-1"><a href="Populating-a-game-world.html"><div class="inner"><span>Populating a game world</span></div></a></li><li class="depth-1"><a href="Pseudo-object-inheritance.html"><div class="inner"><span>Pseudo object inheritance</span></div></a></li><li class="depth-1"><a href="Roadmap.html"><div class="inner"><span>Roadmap (obsolete)</span></div></a></li><li class="depth-1"><a href="Sandbox.html"><div class="inner"><span>Sandbox</span></div></a></li><li class="depth-1"><a href="Selecting_Character.html"><div class="inner"><span>Selecting the Player Character</span></div></a></li><li class="depth-1"><a href="Settling-a-game-world.html"><div class="inner"><span>Settling a game world</span></div></a></li><li class="depth-1"><a href="Sexual-dimorphism.html"><div class="inner"><span>Sexual dimorphism</span></div></a></li><li class="depth-1"><a href="Simulated-genetics.html"><div class="inner"><span>Simulated Genetics</span></div></a></li><li class="depth-1"><a href="Simulation-layers.html"><div class="inner"><span>Simulation layers</span></div></a></li><li class="depth-1"><a href="The-spread-of-knowledge-in-a-large-game-world.html"><div class="inner"><span>The spread of knowledge in a large game world</span></div></a></li><li class="depth-1"><a href="Things_Voice_Interaction_Enables.html"><div class="inner"><span>Things Voice Interaction Enables</span></div></a></li><li class="depth-1"><a href="Towards-a-procedural-animation-api.html"><div class="inner"><span>Towards a procedural animation API</span></div></a></li><li class="depth-1"><a href="Tree-library-evaluation.html"><div class="inner"><span>Tree library evaluation</span></div></a></li><li class="depth-1"><a href="Uncanny_dialogue.html"><div class="inner"><span>The Uncanny Valley, and dynamically generated dialogue</span></div></a></li><li class="depth-1"><a href="Useful-software-libraries.html"><div class="inner"><span>Useful software tools and libraries (open source)</span></div></a></li><li class="depth-1"><a href="Voice-acting-considered-harmful.html"><div class="inner"><span>Voice acting considered harmful</span></div></a></li><li class="depth-1"><a href="Worlds-and-flats.html"><div class="inner"><span>Worlds and flats [obsolete]</span></div></a></li><li class="depth-1"><a href="intro.html"><div class="inner"><span>Introduction to the-great-game</span></div></a></li></ul><h3 class="no-link"><span class="inner">Namespaces</span></h3><ul><li class="depth-1"><div class="no-link"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>cc</span></div></div></li><li class="depth-2"><div class="no-link"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>journeyman</span></div></div></li><li class="depth-3"><div class="no-link"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>the-great-game</span></div></div></li><li class="depth-4"><div class="no-link"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>agent</span></div></div></li><li class="depth-5 branch"><a href="cc.journeyman.the-great-game.agent.agent.html"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>agent</span></div></a></li><li class="depth-5"><a href="cc.journeyman.the-great-game.agent.schedule.html"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>schedule</span></div></a></li><li class="depth-4"><div class="no-link"><div class="inner"><span class="tree" style="top: -83px;"><span class="top" style="height: 92px;"></span><span class="bottom"></span></span><span>buildings</span></div></div></li><li class="depth-5 branch"><a href="cc.journeyman.the-great-game.buildings.module.html"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>module</span></div></a></li><li class="depth-5"><a href="cc.journeyman.the-great-game.buildings.rectangular.html"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>rectangular</span></div></a></li><li class="depth-4"><div class="no-link"><div class="inner"><span class="tree" style="top: -83px;"><span class="top" style="height: 92px;"></span><span class="bottom"></span></span><span>character</span></div></div></li><li class="depth-5"><a href="cc.journeyman.the-great-game.character.sex.html"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>sex</span></div></a></li><li class="depth-4"><div class="no-link"><div class="inner"><span class="tree" style="top: -52px;"><span class="top" style="height: 61px;"></span><span class="bottom"></span></span><span>gossip</span></div></div></li><li class="depth-5 branch"><a href="cc.journeyman.the-great-game.gossip.gossip.html"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>gossip</span></div></a></li><li class="depth-5"><a href="cc.journeyman.the-great-game.gossip.news-items.html"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>news-items</span></div></a></li><li class="depth-4"><div class="no-link"><div class="inner"><span class="tree" style="top: -83px;"><span class="top" style="height: 92px;"></span><span class="bottom"></span></span><span>holdings</span></div></div></li><li class="depth-5"><a href="cc.journeyman.the-great-game.holdings.holding.html"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>holding</span></div></a></li><li class="depth-4 branch"><a href="cc.journeyman.the-great-game.launcher.html"><div class="inner"><span class="tree" style="top: -52px;"><span class="top" style="height: 61px;"></span><span class="bottom"></span></span><span>launcher</span></div></a></li><li class="depth-4"><div class="no-link"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>location</span></div></div></li><li class="depth-5"><a href="cc.journeyman.the-great-game.location.location.html"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>location</span></div></a></li><li class="depth-4"><div class="no-link"><div class="inner"><span class="tree" style="top: -52px;"><span class="top" style="height: 61px;"></span><span class="bottom"></span></span><span>lore</span></div></div></li><li class="depth-5"><a href="cc.journeyman.the-great-game.lore.digester.html"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>digester</span></div></a></li><li class="depth-4"><div class="no-link"><div class="inner"><span class="tree" style="top: -52px;"><span class="top" style="height: 61px;"></span><span class="bottom"></span></span><span>merchants</span></div></div></li><li class="depth-5 branch"><a href="cc.journeyman.the-great-game.merchants.markets.html"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>markets</span></div></a></li><li class="depth-5 branch"><a href="cc.journeyman.the-great-game.merchants.merchant-utils.html"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>merchant-utils</span></div></a></li><li class="depth-5 branch"><a href="cc.journeyman.the-great-game.merchants.merchants.html"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>merchants</span></div></a></li><li class="depth-5 branch"><a href="cc.journeyman.the-great-game.merchants.planning.html"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>planning</span></div></a></li><li class="depth-5"><div class="no-link"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>strategies</span></div></div></li><li class="depth-6"><a href="cc.journeyman.the-great-game.merchants.strategies.simple.html"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>simple</span></div></a></li><li class="depth-4"><div class="no-link"><div class="inner"><span class="tree" style="top: -207px;"><span class="top" style="height: 216px;"></span><span class="bottom"></span></span><span>objects</span></div></div></li><li class="depth-5 branch"><a href="cc.journeyman.the-great-game.objects.character.html"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>character</span></div></a></li><li class="depth-5 branch"><a href="cc.journeyman.the-great-game.objects.container.html"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>container</span></div></a></li><li class="depth-5"><a href="cc.journeyman.the-great-game.objects.game-object.html"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>game-object</span></div></a></li><li class="depth-4 branch"><a href="cc.journeyman.the-great-game.playroom.html"><div class="inner"><span class="tree" style="top: -114px;"><span class="top" style="height: 123px;"></span><span class="bottom"></span></span><span>playroom</span></div></a></li><li class="depth-4"><div class="no-link"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>proving</span></div></div></li><li class="depth-5 branch"><a href="cc.journeyman.the-great-game.proving.core.html"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>core</span></div></a></li><li class="depth-5"><a href="cc.journeyman.the-great-game.proving.sketches.html"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>sketches</span></div></a></li><li class="depth-4 branch"><a href="cc.journeyman.the-great-game.time.html"><div class="inner"><span class="tree" style="top: -83px;"><span class="top" style="height: 92px;"></span><span class="bottom"></span></span><span>time</span></div></a></li><li class="depth-4 branch"><a href="cc.journeyman.the-great-game.utils.html"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>utils</span></div></a></li><li class="depth-4"><div class="no-link"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>world</span></div></div></li><li class="depth-5 branch"><a href="cc.journeyman.the-great-game.world.heightmap.html"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>heightmap</span></div></a></li><li class="depth-5 branch"><a href="cc.journeyman.the-great-game.world.location.html"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>location</span></div></a></li><li class="depth-5 branch"><a href="cc.journeyman.the-great-game.world.mw.html"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>mw</span></div></a></li><li class="depth-5 branch"><a href="cc.journeyman.the-great-game.world.routes.html"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>routes</span></div></a></li><li class="depth-5"><a href="cc.journeyman.the-great-game.world.world.html"><div class="inner"><span class="tree"><span class="top"></span><span class="bottom"></span></span><span>world</span></div></a></li></ul></div><div class="document" id="content"><div class="doc"><div class="markdown"><h1><a href="#sketch-for-an-algorithm-for-a-pure-functional-physics-engine" id="sketch-for-an-algorithm-for-a-pure-functional-physics-engine"></a>Sketch for an algorithm for a pure-functional physics engine</h1>
|
||
<p>What a physics engine needs to do is, at each step</p>
|
||
<ol>
|
||
<li>Take a collection of bodies;</li>
|
||
<li>For every pair of bodies, compute the change in velocity of each consequent on their interaction;</li>
|
||
<li>For each body, merge the changes in velocity found in step two into one change in velocity;</li>
|
||
<li>For each body, update the position of the body.</li>
|
||
</ol>
|
||
<p>Now, in practice, for simulations in a terrestrial environment, the largest interaction any of the other bodies constantly has is that with the planet in the form of gravity; and, gravity of the planet is so much greater than that of any other body in the environment that the gravitational attraction of the other bodies to each other can be ignored; and finally, the difference in mass between the planet and any other of the bodies is such that changes to the velocity of the planet can effectively ignored. So we can modify that to</p>
|
||
<ol>
|
||
<li>Take a collection of bodies excepting the planet;</li>
|
||
<li>For each pair of bodies <em>including the planet</em>, compute as vectors changes in velocity consequent on collisions between them (but the change in velocity of the planet will always be deemed to be zero);</li>
|
||
<li>For each body, compute as a vector the change in velocity consequent on the gravitational attraction of the planet;</li>
|
||
<li>For each body, compute as a vector the change in velocity consequent on the friction of the medium through which it is moving;</li>
|
||
<li>For each body, merge the vectors computed above with the body’s initial velocity to produce a new velocity vector.</li>
|
||
</ol>
|
||
<p>OK so far?</p>
|
||
<p>So that looks something like</p>
|
||
<pre><code class="language-clojure">(require [clojure.math.combinatorics :refer [combinations]])
|
||
|
||
(defn physics-tick
|
||
"Compute the change of velocity to each of these `objects` in one tick."
|
||
[objects]
|
||
(pmap merge-vectors
|
||
(pmap apply-friction
|
||
(pmap apply-gravity
|
||
(merge-collisions
|
||
(remove nil? (pmap collide (combinations objects 2)))
|
||
objects
|
||
)
|
||
)
|
||
)
|
||
)
|
||
</code></pre>
|
||
<p>Where:</p>
|
||
<p><code>collide</code> is a function which takes two objects, and if those objects are not in collision at this physics step, returns nil; if they are in collision, returns a pair of two objects like those passed, except that each has a 3d vector object added to its <code>:deltas</code> property.</p>
|
||
<p>Thus, <code>(pmap collide (combinations objects 2))</code> will return a flat list with potentially many copies of the same object, each with different deltas; but it will not contain any copies of any objects which weren’t in collision at all.</p>
|
||
<p>Consequently, <code>merge-collisions</code> must, for every key in the objects, collect each of the copies of that object from the collisions and from the original objects list, and, for each key, return one object identical to the original object except that its <code>:deltas</code> property is a concatentation of the <code>:deltas</code> properties of each of the copies:</p>
|
||
<pre><code class="language-clojure">(defn merge-collisions
|
||
[collision-pairs objects]
|
||
(pmap
|
||
#(assoc (first %) :deltas (apply concat (map :deltas %)))
|
||
(partition-by :id
|
||
(sort-by :id
|
||
(concat
|
||
(flatten collision-pairs)
|
||
objects)))))
|
||
</code></pre>
|
||
<p><code>apply-gravity</code> is simply a function which returns an object like the object passed to it, but with a constant acceleration-under-gravity vector added to its <code>:deltas</code> property;</p>
|
||
<p><code>apply-friction</code> is a fairly simple function which computes a friction vector in the direction opposite to the current velocity object passed to it, and returns an object like the object passed but with that fricton vector added to its <code>:deltas</code> property;</p>
|
||
<p>and finally,</p>
|
||
<p><code>merge-vectors</code> is a function which takes an object with a <code>:position</code>, a <code>:velocity</code>, and a (possibly empty) sequence of <code>:deltas</code>, computes a new <code>:velocity</code> vector produced by applying each of the deltas in turn to the velocity, and a new <code>:position</code> produced by adding that new <code>:velocity</code> (times the duration of the tick) to the old position. It returns an object like the object passed but with the new <code>:position</code> and <code>:velocity</code> values. I’m too tired to confidently state the maths of that now, but I’m confident it’s simple.</p>
|
||
<p>Which means, in fact, that the whole thing is simple (modulo the <code>collide</code> function, which I haven’t even sketched above, and which is somewhat dependent on the models involved).</p>
|
||
<p>Note that, however</p>
|
||
<ol>
|
||
<li>At this stage it considers only velocity deltas, not spin deltas; it ought to do that too, but, although that adds extra operations, it doesn’t add complexity; and</li>
|
||
<li>This currently considers only rigid bodies. Soft bodies are a significantly more complex problem.</li>
|
||
</ol>
|
||
</div></div></div></body></html> |