player_walkgrid.h

   1 #ifndef PLAYER_WALKGRID_H
   2 #define PLAYER_WALKGRID_H
   3
   4 #include "common.h"
   5 #include "player.h"
   6
   7 /*
   8  * Walkgrid implementation,
   9  *  loosely based of cmuratoris youtube video 'Killing the Walkmonster'
  10  */
  11
  12 #define WALKGRID_SIZE 16
  13 struct walkgrid
  14 {
  15    struct grid_sample
  16    {
  17       enum sample_type
  18       {
  19          k_sample_type_air,      /* Nothing was hit. */
  20          k_sample_type_invalid,  /* The point is invalid, but there is a sample
  21                                     underneath that can be used */
  22          k_sample_type_valid,    /* This point is good */
  23       }
  24       type;
  25
  26       v3f clip[2];
  27       v3f pos;
  28
  29       enum traverse_state
  30       {
  31          k_traverse_none = 0x00,
  32          k_traverse_h    = 0x01,
  33          k_traverse_v    = 0x02
  34       }
  35       state;
  36    }
  37    samples[WALKGRID_SIZE][WALKGRID_SIZE];
  38
  39    boxf region;
  40
  41    float move; /* Current amount of movement we have left to apply */
  42    v2f dir;    /* The movement delta */
  43    v2i cell_id;/* Current cell */
  44    v2f pos;    /* Local position (in cell) */
  45    float h;
  46 };
  47
  48 static int player_walkgrid_tri_walkable( u32 tri[3] )
  49 {
  50    return tri[0] > world.sm_geo_std_oob.vertex_count;
  51 }
  52
  53 /*
  54  * Get a sample at this pole location, will return 1 if the sample is valid,
  55  * and pos will be updated to be the intersection location.
  56  */
  57 static void player_walkgrid_samplepole( struct grid_sample *s )
  58 {
  59    boxf region = {{ s->pos[0] -0.01f, s->pos[1] - 4.0f, s->pos[2] -0.01f},
  60                   { s->pos[0] +0.01f, s->pos[1] + 4.0f, s->pos[2] +0.01f}};
  61
  62    u32 geo[256];
  63    v3f tri[3];
  64    int len = bh_select( &world.geo.bhtris, region, geo, 256 );
  65
  66    const float k_minworld_y = -2000.0f;
  67
  68    float walk_height = k_minworld_y,
  69          block_height = k_minworld_y;
  70
  71    s->type = k_sample_type_air;
  72
  73    for( int i=0; i<len; i++ )
  74    {
  75       u32 *ptri = &world.geo.indices[ geo[i]*3 ];
  76
  77       for( int j=0; j<3; j++ )
  78          v3_copy( world.geo.verts[ptri[j]].co, tri[j] );
  79
  80       v3f vdown = {0.0f,-1.0f,0.0f};
  81       v3f sample_from;
  82       v3_copy( s->pos, sample_from );
  83       sample_from[1] = region[1][1];
  84
  85       float dist;
  86       if( ray_tri( tri, sample_from, vdown, &dist ))
  87       {
  88          v3f p0;
  89          v3_muladds( sample_from, vdown, dist, p0 );
  90
  91          if( player_walkgrid_tri_walkable(ptri) )
  92          {
  93             if( p0[1] > walk_height )
  94             {
  95                walk_height = p0[1];
  96             }
  97          }
  98          else
  99          {
 100             if( p0[1] > block_height )
 101                block_height = p0[1];
 102          }
 103       }
 104    }
 105
 106    s->pos[1] = walk_height;
 107
 108    if( walk_height > k_minworld_y )
 109       if( block_height > walk_height )
 110          s->type = k_sample_type_invalid;
 111       else
 112          s->type = k_sample_type_valid;
 113    else
 114       s->type = k_sample_type_air;
 115 }
 116
 117 float const k_gridscale = 0.5f;
 118
 119 enum eclipdir
 120 {
 121    k_eclipdir_h = 0,
 122    k_eclipdir_v = 1
 123 };
 124
 125 static void player_walkgrid_clip_blocker( struct grid_sample *sa,
 126                                           struct grid_sample *sb,
 127                                           struct grid_sample *st,
 128                                           enum eclipdir dir )
 129 {
 130    v3f clipdir, pos;
 131    int valid_a = sa->type == k_sample_type_valid,
 132        valid_b = sb->type == k_sample_type_valid;
 133    struct grid_sample *target = valid_a? sa: sb,
 134                       *other  = valid_a? sb: sa;
 135    v3_copy( target->pos, pos );
 136    v3_sub( other->pos, target->pos, clipdir );
 137
 138    boxf cell_region;
 139    v3_muladds( pos, (v3f){1.0f,1.0f,1.0f}, -k_gridscale*2.1f, cell_region[0]);
 140    v3_muladds( pos, (v3f){1.0f,1.0f,1.0f},  k_gridscale*2.1f, cell_region[1]);
 141
 142    u32 geo[256];
 143    v3f tri[3];
 144    int len = bh_select( &world.geo.bhtris, cell_region, geo, 256 );
 145
 146    float start_time = v3_length( clipdir ),
 147          min_time = start_time;
 148    v3_normalize( clipdir );
 149    v3_muls( clipdir, 0.0001f, st->clip[dir] );
 150
 151    for( int i=0; i<len; i++ )
 152    {
 153       u32 *ptri = &world.geo.indices[ geo[i]*3 ];
 154       for( int j=0; j<3; j++ )
 155          v3_copy( world.geo.verts[ptri[j]].co, tri[j] );
 156
 157       if( player_walkgrid_tri_walkable(ptri) )
 158          continue;
 159
 160       float dist;
 161       if(ray_tri( tri, pos, clipdir, &dist ))
 162       {
 163          if( dist > 0.0f && dist < min_time )
 164          {
 165             min_time = dist;
 166             sb->type = k_sample_type_air;
 167          }
 168       }
 169    }
 170
 171    if( !(min_time < start_time) )
 172       min_time = 0.5f * k_gridscale;
 173
 174    min_time = vg_clampf( min_time/k_gridscale, 0.01f, 0.99f );
 175
 176    v3_muls( clipdir, min_time, st->clip[dir] );
 177
 178    v3f p0;
 179    v3_muladds( target->pos, st->clip[dir], k_gridscale, p0 );
 180 }
 181
 182 static void player_walkgrid_clip_edge( struct grid_sample *sa,
 183                                        struct grid_sample *sb,
 184                                        struct grid_sample *st, /* data store */
 185                                        enum eclipdir dir )
 186 {
 187    v3f clipdir = { 0.0f, 0.0f, 0.0f }, pos;
 188    int valid_a = sa->type == k_sample_type_valid,
 189        valid_b = sb->type == k_sample_type_valid;
 190
 191    struct grid_sample *target = valid_a? sa: sb,
 192                       *other  = valid_a? sb: sa;
 193
 194    v3_sub( other->pos, target->pos, clipdir );
 195    clipdir[1] = 0.0f;
 196
 197    v3_copy( target->pos, pos );
 198
 199    boxf cell_region;
 200    v3_muladds( pos, (v3f){1.0f,1.0f,1.0f}, -k_gridscale*1.1f, cell_region[0]);
 201    v3_muladds( pos, (v3f){1.0f,1.0f,1.0f},  k_gridscale*1.1f, cell_region[1]);
 202
 203    u32 geo[256];
 204    int len = bh_select( &world.geo.bhtris, cell_region, geo, 256 );
 205
 206    float max_dist = 0.0f;
 207    v3f tri[3];
 208    v3f perp;
 209    v3_cross( clipdir,(v3f){0.0f,1.0f,0.0f},perp );
 210    v3_muls( clipdir, 0.001f, st->clip[dir] );
 211
 212    for( int i=0; i<len; i++ )
 213    {
 214       u32 *ptri = &world.geo.indices[ geo[i]*3 ];
 215       for( int j=0; j<3; j++ )
 216          v3_copy( world.geo.verts[ptri[j]].co, tri[j] );
 217
 218       if( !player_walkgrid_tri_walkable(ptri) )
 219          continue;
 220
 221       for( int k=0; k<3; k++ )
 222       {
 223          int ia = k,
 224              ib = (k+1)%3;
 225
 226          v3f v0, v1;
 227          v3_sub( tri[ia], pos, v0 );
 228          v3_sub( tri[ib], pos, v1 );
 229
 230          if( (clipdir[2]*v0[0] - clipdir[0]*v0[2]) *
 231              (clipdir[2]*v1[0] - clipdir[0]*v1[2]) < 0.0f )
 232          {
 233             float da = v3_dot(v0,perp),
 234                   db = v3_dot(v1,perp),
 235                   d  = da-db,
 236                   qa = da/d;
 237
 238             v3f p0;
 239             v3_muls( v1, qa, p0 );
 240             v3_muladds( p0, v0, 1.0f-qa, p0 );
 241
 242             float h = v3_dot(p0,clipdir)/v3_dot(clipdir,clipdir);
 243
 244             if( h >= max_dist && h <= 1.0f )
 245             {
 246                max_dist = h;
 247                float l = 1.0f/v3_length(clipdir);
 248                v3_muls( p0, l, st->clip[dir] );
 249             }
 250          }
 251       }
 252    }
 253 }
 254
 255 static const struct conf
 256 {
 257    struct confedge
 258    {
 259       /* i: sample index
 260        * d: data index
 261        * a: axis index
 262        * o: the 'other' point to do a A/B test with
 263        *       if its -1, all AB is done.
 264        */
 265       int i0, i1,
 266           d0, d1,
 267           a0, a1,
 268           o0, o1;
 269    }
 270    edges[2];
 271    int edge_count;
 272 }
 273 k_walkgrid_configs[16] = {
 274    {{},0},
 275    {{{ 3,3, 3,0, 1,0, -1,-1 }}, 1},
 276    {{{ 2,2, 1,3, 0,1, -1,-1 }}, 1},
 277    {{{ 2,3, 1,0, 0,0,  3,-1 }}, 1},
 278
 279    {{{ 1,1, 0,1, 1,0, -1,-1 }}, 1},
 280    {{{ 3,3, 3,0, 1,0, -1,-1 },
 281      { 1,1, 0,1, 1,0, -1,-1 }}, 2},
 282    {{{ 1,2, 0,3, 1,1,  2,-1 }}, 1},
 283    {{{ 1,3, 0,0, 1,0,  2, 2 }}, 1},
 284
 285    {{{ 0,0, 0,0, 0,1, -1,-1 }}, 1},
 286    {{{ 3,0, 3,0, 1,1,  0,-1 }}, 1},
 287    {{{ 2,2, 1,3, 0,1, -1,-1 },
 288      { 0,0, 0,0, 0,1, -1,-1 }}, 2},
 289    {{{ 2,0, 1,0, 0,1,  3, 3 }}, 1},
 290
 291    {{{ 0,1, 0,1, 0,0,  1,-1 }}, 1},
 292    {{{ 3,1, 3,1, 1,0,  0, 0 }}, 1},
 293    {{{ 0,2, 0,3, 0,1,  1, 1 }}, 1},
 294    {{},0},
 295 };
 296
 297 /*
 298  * Get a buffer of edges from cell location
 299  */
 300 static const struct conf *player_walkgrid_conf( struct walkgrid *wg,
 301       v2i cell,
 302       struct grid_sample *corners[4] )
 303 {
 304    corners[0] = &wg->samples[cell[1]  ][cell[0]  ];
 305    corners[1] = &wg->samples[cell[1]+1][cell[0]  ];
 306    corners[2] = &wg->samples[cell[1]+1][cell[0]+1];
 307    corners[3] = &wg->samples[cell[1]  ][cell[0]+1];
 308
 309    u32 vd0 = corners[0]->type == k_sample_type_valid,
 310        vd1 = corners[1]->type == k_sample_type_valid,
 311        vd2 = corners[2]->type == k_sample_type_valid,
 312        vd3 = corners[3]->type == k_sample_type_valid,
 313        config = (vd0<<3) | (vd1<<2) | (vd2<<1) | vd3;
 314
 315    return &k_walkgrid_configs[ config ];
 316 }
 317
 318 static void player_walkgrid_floor(v3f pos)
 319 {
 320    v3_muls( pos, 1.0f/k_gridscale, pos );
 321    v3_floor( pos, pos );
 322    v3_muls( pos, k_gridscale, pos );
 323 }
 324
 325 /*
 326  * Computes the barycentric coordinate of location on a triangle (vertical),
 327  * then sets the Y position to the interpolation of the three points
 328  */
 329 static void player_walkgrid_stand_tri( v3f a, v3f b, v3f c, v3f pos )
 330 {
 331    v3f v0,v1,v2;
 332    v3_sub( b, a, v0 );
 333    v3_sub( c, a, v1 );
 334    v3_sub( pos, a, v2 );
 335
 336    float d = v0[0]*v1[2] - v1[0]*v0[2],
 337          v = (v2[0]*v1[2] - v1[0]*v2[2]) / d,
 338          w = (v0[0]*v2[2] - v2[0]*v0[2]) / d,
 339          u = 1.0f - v - w;
 340
 341    vg_line( pos, a, 0xffff0000 );
 342    vg_line( pos, b, 0xff00ff00 );
 343    vg_line( pos, c, 0xff0000ff );
 344    pos[1] = u*a[1] + v*b[1] + w*c[1];
 345 }
 346
 347 /*
 348  * Get the minimum time value of pos+dir until a cell edge
 349  *
 350  * t[0] -> t[3] are the individual time values
 351  * t[5] & t[6]  are the maximum axis values
 352  * t[6] is the minimum value
 353  *
 354  */
 355 static void player_walkgrid_min_cell( float t[7], v2f pos, v2f dir )
 356 {
 357    v2f frac = { 1.0f/dir[0], 1.0f/dir[1] };
 358
 359    t[0] = 999.9f;
 360    t[1] = 999.9f;
 361    t[2] = 999.9f;
 362    t[3] = 999.9f;
 363
 364    if( fabsf(dir[0]) > 0.0001f )
 365    {
 366       t[0] = (0.0f-pos[0]) * frac[0];
 367       t[1] = (1.0f-pos[0]) * frac[0];
 368    }
 369    if( fabsf(dir[1]) > 0.0001f )
 370    {
 371       t[2] = (0.0f-pos[1]) * frac[1];
 372       t[3] = (1.0f-pos[1]) * frac[1];
 373    }
 374
 375    t[4] = vg_maxf(t[0],t[1]);
 376    t[5] = vg_maxf(t[2],t[3]);
 377    t[6] = vg_minf(t[4],t[5]);
 378 }
 379
 380 static void player_walkgrid_iter(struct walkgrid *wg, int iter)
 381 {
 382
 383    /*
 384     * For each walkgrid iteration we are stepping through cells and determining
 385     * the intersections with the grid, and any edges that are present
 386     */
 387
 388    u32 icolours[] = { 0xffff00ff, 0xff00ffff, 0xffffff00 };
 389
 390    v3f pa, pb, pc, pd, pl0, pl1;
 391    pa[0] = wg->region[0][0] + (float)wg->cell_id[0] *k_gridscale;
 392    pa[1] = (wg->region[0][1] + wg->region[1][1]) * 0.5f + k_gridscale;
 393    pa[2] = wg->region[0][2] + (float)wg->cell_id[1] *k_gridscale;
 394 #if 0
 395    pb[0] = pa[0];
 396    pb[1] = pa[1];
 397    pb[2] = pa[2] + k_gridscale;
 398    pc[0] = pa[0] + k_gridscale;
 399    pc[1] = pa[1];
 400    pc[2] = pa[2] + k_gridscale;
 401    pd[0] = pa[0] + k_gridscale;
 402    pd[1] = pa[1];
 403    pd[2] = pa[2];
 404    /* if you want to draw the current cell */
 405    vg_line( pa, pb, 0xff00ffff );
 406    vg_line( pb, pc, 0xff00ffff );
 407    vg_line( pc, pd, 0xff00ffff );
 408    vg_line( pd, pa, 0xff00ffff );
 409 #endif
 410    pl0[0] = pa[0] + wg->pos[0]*k_gridscale;
 411    pl0[1] = pa[1];
 412    pl0[2] = pa[2] + wg->pos[1]*k_gridscale;
 413
 414    /*
 415     * If there are edges present, we need to create a 'substep' event, where
 416     * we find the intersection point, find the fully resolved position,
 417     * then the new pos dir is the intersection->resolution
 418     *
 419     * the resolution is applied in non-discretized space in order to create a
 420     * suitable vector for finding outflow, we want it to leave the cell so it
 421     * can be used by the quad
 422     */
 423
 424    v2f pos, dir;
 425    v2_copy( wg->pos, pos );
 426    v2_muls( wg->dir, wg->move, dir );
 427
 428    struct grid_sample *corners[4];
 429    v2f corners2d[4] = {{0.0f,0.0f},{0.0f,1.0f},{1.0f,1.0f},{1.0f,0.0f}};
 430    const struct conf *conf = player_walkgrid_conf( wg, wg->cell_id, corners );
 431
 432    float t[7];
 433    player_walkgrid_min_cell( t, pos, dir );
 434
 435    for( int i=0; i<conf->edge_count; i++ )
 436    {
 437       const struct confedge *edge = &conf->edges[i];
 438
 439       v2f e0, e1, n, r, target, res, tangent;
 440       e0[0] = corners2d[edge->i0][0] + corners[edge->d0]->clip[edge->a0][0];
 441       e0[1] = corners2d[edge->i0][1] + corners[edge->d0]->clip[edge->a0][2];
 442       e1[0] = corners2d[edge->i1][0] + corners[edge->d1]->clip[edge->a1][0];
 443       e1[1] = corners2d[edge->i1][1] + corners[edge->d1]->clip[edge->a1][2];
 444
 445       v3f pe0 = { pa[0] + e0[0]*k_gridscale,
 446                   pa[1],
 447                   pa[2] + e0[1]*k_gridscale };
 448       v3f pe1 = { pa[0] + e1[0]*k_gridscale,
 449                   pa[1],
 450                   pa[2] + e1[1]*k_gridscale };
 451
 452       v2_sub( e1, e0, tangent );
 453       n[0] = -tangent[1];
 454       n[1] =  tangent[0];
 455       v2_normalize( n );
 456
 457       /*
 458        * If we find ourselfs already penetrating the edge, move back out a
 459        * little
 460        */
 461       v2_sub( e0, pos, r );
 462       float p1 = v2_dot(r,n);
 463
 464       if( -p1 < 0.0001f )
 465       {
 466          v2_muladds( pos, n, p1+0.0001f, pos );
 467          v2_copy( pos, wg->pos );
 468          v3f p_new = { pa[0] + pos[0]*k_gridscale,
 469                        pa[1],
 470                        pa[2] + pos[1]*k_gridscale };
 471          v3_copy( p_new, pl0 );
 472       }
 473
 474       v2_add( pos, dir, target );
 475
 476       v2f v1, v2, v3;
 477       v2_sub( e0, pos, v1 );
 478       v2_sub( target, pos, v2 );
 479
 480       v2_copy( n, v3 );
 481
 482       v2_sub( e0, target, r );
 483       float p = v2_dot(r,n),
 484             t1 = v2_dot(v1,v3)/v2_dot(v2,v3);
 485
 486       if( t1 < t[6] && t1 > 0.0f && -p < 0.001f )
 487       {
 488          v2_muladds( target, n, p+0.0001f, res );
 489
 490          v2f intersect;
 491          v2_muladds( pos, dir, t1, intersect );
 492          v2_copy( intersect, pos );
 493          v2_sub( res, intersect, dir );
 494
 495          v3f p_res = { pa[0] + res[0]*k_gridscale,
 496                        pa[1],
 497                        pa[2] + res[1]*k_gridscale };
 498          v3f p_int = { pa[0] + intersect[0]*k_gridscale,
 499                        pa[1],
 500                        pa[2] + intersect[1]*k_gridscale };
 501
 502          vg_line( pl0, p_int, icolours[iter%3] );
 503          v3_copy( p_int, pl0 );
 504          v2_copy( pos, wg->pos );
 505
 506          player_walkgrid_min_cell( t, pos, dir );
 507       }
 508    }
 509
 510    /*
 511     * Compute intersection with grid cell moving outwards
 512     */
 513    t[6] = vg_minf( t[6], 1.0f );
 514
 515    pl1[0] = pl0[0] + dir[0]*k_gridscale*t[6];
 516    pl1[1] = pl0[1];
 517    pl1[2] = pl0[2] + dir[1]*k_gridscale*t[6];
 518    vg_line( pl0, pl1, icolours[iter%3] );
 519
 520    if( t[6] < 1.0f )
 521    {
 522       /*
 523        * To figure out what t value created the clip so we know which edge
 524        * to wrap around
 525        */
 526
 527       if( t[4] < t[5] )
 528       {
 529          wg->pos[1] = pos[1] + dir[1]*t[6];
 530
 531          if( t[0] > t[1] ) /* left edge */
 532          {
 533             wg->pos[0] = 0.9999f;
 534             wg->cell_id[0] --;
 535
 536             if( wg->cell_id[0] == 0 )
 537                wg->move = -1.0f;
 538          }
 539          else /* Right edge */
 540          {
 541             wg->pos[0] = 0.0001f;
 542             wg->cell_id[0] ++;
 543
 544             if( wg->cell_id[0] == WALKGRID_SIZE-2 )
 545                wg->move = -1.0f;
 546          }
 547       }
 548       else
 549       {
 550          wg->pos[0] = pos[0] + dir[0]*t[6];
 551
 552          if( t[2] > t[3] ) /* bottom edge */
 553          {
 554             wg->pos[1] = 0.9999f;
 555             wg->cell_id[1] --;
 556
 557             if( wg->cell_id[1] == 0 )
 558                wg->move = -1.0f;
 559          }
 560          else /* top edge */
 561          {
 562             wg->pos[1] = 0.0001f;
 563             wg->cell_id[1] ++;
 564
 565             if( wg->cell_id[1] == WALKGRID_SIZE-2 )
 566                wg->move = -1.0f;
 567          }
 568       }
 569
 570       wg->move -= t[6];
 571    }
 572    else
 573    {
 574       v2_muladds( wg->pos, dir, wg->move, wg->pos );
 575       wg->move = 0.0f;
 576    }
 577 }
 578
 579 static void player_walkgrid_stand_cell(struct walkgrid *wg)
 580 {
 581    /*
 582     * NOTE: as opposed to the other function which is done in discretized space
 583     *       this use a combination of both.
 584     */
 585
 586    v3f world;
 587    world[0] = wg->region[0][0]+((float)wg->cell_id[0]+wg->pos[0])*k_gridscale;
 588    world[1] = player.rb.co[1];
 589    world[2] = wg->region[0][2]+((float)wg->cell_id[1]+wg->pos[1])*k_gridscale;
 590
 591    struct grid_sample *corners[4];
 592    const struct conf *conf = player_walkgrid_conf( wg, wg->cell_id, corners );
 593
 594    if( conf != k_walkgrid_configs )
 595    {
 596       if( conf->edge_count == 0 )
 597       {
 598          v3f v0;
 599
 600          /* Split the basic quad along the shortest diagonal */
 601          if( fabsf(corners[2]->pos[1] - corners[0]->pos[1]) <
 602              fabsf(corners[3]->pos[1] - corners[1]->pos[1]) )
 603          {
 604             vg_line( corners[2]->pos, corners[0]->pos, 0xffaaaaaa );
 605
 606             if( wg->pos[0] > wg->pos[1] )
 607                player_walkgrid_stand_tri( corners[0]->pos,
 608                                           corners[3]->pos,
 609                                           corners[2]->pos, world );
 610             else
 611                player_walkgrid_stand_tri( corners[0]->pos,
 612                                           corners[2]->pos,
 613                                           corners[1]->pos, world );
 614          }
 615          else
 616          {
 617             vg_line( corners[3]->pos, corners[1]->pos, 0xffaaaaaa );
 618
 619             if( wg->pos[0] < 1.0f-wg->pos[1] )
 620                player_walkgrid_stand_tri( corners[0]->pos,
 621                                           corners[3]->pos,
 622                                           corners[1]->pos, world );
 623             else
 624                player_walkgrid_stand_tri( corners[3]->pos,
 625                                           corners[2]->pos,
 626                                           corners[1]->pos, world );
 627          }
 628       }
 629       else
 630       {
 631          for( int i=0; i<conf->edge_count; i++ )
 632          {
 633             const struct confedge *edge = &conf->edges[i];
 634
 635             v3f p0, p1;
 636             v3_muladds( corners[edge->i0]->pos,
 637                         corners[edge->d0]->clip[edge->a0], k_gridscale, p0 );
 638             v3_muladds( corners[edge->i1]->pos,
 639                         corners[edge->d1]->clip[edge->a1], k_gridscale, p1 );
 640
 641             /*
 642              * Find penetration distance between player position and the edge
 643              */
 644
 645             v2f normal = { -(p1[2]-p0[2]), p1[0]-p0[0] },
 646                    rel = { world[0]-p0[0], world[2]-p0[2] };
 647
 648             if( edge->o0 == -1 )
 649             {
 650                /* No subregions (default case), just use triangle created by
 651                 * i0, e0, e1 */
 652                player_walkgrid_stand_tri( corners[edge->i0]->pos,
 653                                           p0,
 654                                           p1, world );
 655             }
 656             else
 657             {
 658                /*
 659                 * Test if we are in the first region, which is
 660                 * edge.i0, edge.e0, edge.o0,
 661                 */
 662                v3f v0, ref;
 663                v3_sub( p0, corners[edge->o0]->pos, ref );
 664                v3_sub( world, corners[edge->o0]->pos, v0 );
 665
 666                vg_line( corners[edge->o0]->pos, p0, 0xffffff00 );
 667                vg_line( corners[edge->o0]->pos, world, 0xff000000 );
 668
 669                if( ref[0]*v0[2] - ref[2]*v0[0] < 0.0f )
 670                {
 671                   player_walkgrid_stand_tri( corners[edge->i0]->pos,
 672                                              p0,
 673                                              corners[edge->o0]->pos, world );
 674                }
 675                else
 676                {
 677                   if( edge->o1 == -1 )
 678                   {
 679                      /*
 680                       * No other edges mean we just need to use the opposite
 681                       *
 682                       * e0, e1, o0 (in our case, also i1)
 683                       */
 684                      player_walkgrid_stand_tri( p0,
 685                                                 p1,
 686                                                 corners[edge->o0]->pos, world );
 687                   }
 688                   else
 689                   {
 690                      /*
 691                       * Note: this v0 calculation can be ommited with the
 692                       *       current tileset.
 693                       *
 694                       *       the last two triangles we have are:
 695                       *         e0, e1, o1
 696                       *       and
 697                       *         e1, i1, o1
 698                       */
 699                      v3_sub( p1, corners[edge->o1]->pos, ref );
 700                      v3_sub( world, corners[edge->o1]->pos, v0 );
 701                      vg_line( corners[edge->o1]->pos, p1, 0xff00ffff );
 702
 703                      if( ref[0]*v0[2] - ref[2]*v0[0] < 0.0f )
 704                      {
 705                         player_walkgrid_stand_tri( p0,
 706                                                    p1,
 707                                                    corners[edge->o1]->pos,
 708                                                    world );
 709                      }
 710                      else
 711                      {
 712                         player_walkgrid_stand_tri( p1,
 713                                                    corners[edge->i1]->pos,
 714                                                    corners[edge->o1]->pos,
 715                                                    world );
 716                      }
 717                   }
 718                }
 719             }
 720          }
 721       }
 722    }
 723
 724    v3_copy( world, player.rb.co );
 725 }
 726
 727 static void player_walkgrid_getsurface(void)
 728 {
 729    float const k_stepheight = 0.5f;
 730    float const k_miny = 0.6f;
 731    float const k_height = 1.78f;
 732    float const k_region_size = (float)WALKGRID_SIZE/2.0f * k_gridscale;
 733
 734    static struct walkgrid wg;
 735
 736    v3f cell;
 737    v3_copy( player.rb.co, cell );
 738    player_walkgrid_floor( cell );
 739
 740    v3_muladds( cell, (v3f){-1.0f,-1.0f,-1.0f}, k_region_size, wg.region[0] );
 741    v3_muladds( cell, (v3f){ 1.0f, 1.0f, 1.0f}, k_region_size, wg.region[1] );
 742
 743
 744    /*
 745     * Create player input vector
 746     */
 747    v3f delta = {0.0f,0.0f,0.0f};
 748    v3f fwd = { -sinf(-player.angles[0]), 0.0f, -cosf(-player.angles[0]) },
 749        side = { -fwd[2], 0.0f, fwd[0] };
 750
 751    /* Temp */
 752    if( !vg_console_enabled() )
 753    {
 754       if( glfwGetKey( vg_window, GLFW_KEY_W ) )
 755          v3_muladds( delta, fwd,  ktimestep*k_walkspeed, delta );
 756       if( glfwGetKey( vg_window, GLFW_KEY_S ) )
 757          v3_muladds( delta, fwd, -ktimestep*k_walkspeed, delta );
 758
 759       if( glfwGetKey( vg_window, GLFW_KEY_A ) )
 760          v3_muladds( delta, side, -ktimestep*k_walkspeed, delta );
 761       if( glfwGetKey( vg_window, GLFW_KEY_D ) )
 762          v3_muladds( delta, side,  ktimestep*k_walkspeed, delta );
 763
 764       v3_muladds( delta, fwd,
 765             vg_get_axis("vertical")*-ktimestep*k_walkspeed, delta );
 766       v3_muladds( delta, side,
 767             vg_get_axis("horizontal")*ktimestep*k_walkspeed, delta );
 768    }
 769
 770    /*
 771     * Create our move in grid space
 772     */
 773    wg.dir[0] = delta[0] * (1.0f/k_gridscale);
 774    wg.dir[1] = delta[2] * (1.0f/k_gridscale);
 775    wg.move = 1.0f;
 776
 777    v2f region_pos =
 778    {
 779       (player.rb.co[0] - wg.region[0][0]) * (1.0f/k_gridscale),
 780       (player.rb.co[2] - wg.region[0][2]) * (1.0f/k_gridscale)
 781    };
 782    v2f region_cell_pos;
 783    v2_floor( region_pos, region_cell_pos );
 784    v2_sub( region_pos, region_cell_pos, wg.pos );
 785
 786    wg.cell_id[0] = region_cell_pos[0];
 787    wg.cell_id[1] = region_cell_pos[1];
 788
 789    for(int y=0; y<WALKGRID_SIZE; y++ )
 790    {
 791       for(int x=0; x<WALKGRID_SIZE; x++ )
 792       {
 793          struct grid_sample *s = &wg.samples[y][x];
 794          v3_muladds( wg.region[0], (v3f){ x, 0, y }, k_gridscale, s->pos );
 795          s->state = k_traverse_none;
 796          s->type = k_sample_type_air;
 797          v3_zero( s->clip[0] );
 798          v3_zero( s->clip[1] );
 799       }
 800    }
 801
 802    v2i border[WALKGRID_SIZE*WALKGRID_SIZE];
 803    v2i *cborder = border;
 804    u32 border_length = 1;
 805
 806    struct grid_sample *base = NULL;
 807
 808    v2i starters[] = {{0,0},{1,1},{0,1},{1,0}};
 809
 810    for( int i=0;i<4;i++ )
 811    {
 812       v2i test;
 813       v2i_add( wg.cell_id, starters[i], test );
 814       v2i_copy( test, border[0] );
 815       base = &wg.samples[test[1]][test[0]];
 816
 817       base->pos[1] = cell[1];
 818       player_walkgrid_samplepole( base );
 819
 820       if( base->type == k_sample_type_valid )
 821          break;
 822       else
 823          base->type = k_sample_type_air;
 824    }
 825
 826    vg_line_pt3( base->pos, 0.1f, 0xffffffff );
 827
 828    int iter = 0;
 829
 830    while( border_length )
 831    {
 832       v2i directions[] = {{1,0},{0,1},{-1,0},{0,-1}};
 833
 834       v2i *old_border = cborder;
 835       int  len = border_length;
 836
 837       border_length = 0;
 838       cborder = old_border+len;
 839
 840       for( int i=0; i<len; i++ )
 841       {
 842          v2i co;
 843          v2i_copy( old_border[i], co );
 844          struct grid_sample *sa = &wg.samples[co[1]][co[0]];
 845
 846          for( int j=0; j<4; j++ )
 847          {
 848             v2i newp;
 849             v2i_add( co, directions[j], newp );
 850
 851             if( newp[0] < 0 || newp[1] < 0 ||
 852                 newp[0] == WALKGRID_SIZE || newp[1] == WALKGRID_SIZE )
 853                continue;
 854
 855             struct grid_sample *sb = &wg.samples[newp[1]][newp[0]];
 856             enum traverse_state thismove = j%2==0? 1: 2;
 857
 858             if( (sb->state & thismove) == 0x00 ||
 859                   sb->type == k_sample_type_air )
 860             {
 861                sb->pos[1] = sa->pos[1];
 862
 863                player_walkgrid_samplepole( sb );
 864
 865                if( sb->type != k_sample_type_air )
 866                {
 867                   /*
 868                    * Need to do a blocker pass
 869                    */
 870
 871                   struct grid_sample *store = (j>>1 == 0)? sa: sb;
 872                   player_walkgrid_clip_blocker( sa, sb, store, j%2 );
 873
 874
 875                   if( sb->type != k_sample_type_air )
 876                   {
 877                      vg_line( sa->pos, sb->pos, 0xffffffff );
 878
 879                      if( sb->state == k_traverse_none )
 880                         v2i_copy( newp, cborder[ border_length ++ ] );
 881                   }
 882                   else
 883                   {
 884                      v3f p1;
 885                      v3_muladds( sa->pos, store->clip[j%2], k_gridscale, p1 );
 886                      vg_line( sa->pos, p1, 0xffffffff );
 887                   }
 888                }
 889                else
 890                {
 891                   /*
 892                    * A clipping pass is now done on the edge of the walkable
 893                    * surface
 894                    */
 895
 896                   struct grid_sample *store = (j>>1 == 0)? sa: sb;
 897                   player_walkgrid_clip_edge( sa, sb, store, j%2 );
 898
 899                   v3f p1;
 900                   v3_muladds( sa->pos, store->clip[j%2], k_gridscale, p1 );
 901                   vg_line( sa->pos, p1, 0xffffffff );
 902                }
 903
 904                sb->state |= thismove;
 905             }
 906          }
 907
 908          sa->state = k_traverse_h|k_traverse_v;
 909       }
 910
 911       iter ++;
 912       if( iter == walk_grid_iterations )
 913          break;
 914    }
 915
 916    /* Draw connections */
 917    struct grid_sample *corners[4];
 918    for( int x=0; x<WALKGRID_SIZE-1; x++ )
 919    {
 920       for( int z=0; z<WALKGRID_SIZE-1; z++ )
 921       {
 922          const struct conf *conf =
 923             player_walkgrid_conf( &wg, (v2i){x,z}, corners );
 924
 925          for( int i=0; i<conf->edge_count; i++ )
 926          {
 927             const struct confedge *edge = &conf->edges[i];
 928
 929             v3f p0, p1;
 930             v3_muladds( corners[edge->i0]->pos,
 931                     corners[edge->d0]->clip[edge->a0], k_gridscale, p0 );
 932             v3_muladds( corners[edge->i1]->pos,
 933                     corners[edge->d1]->clip[edge->a1], k_gridscale, p1 );
 934
 935             vg_line( p0, p1, 0xff0000ff );
 936          }
 937       }
 938    }
 939
 940    /*
 941     * Commit player movement into the grid
 942     */
 943
 944    if( v3_length2(delta) <= 0.00001f )
 945       return;
 946
 947    int i=0;
 948    for(; i<8 && wg.move > 0.001f; i++ )
 949       player_walkgrid_iter( &wg, i );
 950
 951    player_walkgrid_stand_cell( &wg );
 952 }
 953
 954 static void player_walkgrid(void)
 955 {
 956    player_walkgrid_getsurface();
 957
 958    m4x3_mulv( player.rb.to_world, (v3f){0.0f,1.8f,0.0f}, player.camera_pos );
 959    player_mouseview();
 960    rb_update_transform( &player.rb );
 961 }
 962
 963 #endif /* PLAYER_WALKGRID_H */