From 39378a28bc0b7c9beaf9f2191f5dc51b8c8865a0 Mon Sep 17 00:00:00 2001 From: hgn Date: Sun, 26 Jun 2022 02:42:56 +0100 Subject: [PATCH] the better walkgrid --- main.c | 8 + player.h | 561 +++++++++++++++++++++++++++++++++++++++++++------------ scene.h | 2 - 3 files changed, 452 insertions(+), 119 deletions(-) diff --git a/main.c b/main.c index 39b9de2..6b9e4d9 100644 --- a/main.c +++ b/main.c @@ -100,6 +100,14 @@ void vg_start(void) .persistent = 1 }); + vg_convar_push( (struct vg_convar){ + .name = "grid", + .data = &walk_grid_iterations, + .data_type = k_convar_dtype_i32, + .opt_i32 = { .min=0, .max=1, .clamp=0 }, + .persistent = 1 + }); + vg_convar_push( (struct vg_convar){ .name = "walk_speed", .data = &k_walkspeed, diff --git a/player.h b/player.h index ccc74dc..7aaa857 100644 --- a/player.h +++ b/player.h @@ -6,6 +6,7 @@ static int freecam = 0; static float k_walkspeed = 2.0f; +static int walk_grid_iterations = 1; static struct gplayer { @@ -58,7 +59,7 @@ static void player_transform_update(void) static int reset_player( int argc, char const *argv[] ) { - v3_zero( player.co ); + v3_copy( (v3f){ 0.0f, -2.0f, 0.0f }, player.co ); if( argc == 1 ) { @@ -432,8 +433,6 @@ static void player_physics_air(void) } /* Prediction - * - * TODO: Find best landing surface and guide player towords it */ float pstep = ktimestep*10.0f; @@ -577,65 +576,261 @@ static void player_do_motion(void) player.camera_pos ); } +static int player_walkgrid_tri_walkable( u32 tri[3] ) +{ + return tri[0] < world.sm_road.vertex_count; +} + +#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]; + +#if 0 + u32 geo[256]; +#endif + + 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; +}; + /* * 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 int player_walkgrid_samplepole( u32 *geo, int len, v3f pos ) +static void player_walkgrid_samplepole( struct grid_sample *s ) { - v3f p1; - v3_copy( pos, p1 ); - p1[1] -= 10.0f; + 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}}; - vg_line( pos, p1, 0x20ffffff ); +#if 0 + vg_line( region[0],region[1], 0x20ffffff ); +#endif - v3f sample_pos; - v3_copy(pos, sample_pos); + u32 geo[256]; + v3f tri[3]; + int len = bvh_select_triangles( &world.geo, region, geo, 256 ); + + const float k_minworld_y = -2000.0f; - v3f vdir = {0.0f,-1.0f,0.0f}; - int count = 0; + float walk_height = k_minworld_y, + block_height = k_minworld_y; + + s->type = k_sample_type_air; - ray_hit hit; - hit.dist = INFINITY; for( int i=0; ipos, 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]; + } + +#if 0 + draw_cross( p0, 0xffffffff, 0.05f ); +#endif + } + else + { + if( p0[1] > block_height ) + block_height = p0[1]; +#if 0 + draw_cross( p0, 0xff0000ff, 0.05f ); +#endif + } + } + } + + 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; + +#if 0 + if( s->type == k_sample_type_valid ) + { + vg_line_pt3( s->pos, 0.01f, 0xff00ff00 ); } +#endif + +#if 0 + int count = 0; + + ray_hit hit; + hit.dist = 10.0f; + count = bvh_raycast( &world.geo, sample_pos, vdir, &hit ); if( count ) { - v3f v0, v1; - float *pa = world.geo.verts[hit.tri[0]].co, - *pb = world.geo.verts[hit.tri[1]].co, - *pc = world.geo.verts[hit.tri[2]].co; - - v3_sub( pa, pb, v0 ); - v3_sub( pc, pb, v1 ); - v3_cross( v1, v0, hit.normal ); - v3_normalize( hit.normal ); - v3_muladds( sample_pos, vdir, hit.dist, pos ); - - draw_cross( pos, 0xff00ff00, 0.05f ); - return count; + v3_copy( hit.pos, s->pos ); + + if( !player_walkgrid_tri_walkable( hit.tri ) ) + { + draw_cross( pos, 0xff0000ff, 0.05f ); + return 0; + } + else + { + draw_cross( pos, 0xff00ff00, 0.05f ); + return count; + } } else return 0; +#endif +} + +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 = bvh_select_triangles( &world.geo, 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 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; + + v3_muls( clipdir, min_time/k_gridscale, st->clip[dir] ); + + v3f p0; + v3_muladds( target->pos, st->clip[dir], k_gridscale, p0 ); } -static void player_walkgrid_clip(u32 *geo, int len, v3f pos, v3f dir, v3f clip) +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 = bvh_select_triangles( &world.geo, cell_region, geo, 256 ); + float max_dist = 0.0f; v3f tri[3]; v3f perp; - v3_cross( dir,(v3f){0.0f,1.0f,0.0f},perp ); - v3_copy( pos, clip ); + v3_cross( clipdir,(v3f){0.0f,1.0f,0.0f},perp ); + v3_muls( clipdir, 0.001f, st->clip[dir] ); for( int i=0; i= max_dist && h <= 1.0f ) { max_dist = h; - float l = 1.0f/v3_length(dir); - v3_muls( p0, l, clip ); + float l = 1.0f/v3_length(clipdir); + v3_muls( p0, l, st->clip[dir] ); } } } } } -#define WALKGRID_SIZE 8 -struct walkgrid +static void player_walkgrid_clip( struct grid_sample *sa, + struct grid_sample *sb, + enum eclipdir dir ) { - struct grid_sample - { - int valid; - v3f clip[2]; - v3f pos; - } - samples[WALKGRID_SIZE][WALKGRID_SIZE]; - u32 geo[256]; + int mintype = VG_MIN( sa->type, sb->type ), + maxtype = VG_MAX( sa->type, sb->type ); - boxf region; + if( maxtype == k_sample_type_valid ) + { + if( mintype == k_sample_type_air || mintype == k_sample_type_invalid ) + { + player_walkgrid_clip_edge( sa, sb, sa, dir ); + } - 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; -}; +#if 0 + else if( mintype == k_sample_type_invalid ) + { + player_walkgrid_clip_blocker( sa, sb, dir ); + } +#endif + } +} static const struct conf { @@ -701,8 +898,6 @@ static const struct conf * a: axis index * o: the 'other' point to do a A/B test with * if its -1, all AB is done. - * - * TODO: Check the major edge against point (for the double cases) */ int i0, i1, d0, d1, @@ -748,14 +943,15 @@ static const struct conf *player_walkgrid_conf( struct walkgrid *wg, corners[2] = &wg->samples[cell[1]+1][cell[0]+1]; corners[3] = &wg->samples[cell[1] ][cell[0]+1]; - u32 config = (corners[0]->valid<<3) | (corners[1]->valid<<2) | - (corners[2]->valid<<1) | corners[3]->valid; + 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 ]; } -float const k_gridscale = 0.5f; - static void player_walkgrid_floor(v3f pos) { v3_muls( pos, 1.0f/k_gridscale, pos ); @@ -1038,6 +1234,7 @@ static void player_walkgrid_stand_cell(struct walkgrid *wg) v3f world; world[0] = wg->region[0][0]+((float)wg->cell_id[0]+wg->pos[0])*k_gridscale; + world[1] = player.co[1]; world[2] = wg->region[0][2]+((float)wg->cell_id[1]+wg->pos[1])*k_gridscale; struct grid_sample *corners[4]; @@ -1183,7 +1380,7 @@ static void player_walkgrid_getsurface(void) float const k_height = 1.78f; float const k_region_size = (float)WALKGRID_SIZE/2.0f * k_gridscale; - struct walkgrid wg; + static struct walkgrid wg; v3f cell; v3_copy( player.co, cell ); @@ -1192,19 +1389,49 @@ static void player_walkgrid_getsurface(void) 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] ); - int tri_count = bvh_select_triangles( &world.geo, wg.region, wg.geo, 256 ); + + /* + * 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] }; - v3f tri[3]; - for( int i=0; ipos ); - s->pos[1] = player.co[1] + k_height; - - s->valid = player_walkgrid_samplepole( wg.geo,tri_count,s->pos )? 1: 0; + s->pos[1] = cell[1]; + player_walkgrid_samplepole( s ); } } @@ -1233,8 +1459,6 @@ static void player_walkgrid_getsurface(void) { for( int z=0; ztype == k_sample_type_valid && + sb->type == k_sample_type_valid ) + vg_line( sa->pos, sb->pos, 0xffffffff ); +#if 0 if( sa->valid != sb->valid ) { clipdir[i*2] = (float)(sa->valid - sb->valid) * k_gridscale; - player_walkgrid_clip( wg.geo, tri_count, - sa->valid? sa->pos: sb->pos, - clipdir, sa->clip[i] ); + + player_walkgrid_clip( sa->valid? sa->pos: sb->pos, + clipdir, sa->clip[i] ); } else { @@ -1261,10 +1491,146 @@ static void player_walkgrid_getsurface(void) vg_line( sa->pos, sb->pos, 0xffffffff ); } } +#endif + } + } + } +#endif + + for(int y=0; ypos ); + 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; istate & 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; } +#if 0 + player.co[0] += wg.dir[0]; + player.co[2] += wg.dir[1]; +#endif + + + /* Draw connections */ struct grid_sample *corners[4]; for( int x=0; xd0]->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 ); - vg_line( corners[edge->i0]->pos, p0, 0xffffffff ); - vg_line( corners[edge->i1]->pos, p1, 0xffffffff ); + vg_line( p0, p1, 0xff0000ff ); } } } @@ -1295,46 +1659,9 @@ static void player_walkgrid_getsurface(void) * Commit player movement into the grid */ - 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 ); - } - if( v3_length2(delta) <= 0.00001f ) return; - /* - * 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.co[0] - wg.region[0][0]) * (1.0f/k_gridscale), - (player.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]; - int i=0; for(; i<8 && wg.move > 0.001f; i++ ) player_walkgrid_iter( &wg, i ); diff --git a/scene.h b/scene.h index 92fe6a1..c644468 100644 --- a/scene.h +++ b/scene.h @@ -1023,8 +1023,6 @@ static int bvh_raycast( scene *s, v3f co, v3f dir, ray_hit *hit ) static int bvh_select_triangles( scene *s, boxf box, u32 *triangles, int len ) { - vg_line_boxf( box, 0xffffff00 ); - /* TODO: use this stack system on the raycast function */ int count = 0; u32 stack[100]; -- 2.25.1