.......

[carveJwlIkooP6JGAAIwe30JlM.git] / player.h

#ifndef PLAYER_H
#define PLAYER_H

#include "audio.h"
#include "common.h"
#include "world.h"
//#include "character.h"
#include "player_model.h"
#include "bvh.h"

/* 
 * Constants 
 */

static float 
   k_walkspeed             = 2.0f,
   k_board_radius          = 0.3f,
   k_board_length          = 0.45f,
   k_board_allowance       = 0.04f,
   k_friction_lat          = 8.8f,
   k_friction_resistance   = 0.01f,
   k_max_push_speed        = 16.0f,
   k_push_accel            = 10.0f,
   k_push_cycle_rate       = 8.0f,
   k_steer_ground          = 2.5f,
   k_steer_air             = 3.6f,
   k_steer_air_lerp        = 0.3f,
   k_pump_force            = 000.0f,
   k_downforce             = 5.0f,
   k_jump_charge_speed     = (1.0f/1.0f),
   k_jump_force            = 5.0f;

static int freecam = 0;
static int walk_grid_iterations = 1;
static float fc_speed = 10.0f;

static struct gplayer
{
   /* Physics */
   rigidbody rb, collide_front, collide_back, rb_gate_frame;

   v3f a, v_last, m, bob, vl;

   /* Utility */
   float vswitch, slip, slip_last,
         reverse;

   float iY;   /* Yaw inertia */
   int in_air, is_dead, on_board;

   v2f board_xy;
   float grab;
   float pitch;
   float pushing, push_time;
   float jump;
   int jump_charge;
   
   v3f land_target;
   v3f land_target_log[22];
   u32 land_target_colours[22];
   int land_log_count;
   m3x3f vr,vr_pstep;
   
   struct character mdl;

   v3f handl_target, handr_target,
       handl, handr;
   
   /* Camera */
   float air_blend;
   
   v3f camera_pos, smooth_localcam;
   v2f angles;
   m4x3f camera, camera_inverse;

   /* animation */
   double jump_time;
   float fslide,
         fdirz, fdirx,
         fstand,
         ffly,
         fpush,
         fairdir,
         fsetup;
}
player = 
{
   .on_board = 1,

   .collide_front = { .type = k_rb_shape_sphere, .inf.sphere.radius = 0.3f },
   .collide_back  = { .type = k_rb_shape_sphere, .inf.sphere.radius = 0.3f }
};

/* 
 * Player API
 */


/*
 * Free camera movement
 */

static void player_mouseview(void)
{
   if( gui_want_mouse() )
      return;

   static v2f mouse_last,
              view_vel = { 0.0f, 0.0f };

   if( vg_get_button_down( "primary" ) )
      v2_copy( vg_mouse, mouse_last );

   else if( vg_get_button( "primary" ) )
   {
      v2f delta;
      v2_sub( vg_mouse, mouse_last, delta );
      v2_copy( vg_mouse, mouse_last );

      v2_muladds( view_vel, delta, 0.001f, view_vel );
   }
   
   v2_muladds( view_vel, 
         (v2f){ vg_get_axis("h1"), vg_get_axis("v1") }, 
         0.05f, view_vel );
   v2_muls( view_vel, 0.93f, view_vel );
   v2_add( view_vel, player.angles, player.angles );
   player.angles[1] = vg_clampf( player.angles[1], -VG_PIf*0.5f, VG_PIf*0.5f );
}

static void player_freecam(void)
{
   player_mouseview();

   float movespeed = fc_speed;
   v3f lookdir = { 0.0f, 0.0f, -1.0f },
       sidedir = { 1.0f, 0.0f,  0.0f };
   
   m3x3_mulv( player.camera, lookdir, lookdir );
   m3x3_mulv( player.camera, sidedir, sidedir );
   
   static v3f move_vel = { 0.0f, 0.0f, 0.0f };
   if( vg_get_button( "forward" ) )
      v3_muladds( move_vel, lookdir, ktimestep * movespeed, move_vel );
   if( vg_get_button( "back" ) )
      v3_muladds( move_vel, lookdir, ktimestep *-movespeed, move_vel );
   if( vg_get_button( "left" ) )
      v3_muladds( move_vel, sidedir, ktimestep *-movespeed, move_vel );
   if( vg_get_button( "right" ) )
      v3_muladds( move_vel, sidedir, ktimestep * movespeed, move_vel );

   v3_muls( move_vel, 0.7f, move_vel );
   v3_add( move_vel, player.camera_pos, player.camera_pos );
}

/*
 * Player Physics Implementation
 */

static void apply_gravity( v3f vel, float const timestep )
{
   v3f gravity = { 0.0f, -9.6f, 0.0f };
   v3_muladds( vel, gravity, timestep, vel );
}

/*
 * TODO: The angle bias should become greater when launching from a steeper 
 *       angle and skewed towords more 'downwards' angles when launching from
 *       shallower trajectories
 *
 *       it should also be tweaked by the controller left stick being pushed
 *       up or down
 */
static void player_start_air(void)
{
   if( player.in_air )
      return;

   player.in_air = 1;

   float pstep = ktimestep*10.0f;
   float best_velocity_delta = -9999.9f;
   float k_bias = 0.96f;

   v3f axis;
   v3_cross( player.rb.up, player.rb.v, axis );
   v3_normalize( axis );
   player.land_log_count = 0;
   
   m3x3_identity( player.vr );

   for( int m=-3;m<=12; m++ )
   {
      float vmod = ((float)m / 15.0f)*0.09f;

      v3f pco, pco1, pv;
      v3_copy( player.rb.co, pco );
      v3_muls( player.rb.v, k_bias, pv );

      /* 
       * Try different 'rotations' of the velocity to find the best possible
       * landing normal. This conserves magnitude at the expense of slightly
       * unrealistic results
       */

      m3x3f vr;
      v4f vr_q;

      q_axis_angle( vr_q, axis, vmod );
      q_m3x3( vr_q, vr );

      m3x3_mulv( vr, pv, pv );
      v3_muladds( pco, pv, pstep, pco );

      for( int i=0; i<50; i++ )
      {
         v3_copy( pco, pco1 );
         apply_gravity( pv, pstep );

         m3x3_mulv( vr, pv, pv );
         v3_muladds( pco, pv, pstep, pco );
         
         ray_hit contact;
         v3f vdir;

         v3_sub( pco, pco1, vdir );
         contact.dist = v3_length( vdir );
         v3_divs( vdir, contact.dist, vdir);

         if( ray_world( pco1, vdir, &contact ))
         {
            float land_delta = v3_dot( pv, contact.normal );
            u32 scolour = (u8)(vg_minf(-land_delta * 2.0f, 255.0f));

            /* Bias prediction towords ramps */
            if( ray_hit_is_ramp( &contact ) )
            {
               land_delta *= 0.1f;
               scolour |= 0x0000a000;
            }

            if( (land_delta < 0.0f) && (land_delta > best_velocity_delta) )
            {
               best_velocity_delta = land_delta;

               v3_copy( contact.pos, player.land_target );
               
               m3x3_copy( vr, player.vr_pstep );
               q_axis_angle( vr_q, axis, vmod*0.1f );
               q_m3x3( vr_q, player.vr );
            }

            v3_copy( contact.pos, 
                  player.land_target_log[player.land_log_count] );
            player.land_target_colours[player.land_log_count] = 
               0xff000000 | scolour;

            player.land_log_count ++;

            break;
         }
      }
   }
}

static void draw_cross(v3f pos,u32 colour, float scale)
{
   v3f p0, p1;
   v3_add( (v3f){ scale,0.0f,0.0f}, pos, p0 );
   v3_add( (v3f){-scale,0.0f,0.0f}, pos, p1 );
   vg_line( p0, p1, colour );
   v3_add( (v3f){0.0f, scale,0.0f}, pos, p0 );
   v3_add( (v3f){0.0f,-scale,0.0f}, pos, p1 );
   vg_line( p0, p1, colour );
   v3_add( (v3f){0.0f,0.0f, scale}, pos, p0 );
   v3_add( (v3f){0.0f,0.0f,-scale}, pos, p1 );
   vg_line( p0, p1, colour );
}

