One way to stop a 2D spaceship as fast as possible.

For a quite a while, I have wanted to try and create simple touch based interface for a 2D spaceship game. I want to allow the player to simply drag anywhere on the screen, and the spaceship moves to that position and direction in an efficient manner. Ideally the most efficient manner.

Spaceships in 2D games usually have one main engine that allows forward thrust, and some that allow rotation around the ships center of mass.

Moving from point A to B efficiently (in minimal time) is not trivial with such constraints, as changes to direction and thrust may have huge consequences for later possible movements due to inertia.

So instead of looking at the full A to B problem immediately, I wanted to look at something simpler first, namely to go from having velocity \(v_0\) and pointing in direction \(\theta_0\) to have 0 velocity as fast as possible.

The idea I use originally came from talking to a colleague, but something very similar sounding is mentioned in planning algorithms, though examples always seems to involve driftless systems. Anyway, my current approach involves these known quantities and assumptions:

  • \(a\) – Acceleration – The ship can only accelerate by a constant amount, and acceleration turns on and off instantly. Velocity and acceleration are related by \(v=at\).
  • \(s\) – Turn speed – rotating the ship requires no acceleration, and the ship has constant rotation rate along the unit circle when turning.
  • \(\theta_0\) – Initial orientation on unit circle.
  • \(v_0\) – Initial velocity

These quantities allow me to find a legal, but very suboptimal way to stop. It simply involves to turn the ship to face its velocity vector, and then accelerate until it stops. Both the time needed to turn the ship \(t_a\) and the time \(t_m\) needed to turn and reverse the velocity are easy to calculate.

Turn until facing velocity and initiate burn at time \(t_a\). At \(t_m\) the ship has velocity 0.

It is also easy to see that this is suboptimal, it would clearly be faster, to start burning some time before the turn is fully completed, but the question is when to start the burn.

To allow for this freedom in my model, I therefore introduce a third time variable \(t_s\). \(t_s\) is the time to start turning and accelerating at the same time. \(t_a\) now becomes the time when I stop turning and only accelerate.

Turn and initiate burn after \(t_s\) time, at \(t_a\) time only accelerate. At \(t_m\) the ship has velocity 0.

Given these intervals, two integrals describe how the velocity will change when \(t_s\), \(t_a\) and \(t_m\) vary.

$$ v_x = \int_{t_s}^{t_a} a\cos(\theta_0+st)dt + \int_{t_a}^{t_m} a\cos(\theta_0+st_a)dt $$

$$ v_y = \int_{t_a}^{t_a} a\sin(\theta_0+st)dt + \int_{t_a}^{t_m} a\sin(\theta_0+st_a)dt $$

This gives two constraints, that must hold for all solutions of this kind.

$$ 0 = v_{0x} + \int_{t_s}^{t_a} a\cos(\theta_0+st)dt + \int_{t_a}^{t_m} a\cos(\theta_0+st_a)dt $$

$$ 0 = v_{0y} + \int_{t_s}^{t_a} a\sin(\theta_0+st)dt + \int_{t_a}^{t_m} a\sin(\theta_0+st_a)dt $$

The most efficient solution to this problem, is the \(t_s\), \(t_a\) and \(t_m\) triplet with the lowest value for \(t_m\).

This information allows me to formulate this as a optimization problem.

Since I want to minimise \(t_m\), the objective function simply becomes \({t_m}^2\).

This is subject to the two equality constraints given.

Since the objective and constraints are non-linear, I plug i into Optizelle which is a framework for solving non-linear optimization problems.

The implementation can be found on github, it uses autograd, to calculate derivatives and hessians. This is an incredible time saver since calculating 9 combinations of partial derivatives would have been a major pain, not to mention having to recalculate them whenever I did something wrong.

Running the program with inputs \(a=2.0\), \(\theta_0=0\), \(v_0=[2,0]\) and \(s=\frac{\pi}{2}\) returns:

running-optizelle

The optimal point vector contains the values for \(t_s\),\(t_a\) and \(t_m\). This means that for a ship with the given input, it should start turning immediately, then start the burn after approximately 1.43 seconds, stop turning and only accelerate at 2.43 and finally be at rest after 2.57 seconds, approximately 0.43 seconds faster then the naive version.

To test the result, I implemented a quick and dirty javascript program that simulates these choices and renders to a canvas:

Sometimes the ships end up drifting a bit after the simulation has finished. This is due to the discrete nature of the simulation not perfectly emulating the continuous solution (I do not integrate rotation analytically in the simulation). This could also have been a problem if I applied this style of planning to a game that did the same, from the simulation above it looks negligible though, which is great!

I am very happy with this result, it seems like it could work for the larger problem as well. The next step I’ll try, is to tackle some specific cases of moving from point A to B efficiently. For those cases there will be many more time variables involved, and possibly many constellations of safe initial starting points as well as possible freedoms to introduce in the model. It will be interesting to see how that works out.

Solving Get1000 continued…

In one of my previous posts, I laid out a plan to solve the Get 1000 game. It turns out that plan was wrong.

My expectiminimax based solution works well for a game with random elements and perfect information, but it is not very useful for a game with imperfect information. Get1000 is played simultaneously by the players, and the opponents choices are hidden until the end of the game.

This meant I had to go back to find a new strategy for solving the game. I decided to try and find the correct brute force way first, and then see if that could be made faster in some way.

Exploring brute force

A solution to the game involves finding a Nash equilibrium from all the pure strategies of the game. A brute force solution could be done by creating a matrix where all pure strategies are pitted against all the other pure strategies.

The full payoff matrix needed for a normal form brute force solution.

A strategy here refers to a function S \rightarrow Pl which given any game state S gives a Get1000 placement Pl . Since there are at most 211248 - 27648\cdot3 = 128304 states in the game, each which at most have 3 choices, there is an upper bound of M = 3^{128304} unique pure strategies.

This is of course not that helpful, since a 3^{128304}\times3^{128304} matrix is is enormous, and for each cell in the matrix all possible 6^9 games would have to be played to find the payoff P for the pure strategy pairs. On top of that, the best mixed strategy would then have to be calculated.

Subgame perfection and backwards induction

Modeling this in normal form as above seemed to get me nowhere, I therefore turned to extensive form, and something called subgame-perfect nash equilibria, and backwards induction. In the normal form solution I need to look at all possible strategies. Using subgame perfection, I hoped to get away with only looking at a very small subset.

While this sounds straighforward in theory, I found it quite hard to figure out where my information sets are, and whether I could consider each choice node in Get1000 a subgame. After struggling for a while, I ended up with an extensive form structure looking like this. Players are P1 and P2, and “move by nature” is the dice roll.

Extensive form of a game with the same structure as Get1000. As players do their choices, the information sets get larger and larger. Since the “moves by nature” are known by all, they do not increase the information sets.

This structure means that only the roots of the tree are subgames, since all other nodes are part of larger information sets.

Attempting backwards induction

The above structure means that it is not practical to use subgame perfection and backwards induction to solve the game, but taking inspiration from it could still be useful to get a good strategy.

The algorithm for subgame perfection goes like this:

  1. Consider the final subgames (those with no further subgames), pick a Nash equilibrium as solution there.
  2. When considering the next subgames up the tree, the payoffs in the subgames already considered are used to create the payoff matrix.
  3. Iterate step 2 until the root node of the extensive form tree is reached.

To get something working, I pretend that the other player is at the same state as me always. This means I can need only focus on the branches below that state. To keep memory in check i also recalculated payoffs instead of storing the result for each combination of states and games. The final algorithm I ended up with works like this:

  1. Consider the final subgames and pick a Nash equilibrium as solution.
  2. When looking at subgames higher up the tree, I use the choices (not payoffs) computed in 1, and use those choices to play out the game. Then I compare end results to get the payoff matrix for that subgame.
  3. As before, I iterate step 2 until I reach the root node.

This seems intuitively pretty reasonable.

Experimental results

The above method gives me a strategy that partly takes the imperfect information nature of the game into account. At many states it detected mixed strategies that had much higher payoffs compared to the pure versions. The strategies smashes all my previous best strategies by winning 1.75% more games.

The mixed strategy seems to play even more aggressively for results close to a 1000, and allowing heavy overshoot.

At this point, I was not really sure how to approach the game in a better way. In fact I was pretty ready to admin defeat for quite some time. Of course, immediately after i wrote that, I found this thesis, and this report.

Lots of new concepts to learn!

Learning what WebRTC SDP a=setup values mean

My very hacky webRTC datachannel implementation stopped working a while back, and I could not figure out why.

The way it behaved was hard to understand. Signaling worked as expected, and I received a STUN on the correct port and responded to that. Both Firefox and Chrome reported the response as fine, and kept sending new STUN heartbeats at the normal rate, but no DTLS handshake was initiated.

