KSP Lalande log 3

// 60101 Mun autolander program test

Second iteration of autoland script for kOS. Script waits until over target within 10 degrees, then executes retro burn followed by pitch control to track onto landing target. Multiple failed iterations. Current script does not auto-throttle for descent phase, but managed to crash directly into the landing target. Success. Image 1, 2, 3, 4.

Full script:

// kOS semi-autoland. (c) 2016 Aaron Lahman
// Source license: http://www.wtfpl.net/txt/copying/

// this script assumes a targeted vessel/object for landing, and the
// ship is already on a flight path over the target.

clearscreen.
print "mode: flyby".

// phase 1: target acquisition
lock shipFuturePosition to ship:position + (ship:velocity:surface * 5.0).
lock dTarget to (shipFuturePosition - target:position).
wait until VECTORANGLE(target:up:vector, dTarget) < 15.

// phace 2: retro burn to enter descent
print "mode: retro burn turn".
lock steering to ship:srfretrograde.
wait until VECTORANGLE(ship:facing:vector, ship:srfretrograde:vector) < 10.

print "mode: retro burn".
SET SHIP:CONTROL:PILOTMAINTHROTTLE TO 0. // cancel any old pilot input
lock throttle to 1.0.
wait until ship:velocity:surface:mag < 20.0.

// phase 2: controlled descent 
print "mode: final approach".
unlock throttle.
lock desiredVelocity to ship:altitude / 100.0 + 3.0.
lock dTargetCorrection to ship:up:vector - dTarget:normalized. // orientation correction
lock steering TO ship:up:vector + dTargetCorrection * 0.5.
wait until ship:status = "LANDED".

print "done".
unlock steering.
unlock throttle.

KSP Lalande log 2

// 51228 Solar Science Probe

Mun base construction lacks sufficient solar technology; rush construction of a solar science probe. Collect about 100 science for unlocking advanced electronics. 1×6 solar panels and KIS screwdriver will be essential for Munar colony mission to follow. Image

// 51228b Mun base Alpha hab dry run

Deployed the Mun base Alpha lander and hab assembly kit on Kerbin near KSC to verify proper function of KIS assembly and practice base assembly. Forgot screwdriver. Delivered screwdriver by UAV. Some glitches in assembly, but all mistakes were correctable. Crew quarters and hydroponics deployed. Need further verification to ensure sufficient electrical supply; may need supplementary solar to be delivered later. Dry run success. Image 1, 2.

// 51229 Mun base Alpha deployment

Developed new 20t lifter. 4 booster + 1 stage to orbit. Additional 2.5m x 2 fuel pod added for Mun transfer burn and orbital capture, to be left in orbit for future refueling needs. Deployment and assembly of base successful. Misunderstanding about supplies stored in inventory; will need to figure out how to resupply within 15 days. Image at Kerbin, landing, unpacking, assembled.

KSP – Lalande Server log 1

Getting back into Kerbal Space Program with some folks using the multiplayer mod. Taking mission notes to refer back to.

// 51224 Mun landing

Manned mission to Mun for science and practice. First attempt success. Touched down 1.2km from CK’s landing zone (for the bragging rights). Image 1, 2.

// 51225 Minmus probe

Unmanned probe to land on Minmus and collect science. First launch failed; insufficient batteries, became space trash. Redesigned. Successful landing. Image 1, 2.

// 51226 Minmus manned landing

Staging malfunction in first mission resulting in early return. Second mission success. Gathered samples from two biomes and some science experiments. 441.5 science gathered. Image.

// 51226b Space station science module

Adding a science module to CK’s existing station. Only had a crew report to add; should consider future mission to bring surface samples up to space for study to increase science yield. Docking a little stressful due to low FPS due to multiplayer mod, but docking was successful, no damage. Problems deorbiting main lifter; left as space trash (sorry!). Image 1, 2.

Pruning collision detection with a 1D sort

Recently I was trying out Phaser.io. It’s a nifty little HTML5/JS game development framework for 2D games with graphics, audio, physics, etc. It’s free, and MIT licensed.

Anyway, I ran into a limitation in its physics optimization. You can collide object-to-object, or entire groups of objects to other groups. Colliding entire groups at a time gets some optimization — not sure the details, but much faster than pairwise testing each element. However, the limitation is that groups also affect render z-order, and I have other plans for z-order.

It permits array-to-array tests, but that was slow; I’d guess it’s just a pairwise test underneath.

So, I remembered a 1D sort I wrote up a few years back. I coded it up, and it ended up outperforming groups on the benchmark I threw together. Here’s the core code:

function leftOfBody(b) { return b.x - b.halfWidth; }
function rightOfBody(b) { return b.x + b.halfWidth; }
function sortedCollide(game, arr) {
  arr.sort(function(a,b) { 
    return leftOfBody(a.body) - leftOfBody(b.body);
  })
  for (var i = 0; i < arr.length; ++i){
    var elem_i = arr[i]

    for (var j = i + 1; j < arr.length; ++j) {
      var elem_j = arr[j]
      if (rightOfBody(elem_i.body) < leftOfBody(elem_j.body)) { 
          // bail early. All elements right of 'j' are also entirely right of 'i'
          break; 
      }
      game.physics.arcade.collide(elem_i, elem_j)
    }
  }
}

By sorting in one dimension, we can bail out early from the loop. Once we see an element that is too far right to collide, we know that the rest of the elements in the array are also too far right.

For a typical 2D platformer, most of the world is either entirely to your right or left, so the inner loop runs effectively a constant number of iterations. This brings collision detection down from O(n**2) to O(n), plus the cost of the sort. The sort itself can be optimized to O(n) as well given reasonable assumptions about game mechanics, but I’ll leave that for another post.

You can try it out yourself at http://jsfiddle.net/cwgbxss5/1/.

If you want to use the above code, I’m making available under the WTFPL license. Enjoy.

(Mostly) Imperative Packrat Parsing

I’ve been tinkering with monadic parser combinators combined with continuations (see Monads, Mother of All), but my latest toy simplifies all that by using PEG grammars. PEGs and CFGs are nearly interchangable for most parsing of computer languages, and can be parsed in linear time and space by packrat parsing — parsing with backtracking, but uses memoization to bound backtracking cost to a constant factor as parsing work is not repeated.

The end result will be succinctly:

@grammar
def number():
  x = digit()
  while test(digit):
    x = x*10 + digit()
  return x

print parse(number, "15")

Continue reading “(Mostly) Imperative Packrat Parsing”

Non-determinism from generators

UPDATE(7/3/2013) I’ve found an earlier use of this technique written about on a blog, Valued Lessons – Monads in Python from 2008. Please read it too!

~~~

I was tinkering a bit tonight with simulating nondeterminism a-la McCarthy’s Amb operator — in Python. This is peculiar as Amb is usually implemented using either first class continuations or syntactic abstractions. Python supports neither.

So what is non-deterministic programming? Continue reading “Non-determinism from generators”