static void player_physics_control(void)
{
   /*
    * Computing localized friction forces for controlling the character
    * Friction across X is significantly more than Z
    */

   v3f vel;
   m3x3_mulv( player.rb.to_local, player.rb.v, vel );
   float slip = 0.0f;
   
   if( fabsf(vel[2]) > 0.01f )
      slip = fabsf(-vel[0] / vel[2]) * vg_signf(vel[0]);

   if( fabsf( slip ) > 1.2f )
      slip = vg_signf( slip ) * 1.2f;
   player.slip = slip;
   player.reverse = -vg_signf(vel[2]);

   float substep = ktimestep * 0.2f;
   float fwd_resistance = (vg_get_button( "break" )? 5.0f: 0.02f) * -substep;

   for( int i=0; i<5; i++ )
   {
      vel[2] = stable_force( vel[2], vg_signf( vel[2] ) * fwd_resistance );
      vel[0] = stable_force( vel[0], 
            vg_signf( vel[0] ) * -k_friction_lat*substep );
   }
   
   static double start_push = 0.0;
   if( vg_get_button_down( "push" ) )
      start_push = vg_time;

   if( vg_get_button( "jump" ) )
   {
      player.jump += ktimestep * k_jump_charge_speed;
      player.jump_charge = 1;
   }

   if( !vg_get_button("break") && vg_get_button( "push" ) )
   {
      player.pushing = 1.0f;
      player.push_time = vg_time-start_push;

      float cycle_time = player.push_time*k_push_cycle_rate,
            amt = k_push_accel * (sinf(cycle_time)*0.5f+0.5f)*ktimestep,
            current = v3_length( vel ),
            new_vel = vg_minf( current + amt, k_max_push_speed );

      new_vel -= vg_minf(current, k_max_push_speed);
      vel[2] -= new_vel * player.reverse;
   }

   /* Pumping */
   static float previous = 0.0f;
   float delta = previous - player.grab,
          pump = delta * k_pump_force*ktimestep;
   previous = player.grab;

   v3f p1;
   v3_muladds( player.rb.co, player.rb.up, pump, p1 );
   vg_line( player.rb.co, p1, 0xff0000ff );

   vel[1] += pump;

   
   m3x3_mulv( player.rb.to_world, vel, player.rb.v );
   
   float steer = vg_get_axis( "horizontal" );
   player.iY -= vg_signf(steer)*powf(steer,2.0f) * k_steer_ground * ktimestep;
   
   v2_lerp( player.board_xy, (v2f){ slip*0.25f, 0.0f }, 
         ktimestep*5.0f, player.board_xy);
}

static void player_physics_control_air(void)
{
   m3x3_mulv( player.vr, player.rb.v, player.rb.v );
   draw_cross( player.land_target, 0xff0000ff, 0.25f );

   ray_hit hit;

   /* 
    * Prediction 
    */
   float pstep = ktimestep*10.0f;

   v3f pco, pco1, pv;
   v3_copy( player.rb.co, pco );
   v3_copy( player.rb.v, pv );
   
   float time_to_impact = 0.0f;
   float limiter = 1.0f;

   for( int i=0; i<50; i++ )
   {
      v3_copy( pco, pco1 );
      m3x3_mulv( player.vr_pstep, pv, pv );
      apply_gravity( pv, pstep );
      v3_muladds( pco, pv, pstep, pco );

      //vg_line( pco, pco1, i&0x1?0xff000000:0xffffffff );
      
      ray_hit contact;
      v3f vdir;

      v3_sub( pco, pco1, vdir );
      contact.dist = v3_length( vdir );
      v3_divs( vdir, contact.dist, vdir);
      
      float orig_dist = contact.dist;
      if( ray_world( pco1, vdir, &contact ))
      {
         float angle = v3_dot( player.rb.up, contact.normal );
         v3f axis; 
         v3_cross( player.rb.up, contact.normal, axis );

         time_to_impact += (contact.dist/orig_dist)*pstep;
         limiter = vg_minf( 5.0f, time_to_impact )/5.0f;
         limiter = 1.0f-limiter;
         limiter *= limiter;
         limiter = 1.0f-limiter;

         if( angle < 0.99f )
         {
            v4f correction;
            q_axis_angle( correction, axis, acosf(angle)*0.05f*(1.0f-limiter) );
            q_mul( correction, player.rb.q, player.rb.q );
         }

         draw_cross( contact.pos, 0xffff0000, 0.25f );
         break;
      }
      time_to_impact += pstep;
   }

   player.iY -= vg_get_axis( "horizontal" ) * k_steer_air * ktimestep;
   {
      float iX = vg_get_axis( "vertical" ) * 
         player.reverse * k_steer_air * limiter * ktimestep;

      static float siX = 0.0f;
      siX = vg_lerpf( siX, iX, k_steer_air_lerp );
      
      v4f rotate;
      q_axis_angle( rotate, player.rb.right, siX );
      q_mul( rotate, player.rb.q, player.rb.q );
   }
   
   v2f target = {0.0f,0.0f};
   v2_muladds( target, (v2f){ vg_get_axis("h1"), vg_get_axis("v1") },
               player.grab, target );
   v2_lerp( player.board_xy, target, ktimestep*3.0f, player.board_xy );
}

static void player_init(void)
{
   rb_init( &player.collide_front );
   rb_init( &player.collide_back  );
}

static void player_physics(void)
{
   /*
    * Update collision fronts
    */
   
   rigidbody *rbf = &player.collide_front,
             *rbb = &player.collide_back;

   m3x3_copy( player.rb.to_world, player.collide_front.to_world );
   m3x3_copy( player.rb.to_world, player.collide_back.to_world );
   
   player.air_blend = vg_lerpf( player.air_blend, player.in_air, 0.1f );
   float h = player.air_blend*0.2f;

   m4x3_mulv( player.rb.to_world, (v3f){0.0f,h,-k_board_length}, rbf->co );
   v3_copy( rbf->co, rbf->to_world[3] );
   m4x3_mulv( player.rb.to_world, (v3f){0.0f,h, k_board_length}, rbb->co );
   v3_copy( rbb->co, rbb->to_world[3] );

   m4x3_invert_affine( rbf->to_world, rbf->to_local );
   m4x3_invert_affine( rbb->to_world, rbb->to_local );

   rb_update_bounds( rbf );
   rb_update_bounds( rbb );

   rb_debug( rbf, 0xff00ffff );
   rb_debug( rbb, 0xffffff00 );

   rb_ct manifold[24];
   int len = 0;

   len += rb_sphere_vs_scene( rbf, &world.rb_geo, manifold+len );
   len += rb_sphere_vs_scene( rbb, &world.rb_geo, manifold+len );

   rb_presolve_contacts( manifold, len );
   v3f surface_avg = {0.0f, 0.0f, 0.0f};

   if( !len )
   {
      player_start_air();
   }
   else
   {
      for( int i=0; i<len; i++ )
      {
         v3_add( manifold[i].n, surface_avg, surface_avg );

#if 0
         if( manifold[i].element_id <= world.sm_geo_std_oob.vertex_count )
         {
            player.is_dead = 1;
            character_ragdoll_copypose( &player.mdl, player.rb.v );
            return;
         }
#endif
      }

      v3_normalize( surface_avg );

      if( v3_dot( player.rb.v, surface_avg ) > 0.5f )
      {
         player_start_air();
      }
      else
         player.in_air = 0;
   }

   for( int j=0; j<5; j++ )
   {
      for( int i=0; i<len; i++ )
      {
         struct contact *ct = &manifold[i];
         
         v3f dv, delta;
         v3_sub( ct->co, player.rb.co, delta ); 
         v3_cross( player.rb.w, delta, dv );
         v3_add( player.rb.v, dv, dv );

         float vn = -v3_dot( dv, ct->n );
         vn += ct->bias;

         float temp = ct->norm_impulse;
         ct->norm_impulse = vg_maxf( temp + vn, 0.0f );
         vn = ct->norm_impulse - temp;

         v3f impulse;
         v3_muls( ct->n, vn, impulse );

         if( fabsf(v3_dot( impulse, player.rb.forward )) > 10.0f ||
             fabsf(v3_dot( impulse, player.rb.up )) > 50.0f )
         {
            player.is_dead = 1;
            character_ragdoll_copypose( &player.mdl, player.rb.v );
            return;
         }

         v3_add( impulse, player.rb.v, player.rb.v );
         v3_cross( delta, impulse, impulse );

         /*
          * W Impulses are limited to the Y and X axises, we don't really want
          * roll angular velocities being included.
          *
          * Can also tweak the resistance of each axis here by scaling the wx,wy
          * components.
          */
         
         float wy = v3_dot( player.rb.up, impulse ),
               wx = v3_dot( player.rb.right, impulse )*1.5f;

         v3_muladds( player.rb.w, player.rb.up, wy, player.rb.w );
         v3_muladds( player.rb.w, player.rb.right, wx, player.rb.w );
      }
   }

   float grabt = vg_get_axis( "grabr" )*0.5f+0.5f;
   player.grab = vg_lerpf( player.grab, grabt, 0.14f );
   player.pushing = 0.0f;

   if( !player.in_air )
   {
      v3f axis;
      float angle = v3_dot( player.rb.up, surface_avg );
      v3_cross( player.rb.up, surface_avg, axis );

      //float cz = v3_dot( player.rb.forward, axis );
      //v3_muls( player.rb.forward, cz, axis );

      if( angle < 0.999f )
      {
         v4f correction;
         q_axis_angle( correction, axis, acosf(angle)*0.3f );
         q_mul( correction, player.rb.q, player.rb.q );
      }

      v3_muladds( player.rb.v, player.rb.up, 
            -k_downforce*ktimestep, player.rb.v );

      player_physics_control();

      if( !player.jump_charge && player.jump > 0.2f )
      {
         v3_muladds( player.rb.v, player.rb.up, k_jump_force*player.jump,
                     player.rb.v );

         player.jump_time = vg_time;
      }
   }
   else
   {
      player_physics_control_air();
   }

   if( !player.jump_charge )
   {
      player.jump -= k_jump_charge_speed * ktimestep;
   }
   player.jump_charge = 0;
   player.jump = vg_clampf( player.jump, 0.0f, 1.0f );
}