Initially i thought something was really broken with my STUN/DTLS multiplexing, but I soon figured out that it behaved as expected.

This meant I was probably sending some wrong parameter during signaling, but what?

This is the SDP of my answer to the given offer from the browser.

v=0
o=- 1234567 2 IN IP4 192.168.1.158
s=-
t=0 0
a=group:BUNDLE data
a=msid-semantic: WMS
m=application 51410 DTLS/SCTP 5000
c=IN IP4 192.168.1.158
a=candidate:1 1 udp 2113937151 192.168.1.158 51410 typ host
a=ice-ufrag:4a64ca2b
a=ice-pwd:a26b6a15a8b4d35db21692d37906840a
a=ice-options:trickle
a=fingerprint:sha-256 C9:E2:48:09:47:C8:CC:B3:51:A8:A1:C5:AA:63:51:26:50:1D:FF:76:AE:EF:CB:31:0C:E7:41:21:5A:11:FA:D5
a=setup:actpass
a=mid:data
a=sctpmap:5000 webrtc-datachannel 1024

SDPs are confusing to me, and figuring out what stuff really means in WebRTC context is a lesson in reading RFCs with a microscope, while always wondering if this is the correct RFC for this concrete problem.

Suddenly it dawned on me that it seemed like both sides were waiting for the other side to initiate the DTLS handshake.

It turned out this was the problem:

a=setup:actpass

Since i responded with actpass in my answer SDP, the browser could not know if it wanted to initiate DTLS or not, and I guess it defaults to passive now. actpass is an illegal response value according to this RFC, and defaulting to passive is probably more correct then active. Setting a=setup:passive fixed the issue, since that tells the browser to be the initiating party.

Good times.

Starting Marathon Infinity in vidmaster mode on linux

A few days ago I installed Marathon Infinity for some multiplayer games. I wanted to practice a bit first, but sadly it is not possible to start a multiplayer game alone, so the only way to get some fast action is to play singleplayer in vidmaster mode.

This resulted in another problem. I could not figure out the button combination to trigger vidmaster mode on linux. After some minutes searching I was quite frustrated, but thankfully the Aleph One source is available, and the source revealed:


static bool has_cheat_modifiers(void)
{
	SDL_Keymod m = SDL_GetModState();
#if (defined(__APPLE__) && defined(__MACH__))
	return ((m & KMOD_SHIFT) && (m & KMOD_CTRL)) || ((m & KMOD_ALT) && (m & KMOD_GUI));
#else
	return (m & KMOD_SHIFT) && (m & KMOD_CTRL) && !(m & KMOD_ALT) && !(m & KMOD_GUI);
#endif
}

Based on this, vidmaster mode on linux is activated by holding SHIFT and CTRL while clicking BEGIN NEW GAME, and sure enough:

Pledging hard here

Sci-fi book review

Last year i got a kindle for Christmas. This is a review of all the science-fiction books it contains at this moment, with the exception of Robert A. Heinlein’s Starship Troopers and Joe Haldeman’s Forever War (This post is already way too long and these are pretty well known books). For each book/series I’ll try and give a very short description followed by my thoughts.

The TLDR; these books provide a balanced diet ;-).

If you only have time to read one book, read Ann Leckie’s Ancillary Justice.

Not just the TLDR

