Eco-Tripping

Definition: Eco-Tripping

To own a 'local' car that is ultra efficient, perhaps electric, with a limited range a speed. When you want to go on a " trip to grandma's " you rent a family van with all the fancy TV and such for the trip.

The net result is less money spent, and a HIGHER STANDARD OF LIVING.

---

Standard of Living:

What is meant by wealth and standard of living?  These are the combined sum of how much 'stuff' you get for your day's work at some job.  By 'stuff' we mean material position, travel, security (police, fire, safe neighborhood), medical care, entertainment, internet access, recreation, family togetherness, food, clothing, house, exercise.  Notice that money is not in that list.  Money is a future claim on all the above.

A standard of living item that Americans cling to very tightly is transportation freedom.  Go where you want, when you want, in style.

There are two ways to raise standard of living: First is to make more money, and second is to get more stuff for less money.

The Diesel Rabbit Story:

My first car way back when was a VW Diesel Rabbit.  It was a freedom machine for me because at the time it went very far on very little money.  Going on a trip somewhere was not a big money decision.  The car was a very tangible increase in my standard of living.

One thing that lowers standard of living is when we worry about some activity we are doing or material we are using.  For example if you have to worry about the cost of gas, global warming, foreign wars fought over oil, then you standard of living is lower. You tend to have a negative mindset about driving anywhere.

Large Car Costs

If you currently have a Ford Expedition and haul the kids around in it, and gas hits $5 per gallon, the car becomes a drag on all trip decisions.  "Maybe we could go to the park, but it would cost too much in gas."  Why haul around such a huge car all the time when you only need it twice a year for long distance trips?  Not only is the big car a gas hog, but also repairs, tires, filters, oil changes, transmission, and the whole thing is very expensive. On the flip side if you look at person-miles-per-gallon a big car is very efficient if all seats have people in them.  A Hummer at 12 MPG with 8 people in it is 12 x 8 = 96 person-miles-per-gallon!

Electric Car Costs