static void player_do_motion(void)
{
   float horizontal = vg_get_axis("horizontal"),
         vertical = vg_get_axis("vertical");

   player_physics();
   
   /* Integrate velocity */
   v3f prevco;
   v3_copy( player.rb.co, prevco );
   
   apply_gravity( player.rb.v, ktimestep );
   v3_muladds( player.rb.co, player.rb.v, ktimestep, player.rb.co );

   /* Real angular velocity integration */
   v3_lerp( player.rb.w, (v3f){0.0f,0.0f,0.0f}, 0.125f, player.rb.w );
   if( v3_length2( player.rb.w ) > 0.0f )
   {
      v4f rotation;
      v3f axis;
      v3_copy( player.rb.w, axis );
      
      float mag = v3_length( axis );
      v3_divs( axis, mag, axis );
      q_axis_angle( rotation, axis, mag*k_rb_delta );
      q_mul( rotation, player.rb.q, player.rb.q );
   }

   /* Faux angular velocity */
   v4f rotate; 

   static float siY = 0.0f;
   float lerpq = player.in_air? 0.04f: 0.3f;
   siY = vg_lerpf( siY, player.iY, lerpq );

   q_axis_angle( rotate, player.rb.up, siY );
   q_mul( rotate, player.rb.q, player.rb.q );
   player.iY = 0.0f;

   /* 
    * Gate intersection, by tracing a line over the gate planes 
    */
   for( int i=0; i<world.routes.gate_count; i++ )
   {
      struct route_gate *rg = &world.routes.gates[i];
      teleport_gate *gate = &rg->gate;

      if( gate_intersect( gate, player.rb.co, prevco ) )
      {
         m4x3_mulv( gate->transport, player.rb.co, player.rb.co );
         m3x3_mulv( gate->transport, player.rb.v, player.rb.v );
         m3x3_mulv( gate->transport, player.vl, player.vl );
         m3x3_mulv( gate->transport, player.v_last, player.v_last );
         m3x3_mulv( gate->transport, player.m, player.m );
         m3x3_mulv( gate->transport, player.bob, player.bob );

         v4f transport_rotation;
         m3x3_q( gate->transport, transport_rotation );
         q_mul( transport_rotation, player.rb.q, player.rb.q );
         
         world_routes_activate_gate( i );
         player.rb_gate_frame = player.rb;
         break;
      }
   }
   
   rb_update_transform( &player.rb );
}

/*
 * Walkgrid implementation,
 *  loosely based of cmuratoris youtube video 'Killing the Walkmonster'
 */

#define WALKGRID_SIZE 16
struct walkgrid
{
   struct grid_sample
   {
      enum sample_type
      {
         k_sample_type_air,      /* Nothing was hit. */
         k_sample_type_invalid,  /* The point is invalid, but there is a sample
                                    underneath that can be used */
         k_sample_type_valid,    /* This point is good */
      }
      type;

      v3f clip[2];
      v3f pos;

      enum traverse_state
      {
         k_traverse_none = 0x00,
         k_traverse_h    = 0x01,
         k_traverse_v    = 0x02
      }
      state;
   }
   samples[WALKGRID_SIZE][WALKGRID_SIZE];

   boxf region;

   float move; /* Current amount of movement we have left to apply */
   v2f dir;    /* The movement delta */
   v2i cell_id;/* Current cell */
   v2f pos;    /* Local position (in cell) */
   float h;
};

static int player_walkgrid_tri_walkable( u32 tri[3] )
{
   return tri[0] > world.sm_geo_std_oob.vertex_count;
}

/*
 * Get a sample at this pole location, will return 1 if the sample is valid,
 * and pos will be updated to be the intersection location.
 */
static void player_walkgrid_samplepole( struct grid_sample *s )
{
   boxf region = {{ s->pos[0] -0.01f, s->pos[1] - 4.0f, s->pos[2] -0.01f},
                  { s->pos[0] +0.01f, s->pos[1] + 4.0f, s->pos[2] +0.01f}};

   u32 geo[256];
   v3f tri[3];
   int len = bh_select( &world.geo.bhtris, region, geo, 256 );
   
   const float k_minworld_y = -2000.0f;

   float walk_height = k_minworld_y,
         block_height = k_minworld_y;

   s->type = k_sample_type_air;

   for( int i=0; i<len; i++ )
   {
      u32 *ptri = &world.geo.indices[ geo[i]*3 ];

      for( int j=0; j<3; j++ )
         v3_copy( world.geo.verts[ptri[j]].co, tri[j] );
      
      v3f vdown = {0.0f,-1.0f,0.0f};
      v3f sample_from;
      v3_copy( s->pos, sample_from );
      sample_from[1] = region[1][1];
      
      float dist;
      if( ray_tri( tri, sample_from, vdown, &dist ))
      {
         v3f p0;
         v3_muladds( sample_from, vdown, dist, p0 );

         if( player_walkgrid_tri_walkable(ptri) )
         {
            if( p0[1] > walk_height )
            {
               walk_height = p0[1];
            }
         }
         else
         {
            if( p0[1] > block_height )
               block_height = p0[1];
         }
      }
   }

   s->pos[1] = walk_height;

   if( walk_height > k_minworld_y )
      if( block_height > walk_height )
         s->type = k_sample_type_invalid;
      else
         s->type = k_sample_type_valid;
   else
      s->type = k_sample_type_air;
}

float const k_gridscale = 0.5f;

enum eclipdir
{
   k_eclipdir_h = 0,
   k_eclipdir_v = 1
};

static void player_walkgrid_clip_blocker( struct grid_sample *sa,
                                          struct grid_sample *sb,
                                          struct grid_sample *st,
                                          enum eclipdir dir )
{
   v3f clipdir, pos;
   int valid_a = sa->type == k_sample_type_valid,
       valid_b = sb->type == k_sample_type_valid;
   struct grid_sample *target = valid_a? sa: sb,
                      *other  = valid_a? sb: sa;
   v3_copy( target->pos, pos );
   v3_sub( other->pos, target->pos, clipdir );

   boxf cell_region;
   v3_muladds( pos, (v3f){1.0f,1.0f,1.0f}, -k_gridscale*2.1f, cell_region[0]);
   v3_muladds( pos, (v3f){1.0f,1.0f,1.0f},  k_gridscale*2.1f, cell_region[1]);

   u32 geo[256];
   v3f tri[3];
   int len = bh_select( &world.geo.bhtris, cell_region, geo, 256 );
   
   float start_time = v3_length( clipdir ),
         min_time = start_time;
   v3_normalize( clipdir );
   v3_muls( clipdir, 0.0001f, st->clip[dir] );