These are the books I have read in no particular order:

  • Jason M. Hough – The dire earth cycle

    Someone (not humans) has built a space elevator in Darwin Australia. After some years a disease either kills or turns everyone into zombies except in a safe zone around the space elevator.

    The dire earth cycle is a quick read, and an entertaining one. It was way better then I expected. Sometimes it goes into these very long and meaningless action sequences; you can safely skim those.

  • Ann Leckie – Ancillary Justice

    The story follows an AI fragment from the Radch starship Justice of Toren‍. This fragment is all that is left after the starship was destroyed. While Justice of Toren plans revenge on its destructor, we get flashbacks to its previous life as a ship AI in service of the Radch.

    I do not have enough positive things to say about this book. The main character is extremely well written. The pace is good. I’m really looking forward to the third book in the series. If you are going to read it, do not read about the book first, it might spoil some parts which it is worth not to have spoiled.

  • Ann Leckie – Ancillary Sword

    Not as good as the first book, but still great.

  • Kim Stanley Robinson – Mars trilogy

    We follow the first 100 colonists of Mars as they colonize and attempt to terraform mars.

    Of all the books on this list, this series really stands out as different. Most of the time the book follows the everyday work of the 100 colonists as they work, scheme, and daydream. There is no good and evil here. While the political views of the author shines through it never feels like preaching. On the negative side the book has travel descriptions that makes the travel descriptions in Lord of the Rings feel like short strolls. Still the series is one of my favourites.

  • Kim Stanley Robinson – Icehenge

    Someone made a huge monument on pluto, why?

    Set in the same universe as the Mars Trilogy. It follows some of the same style, but the pace was a bit faster. The story has a lot of references to the Mars Trilogy, so it might be better to read that first.

  • Kim Stanley Robinson – The Memory of Whiteness

    We follow the master of ‘Holywelkins Orchestra’ on its tour from the outer to the inner solar system. On the way it becomes clear that the orchestra is immensely powerful. And also some cult controls Mercury and therefore the power distribution to the rest of the solar system.

    That probably made no sense. The book seemed to make sense (and was enjoyable) for the first half, then it stopped making sense. Too weird for me.

  • Vernor Vinge – Marooned in Realtime

    In the future humanity figures out a way to suspend time in bobbles (allowing time travel to the future). The main character is unwillingly suspended and returns to a worlds where human civilisation is gone and only a few humans (bobblers from varying degrees of civilisation) are left, including his suspender.

    Vernor Vinge does a very good job with his concepts. He introduces the rules of his universe and then follows them. This book is short and to the point. No infinite traveling on Mars; no zombies. A very enjoyable read.

  • Vernor Vinge – The Peace War

    In this book we follow the world just after the bobbles (see previous book) were invented, and are discovered to be finite stasis fields.

    I enjoyed Marooned in realtime more, but it is well worth reading.

  • Vernor Vinge – A fire upon the deep

    Our galaxy is divided in zones that allow different sorts of intelligence and technology to arise and be used. We follow humanity which has traveled to the Beyond where AI and FTL travel is possible ( Earth is located in the Slow zone where these things are not possible). The outer zone is called the Transcend, where the beings are basically gods. Trying to enter the Transcend from the Beyond, some humans fall into a trap and release a being which threatens all life in the beyond. A ship escapes the trap with information on how to counter the being, but strands on a world with wolf like creatures with group-minds.

    Very interesting concepts and quite well executed. A lot of the book is written from the perspective of packs which are group-minds of several individual wolfs. For me these chapters were initially hard to follow, since I do not think it was explicitly explained that these were group-minds.

  • Vernor Vinge – A Deepness in the Sky

    This book takes place in the Slow zone (no FTL). Two human space traveling civilisations discover a world which orbits around a star that is only active for one year every 250 years. On this world lives a species of spiders which will soon reach space. The two human civilisations clash over the right to trade with/enslave this species. The clash leaves them both crippled though, and they need to cooperate while waiting for the star to wake and get new resources from the Spiders.

    I liked this book more then A fire upon the deep. There are some parts about layered complex software growing over time (they have very old software on their spaceships, like if glibc would be used several thousand years in the future), which to an enterprise programmer almost feels way too believable.

  • Christian Cantrell – Containment

    Arik must figure out artificial photosynthesis, or his not yet born child will cause the colony he belongs to on Venus to eventually run out of of oxygen.

    I was really surprised by this book. It has some great plot twists, and was very difficult to put down. I am currently in the process of reading the sequel Equinox. These books both has very brief encounters with zombies. Thankfully very short, but they would be better without.

  • Mike Resnick – Seven Views of Olduvai Gorge

    Alien archeologists come to earth to excavate after humanity is long gone.

    Short and very enjoyable read. Just read it.

  • Jon Scalzi – Old Man’s War universe

    Humanity has reached space and has settled several planets, but it is in conflict with several alien species over territory. This conflict is handled by the CDF (Colonial Defense Forces) who is in constant need of new soldier on a very deadly battlefield. These soldiers are recruited from an overpopulated Earth where the CDF controls the only access point to space. To keep the stream of soldiers the CDF largely keeps Earth in the dark of their technology and stategies. The series explores the conflicts with the alien and the political struggles resulting from this situation from the perspective of the soldiers and political figures caught in it.

    The overall quality of this series is great. If you liked Starship Troopers you will most likely like this. I do not think any single book of the series is as good as Ancillary Justice, but I read every new book in the series.

  • Conclusion

    If you only have time to read one book, you can not go wrong with Ann Leckie’s Ancillary Justice.

    Polar bears, not zombies!

    Scape – a very ninja scripting language


    I made a small scripting language that runs in the browser. It is very ninja. To see the ninja, first open Javascript console and write:

    function recur() {recur()};recur();
    

    Hopefully it blew the stack. Then type this into the Scape REPL:

    def recur() recur(); recur();
    

    When you are convinced it will infinitely loop without blowing the stack, hit ctrl-c to stop further processing.

    Rincewinds rave, that is black magic! Also called tail call elimination. Scape code is not evaluated by snarfing functions from Javascript (JS functions do not have tail call elimination before ECMAScript 6), but instead is compiled to its own set of instructions, which are then run on a stack machine (running in the Javascript VM). During parsing Scape functions are checked for whether they can use tail call elimination. If they can, they get different instructions that reuse the existing stack frame.

    More magic

    Scape has forward mode automatic differentiation as a language feature. Automatic differentiation allows you to compute the derivative of a function, without having to define the derivative explicitly.

    Without automatic differentiation, this would be the way to compute the partial derivative of the function f(x,y) =  x^{2}y^{2} for x and y:

    def fun(x,y) * (* x x) (* y y);
    def diff_fun(x,y) [* (* 2 x) (* y y),* (* 2 y) (* x x)];
    diff_fun(4,5);
    [200, 160]
    

    With automatic differentiation in Scape, this is how it is done:

    def fun(x,y) * (* x x) (* y y);
    diff(fun(4,5));
    [200, 160]
    

    This is very useful for a number of numerical methods involving derivatives. The feature is currently experimental, it might interact with non-double types in funky ways.

    Wai?

    Mostly just for fun. I also started toying with the idea to make a safe scripting language for use in networked games. A language and runtime that would allow the player to define custom logic during gameplay without being able to ruin the experience for other players.

    A dream would be a personalized Starcraft where it is you and your custom control scripts versus the other player and his scripts.

    I hope to create a simple real time multiplayer game to show how I imagine it working. For now, playing with the Scape REPL is the only way to try the language.

    Sayōnara

    Artifact-1.0.2

    Today I released Artifact-1.0.2 after finally getting my ass around to create a close to fully automated build script for Mac OS X (a topic for another blog post). The full changelog is listed below, but I instead recommend you go get it and try it!

    mech-sec-new
    New second orb graphics

    Changelog:

    1. Added full screen and resolution management in game.
    2. Removed splash screen.
    3. Adjusted difficulties and added new names (Apprentice, Journeyman, Master).
    4. Added additional fire button, allowing better control using a touch-pad.
    5. Redesigned second orb with additional graphics and new behavior.

    More in detail:

    1. The splash screen in Artifact was unnecessary and the only issue keeping me from removing it was having in-game window and resolution management.
    2. See above.
    3. The Normal and Hard game difficulties were hardly different in version 1.0.0, while the Not sane difficulty was extremely hard. Now the Apprentice difficulty is much easier then the old Normal, Journeyman is similar to the old Normal, while Master is slightly easier then the old Not Sane difficulty. The change was mainly done to make the initial difficulty easier for new players.
    4. On a touch-pad moving the mouse and clicking might interfere with each other, so I added an alternate fire welder button for those who might prefer that.
    5. The Second orb was very hard to predict and its mechanic felt wrong. The new version is cooler , and most of the time way easier to predict. It also has a slight comeback factor, which is nice in this cutthroat game.

    Superb toy!

    This toy is incredible. It is reasonably easy to construct things, while still providing a challenge once you get the basics. It is suitable for nearly all ages. It says 3+ but if you remove the smaller parts it is suitable for much younger children even though they might just enjoy tearing down your constructs. The absurd thing is that when they do, you wont hesitate to make another one, since building these are way too much fun.

    WEDGiTS
    WEDGiTS

     

    Adding javascript functionality to WordPress posts

    Adding your own javascript implementation to posts in your wordpress blog is slightly more difficult then one might think. The difficulties stem from the way WordPress editors format html and javascript in posts. If you just type refer to .js files and then add it by adding some inline script tags, WP will mangle the inline js.

    The easiest way to do it is to add the files normally:

    <script scr="/path-to-script/cool.js"></script>

    Then refer to it using inline script like this:

    <script><!--
    //Use script here
    --></script>

    This can of course also be done in several other ways, using WP functionality, but those are all not very satisfactory in my opinion, and they do not fit JS that will only be used in a single post.