2 * Copyright (C) 2021-2022 Mt.ZERO Software, Harry Godden - All Rights Reserved
5 #ifndef PLAYER_WALKGRID_H
6 #define PLAYER_WALKGRID_H
12 * Walkgrid implementation,
13 * loosely based of cmuratoris youtube video 'Killing the Walkmonster'
16 #define WALKGRID_SIZE 16
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 */
35 k_traverse_none
= 0x00,
41 samples
[WALKGRID_SIZE
][WALKGRID_SIZE
];
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) */
52 static int player_walkgrid_tri_walkable( u32 tri
[3] )
54 return tri
[0] > world
.sm_geo_std_oob
.vertex_count
;
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.
61 static void player_walkgrid_samplepole( struct grid_sample
*s
)
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
}};
68 int len
= bh_select( &world
.geo
.bhtris
, region
, geo
, 256 );
70 const float k_minworld_y
= -2000.0f
;
72 float walk_height
= k_minworld_y
,
73 block_height
= k_minworld_y
;
75 s
->type
= k_sample_type_air
;
77 for( int i
=0; i
<len
; i
++ )
79 u32
*ptri
= &world
.geo
.indices
[ geo
[i
]*3 ];
81 for( int j
=0; j
<3; j
++ )
82 v3_copy( world
.geo
.verts
[ptri
[j
]].co
, tri
[j
] );
84 v3f vdown
= {0.0f
,-1.0f
,0.0f
};
86 v3_copy( s
->pos
, sample_from
);
87 sample_from
[1] = region
[1][1];
90 if( ray_tri( tri
, sample_from
, vdown
, &dist
))
93 v3_muladds( sample_from
, vdown
, dist
, p0
);
95 if( player_walkgrid_tri_walkable(ptri
) )
97 if( p0
[1] > walk_height
)
104 if( p0
[1] > block_height
)
105 block_height
= p0
[1];
110 s
->pos
[1] = walk_height
;
112 if( walk_height
> k_minworld_y
)
113 if( block_height
> walk_height
)
114 s
->type
= k_sample_type_invalid
;
116 s
->type
= k_sample_type_valid
;
118 s
->type
= k_sample_type_air
;
121 float const k_gridscale
= 0.5f
;
129 static void player_walkgrid_clip_blocker( struct grid_sample
*sa
,
130 struct grid_sample
*sb
,
131 struct grid_sample
*st
,
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
);
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]);
148 int len
= bh_select( &world
.geo
.bhtris
, cell_region
, geo
, 256 );
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
] );
155 for( int i
=0; i
<len
; i
++ )
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
] );
161 if( player_walkgrid_tri_walkable(ptri
) )
165 if(ray_tri( tri
, pos
, clipdir
, &dist
))
167 if( dist
> 0.0f
&& dist
< min_time
)
170 sb
->type
= k_sample_type_air
;
175 if( !(min_time
< start_time
) )
176 min_time
= 0.5f
* k_gridscale
;
178 min_time
= vg_clampf( min_time
/k_gridscale
, 0.01f
, 0.99f
);
180 v3_muls( clipdir
, min_time
, st
->clip
[dir
] );
183 v3_muladds( target
->pos
, st
->clip
[dir
], k_gridscale
, p0
);
186 static void player_walkgrid_clip_edge( struct grid_sample
*sa
,
187 struct grid_sample
*sb
,
188 struct grid_sample
*st
, /* data store */
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
;
195 struct grid_sample
*target
= valid_a
? sa
: sb
,
196 *other
= valid_a
? sb
: sa
;
198 v3_sub( other
->pos
, target
->pos
, clipdir
);
201 v3_copy( target
->pos
, pos
);
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]);
208 int len
= bh_select( &world
.geo
.bhtris
, cell_region
, geo
, 256 );
210 float max_dist
= 0.0f
;
213 v3_cross( clipdir
,(v3f
){0.0f
,1.0f
,0.0f
},perp
);
214 v3_muls( clipdir
, 0.001f
, st
->clip
[dir
] );
216 for( int i
=0; i
<len
; i
++ )
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
] );
222 if( !player_walkgrid_tri_walkable(ptri
) )
225 for( int k
=0; k
<3; k
++ )
231 v3_sub( tri
[ia
], pos
, v0
);
232 v3_sub( tri
[ib
], pos
, v1
);
234 if( (clipdir
[2]*v0
[0] - clipdir
[0]*v0
[2]) *
235 (clipdir
[2]*v1
[0] - clipdir
[0]*v1
[2]) < 0.0f
)
237 float da
= v3_dot(v0
,perp
),
238 db
= v3_dot(v1
,perp
),
243 v3_muls( v1
, qa
, p0
);
244 v3_muladds( p0
, v0
, 1.0f
-qa
, p0
);
246 float h
= v3_dot(p0
,clipdir
)/v3_dot(clipdir
,clipdir
);
248 if( h
>= max_dist
&& h
<= 1.0f
)
251 float l
= 1.0f
/v3_length(clipdir
);
252 v3_muls( p0
, l
, st
->clip
[dir
] );
259 static const struct conf
266 * o: the 'other' point to do a A/B test with
267 * if its -1, all AB is done.
277 k_walkgrid_configs
[16] = {
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},
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},
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},
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},
302 * Get a buffer of edges from cell location
304 static const struct conf
*player_walkgrid_conf( struct walkgrid
*wg
,
306 struct grid_sample
*corners
[4] )
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];
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
;
319 return &k_walkgrid_configs
[ config
];
322 static void player_walkgrid_floor(v3f pos
)
324 v3_muls( pos
, 1.0f
/k_gridscale
, pos
);
325 v3_floor( pos
, pos
);
326 v3_muls( pos
, k_gridscale
, pos
);
330 * Computes the barycentric coordinate of location on a triangle (vertical),
331 * then sets the Y position to the interpolation of the three points
333 static void player_walkgrid_stand_tri( v3f a
, v3f b
, v3f c
, v3f pos
)
338 v3_sub( pos
, a
, v2
);
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
,
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];
352 * Get the minimum time value of pos+dir until a cell edge
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
359 static void player_walkgrid_min_cell( float t
[7], v2f pos
, v2f dir
)
361 v2f frac
= { 1.0f
/dir
[0], 1.0f
/dir
[1] };
368 if( fabsf(dir
[0]) > 0.0001f
)
370 t
[0] = (0.0f
-pos
[0]) * frac
[0];
371 t
[1] = (1.0f
-pos
[0]) * frac
[0];
373 if( fabsf(dir
[1]) > 0.0001f
)
375 t
[2] = (0.0f
-pos
[1]) * frac
[1];
376 t
[3] = (1.0f
-pos
[1]) * frac
[1];
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]);
384 static void player_walkgrid_iter(struct walkgrid
*wg
, int iter
)
388 * For each walkgrid iteration we are stepping through cells and determining
389 * the intersections with the grid, and any edges that are present
392 u32 icolours
[] = { 0xffff00ff, 0xff00ffff, 0xffffff00 };
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
;
401 pb
[2] = pa
[2] + k_gridscale
;
402 pc
[0] = pa
[0] + k_gridscale
;
404 pc
[2] = pa
[2] + k_gridscale
;
405 pd
[0] = pa
[0] + k_gridscale
;
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 );
414 pl0
[0] = pa
[0] + wg
->pos
[0]*k_gridscale
;
416 pl0
[2] = pa
[2] + wg
->pos
[1]*k_gridscale
;
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
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
429 v2_copy( wg
->pos
, pos
);
430 v2_muls( wg
->dir
, wg
->move
, dir
);
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
);
437 player_walkgrid_min_cell( t
, pos
, dir
);
439 for( int i
=0; i
<conf
->edge_count
; i
++ )
441 const struct confedge
*edge
= &conf
->edges
[i
];
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];
449 v3f pe0
= { pa
[0] + e0
[0]*k_gridscale
,
451 pa
[2] + e0
[1]*k_gridscale
};
452 v3f pe1
= { pa
[0] + e1
[0]*k_gridscale
,
454 pa
[2] + e1
[1]*k_gridscale
};
456 v2_sub( e1
, e0
, tangent
);
462 * If we find ourselfs already penetrating the edge, move back out a
465 v2_sub( e0
, pos
, r
);
466 float p1
= v2_dot(r
,n
);
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
,
474 pa
[2] + pos
[1]*k_gridscale
};
475 v3_copy( p_new
, pl0
);
478 v2_add( pos
, dir
, target
);
481 v2_sub( e0
, pos
, v1
);
482 v2_sub( target
, pos
, v2
);
486 v2_sub( e0
, target
, r
);
487 float p
= v2_dot(r
,n
),
488 t1
= v2_dot(v1
,v3
)/v2_dot(v2
,v3
);
490 if( t1
< t
[6] && t1
> 0.0f
&& -p
< 0.001f
)
492 v2_muladds( target
, n
, p
+0.0001f
, res
);
495 v2_muladds( pos
, dir
, t1
, intersect
);
496 v2_copy( intersect
, pos
);
497 v2_sub( res
, intersect
, dir
);
499 v3f p_res
= { pa
[0] + res
[0]*k_gridscale
,
501 pa
[2] + res
[1]*k_gridscale
};
502 v3f p_int
= { pa
[0] + intersect
[0]*k_gridscale
,
504 pa
[2] + intersect
[1]*k_gridscale
};
506 vg_line( pl0
, p_int
, icolours
[iter
%3] );
507 v3_copy( p_int
, pl0
);
508 v2_copy( pos
, wg
->pos
);
510 player_walkgrid_min_cell( t
, pos
, dir
);
515 * Compute intersection with grid cell moving outwards
517 t
[6] = vg_minf( t
[6], 1.0f
);
519 pl1
[0] = pl0
[0] + dir
[0]*k_gridscale
*t
[6];
521 pl1
[2] = pl0
[2] + dir
[1]*k_gridscale
*t
[6];
522 vg_line( pl0
, pl1
, icolours
[iter
%3] );
527 * To figure out what t value created the clip so we know which edge
533 wg
->pos
[1] = pos
[1] + dir
[1]*t
[6];
535 if( t
[0] > t
[1] ) /* left edge */
537 wg
->pos
[0] = 0.9999f
;
540 if( wg
->cell_id
[0] == 0 )
543 else /* Right edge */
545 wg
->pos
[0] = 0.0001f
;
548 if( wg
->cell_id
[0] == WALKGRID_SIZE
-2 )
554 wg
->pos
[0] = pos
[0] + dir
[0]*t
[6];
556 if( t
[2] > t
[3] ) /* bottom edge */
558 wg
->pos
[1] = 0.9999f
;
561 if( wg
->cell_id
[1] == 0 )
566 wg
->pos
[1] = 0.0001f
;
569 if( wg
->cell_id
[1] == WALKGRID_SIZE
-2 )
578 v2_muladds( wg
->pos
, dir
, wg
->move
, wg
->pos
);
583 static void player_walkgrid_stand_cell(struct walkgrid
*wg
)
586 * NOTE: as opposed to the other function which is done in discretized space
587 * this use a combination of both.
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
;
595 struct grid_sample
*corners
[4];
596 const struct conf
*conf
= player_walkgrid_conf( wg
, wg
->cell_id
, corners
);
598 if( conf
!= k_walkgrid_configs
)
600 if( conf
->edge_count
== 0 )
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]) )
608 vg_line( corners
[2]->pos
, corners
[0]->pos
, 0xffaaaaaa );
610 if( wg
->pos
[0] > wg
->pos
[1] )
611 player_walkgrid_stand_tri( corners
[0]->pos
,
613 corners
[2]->pos
, world
);
615 player_walkgrid_stand_tri( corners
[0]->pos
,
617 corners
[1]->pos
, world
);
621 vg_line( corners
[3]->pos
, corners
[1]->pos
, 0xffaaaaaa );
623 if( wg
->pos
[0] < 1.0f
-wg
->pos
[1] )
624 player_walkgrid_stand_tri( corners
[0]->pos
,
626 corners
[1]->pos
, world
);
628 player_walkgrid_stand_tri( corners
[3]->pos
,
630 corners
[1]->pos
, world
);
635 for( int i
=0; i
<conf
->edge_count
; i
++ )
637 const struct confedge
*edge
= &conf
->edges
[i
];
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
);
646 * Find penetration distance between player position and the edge
649 v2f normal
= { -(p1
[2]-p0
[2]), p1
[0]-p0
[0] },
650 rel
= { world
[0]-p0
[0], world
[2]-p0
[2] };
654 /* No subregions (default case), just use triangle created by
656 player_walkgrid_stand_tri( corners
[edge
->i0
]->pos
,
663 * Test if we are in the first region, which is
664 * edge.i0, edge.e0, edge.o0,
667 v3_sub( p0
, corners
[edge
->o0
]->pos
, ref
);
668 v3_sub( world
, corners
[edge
->o0
]->pos
, v0
);
670 vg_line( corners
[edge
->o0
]->pos
, p0
, 0xffffff00 );
671 vg_line( corners
[edge
->o0
]->pos
, world
, 0xff000000 );
673 if( ref
[0]*v0
[2] - ref
[2]*v0
[0] < 0.0f
)
675 player_walkgrid_stand_tri( corners
[edge
->i0
]->pos
,
677 corners
[edge
->o0
]->pos
, world
);
684 * No other edges mean we just need to use the opposite
686 * e0, e1, o0 (in our case, also i1)
688 player_walkgrid_stand_tri( p0
,
690 corners
[edge
->o0
]->pos
, world
);
695 * Note: this v0 calculation can be ommited with the
698 * the last two triangles we have are:
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 );
707 if( ref
[0]*v0
[2] - ref
[2]*v0
[0] < 0.0f
)
709 player_walkgrid_stand_tri( p0
,
711 corners
[edge
->o1
]->pos
,
716 player_walkgrid_stand_tri( p1
,
717 corners
[edge
->i1
]->pos
,
718 corners
[edge
->o1
]->pos
,
728 v3_copy( world
, player
.phys
.rb
.co
);
731 static void player_walkgrid_getsurface(void)
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
;
738 static struct walkgrid wg
;
741 v3_copy( player
.phys
.rb
.co
, cell
);
742 player_walkgrid_floor( cell
);
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] );
749 * Create player input vector
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] };
756 if( !vg_console_enabled() )
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
);
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
);
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
);
775 * Create our move in grid space
777 wg
.dir
[0] = delta
[0] * (1.0f
/k_gridscale
);
778 wg
.dir
[1] = delta
[2] * (1.0f
/k_gridscale
);
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
)
787 v2_floor( region_pos
, region_cell_pos
);
788 v2_sub( region_pos
, region_cell_pos
, wg
.pos
);
790 wg
.cell_id
[0] = region_cell_pos
[0];
791 wg
.cell_id
[1] = region_cell_pos
[1];
793 for(int y
=0; y
<WALKGRID_SIZE
; y
++ )
795 for(int x
=0; x
<WALKGRID_SIZE
; x
++ )
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] );
806 v2i border
[WALKGRID_SIZE
*WALKGRID_SIZE
];
807 v2i
*cborder
= border
;
808 u32 border_length
= 1;
810 struct grid_sample
*base
= NULL
;
812 v2i starters
[] = {{0,0},{1,1},{0,1},{1,0}};
814 for( int i
=0;i
<4;i
++ )
817 v2i_add( wg
.cell_id
, starters
[i
], test
);
818 v2i_copy( test
, border
[0] );
819 base
= &wg
.samples
[test
[1]][test
[0]];
821 base
->pos
[1] = cell
[1];
822 player_walkgrid_samplepole( base
);
824 if( base
->type
== k_sample_type_valid
)
827 base
->type
= k_sample_type_air
;
830 vg_line_pt3( base
->pos
, 0.1f
, 0xffffffff );
834 while( border_length
)
836 v2i directions
[] = {{1,0},{0,1},{-1,0},{0,-1}};
838 v2i
*old_border
= cborder
;
839 int len
= border_length
;
842 cborder
= old_border
+len
;
844 for( int i
=0; i
<len
; i
++ )
847 v2i_copy( old_border
[i
], co
);
848 struct grid_sample
*sa
= &wg
.samples
[co
[1]][co
[0]];
850 for( int j
=0; j
<4; j
++ )
853 v2i_add( co
, directions
[j
], newp
);
855 if( newp
[0] < 0 || newp
[1] < 0 ||
856 newp
[0] == WALKGRID_SIZE
|| newp
[1] == WALKGRID_SIZE
)
859 struct grid_sample
*sb
= &wg
.samples
[newp
[1]][newp
[0]];
860 enum traverse_state thismove
= j
%2==0? 1: 2;
862 if( (sb
->state
& thismove
) == 0x00 ||
863 sb
->type
== k_sample_type_air
)
865 sb
->pos
[1] = sa
->pos
[1];
867 player_walkgrid_samplepole( sb
);
869 if( sb
->type
!= k_sample_type_air
)
872 * Need to do a blocker pass
875 struct grid_sample
*store
= (j
>>1 == 0)? sa
: sb
;
876 player_walkgrid_clip_blocker( sa
, sb
, store
, j
%2 );
879 if( sb
->type
!= k_sample_type_air
)
881 vg_line( sa
->pos
, sb
->pos
, 0xffffffff );
883 if( sb
->state
== k_traverse_none
)
884 v2i_copy( newp
, cborder
[ border_length
++ ] );
889 v3_muladds( sa
->pos
, store
->clip
[j
%2], k_gridscale
, p1
);
890 vg_line( sa
->pos
, p1
, 0xffffffff );
896 * A clipping pass is now done on the edge of the walkable
900 struct grid_sample
*store
= (j
>>1 == 0)? sa
: sb
;
901 player_walkgrid_clip_edge( sa
, sb
, store
, j
%2 );
904 v3_muladds( sa
->pos
, store
->clip
[j
%2], k_gridscale
, p1
);
905 vg_line( sa
->pos
, p1
, 0xffffffff );
908 sb
->state
|= thismove
;
912 sa
->state
= k_traverse_h
|k_traverse_v
;
916 if( iter
== walk_grid_iterations
)
920 /* Draw connections */
921 struct grid_sample
*corners
[4];
922 for( int x
=0; x
<WALKGRID_SIZE
-1; x
++ )
924 for( int z
=0; z
<WALKGRID_SIZE
-1; z
++ )
926 const struct conf
*conf
=
927 player_walkgrid_conf( &wg
, (v2i
){x
,z
}, corners
);
929 for( int i
=0; i
<conf
->edge_count
; i
++ )
931 const struct confedge
*edge
= &conf
->edges
[i
];
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
);
939 vg_line( p0
, p1
, 0xff0000ff );
945 * Commit player movement into the grid
948 if( v3_length2(delta
) <= 0.00001f
)
952 for(; i
<8 && wg
.move
> 0.001f
; i
++ )
953 player_walkgrid_iter( &wg
, i
);
955 player_walkgrid_stand_cell( &wg
);
958 static void player_walkgrid(void)
960 player_walkgrid_getsurface();
962 m4x3_mulv(player
.phys
.rb
.to_world
, (v3f
){0.0f
,1.8f
,0.0f
}, player
.camera_pos
);
964 rb_update_transform( &player
.phys
.rb
);
967 #endif /* PLAYER_WALKGRID_H */