   for( int i=0; i<len; i++ )
   {
      u32 *ptri = &world.geo.indices[ geo[i]*3 ];
      for( int j=0; j<3; j++ )
         v3_copy( world.geo.verts[ptri[j]].co, tri[j] );

      if( player_walkgrid_tri_walkable(ptri) )
         continue;

      float dist;
      if(ray_tri( tri, pos, clipdir, &dist ))
      {
         if( dist > 0.0f && dist < min_time )
         {
            min_time = dist;
            sb->type = k_sample_type_air;
         }
      }
   }

   if( !(min_time < start_time) )
      min_time = 0.5f * k_gridscale;

   min_time = vg_clampf( min_time/k_gridscale, 0.01f, 0.99f );

   v3_muls( clipdir, min_time, st->clip[dir] );

   v3f p0;
   v3_muladds( target->pos, st->clip[dir], k_gridscale, p0 );
}

static void player_walkgrid_clip_edge( struct grid_sample *sa,
                                       struct grid_sample *sb,
                                       struct grid_sample *st, /* data store */
                                       enum eclipdir dir )
{
   v3f clipdir = { 0.0f, 0.0f, 0.0f }, pos;
   int valid_a = sa->type == k_sample_type_valid,
       valid_b = sb->type == k_sample_type_valid;

   struct grid_sample *target = valid_a? sa: sb,
                      *other  = valid_a? sb: sa;
   
   v3_sub( other->pos, target->pos, clipdir );
   clipdir[1] = 0.0f;

   v3_copy( target->pos, pos );

   boxf cell_region;
   v3_muladds( pos, (v3f){1.0f,1.0f,1.0f}, -k_gridscale*1.1f, cell_region[0]);
   v3_muladds( pos, (v3f){1.0f,1.0f,1.0f},  k_gridscale*1.1f, cell_region[1]);

   u32 geo[256];
   int len = bh_select( &world.geo.bhtris, cell_region, geo, 256 );

   float max_dist = 0.0f;
   v3f tri[3];
   v3f perp;
   v3_cross( clipdir,(v3f){0.0f,1.0f,0.0f},perp );
   v3_muls( clipdir, 0.001f, st->clip[dir] );

   for( int i=0; i<len; i++ )
   {
      u32 *ptri = &world.geo.indices[ geo[i]*3 ];
      for( int j=0; j<3; j++ )
         v3_copy( world.geo.verts[ptri[j]].co, tri[j] );
      
      if( !player_walkgrid_tri_walkable(ptri) )
         continue;

      for( int k=0; k<3; k++ )
      {
         int ia = k,
             ib = (k+1)%3;
         
         v3f v0, v1;
         v3_sub( tri[ia], pos, v0 );
         v3_sub( tri[ib], pos, v1 );

         if( (clipdir[2]*v0[0] - clipdir[0]*v0[2]) *
             (clipdir[2]*v1[0] - clipdir[0]*v1[2]) < 0.0f )
         {
            float da = v3_dot(v0,perp),
                  db = v3_dot(v1,perp),
                  d  = da-db,
                  qa = da/d;

            v3f p0;
            v3_muls( v1, qa, p0 );
            v3_muladds( p0, v0, 1.0f-qa, p0 );
            
            float h = v3_dot(p0,clipdir)/v3_dot(clipdir,clipdir);

            if( h >= max_dist && h <= 1.0f )
            {
               max_dist = h;
               float l = 1.0f/v3_length(clipdir);
               v3_muls( p0, l, st->clip[dir] );
            }
         }
      }
   }
}

static const struct conf
{
   struct confedge
   {  
      /* i: sample index
       * d: data index
       * a: axis index
       * o: the 'other' point to do a A/B test with
       *       if its -1, all AB is done.
       */
      int i0, i1, 
          d0, d1,
          a0, a1,
          o0, o1;
   }
   edges[2];
   int edge_count;
}
k_walkgrid_configs[16] = {
   {{},0},
   {{{ 3,3, 3,0, 1,0, -1,-1 }}, 1},
   {{{ 2,2, 1,3, 0,1, -1,-1 }}, 1},
   {{{ 2,3, 1,0, 0,0,  3,-1 }}, 1},

   {{{ 1,1, 0,1, 1,0, -1,-1 }}, 1},
   {{{ 3,3, 3,0, 1,0, -1,-1 },
     { 1,1, 0,1, 1,0, -1,-1 }}, 2},
   {{{ 1,2, 0,3, 1,1,  2,-1 }}, 1},
   {{{ 1,3, 0,0, 1,0,  2, 2 }}, 1},

   {{{ 0,0, 0,0, 0,1, -1,-1 }}, 1},
   {{{ 3,0, 3,0, 1,1,  0,-1 }}, 1},
   {{{ 2,2, 1,3, 0,1, -1,-1 },
     { 0,0, 0,0, 0,1, -1,-1 }}, 2},
   {{{ 2,0, 1,0, 0,1,  3, 3 }}, 1},

   {{{ 0,1, 0,1, 0,0,  1,-1 }}, 1},
   {{{ 3,1, 3,1, 1,0,  0, 0 }}, 1},
   {{{ 0,2, 0,3, 0,1,  1, 1 }}, 1},
   {{},0},
};

/* 
 * Get a buffer of edges from cell location
 */
static const struct conf *player_walkgrid_conf( struct walkgrid *wg, 
      v2i cell,
      struct grid_sample *corners[4] )
{
   corners[0] = &wg->samples[cell[1]  ][cell[0]  ];
   corners[1] = &wg->samples[cell[1]+1][cell[0]  ];
   corners[2] = &wg->samples[cell[1]+1][cell[0]+1];
   corners[3] = &wg->samples[cell[1]  ][cell[0]+1];

   u32 vd0 = corners[0]->type == k_sample_type_valid,
       vd1 = corners[1]->type == k_sample_type_valid,
       vd2 = corners[2]->type == k_sample_type_valid,
       vd3 = corners[3]->type == k_sample_type_valid,
       config = (vd0<<3) | (vd1<<2) | (vd2<<1) | vd3;

   return &k_walkgrid_configs[ config ];
}

static void player_walkgrid_floor(v3f pos)
{
   v3_muls( pos, 1.0f/k_gridscale, pos );
   v3_floor( pos, pos );
   v3_muls( pos, k_gridscale, pos );
}

/* 
 * Computes the barycentric coordinate of location on a triangle (vertical),
 * then sets the Y position to the interpolation of the three points
 */
static void player_walkgrid_stand_tri( v3f a, v3f b, v3f c, v3f pos )
{
   v3f v0,v1,v2; 
   v3_sub( b, a, v0 );
   v3_sub( c, a, v1 );
   v3_sub( pos, a, v2 );

   float d = v0[0]*v1[2] - v1[0]*v0[2],
         v = (v2[0]*v1[2] - v1[0]*v2[2]) / d,
         w = (v0[0]*v2[2] - v2[0]*v0[2]) / d,
         u = 1.0f - v - w;

   vg_line( pos, a, 0xffff0000 );
   vg_line( pos, b, 0xff00ff00 );
   vg_line( pos, c, 0xff0000ff );
   pos[1] = u*a[1] + v*b[1] + w*c[1];
}

/*
 * Get the minimum time value of pos+dir until a cell edge
 *
 * t[0] -> t[3] are the individual time values
 * t[5] & t[6]  are the maximum axis values
 * t[6] is the minimum value
 *
 */
static void player_walkgrid_min_cell( float t[7], v2f pos, v2f dir )
{
   v2f frac = { 1.0f/dir[0], 1.0f/dir[1] };

   t[0] = 999.9f;
   t[1] = 999.9f;
   t[2] = 999.9f;
   t[3] = 999.9f;
   
   if( fabsf(dir[0]) > 0.0001f )
   {
      t[0] = (0.0f-pos[0]) * frac[0];
      t[1] = (1.0f-pos[0]) * frac[0];
   }
   if( fabsf(dir[1]) > 0.0001f )
   {
      t[2] = (0.0f-pos[1]) * frac[1];
      t[3] = (1.0f-pos[1]) * frac[1];
   }

   t[4] = vg_maxf(t[0],t[1]);
   t[5] = vg_maxf(t[2],t[3]);
   t[6] = vg_minf(t[4],t[5]);
}