A very efficient electric car (or gas for that matter) is less expensive, and less costly to repair.  The exception to this is some hybrids where the unique nature of the car pushes repair costs up.  That is a temporary condition.  An all electric car is less expensive to build, repair, and drive. The current lineup of electric cars are expensive because it is new technology. (Remember how expensive flat screen TV's started out?)

The Electric Car Delusion

There is  a current impression that electric cars are a reduction in standard of living.  This has been fostered by the automotive manufacturers. The problem is that it is obvious that if electric cars cost less to make, and have virtually no repairs, then selling the same number of cars per year will result in something like half the revenue.  Not a good business direction.  The fallacy is that either way cars are going to change to electric, the question is just when.  Only Nissan and Toyota have fully embraced this fact and are looking toward a future where they dominate the market. (Side note: electric cars can waaaaay out accelerate gas cars.)

Other Similar Topics

On a similar vein is how we handle the two largest home uses of energy, heat and hot water.  Both use natural gas and are completely unnecessary. Solar systems, if massed produced, should not cost much more to install, and result in a complete freedom from subsequent cost of hot water.  So take a shower as long as you want.  Once again a higher standard of living on less money.

Cultural Inertia

We have a cultural inertia where the way we have been doing things is what everyone knows, and it is difficult to imagine a different way, even if it might be better, more fun, and a 'higher standard of living'.  Instead we are stuck with the tree hugger nightmare where we all are supposed to suffer, trim back, reduce, scrimp and save, drive some eco-car that is no fun, freeze in the winter, bake in the summer and so on.  It is all wrong.  We need to put our creative powers toward how to live sustainably at a higher standard of living. 

It can be done.

TF

C++ std::list Chop off end of list

A little code here.

I have a list of X,Y,Goodness values.  I want to randomly select one entry from the top Goodness entries with some leeway for what 'top goodness' is.

  // Now sort the list by goodness, largest goodness at front.
  fits.sort(compare_PlacementRule_goodness);

  // Keep entries within a certain closeness to the maximm value.
  BuildingRect::xyPairGoodness & pg = fits.front();
  float topval = pg.goodness - r->m_placementRuleAllowance;
  // If topval is negative then no elements will get cut out.
  if(topval > 0.0f)
  {
    for(std::list<BuildingRect::xyPairGoodness>::iterator it = fits.begin(); it != fits.end(); ++it)
    {
      float g = it->goodness;
      if(g < topval)
      {
        // Cut rest of list off.
        fits.erase(it, fits.end());
        break;
      }
    }
  }

and the compare is

bool compare_PlacementRule_goodness(BuildingRect::xyPairGoodness first, BuildingRect::xyPairGoodness second)
{
  // We want the highest positive goodness at the top of the list.
  if (first.goodness > second.goodness) 
  {
    return true;
  }
  else 
  {
    return false;
  }
}

And as usual the greater than and less than symbols get munged.

TF

Physics Engines

Ok, a bit of advice earned the hard way...

DO NOT TRY TO WRITE YOUR OWN PHYSICS ENGINE.

We decided to go with Havok.

First we tried Bullet Physics, but it does not handle multiple independent simulation worlds, and our game (The Dead Linger) deals with an infinite world.  So we need to break it up into 1km cubes, each one an independent physics simulation.

The I spent two months part of which was general game stuff, but much of which was a custom infinite world physics engine.  Eventually we realized that we will never hit our deadline that way...

So we looked at Crysis (too expensive) and Havok.

A talk with the Havok engineers assured us that multiple worlds is fine (and yes, it is) and the licensing terms are perfect for a startup like Sandswept Studios.

So now after 2.5 weeks of effort we are on Havok and working.  The performance is amazing, and the robustness of the player motion among world objects is amazing.

TF

Capsule-Capsule Collision in Games

I have had to solve the problem of capsule on capsule collision solution and have found little if any good code or solutions on the 'net.  So here is my solution with code samples.  Also most game physics books discuss the math but not the overall view of how to sequence collision and physics in a game.  I highly recommend the book, Real-Time Collision Detection, by Christer Ericson.  A lot of the code here is derived and adapted from this book.

But first, lots of background about game collision.

Collision
In computer games (like TDL from Sandswept Studios, which I am writing) you need to have the Players and Non-Player Characters (Personas) move around the scene. As they move they should never be allowed to interpenetrate other objects like walls, the ground, and other personas.

You achieve this in two phases:

• First by making a list of all physics objects in the whole world that might interact.  This is the coarse phase, and results in each object having a list of all the other objects to check.
• Second is by moving each physics object with non-zero velocity while holding everything else still, and seeing if it collides with any of the objects it was paired with in the Coarse Phase. If it collides you move that distance, then adjust the velocity by the collision normal vector. This is called Movement Clipping.

Movement should not be confused with hit detection such as punches, baseball bat swings, and rifle shots.  These are solved with a very different strategy that involves triangle meshes and such.

There are several 3D shapes that are useful for movement clipping. A sphere is very simple to solve and is good for roundish objects like rocks, grenades, and such. Boxes can be good for walls and come in two flavors, Axis Aligned Bounding Boxes (AABB), and Object Bounding Boxes (OBB).  An AABB is a box aligned with the X,Y,Z axis and is very fast to solve.  OBB is a box but aligned along the natural axis of the object and moves and rotates with the object. OBB is pretty fast to solve too and is good for walls, and about any boxy objects.

Personas are best represented as Capsules.  A capsule is two spheres with a cylinder between them.  I have heard them called pills or suppositories too. The upper and lower ends are actually half-spheres.

A Capsule.

The reason capsules are so good to use is that they give a very realistic feel to collisions with walls and other Personas.  Also they are reasonably easy to program and compute. One very nice feature is they will slide up stair step due to the lower half sphere without any special programming for stairs.

Capsule represents a player. Lower curve navigates stairs.

Coarse Pass 
So, how do we solve the Coarse Pass?  What you do is every physics object has a AABB.  For each physics object you compare it against every other physics object to see if their AABBs overlap.  There are several complications.  Firstly the objects can be moving so you want to expand the AABB in the direction of motion so it fits the start and end locations of the object.  Not to hard to implement.  The second problem is a bit more complex.  In a large scene (TDL is infinite) there can be a huge number of physics objects.  Comparing all of them to each other is an Order Squared or O2 problem.  For example, 5,000 parts will require almost 25,000,000 comparisons!

So what you have to do is break the problem down so you are only comparing against parts that are reasonably close.  This can be done by grouping parts in some natural way, like all the parts in a given room, and put an AABB around them all and if your physics object does not intersect the big AABB, then ignore all the parts inside.  Often this ends up being a hierarchy of AABBs.

Nested AABBs

In TDL we do an OctTree.  We divided space up into cubes, then each cube is divided in to 8 sub-cubes for about 8 levels deep.  We only check a given physics objects others in it's parent cube, its cube, and all the sub cubes below it.

SubCube division.
From http://software.intel.com/en-us/articles/extending-stl-for-games/

On other major speed up for the Coarse Pass is to only have moving objects do checking against all other objects moving or not. (This particular strategy sped our Coarse Pass up by 32x!)

The result of the Coarse pass is that each Physics Object now has a list of all other potential other objects that might collide with it when it does is move.

Some improvements are to keep two lists, moving and not moving parts. Or keep three lists, moving, not moving but movable, and permanently immovable parts. (like walls)

The Fine Pass
So now we want to take all the parts that are moving and move them, but clip their movement by anything they collide with.  A object will have a certain movement it does in the current game time interval. For example a player moving at 3 meters per second will move 0.18 meters in 1/60th of a second.

What we want to do is check if any of the potential other objects get hit in that 0.18 meters and if so which are the closest. We then take those closest objects and subtract any component of our velocity that is perpendicular to the impact surface normal.

There are two approaches for finding the collision distance.  The first and best is to do a direct linear math solution as to how far you can move before hitting the other object.  This is best because is arrives at an exact distance in one pass of equations.

The other not-so-good approach is to do successive approximations.  This is where you first test the farthest move distance (in our example 0.18 meters) and see if it overlaps the other object.  If it does you cut the distance in half and try again.  On success you add half again, and on fail subtract half again.  The more times you do this the closer you get to the correct distance. 8 iterations get you withing 2 to the -8th power or 1/256 of the total distance within the correct answer.  One approach is to make longer absolute distance do more iterations, and short distances do less.  This can be done with a single tolerance number.  Why would you ever use successive approximations?  Because there are some geometric solutions that get into very complex and ugly math, yet the 'does it overlap' math is very simple. A good example of this is unaligned capsules.

Rounding Errors
One other important issue with solving move distance to hit objects.  Once you have hit the object and adjusted you velocity to be parallel to the hit surface, you bay be just a very tiny bit inside the surface, and you velocity may not be exactly parallel.  On computer the actual math is in binary and there are rounding errors. For example 1 divided by 3 is not 1/3, it is 0.333333333 and the number is not infinite.  So you need to have a small number that is the limit of how close 'equal' is.  In TDL is is called PHYSICS_EPSILON and is 0.0001 meters.

You then have macros (inline functions) such as isEqual, isZero, that are like this...

    inline bool isEqual(float a, float b) { return abs(a - b) <= PHYSICS_EPSILON; }

You also need the same methods for your 3D vector classes.

Now when you check for the collision distance you check whether the velocity is away or parallel (nearly parallel!) to the surface.  If it is it is not a hit.

One other note: Testing for dot products to be small requires a test against PHYSICS_EPSILON squared since a dot product is in essence a multiply.  This can bite you if you are comparing normals for parallel and also comparing velocity values for near zero.  Your dot products can be very small and not appear to be not near zero when they are.

Back to Fine Pass
For the fine pass we now find how far we can move, move there, adjust our velocity by any impacts, subtract how far we moved from the total (the 0.18 meters) and keep doing that until we have moved the full distance, or our velocity hits zero.

Oh, one question you might have, where did our velocity come from in the first place?  Every tick of the game you add gravity to the velocity, and add some velocity according to the controls such as in TDL, the W key makes you move forward.

Capsules
Ok, enough back story. The real intent of this posting is to discuss solutions for capsules and give code examples.

A capsule is defined one of two ways, either points A and B which are the centers of the two spheres, and a radius, or a single point A and a direction and distance given by a vector, and a radius.

There are several solutions you need and methods.  They are surfaceNormal, intersects, and collisionDistance.

But to implement those you need some utility methods.  One is segmentSegmentDistance which is given segment AB and segment CD find the least distance between the segments and the two points on the segments that are closest.  In the case of a capsule if this distance is less than the sum of the two radii then they are intersecting.  If the distance is more than the sum of the radii plus the speed of motion, then they wont collide at all.

A very similar method as ptSegmentNearest which finds the distance between a point P and a line segment AB and wht the point on the segment is.

Surface Normal
The surface normal is fairly simple.Given a point P presumed to be on the surface use ptSegmentNearest to find the point Q on the capusles AB segment and subtract Q from P to get a vector and then normalize the vector.  It will be the surface normal.  Watch out for the degenerate case where P is on the segment AB!

Intersects
If you are solving the distance to impact by successive approximations you need to have a fast way to tell if two Capsules intersect.  The best is to use segmentSegmentDistance.  If it is less than the sum of the radii then they intersect.  Watch out for the PHYSCIS_EPSILON issues here.  It is really

  if(isZero(dist - R1 - R2)) ...
Collision Distance
Now for the hard part!
If we have a moving capsule and it might collide with another capsule, well, do they and how far?

Turns out there are two cases for this.

If the capsules are aligned, in other words their AB lines are parallel or anti-parallel then the solution is much easier. (Anti-parallel means line AB is exactly the opposite direction from the other capsule's AB).

To tell if they are parallel just take the dot product of the two ABs.  If it 1.0 or -1.0 then they are parallel so you do the easy direct linear math solution.  Careful, once again don't just do abs(AB.dot(other->AB)) == 1.0.  You must use isZero(abs(AB.dot(other->AB)) - 1.0) to account for PHYSICS_EPSILON.

Parallel Capsules

* note: in some graphics code PHYSICS_EPSILON is just called EPSILON.

If they are not parallel then you have to solve by successive approximations.

Direct Linear Solution
Parallel capsules can be solved by adding the two AB segment together into one longer segment (watch out for the anti-parallel case!) and adding the radii resulting in a bigger capsule.  Then solve a ray from the A point of this to hit the combined capsule.  The distance will be correct.

-- Picture here ---

To solve the ray, first solve for an infinite cylinder and if it misses then there is no collision.  If it hits, find the point along the cylinder center line nearest the hit point.  If it is between A and B then you hit the body of the capsule.  If not then solve each of the spheres. and see which is closest.  There are some odd cases where your ray origin is inside the capsule, oops, the capsules were already intersecting.

You also have to see if the surface normal at the hit point is at right angles to your velocity.  This means it is a grazing hit (a miss) or you are just on the surface and are moving parallel to the surface, also a miss.  In fact any solution with the ray origin inside the capsule is a miss. These near misses are critical to good collision behavior.

Combine two capsules and then collide as a vector to get distance to collision.

Successive Approximation
If the capsules are not parallel you have to do a successive approximation.  Above I explained that you can tell whether two capsules are intersecting by simply finding the distance between the two AB segments. So you call the intersects method to decide how to iterate.  One great optimization is that much of the math for distance doe not depend on the resulting distance, only on the dot or cross product between the two AB segments.  You can take advantage of this to speed the iterations up.

Successive Approximation. Shown with parallel capsules but in our case they would not be parallel. Shows just 3 iteration, you would do more like 10.

Terrain Collision
One exception in all this collision is terrain.
Since TLD is an infinite world, and based on a OctTree, the terrain is not a normal object in the scene.  It changes altitude as a single sheet of triangles, penetrates between OctTree cubes and is generally misbehaved So I treat terrain as a special case in the collision code as a check before checking object collision in the Fine Pass.  I also do not collide physics objects with the terrain as such, I instead take a lowest point in the physics object and just collide that with the start and end points on the ground for the move interval. This makes the assumption that you are moving less than a terrain square tile interval.  Since my terrain is 1 meter squares this assumes you are doing somewhat less than 60 meters per second, which is very fast. So rather than check each triangle along the path of the move, I just check the start and end points.  In practice this works well.  Then I use the surface normal of the ground to adjust velocity.  Inelegant, but efficient.

Movement vectors with convex and concave terrain.  Vectors are exaggerated long. 

Code
Some words about collision code.  Each game physics engine has its own vector type, some float or double scalar type, and its own convention for variable names.  When making a game it is a good idea to use an existing physics engine.  We tried Bullet Physics.  In the end I ended up doing a custom physics engine for TDL for several reasons.

• We have an infinite world and physics engines are usually geared toward a 'level' in a game which is limited in space.
• We have all the data structures in place such as an OctTree, terrain definitions, all the objects in the scene, all because we are generating the whole world on-the-fly as you move through it. (Go play Minecraft)  Using and existing engine tends to result in duplicate data for everything.  We have to use memory very efficiently.
• We are very efficient with CPU use.  Every cycle counts.

There are only two reasons you should write your own physics engine...

• The above three reasons of you have a very unique game world.
• Because it is downright fun and you like algorithms, math, and lots of debugging.

So, the following code examples are built on the bullet physics base types such as btVector3 and btScalar (set to double precision) so I don't have to rewrite all the vector math and Quaternions, and Matrices.

---- Code examples coming soon. -----

Oh, BTW, X is to the right of the screen, Y is Up, Z is out of the screen toward the viewer, but collision is in world coordinates, not screen coordinate, so you can think of it as X is East, Y is Up, Z is South.

Profiling
I can't emphasize enough how important it is to do code profiling. I use cRunWatch from raven.  It is very simple.  I was doing lots of work on getting the Fine Pass collision to be fast, and as soon as I profiled TDL, I saw that my Coarse Pass was taking 80% of the total execution time.  I easily then made it much faster and it now gets 32 FPS in debug mode, and > 200 FPS in release mode.

Debugging
Debugging physics is very difficult because everything is happening in a fraction of a second and if you set a break point the timing is all off and the keyboard is no longer game movement input.  The best thing to do is put if statements specifically as breakpoints.  In TDL it looks like this...

volatile int foo = 0;

if(!IsServer && m_isPlayer && m_velocity.getX() > 0.0 and other->m_isAABB)
{
     foo = 1;
}Then you can get to the right place in the game, like running into a wall and set the breakpoint on foo = 1 and then continue and when you start to move forward the breakpoint is triggered.  So get creative on breakpoints in this style.

Another great class I designed is a PeriodicLog.  What it does is every n milliseconds it enables logging for one frame.  Then you can have a log entry for example that prints the solution distance every frame but instead of getting swamped with log lines, you just get one or two per second.

Also at a higher level it helps to be able to turn on wireframe representations of all collision objects and they change color when impacting or moving etc.  This does not help much with low level collision code debugging, but is great for in game whole scene setup issues.

TF

The Real Problem with SOPA

So Congress has the SOPA bill before it. There is a huge online protest to stop it, which is being very effective.

But next week? Next month?

The SOPA and PIPA bills are just the latest in a fairly long line of bills that are designed to control the internet and will not be the last. Already there is talk about the next bill and how it will be worded better.

The real problem is not the particular bills. It is that our elected politicians even feel a need for any bill at all.

If I remember my Democracy 101, the politicians represent The People. And I sure don't hear The People clamoring for more internet regulation.

So what is really up? We have old congressmen that do not have a clue about the internet. Some lobbyist comes to them with money and supposed expertise. The congressmen don't understand the hidden (or not so hidden) agenda of the lobbyists to preserve outdated business models. And they sure don't understand the internet at all.

The only real hope to come from today's internet protest is that the pile of phone calls from constituents will give the congressmen such a bad taste in their mouth that in the future they will shy away from any bill with the word 'internet' in it.

And the world will then be a better place.

TF

P.S. A recent article here has the opinion that the latest session of congress has been the least productive in history. Meaning they passed the fewest laws. Since when is passing more laws better? How about we measure congressional success by how many laws they repeal.

A New Kind of Science - Stephen Wolfram

I saw a book called A New Kind of Science online and ordered a used copy.

Meanwhile, I read it on line while waiting for the hard copy to show up. When it did the tome was huge. Yup, I like to buy books by the pound.

Any ways, The web site for the book is here. A New Kind of Science

This is not just any old book. There have been several books of science over the centuries that would be called landmark books. For example Principia Mathematica, The Origin of the Species or Godel, Escher, Bach. This book is right up there with them.

(I realize the hyperbole there and am quite serious.)

Back in Galileo and Newton's time the earthshaking idea they proposed was not just about astronomy, but was the idea that Mathematics could be used to understand and describe the natural world. Before that Mathematics was considered purely abstract, of the mind. Newton came up with calculus and linear equations to describe motion.

Because science has used solvable mathematics, proofs, and equations to discover how Things Work, that has been the class of problems solved. Some problems in biological growth, physics, and such have been impossible to solve, and so have been ignored or swept under the rug.

What Wolfram proposes in A New Kind of Science is that there are many structures and processes in the universe that can not be described by linear math. Instead there are automatons and computer programs that can easily describe and model some processes. Not only does this technique model many processes that were previously 'complex' but great complexity can often flow from very simple processes. A familiar example of this is fractals, where a simple set of rules generate a very detailed and complex drawing.

The other side of this coin is that some problems and models can never be proven no matter how long you simulate or compute them. Science hates to say 'I don't know', but Wolfram clearly states that there are some things that can not be known.

Much of the book centers around the idea of generating complexity by way of ultra simple programs, and finding out just how simple you can get and still get huge complexity.

The book touches on biological organisms, stellar systems, fluid flow, the mind, free will, evolution, religion, society, and of course, mathematics.

So, when reading the book one thing stood out as odd. One is the general use of I, My, This Science, where Wolfram's ideas and science is 'All New and Improved!' and will revolutionize science. This gives it about the same tone as crackpots on the internet with some hair-brained theory that will change the world and has never been know before (tm). The difference with this book is that Wolfram is correct! Books such as The Origin of the Species have none of that tone.

Another thing that will help with this book is to not get stuck on the huge amount of ideas and processes presented. You don't have to understand every concept and program process presented. If I read this and learned to understand every mathematical concept presented in depth it would take years to read.

In the end the core idea is of The Principle of Computational Equivalence. The idea is that it does not matter whether a program is run on a computer, in a biological system, or a flow of atoms in a fluid, it is all the same. This is much like how the equation of gravity, F = MmG/r^2 is equivalent to what actual gravity does. But the equation and computing it is not what gravity is doing in the real world. It is a model that matches what we see, so gives understanding.

The other core idea is that the only way of discovering the outcome of some simple systems is to run the system to completion. For example, it is impossible to determine whether pi ever repeats, except to keep computing digits of pi until it does. (And so far it has not after billions of digits.)

The final paragraph is a gem...

And indeed in the end the Principle of Computational Equivalence encapsulates both the ultimate power and the ultimate weakness of science. For it implies that all the wonders of the universe can in effect be captured by simple rules, yet it shows that there can be no way to know all the consequences of these rules, except in effect just to watch and see how they unfold.

Wow.

TF

Honda Civic Hybrid 2005 Headlamp Replacement

Ok,

A headlight blew. So I had to replace it.

The high beams are toward the middle of the car and are fairly easy to replace.

In general you rotate the lamp to the left so it unclips. Then push in the tab on the wire harness end and pull the lamp loose.

Don't touch the bulbs you are putting in ever. The oil from your fingers will shatter the bulb once it is on for a while.

The low beams are the next outward from the center of the car. They are difficult.
On the driver side the battery is in the way. On the passenger side the fuel pump (?) is in the way.

The instructions say on the driver side you have to remove the wiper fluid reservoir, but I think the Hybrid is different.

What I did on the passenger side is go in through the wheel well. You use a screwdriver to pry out the two black plastic clips and then bend the wheel well plastic cover down so you can get your hand in. (Major yoga here.) I assume you do the same on the driver side.

The left and right blinker are accessed through the wheel well too.

Oh, you have to turn the steering wheel all the way to one side so the wheel well is exposed and you can get in there.

TF