player_walkgrid.h

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