static void player_walkgrid_iter(struct walkgrid *wg, int iter)
{

   /*
    * For each walkgrid iteration we are stepping through cells and determining
    * the intersections with the grid, and any edges that are present
    */

   u32 icolours[] = { 0xffff00ff, 0xff00ffff, 0xffffff00 };
   
   v3f pa, pb, pc, pd, pl0, pl1;
   pa[0] = wg->region[0][0] + (float)wg->cell_id[0] *k_gridscale;
   pa[1] = (wg->region[0][1] + wg->region[1][1]) * 0.5f + k_gridscale;
   pa[2] = wg->region[0][2] + (float)wg->cell_id[1] *k_gridscale;
#if 0
   pb[0] = pa[0];
   pb[1] = pa[1];
   pb[2] = pa[2] + k_gridscale;
   pc[0] = pa[0] + k_gridscale;
   pc[1] = pa[1];
   pc[2] = pa[2] + k_gridscale;
   pd[0] = pa[0] + k_gridscale;
   pd[1] = pa[1];
   pd[2] = pa[2];
   /* if you want to draw the current cell */
   vg_line( pa, pb, 0xff00ffff );
   vg_line( pb, pc, 0xff00ffff );
   vg_line( pc, pd, 0xff00ffff );
   vg_line( pd, pa, 0xff00ffff );
#endif
   pl0[0] = pa[0] + wg->pos[0]*k_gridscale;
   pl0[1] = pa[1];
   pl0[2] = pa[2] + wg->pos[1]*k_gridscale;

   /* 
    * If there are edges present, we need to create a 'substep' event, where
    * we find the intersection point, find the fully resolved position,
    * then the new pos dir is the intersection->resolution
    *
    * the resolution is applied in non-discretized space in order to create a 
    * suitable vector for finding outflow, we want it to leave the cell so it 
    * can be used by the quad
    */

   v2f pos, dir;
   v2_copy( wg->pos, pos );
   v2_muls( wg->dir, wg->move, dir );

   struct grid_sample *corners[4];
   v2f corners2d[4] = {{0.0f,0.0f},{0.0f,1.0f},{1.0f,1.0f},{1.0f,0.0f}};
   const struct conf *conf = player_walkgrid_conf( wg, wg->cell_id, corners );
   
   float t[7];
   player_walkgrid_min_cell( t, pos, dir );

   for( int i=0; i<conf->edge_count; i++ )
   {
      const struct confedge *edge = &conf->edges[i];

      v2f e0, e1, n, r, target, res, tangent;
      e0[0] = corners2d[edge->i0][0] + corners[edge->d0]->clip[edge->a0][0];
      e0[1] = corners2d[edge->i0][1] + corners[edge->d0]->clip[edge->a0][2];
      e1[0] = corners2d[edge->i1][0] + corners[edge->d1]->clip[edge->a1][0];
      e1[1] = corners2d[edge->i1][1] + corners[edge->d1]->clip[edge->a1][2];
      
      v3f pe0 = { pa[0] + e0[0]*k_gridscale,
                  pa[1],
                  pa[2] + e0[1]*k_gridscale };
      v3f pe1 = { pa[0] + e1[0]*k_gridscale,
                  pa[1],
                  pa[2] + e1[1]*k_gridscale };

      v2_sub( e1, e0, tangent );
      n[0] = -tangent[1];
      n[1] =  tangent[0];
      v2_normalize( n );

      /*
       * If we find ourselfs already penetrating the edge, move back out a
       * little
       */
      v2_sub( e0, pos, r );
      float p1 = v2_dot(r,n);

      if( -p1 < 0.0001f )
      {
         v2_muladds( pos, n, p1+0.0001f, pos );
         v2_copy( pos, wg->pos );
         v3f p_new = { pa[0] + pos[0]*k_gridscale,
                       pa[1],
                       pa[2] + pos[1]*k_gridscale };
         v3_copy( p_new, pl0 );
      }
      
      v2_add( pos, dir, target );

      v2f v1, v2, v3;
      v2_sub( e0, pos, v1 );
      v2_sub( target, pos, v2 );

      v2_copy( n, v3 );

      v2_sub( e0, target, r );
      float p = v2_dot(r,n),
            t1 = v2_dot(v1,v3)/v2_dot(v2,v3);

      if( t1 < t[6] && t1 > 0.0f && -p < 0.001f )
      {
         v2_muladds( target, n, p+0.0001f, res );

         v2f intersect;
         v2_muladds( pos, dir, t1, intersect );
         v2_copy( intersect, pos );
         v2_sub( res, intersect, dir );

         v3f p_res = { pa[0] + res[0]*k_gridscale,
                       pa[1],
                       pa[2] + res[1]*k_gridscale };
         v3f p_int = { pa[0] + intersect[0]*k_gridscale,
                       pa[1],
                       pa[2] + intersect[1]*k_gridscale };

         vg_line( pl0, p_int, icolours[iter%3] );
         v3_copy( p_int, pl0 );
         v2_copy( pos, wg->pos );

         player_walkgrid_min_cell( t, pos, dir );
      }
   }

   /* 
    * Compute intersection with grid cell moving outwards
    */
   t[6] = vg_minf( t[6], 1.0f );
   
   pl1[0] = pl0[0] + dir[0]*k_gridscale*t[6];
   pl1[1] = pl0[1];
   pl1[2] = pl0[2] + dir[1]*k_gridscale*t[6];
   vg_line( pl0, pl1, icolours[iter%3] );
   
   if( t[6] < 1.0f )
   {
      /*
       * To figure out what t value created the clip so we know which edge 
       * to wrap around
       */

      if( t[4] < t[5] )
      {
         wg->pos[1] = pos[1] + dir[1]*t[6];

         if( t[0] > t[1] ) /* left edge */
         {
            wg->pos[0] = 0.9999f;
            wg->cell_id[0] --;

            if( wg->cell_id[0] == 0 )
               wg->move = -1.0f;
         }
         else /* Right edge */
         {
            wg->pos[0] = 0.0001f;
            wg->cell_id[0] ++;

            if( wg->cell_id[0] == WALKGRID_SIZE-2 )
               wg->move = -1.0f;
         }
      }
      else
      {
         wg->pos[0] = pos[0] + dir[0]*t[6];

         if( t[2] > t[3] ) /* bottom edge */
         {
            wg->pos[1] = 0.9999f;
            wg->cell_id[1] --;

            if( wg->cell_id[1] == 0 )
               wg->move = -1.0f;
         }
         else /* top edge */
         {
            wg->pos[1] = 0.0001f;
            wg->cell_id[1] ++;

            if( wg->cell_id[1] == WALKGRID_SIZE-2 )
               wg->move = -1.0f;
         }
      }

      wg->move -= t[6];
   }
   else
   {
      v2_muladds( wg->pos, dir, wg->move, wg->pos );
      wg->move = 0.0f;
   }
}

static void player_walkgrid_stand_cell(struct walkgrid *wg)
{
   /*
    * NOTE: as opposed to the other function which is done in discretized space
    *       this use a combination of both.
    */

   v3f world;
   world[0] = wg->region[0][0]+((float)wg->cell_id[0]+wg->pos[0])*k_gridscale;
   world[1] = player.rb.co[1];
   world[2] = wg->region[0][2]+((float)wg->cell_id[1]+wg->pos[1])*k_gridscale;

   struct grid_sample *corners[4];
   const struct conf *conf = player_walkgrid_conf( wg, wg->cell_id, corners );

   if( conf != k_walkgrid_configs )
   {
      if( conf->edge_count == 0 )
      {
         v3f v0;

         /* Split the basic quad along the shortest diagonal */
         if( fabsf(corners[2]->pos[1] - corners[0]->pos[1]) < 
             fabsf(corners[3]->pos[1] - corners[1]->pos[1]) )
         {
            vg_line( corners[2]->pos, corners[0]->pos, 0xffaaaaaa );
            
            if( wg->pos[0] > wg->pos[1] )
               player_walkgrid_stand_tri( corners[0]->pos,
                                          corners[3]->pos,
                                          corners[2]->pos, world );
            else
               player_walkgrid_stand_tri( corners[0]->pos,
                                          corners[2]->pos,
                                          corners[1]->pos, world );
         }
         else
         {
            vg_line( corners[3]->pos, corners[1]->pos, 0xffaaaaaa );

            if( wg->pos[0] < 1.0f-wg->pos[1] )
               player_walkgrid_stand_tri( corners[0]->pos,
                                          corners[3]->pos,
                                          corners[1]->pos, world );
            else
               player_walkgrid_stand_tri( corners[3]->pos,
                                          corners[2]->pos,
                                          corners[1]->pos, world );
         }
      }
      else
      {
         for( int i=0; i<conf->edge_count; i++ )
         {
            const struct confedge *edge = &conf->edges[i];

            v3f p0, p1;
            v3_muladds( corners[edge->i0]->pos, 
                        corners[edge->d0]->clip[edge->a0], k_gridscale, p0 );
            v3_muladds( corners[edge->i1]->pos, 
                        corners[edge->d1]->clip[edge->a1], k_gridscale, p1 );

            /* 
             * Find penetration distance between player position and the edge
             */

            v2f normal = { -(p1[2]-p0[2]), p1[0]-p0[0] },
                   rel = { world[0]-p0[0], world[2]-p0[2] };

            if( edge->o0 == -1 )
            {
               /* No subregions (default case), just use triangle created by
                * i0, e0, e1 */
               player_walkgrid_stand_tri( corners[edge->i0]->pos,
                                          p0,
                                          p1, world );
            }
            else
            {
               /* 
                * Test if we are in the first region, which is
                * edge.i0, edge.e0, edge.o0,
                */
               v3f v0, ref;
               v3_sub( p0, corners[edge->o0]->pos, ref );
               v3_sub( world, corners[edge->o0]->pos, v0 );

               vg_line( corners[edge->o0]->pos, p0, 0xffffff00 );
               vg_line( corners[edge->o0]->pos, world, 0xff000000 );
               
               if( ref[0]*v0[2] - ref[2]*v0[0] < 0.0f )
               {
                  player_walkgrid_stand_tri( corners[edge->i0]->pos,
                                             p0,
                                             corners[edge->o0]->pos, world );
               }
               else
               {
                  if( edge->o1 == -1 )
                  {
                     /*
                      * No other edges mean we just need to use the opposite
                      *
                      * e0, e1, o0 (in our case, also i1)
                      */
                     player_walkgrid_stand_tri( p0,
                                                p1,
                                                corners[edge->o0]->pos, world );
                  }
                  else
                  {
                     /*
                      * Note: this v0 calculation can be ommited with the 
                      *       current tileset.
                      *
                      *       the last two triangles we have are:
                      *         e0, e1, o1
                      *       and
                      *         e1, i1, o1
                      */
                     v3_sub( p1, corners[edge->o1]->pos, ref );
                     v3_sub( world, corners[edge->o1]->pos, v0 );
                     vg_line( corners[edge->o1]->pos, p1, 0xff00ffff );

                     if( ref[0]*v0[2] - ref[2]*v0[0] < 0.0f )
                     {
                        player_walkgrid_stand_tri( p0,
                                                   p1,
                                                   corners[edge->o1]->pos,
                                                   world );
                     }
                     else
                     {
                        player_walkgrid_stand_tri( p1,
                                                   corners[edge->i1]->pos,
                                                   corners[edge->o1]->pos,
                                                   world );
                     }
                  }
               }
            }
         }
      }
   }

   v3_copy( world, player.rb.co );
}

static void player_walkgrid_getsurface(void)
{
   float const k_stepheight = 0.5f;
   float const k_miny = 0.6f;
   float const k_height = 1.78f;
   float const k_region_size = (float)WALKGRID_SIZE/2.0f * k_gridscale;

   static struct walkgrid wg;

   v3f cell;
   v3_copy( player.rb.co, cell );
   player_walkgrid_floor( cell );

   v3_muladds( cell, (v3f){-1.0f,-1.0f,-1.0f}, k_region_size, wg.region[0] );
   v3_muladds( cell, (v3f){ 1.0f, 1.0f, 1.0f}, k_region_size, wg.region[1] );

   
   /* 
    * Create player input vector
    */
   v3f delta = {0.0f,0.0f,0.0f};
   v3f fwd = { -sinf(-player.angles[0]), 0.0f, -cosf(-player.angles[0]) },
       side = { -fwd[2], 0.0f, fwd[0] };

   /* Temp */
   if( !vg_console_enabled() )
   {
      if( glfwGetKey( vg_window, GLFW_KEY_W ) )
         v3_muladds( delta, fwd,  ktimestep*k_walkspeed, delta );
      if( glfwGetKey( vg_window, GLFW_KEY_S ) )
         v3_muladds( delta, fwd, -ktimestep*k_walkspeed, delta );

      if( glfwGetKey( vg_window, GLFW_KEY_A ) )
         v3_muladds( delta, side, -ktimestep*k_walkspeed, delta );
      if( glfwGetKey( vg_window, GLFW_KEY_D ) )
         v3_muladds( delta, side,  ktimestep*k_walkspeed, delta );

      v3_muladds( delta, fwd, 
            vg_get_axis("vertical")*-ktimestep*k_walkspeed, delta );
      v3_muladds( delta, side, 
            vg_get_axis("horizontal")*ktimestep*k_walkspeed, delta );
   }

   /* 
    * Create our move in grid space
    */
   wg.dir[0] = delta[0] * (1.0f/k_gridscale);
   wg.dir[1] = delta[2] * (1.0f/k_gridscale);
   wg.move = 1.0f;

   v2f region_pos = 
   {
      (player.rb.co[0] - wg.region[0][0]) * (1.0f/k_gridscale),
      (player.rb.co[2] - wg.region[0][2]) * (1.0f/k_gridscale)
   };
   v2f region_cell_pos;
   v2_floor( region_pos, region_cell_pos );
   v2_sub( region_pos, region_cell_pos, wg.pos );

   wg.cell_id[0] = region_cell_pos[0];
   wg.cell_id[1] = region_cell_pos[1];

   for(int y=0; y<WALKGRID_SIZE; y++ )
   {
      for(int x=0; x<WALKGRID_SIZE; x++ )
      {
         struct grid_sample *s = &wg.samples[y][x];
         v3_muladds( wg.region[0], (v3f){ x, 0, y }, k_gridscale, s->pos );
         s->state = k_traverse_none;
         s->type = k_sample_type_air;
         v3_zero( s->clip[0] );
         v3_zero( s->clip[1] );
      }
   }

   v2i border[WALKGRID_SIZE*WALKGRID_SIZE];
   v2i *cborder = border;
   u32 border_length = 1;

   struct grid_sample *base = NULL; 

   v2i starters[] = {{0,0},{1,1},{0,1},{1,0}};

   for( int i=0;i<4;i++ )
   {
      v2i test;
      v2i_add( wg.cell_id, starters[i], test );
      v2i_copy( test, border[0] );
      base = &wg.samples[test[1]][test[0]];

      base->pos[1] = cell[1];
      player_walkgrid_samplepole( base );

      if( base->type == k_sample_type_valid )
         break;
      else
         base->type = k_sample_type_air;
   }
   
   vg_line_pt3( base->pos, 0.1f, 0xffffffff );

   int iter = 0;

   while( border_length )
   {
      v2i directions[] = {{1,0},{0,1},{-1,0},{0,-1}};

      v2i *old_border = cborder;
      int  len = border_length;

      border_length = 0;
      cborder = old_border+len;

      for( int i=0; i<len; i++ )
      {
         v2i co;
         v2i_copy( old_border[i], co );
         struct grid_sample *sa = &wg.samples[co[1]][co[0]];

         for( int j=0; j<4; j++ )
         {
            v2i newp;
            v2i_add( co, directions[j], newp );

            if( newp[0] < 0 || newp[1] < 0 || 
                newp[0] == WALKGRID_SIZE || newp[1] == WALKGRID_SIZE )
               continue;

            struct grid_sample *sb = &wg.samples[newp[1]][newp[0]];
            enum traverse_state thismove = j%2==0? 1: 2;

            if( (sb->state & thismove) == 0x00 || 
                  sb->type == k_sample_type_air )
            {
               sb->pos[1] = sa->pos[1];

               player_walkgrid_samplepole( sb );

               if( sb->type != k_sample_type_air )
               {
                  /* 
                   * Need to do a blocker pass
                   */

                  struct grid_sample *store = (j>>1 == 0)? sa: sb;
                  player_walkgrid_clip_blocker( sa, sb, store, j%2 );
                  

                  if( sb->type != k_sample_type_air )
                  {
                     vg_line( sa->pos, sb->pos, 0xffffffff );
                  
                     if( sb->state == k_traverse_none )
                        v2i_copy( newp, cborder[ border_length ++ ] );
                  }
                  else
                  {
                     v3f p1;
                     v3_muladds( sa->pos, store->clip[j%2], k_gridscale, p1 );
                     vg_line( sa->pos, p1, 0xffffffff );
                  }
               }
               else
               {
                  /* 
                   * A clipping pass is now done on the edge of the walkable
                   * surface
                   */
                  
                  struct grid_sample *store = (j>>1 == 0)? sa: sb;
                  player_walkgrid_clip_edge( sa, sb, store, j%2 );

                  v3f p1;
                  v3_muladds( sa->pos, store->clip[j%2], k_gridscale, p1 );
                  vg_line( sa->pos, p1, 0xffffffff );
               }

               sb->state |= thismove;
            }
         }

         sa->state = k_traverse_h|k_traverse_v;
      }

      iter ++;
      if( iter == walk_grid_iterations )
         break;
   }

   /* Draw connections */
   struct grid_sample *corners[4];
   for( int x=0; x<WALKGRID_SIZE-1; x++ )
   {
      for( int z=0; z<WALKGRID_SIZE-1; z++ )
      {
         const struct conf *conf = 
            player_walkgrid_conf( &wg, (v2i){x,z}, corners );

         for( int i=0; i<conf->edge_count; i++ )
         {
            const struct confedge *edge = &conf->edges[i];

            v3f p0, p1;
            v3_muladds( corners[edge->i0]->pos, 
                    corners[edge->d0]->clip[edge->a0], k_gridscale, p0 );
            v3_muladds( corners[edge->i1]->pos, 
                    corners[edge->d1]->clip[edge->a1], k_gridscale, p1 );

            vg_line( p0, p1, 0xff0000ff );
         }
      }
   }

   /*
    * Commit player movement into the grid 
    */
   
   if( v3_length2(delta) <= 0.00001f )
      return;
   
   int i=0;
   for(; i<8 && wg.move > 0.001f; i++ )
      player_walkgrid_iter( &wg, i );

   player_walkgrid_stand_cell( &wg );
}

static void player_walkgrid(void)
{
   player_walkgrid_getsurface();
   
   m4x3_mulv( player.rb.to_world, (v3f){0.0f,1.8f,0.0f}, player.camera_pos );
   player_mouseview();
   rb_update_transform( &player.rb );
}

/*
 * Animation
 */

static void player_animate(void)
{
   /* Camera position */
   v3_sub( player.rb.v, player.v_last, player.a );
   v3_copy( player.rb.v, player.v_last );

   v3_add( player.m, player.a, player.m );
   v3_lerp( player.m, (v3f){0.0f,0.0f,0.0f}, 0.1f, player.m );

   player.m[0] = vg_clampf( player.m[0], -2.0f, 2.0f );
   player.m[1] = vg_clampf( player.m[1], -2.0f, 2.0f );
   player.m[2] = vg_clampf( player.m[2], -2.0f, 2.0f );
   v3_lerp( player.bob, player.m, 0.2f, player.bob );

   /* Head */
   float lslip = fabsf(player.slip);

   float kheight = 2.0f,
         kleg = 0.6f;

   v3f offset;
   v3_zero( offset );
   m3x3_mulv( player.rb.to_local, player.bob, offset );

   static float speed_wobble = 0.0f, speed_wobble_2 = 0.0f;
   
   float kickspeed = vg_clampf(v3_length(player.rb.v)*(1.0f/40.0f), 0.0f, 1.0f);
   float kicks = (vg_randf()-0.5f)*2.0f*kickspeed;
   float sign = vg_signf( kicks );
   speed_wobble = vg_lerpf( speed_wobble, kicks*kicks*sign, 0.1f );
   speed_wobble_2 = vg_lerpf( speed_wobble_2, speed_wobble, 0.04f );

   offset[0] *= 0.26f;
   offset[0] += speed_wobble_2*3.0f;

   offset[1] *= -0.3f;
   offset[2] *= 0.01f;

   offset[0] = vg_clampf( offset[0], -0.8f, 0.8f );
   offset[1] = vg_clampf( offset[1], -0.5f, 0.0f );
   offset[1] = 0.0f;

   /* 
    * Animation blending
    * ===========================================
    */

   /* scalar blending information */
   float speed = v3_length( player.rb.v );
   
   /* sliding */
   {
      float desired = vg_clampf( lslip, 0.0f, 1.0f );
      player.fslide = vg_lerpf( player.fslide, desired, 0.04f );
   }
   
   /* movement information */
   {
      float dirz = player.reverse > 0.0f? 0.0f: 1.0f,
            dirx = player.slip < 0.0f?    0.0f: 1.0f,
            fly  = player.in_air?         1.0f: 0.0f;

      player.fdirz = vg_lerpf( player.fdirz, dirz, 0.04f );
      player.fdirx = vg_lerpf( player.fdirx, dirx, 0.01f );
      player.ffly  = vg_lerpf( player.ffly, fly, 0.04f );
   }
   
   struct skeleton *sk = &player.mdl.sk;

   mdl_keyframe apose[32], bpose[32];
   mdl_keyframe ground_pose[32];
   {
      /* when the player is moving fast he will crouch down a little bit */
      float stand = 1.0f - vg_clampf( speed * 0.03f, 0.0f, 1.0f );
      player.fstand = vg_lerpf( player.fstand, stand, 0.1f );

      /* stand/crouch */
      float dir_frame   = player.fdirz * (15.0f/30.0f),
            stand_blend = offset[1]*-2.0f;
      
      skeleton_sample_anim( sk, player.mdl.anim_stand, dir_frame, apose );
      skeleton_sample_anim( sk, player.mdl.anim_highg, dir_frame, bpose );
      skeleton_lerp_pose( sk, apose, bpose, stand_blend, apose );

      /* sliding */
      float slide_frame = player.fdirx * (15.0f/30.0f);
      skeleton_sample_anim( sk, player.mdl.anim_slide, slide_frame, bpose );
      skeleton_lerp_pose( sk, apose, bpose, player.fslide, apose );

      /* pushing */
      player.fpush = vg_lerpf( player.fpush, player.pushing, 0.1f );

      float pt = player.push_time;
      if( player.reverse > 0.0f )
         skeleton_sample_anim( sk, player.mdl.anim_push, pt, bpose );
      else
         skeleton_sample_anim( sk, player.mdl.anim_push_reverse, pt, bpose );

      skeleton_lerp_pose( sk, apose, bpose, player.fpush, apose );

      /* trick setup */
      float setup_frame = player.jump * (12.0f/30.0f),
            setup_blend = vg_minf( player.jump*5.0f, 1.0f );
      
      float jump_frame = (vg_time - player.jump_time) + (12.0f/30.0f);
      if( jump_frame >= (12.0f/30.0f) && jump_frame <= (40.0f/30.0f) )
         setup_frame = jump_frame;

      skeleton_sample_anim_clamped( sk, player.mdl.anim_ollie, 
                                       setup_frame, bpose );
      skeleton_lerp_pose( sk, apose, bpose, setup_blend, ground_pose );
   }
   
   mdl_keyframe air_pose[32];
   {
      float target = -vg_get_axis("horizontal");
      player.fairdir = vg_lerpf( player.fairdir, target, 0.04f );
      
      float air_frame = (player.fairdir*0.5f+0.5f) * (15.0f/30.0f);
      
      skeleton_sample_anim( sk, player.mdl.anim_air, air_frame, air_pose );
   }

   skeleton_lerp_pose( sk, ground_pose, air_pose, player.ffly, apose );

   /* additive effects */
   apose[player.mdl.id_hip-1].co[0] += offset[0];
   apose[player.mdl.id_hip-1].co[2] += offset[2];
   apose[player.mdl.id_ik_hand_l-1].co[0] += offset[0];
   apose[player.mdl.id_ik_hand_l-1].co[2] += offset[2];
   apose[player.mdl.id_ik_hand_r-1].co[0] += offset[0];
   apose[player.mdl.id_ik_hand_r-1].co[2] += offset[2];
   apose[player.mdl.id_ik_elbow_l-1].co[0] += offset[0];
   apose[player.mdl.id_ik_elbow_l-1].co[2] += offset[2];
   apose[player.mdl.id_ik_elbow_r-1].co[0] += offset[0];
   apose[player.mdl.id_ik_elbow_r-1].co[2] += offset[2];

   skeleton_apply_pose( &player.mdl.sk, apose, k_anim_apply_defer_ik );
   skeleton_apply_ik_pass( &player.mdl.sk );
   skeleton_apply_pose( &player.mdl.sk, apose, k_anim_apply_deffered_only );

   v3_copy( player.mdl.sk.final_mtx[player.mdl.id_head-1][3], 
               player.mdl.cam_pos );
   skeleton_apply_inverses( &player.mdl.sk );
   skeleton_apply_transform( &player.mdl.sk, player.rb.to_world );

   skeleton_debug( &player.mdl.sk );
}

static void player_camera_update(void)
{
   /* Update camera matrices */
   m4x3_identity( player.camera );
   m4x3_rotate_y( player.camera, -player.angles[0] );
   m4x3_rotate_x( player.camera, -player.angles[1] );
   v3_copy( player.camera_pos, player.camera[3] );
   m4x3_invert_affine( player.camera, player.camera_inverse );
}

static void player_animate_death_cam(void)
{
#if 0
   v3f delta;
   v3f head_pos;
   v3_copy( player.mdl.ragdoll[k_chpart_head].co, head_pos );

   v3_sub( head_pos, player.camera_pos, delta );
   v3_normalize( delta );

   v3f follow_pos;
   v3_muladds( head_pos, delta, -2.5f, follow_pos );
   v3_lerp( player.camera_pos, follow_pos, 0.1f, player.camera_pos );

   /* 
    * Make sure the camera stays above the ground
    */
   v3f min_height = {0.0f,1.0f,0.0f};

   v3f sample;
   v3_add( player.camera_pos, min_height, sample );
   ray_hit hit;
   hit.dist = min_height[1]*2.0f;

   if( ray_world( sample, (v3f){0.0f,-1.0f,0.0f}, &hit ))
      v3_add( hit.pos, min_height, player.camera_pos );

   player.camera_pos[1] = 
      vg_maxf( wrender.height + 2.0f, player.camera_pos[1] );

   player.angles[0] = atan2f( delta[0], -delta[2] ); 
   player.angles[1] = -asinf( delta[1] );
#endif
}

static void player_animate_camera(void)
{
   static v3f lerp_cam = {0.0f,0.0f,0.0f};
   v3f offs = { -0.4f, 0.15f, 0.0f };

   v3_lerp( lerp_cam, player.mdl.cam_pos, 0.8f, lerp_cam );
   v3_add( lerp_cam, offs, offs );
   m4x3_mulv( player.rb.to_world, offs, player.camera_pos );
   
   /* Look angles */
   v3_lerp( player.vl, player.rb.v, 0.05f, player.vl );

   float yaw = atan2f(  player.vl[0], -player.vl[2] ),
       pitch = atan2f( -player.vl[1], 
             sqrtf(
               player.vl[0]*player.vl[0] + player.vl[2]*player.vl[2]
             )) * 0.7f;

   player.angles[0] = yaw;
   player.angles[1] = pitch + 0.30f;

   /* Camera shake */
   static v2f shake_damp = {0.0f,0.0f};
   v2f shake = { vg_randf()-0.5f, vg_randf()-0.5f };
   v2_muls( shake, v3_length(player.rb.v)*0.3f 
                        * (1.0f+fabsf(player.slip)), shake);

   v2_lerp( shake_damp, shake, 0.01f, shake_damp );
   shake_damp[0] *= 0.2f;

   v2_muladds( player.angles, shake_damp, 0.1f, player.angles );
}

/* 
 * Audio
 */
static void player_audio(void)
{
   float speed = vg_minf(v3_length( player.rb.v )*0.1f,1.0f),
         attn = v3_dist( player.rb.co, player.camera[3] )+1.0f;
   attn = (1.0f/(attn*attn)) * speed;

   static float air = 0.0f;
   air = vg_lerpf(air, player.in_air? 1.0f: 0.0f, 0.7f);
   
   v3f ears = { 1.0f,0.0f,0.0f };
   v3f delta;

   v3_sub( player.rb.co, player.camera[3], delta );
   v3_normalize( delta );
   m3x3_mulv( player.camera, ears, ears );

   float pan = v3_dot( ears, delta );
   audio_player0.pan = pan;
   audio_player1.pan = pan;
   audio_player2.pan = pan;

   if( freecam )
   {
      audio_player0.vol = 0.0f;
      audio_player1.vol = 0.0f;
      audio_player2.vol = 0.0f;
   }
   else
   {
      if( player.is_dead )
      {
         audio_player0.vol = 0.0f;
         audio_player1.vol = 0.0f;
         audio_player2.vol = 0.0f;
      }
      else
      {
         float slide = vg_clampf( fabsf(player.slip), 0.0f, 1.0f );
         audio_player0.vol = (1.0f-air)*attn*(1.0f-slide);
         audio_player1.vol =       air *attn;
         audio_player2.vol = (1.0f-air)*attn*slide;
      }
   }
}

/*
 * Public Endpoints
 */
static float *player_cam_pos(void)
{
   return player.camera_pos;
}

static int reset_player( int argc, char const *argv[] )
{
   struct respawn_point *rp = NULL, *r;

   if( argc == 1 )
   {
      for( int i=0; i<world.spawn_count; i++ )
      {
         r = &world.spawns[i];
         if( !strcmp( r->name, argv[0] ) )
         {
            rp = r;
            break;
         }
      }

      if( !rp )
         vg_warn( "No spawn named '%s'\n", argv[0] );
   }

   if( !rp )
   {
      float min_dist = INFINITY;

      for( int i=0; i<world.spawn_count; i++ )
      {
         r = &world.spawns[i];
         float d = v3_dist2( r->co, player.rb.co );
         
         vg_info( "Dist %s : %f\n", r->name, d );
         if( d < min_dist )
         {
            min_dist = d;
            rp = r;
         }
      }
   }

   if( !rp )
   {
      vg_error( "No spawn found\n" );
      if( !world.spawn_count )
         return 0;

      rp = &world.spawns[0];
   }

   v4_copy( rp->q, player.rb.q );
   v3_copy( rp->co, player.rb.co );

   player.vswitch = 1.0f;
   player.slip_last = 0.0f;
   player.is_dead = 0;
   player.in_air = 1;
   m3x3_identity( player.vr );

   player.mdl.shoes[0] = 1;
   player.mdl.shoes[1] = 1;
   
   rb_update_transform( &player.rb );
   m3x3_mulv( player.rb.to_world, (v3f){ 0.0f, 0.0f, -1.2f }, player.rb.v );

   player.rb_gate_frame = player.rb;
   return 1;
}

static void player_update(void)
{
   for( int i=0; i<player.land_log_count; i++ )
      draw_cross( player.land_target_log[i], 
            player.land_target_colours[i], 0.25f);

   if( vg_get_axis("grabl")>0.0f)
   {
      player.rb = player.rb_gate_frame;
      player.is_dead = 0;
      player.in_air = 1;
      m3x3_identity( player.vr );

      player.mdl.shoes[0] = 1;
      player.mdl.shoes[1] = 1;

      world_routes_notify_reset();
   }

   if( vg_get_button_down( "switchmode" ) )
   {
      player.on_board ^= 0x1;
   }

   if( player.is_dead )
   {
      character_ragdoll_iter( &player.mdl );
      character_debug_ragdoll( &player.mdl );

      if( !freecam )
         player_animate_death_cam();
   }
   else
   {
      if( player.on_board )
      {
         player_do_motion();
         player_animate();

         if( !freecam )
            player_animate_camera();
      }
      else
      {
         player_walkgrid();
      }
   }

   if( freecam )
      player_freecam();

   player_camera_update();
   player_audio();
}

static void draw_player(void)
{
   /* Draw */
#if 0
   m4x3_copy( player.rb.to_world, player.mdl.mroot );

   if( player.is_dead )
      character_mimic_ragdoll( &player.mdl );
   else
      character_eval( &player.mdl );

   float opacity = 1.0f-player.air_blend;
   if( player.is_dead )
      opacity = 0.0f;

   character_draw( &player.mdl, opacity, player.camera );
#endif

   shader_viewchar_use();
   vg_tex2d_bind( &tex_characters, 0 );
   shader_viewchar_uTexMain( 0 );
   shader_viewchar_uCamera( player.camera[3] );
   shader_viewchar_uPv( vg_pv );
   shader_link_standard_ub( _shader_viewchar.id, 2 );
   glUniformMatrix4x3fv( _uniform_viewchar_uTransforms, 
                         player.mdl.sk.bone_count,
                         0,
                         (float *)player.mdl.sk.final_mtx );
   
   mesh_bind( &player.mdl.mesh );
   mesh_draw( &player.mdl.mesh );
}

#endif /* PLAYER_H */