1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
|
/*
* ============================================================
* FILE: level.c
*
* PURPOSE: What's in the test world: the boxes it's made of and how the
* moving ones move. It's still a test space, like the one SM64's
* team tuned Mario in, just with a lot more to jump on now.
*
* FITS IN: Implements level.h. world.c calls level_build() once and
* level_motion_offset() every tick. Uses only config.h, math3d.h
* and the types in world.h; it never calls world.c.
*
* IMPLEMENT:
* - A tiny xorshift32 random generator. WHY our own instead of rand():
* rand() differs between C libraries, so the "same" seed could give a
* different level on another machine.
*
* - level_build() adds, in this order (each check below looks at all boxes
* added before it):
* 1. Random platforms (seeded from WORLD_SEED): WORLD_PLATFORM_COUNT boxes
* within WORLD_PLATFORM_AREA of spawn, re-rolled if they come within
* SPAWN_CLEAR_RADIUS of it. Two kinds:
* block stands on the ground, top low enough to jump onto (a
* full jump lifts the feet ~2.3 m)
* floating a thin slab higher up, reached by jumping from a block
* They may overlap each other; that's fine for collision and drawing.
* 2. WALL_COURSE: hand-placed boxes for tuning the wall hang, straight
* ahead of the starting view (it looks toward -Z). Its walls allow the
* wall hang; its platforms and the comparison pillar don't.
* 3. The cliff course, behind spawn (+Z; turn around), seeded from
* CLIFF_COURSE_SEED so it doesn't change when the random platforms do:
* Triangle cliff a right triangle, CLIFF_TOP (55 m) tall. Its SOUTH
* face (z = 40, facing spawn) and EAST face (x = 20)
* meet at the south-east corner. The third side faces
* north-west and can't be axis-aligned, so the cliff
* is CLIFF_STRIP_COUNT strips whose north ends step
* down that diagonal. Rock, and HANGABLE: big terrain
* surfaces allow the wall hang; small platforms don't.
* Rock pillars PILLAR_COUNT tall hangable pillars 4-6 m out from
* the faces, so they form chimneys with the cliff.
* Placed AFTER the route and never in its way.
* Height tiers every generated platform's top sits on a grid of
* TIER_HEIGHT (1.5 m) steps down from the cliff top, so
* one tier up is a single jump and two tiers up is a
* double (second) jump, and it's visible which is which.
* The climb a band that wraps the cliff: along the south face
* west to east, around the corner, north along the
* east face. Distance along it is `s`; distance out
* from the face is `out`. Each row turns the corner at
* its own spot (corner_s), so `s` is continuous round
* the turn. On it:
* - one ROUTE of big platforms (4-6 m) from the ground to
* one tier below the top, ROUTE_MIN_OUT..ROUTE_WIDEST_OUT
* out from the face (not hugging it). Each step is a
* single jump (+1 tier), or now and then a double (+2),
* NEVER two doubles in a row, with the path between the
* two platforms clear. It isn't marked. It goes along
* the band or switches rows (out a row, or back in, at
* the same spot along the face), switching more when
* it's ahead of schedule so it arrives by
* ROUTE_ARRIVE_BY without running off the face. Hops in
* toward the face are singles; the last platforms drift
* in so the final hop is onto the top. When stuck it
* tries easier hops, then a scan of nearby spots.
* - the SCATTER: SCATTER_COUNT more platforms, each one
* single hop beside a route platform, level or one tier
* up or down: other ways up, shortcuts and dead ends.
* Some ambiguity is WANTED: the player should have to
* judge which paths work.
* The river overlapping water tiles along the diagonal, parallel
* to the cliff's third side.
* The crossing the same idea (a tiered route, mostly up or level,
* plus a couple of extras beside it) on the straight
* line from the top's north-west corner over the river
* to the far cliff (58 m: two tiers above the top,
* hangable), the finish.
* Some platforms move (ROUTE_MOVING_SHARE / SCATTER_MOVING_SHARE): they
* slide back and forth along the band, bob up and down, or loop round a
* flat or upright circle, each with its own period and phase. A moving
* route platform is never next to another moving one, and passes through
* its placed position every cycle, so waiting on the previous platform
* always works. Moving platforms stay MOVING_MIN_BOTTOM above the ground.
* Placement rules (is_clear): nothing overlaps; platforms (nearly) over
* one another (footprints within CLEAR_SIDE_GAP) are at least
* CLEAR_HEADROOM apart vertically, so none blocks a jump from another;
* a platform over a rock's top keeps that headroom too; moving platforms keep
* MOVING_ROCK_GAP from rock so they can't pin the player against it.
* WHY a guaranteed route under a scatter: the scatter makes the climb a
* choice ("how do I get up there?") instead of one correct jump after
* another, and the route makes sure a way up always exists.
*
* - level_motion_offset(m, time): see level.h.
* - level_spawn_point(): (0, 0, 0).
*
* CONVENTIONS: Y up, boxes axis-aligned, the ground surface is y = 0. Every
* Box literal spells out all its fields (the build warns on
* missing ones); false / BOX_STYLE_PLATFORM are the defaults.
*
* NOT IN SCOPE: Level files, hand-authoring tools, moving walls.
*
* DONE WHEN: The same seeds always build the same level, spawn is clear, the
* wall course is ahead of the starting view, and the cliff course
* behind it can be climbed and crossed with the moves in player.c,
* using about 30-40 platforms of 4-6 m, mostly single jumps apart.
* ============================================================
*/
#include <math.h>
#include <stdint.h>
#include "config.h"
#include "level.h"
/* ---- Random numbers ---------------------------------------------------- */
static uint32_t s_rng_state;
/* xorshift32: three shifts and XORs give a decent, fully repeatable sequence. */
static uint32_t next_random(void)
{
s_rng_state ^= s_rng_state << 13;
s_rng_state ^= s_rng_state >> 17;
s_rng_state ^= s_rng_state << 5;
return s_rng_state;
}
static void seed_random(uint32_t seed)
{
s_rng_state = seed ? seed : 1u; /* xorshift must not start at 0 */
}
/* A float in [lo, hi]. */
static float random_range(float lo, float hi)
{
return lo + (hi - lo) * ((float)next_random() / 4294967295.0f);
}
static bool random_chance(float share)
{
return random_range(0.0f, 1.0f) < share;
}
/* ---- The box list being built ------------------------------------------ */
static LevelBox *s_out;
static int s_count, s_capacity;
/* The space each box can ever occupy (its whole path, if it moves), for the
* placement rules. */
static Box s_reach[LEVEL_MAX_BOXES];
static BoxMotion no_motion(void)
{
BoxMotion m = { MOTION_NONE, { 0.0f, 0.0f, 0.0f }, { 0.0f, 0.0f, 0.0f }, 1.0f, 0.0f };
return m;
}
static Box shift_box(Box b, Vec3 by)
{
b.min = vec3_add(b.min, by);
b.max = vec3_add(b.max, by);
return b;
}
/* Everywhere a box goes over one cycle: its bounds sampled round the cycle. */
static Box reach_of(Box b, BoxMotion m)
{
if (m.kind == MOTION_NONE)
return b;
Box reach = b;
for (int i = 0; i < 32; i++) {
Box at = shift_box(b, level_motion_offset(m, m.period * (float)i / 32.0f));
reach.min.x = fminf(reach.min.x, at.min.x); reach.max.x = fmaxf(reach.max.x, at.max.x);
reach.min.y = fminf(reach.min.y, at.min.y); reach.max.y = fmaxf(reach.max.y, at.max.y);
reach.min.z = fminf(reach.min.z, at.min.z); reach.max.z = fmaxf(reach.max.z, at.max.z);
}
return reach;
}
static void add_box(Box b, BoxMotion m)
{
if (s_count >= s_capacity)
return; /* full: LEVEL_MAX_BOXES is sized with room to spare */
s_out[s_count].box = b;
s_out[s_count].motion = m;
s_reach[s_count] = reach_of(b, m);
s_count++;
}
/* ---- 1. Random platforms ----------------------------------------------- */
#define PLATFORM_MIN_SIZE 2.0f /* m, shortest footprint side */
#define PLATFORM_MAX_SIZE 6.0f /* m, longest footprint side */
#define BLOCK_MIN_TOP 0.6f /* m, lowest ground block */
#define BLOCK_MAX_TOP 2.0f /* m, highest ground block (full jump reaches ~2.3) */
#define FLOATING_MIN_TOP 2.6f /* m, lowest floating slab top */
#define FLOATING_MAX_TOP 4.2f /* m, highest floating slab top (reachable from a block) */
#define FLOATING_THICKNESS 0.5f /* m, floating slab thickness */
#define FLOATING_CHANCE 0.35f /* fraction of platforms that float */
#define SPAWN_CLEAR_RADIUS 4.0f /* m around spawn kept free of platforms */
#define MAX_PLACEMENT_TRIES 50 /* re-rolls before giving up on a platform */
/* True if the footprint comes within SPAWN_CLEAR_RADIUS of spawn. Uses the
* closest point of the footprint to spawn, so big platforms can't sneak in. */
static bool too_close_to_spawn(Box b)
{
Vec3 spawn = level_spawn_point();
float dx = clampf(spawn.x, b.min.x, b.max.x) - spawn.x;
float dz = clampf(spawn.z, b.min.z, b.max.z) - spawn.z;
return dx * dx + dz * dz < SPAWN_CLEAR_RADIUS * SPAWN_CLEAR_RADIUS;
}
/* One platform with a random size and height, centered on the origin. */
static Box random_platform_shape(void)
{
float half_x = 0.5f * random_range(PLATFORM_MIN_SIZE, PLATFORM_MAX_SIZE);
float half_z = 0.5f * random_range(PLATFORM_MIN_SIZE, PLATFORM_MAX_SIZE);
float bottom, top;
if (random_chance(FLOATING_CHANCE)) {
top = random_range(FLOATING_MIN_TOP, FLOATING_MAX_TOP);
bottom = top - FLOATING_THICKNESS;
} else {
top = random_range(BLOCK_MIN_TOP, BLOCK_MAX_TOP);
bottom = 0.0f;
}
Box b = { { -half_x, bottom, -half_z }, { half_x, top, half_z },
false, BOX_STYLE_PLATFORM }; /* no wall hang, palette color */
return b;
}
static void add_random_platforms(void)
{
seed_random(WORLD_SEED);
for (int i = 0; i < WORLD_PLATFORM_COUNT; i++) {
Box shape = random_platform_shape();
for (int tries = 0; tries < MAX_PLACEMENT_TRIES; tries++) {
Vec3 spot = vec3_make(random_range(-WORLD_PLATFORM_AREA, WORLD_PLATFORM_AREA), 0.0f,
random_range(-WORLD_PLATFORM_AREA, WORLD_PLATFORM_AREA));
Box placed = shift_box(shape, spot);
if (!too_close_to_spawn(placed)) {
add_box(placed, no_motion());
break;
}
}
}
}
/* ---- 2. The wall course ------------------------------------------------ */
/* Min corner, max corner, wall hang, style. */
static const Box WALL_COURSE[] = {
/* The main wall: 12 m wide and 8 m tall, its hangable face toward spawn. */
{ { -10.0f, 0.0f, -40.5f }, { 2.0f, 8.0f, -40.0f }, true, BOX_STYLE_PLATFORM },
/* A chimney: two 10 m walls with a 4 m gap, for wall-to-wall jumps.
* Enter from the open end facing spawn. */
{ { 6.0f, 0.0f, -48.0f }, { 6.5f, 10.0f, -36.0f }, true, BOX_STYLE_PLATFORM },
{ { 10.5f, 0.0f, -48.0f }, { 11.0f, 10.0f, -36.0f }, true, BOX_STYLE_PLATFORM },
/* A step block in front of the main wall. */
{ { -6.0f, 0.0f, -36.5f }, { -3.0f, 1.5f, -33.5f }, false, BOX_STYLE_PLATFORM },
/* A ledge on the main wall's face, to land on from a wall jump. */
{ { -2.0f, 4.0f, -40.0f }, { 1.0f, 4.5f, -38.0f }, false, BOX_STYLE_PLATFORM },
/* A high slab off the main wall's left end, reached with a wall jump. */
{ { -13.0f, 5.5f, -39.0f }, { -10.5f, 6.0f, -36.0f }, false, BOX_STYLE_PLATFORM },
/* A pillar as tall as the main wall but NOT hangable, for comparison. */
{ { -18.0f, 0.0f, -41.0f }, { -16.0f, 8.0f, -39.0f }, false, BOX_STYLE_PLATFORM },
};
#define WALL_COURSE_COUNT ((int)(sizeof WALL_COURSE / sizeof WALL_COURSE[0]))
/* ---- 3. The cliff course: fixed terrain -------------------------------- */
#define CLIFF_TOP 55.0f /* m, the triangle cliff's flat top */
#define CLIFF_WEST_X -30.0f /* m, west end of the south face */
#define CLIFF_SOUTH_Z 40.0f /* m, the south face */
#define CLIFF_STRIP_WIDTH 5.0f /* m, width of each strip = step size along the diagonal */
#define CLIFF_STRIP_COUNT 10 /* strips west to east; the east face is the last one's side */
#define CLIFF_EAST_X (CLIFF_WEST_X + CLIFF_STRIP_WIDTH * CLIFF_STRIP_COUNT) /* 20 m */
#define RIVER_START_X -80.0f /* m, south-west corner of the first river tile */
#define RIVER_START_Z 12.0f
#define RIVER_TILE_SIZE 12.0f /* m, each square tile's side */
#define RIVER_TILE_STEP 6.0f /* m, each tile is this far along x AND z from the last */
#define RIVER_TILE_COUNT 13
#define RIVER_DEPTH 0.05f /* m, the water is a thin sheet on the ground */
/* The far cliff: the finish, 58 m up (on the tier grid: two tiers above the top), across the river. */
static const Box FAR_CLIFF = { { -70.0f, 0.0f, 80.0f }, { -32.0f, 58.0f, 98.0f }, true, BOX_STYLE_CLIFF };
/* The triangle cliff: strips side by side along the south face, each
* reaching one step further north than the last. Their row of north ends is
* the diagonal third side; the last strip's east side is the east face. */
static void add_triangle_cliff(void)
{
for (int i = 0; i < CLIFF_STRIP_COUNT; i++) {
float west = CLIFF_WEST_X + CLIFF_STRIP_WIDTH * (float)i;
Box strip = { { west, 0.0f, CLIFF_SOUTH_Z },
{ west + CLIFF_STRIP_WIDTH, CLIFF_TOP,
CLIFF_SOUTH_Z + CLIFF_STRIP_WIDTH * (float)(i + 1) },
true, BOX_STYLE_CLIFF };
add_box(strip, no_motion());
}
}
/* The river: square water tiles, each one step further along x AND z, so
* they overlap into a band running diagonally, parallel to the cliff's third
* side. */
static void add_river(void)
{
for (int i = 0; i < RIVER_TILE_COUNT; i++) {
float x = RIVER_START_X + RIVER_TILE_STEP * (float)i;
float z = RIVER_START_Z + RIVER_TILE_STEP * (float)i;
Box tile = { { x, 0.0f, z }, { x + RIVER_TILE_SIZE, RIVER_DEPTH, z + RIVER_TILE_SIZE },
false, BOX_STYLE_WATER };
add_box(tile, no_motion());
}
}
/* ---- 3. The cliff course: placement rules ------------------------------ */
#define CLEAR_SIDE_GAP 0.3f /* m; platforms (nearly) over one another must be far apart vertically... */
#define CLEAR_HEADROOM 4.3f /* m; ...by this much, so a jump from the lower can't hit the upper */
#define MOVING_ROCK_GAP 1.0f /* m a moving platform keeps from rock: more than the player is wide, so it can't pin them */
#define MOVING_MIN_BOTTOM 1.0f /* m; a moving platform's underside never goes lower than this */
static bool is_rock(Box b)
{
return b.style == BOX_STYLE_CLIFF;
}
/* Horizontal distance between two footprints (0 if they touch or overlap). */
static float footprint_gap(Box a, Box b)
{
float dx = fmaxf(0.0f, fmaxf(a.min.x - b.max.x, b.min.x - a.max.x));
float dz = fmaxf(0.0f, fmaxf(a.min.z - b.max.z, b.min.z - a.max.z));
return sqrtf(dx * dx + dz * dz);
}
static bool footprints_overlap(Box a, Box b)
{
return a.min.x < b.max.x && a.max.x > b.min.x && a.min.z < b.max.z && a.max.z > b.min.z;
}
/* Vertical space between two boxes (negative if their height ranges overlap). */
static float vertical_gap(Box a, Box b)
{
return fmaxf(a.min.y - b.max.y, b.min.y - a.max.y);
}
/* Can a platform that sweeps through `reach` go here? See the placement
* rules in the prompt above. */
static bool is_clear(Box reach, bool moving)
{
if (moving && reach.min.y < MOVING_MIN_BOTTOM)
return false; /* it would dip into (or skim) the ground */
for (int i = 0; i < s_count; i++) {
Box other = s_reach[i];
if (footprints_overlap(reach, other) && vertical_gap(reach, other) < 0.0f)
return false; /* they'd overlap */
if (is_rock(other)) {
if (moving && footprint_gap(reach, other) < MOVING_ROCK_GAP)
return false;
if (footprints_overlap(reach, other) && vertical_gap(reach, other) < CLEAR_HEADROOM)
return false; /* hovering too low over a rock top */
} else if (footprint_gap(reach, other) < CLEAR_SIDE_GAP &&
vertical_gap(reach, other) < CLEAR_HEADROOM) {
return false;
}
}
return true;
}
/* ---- 3. The cliff course: the band round the cliff --------------------- */
/* The band runs east along the south face from BAND_START_X, turns the
* corner, and runs north along the east face. Each row (a distance `out` from
* the faces) turns the corner at its own spot, so s, the distance along that
* row, is continuous round the turn whether the row hugs the face or not. */
#define BAND_START_X -40.0f /* m; the climb starts west of the south face */
#define BAND_LENGTH 116.0f /* m along a row about 3 m out; rows further out run a bit longer */
#define PLATFORM_THICKNESS 0.5f /* m, every generated platform is a slab this thick */
/* Where a row `out` from the faces (platforms `depth` deep) turns the corner. */
static float corner_s(float out, float depth)
{
return CLIFF_EAST_X + out + 0.5f * depth - BAND_START_X;
}
/* The direction along the band, and the direction away from the face, for
* a platform at s in that row. */
static Vec3 band_along(float s, float out, float depth)
{
return s < corner_s(out, depth) ? vec3_make(1.0f, 0.0f, 0.0f) : vec3_make(0.0f, 0.0f, 1.0f);
}
static Vec3 band_out(float s, float out, float depth)
{
return s < corner_s(out, depth) ? vec3_make(0.0f, 0.0f, -1.0f) : vec3_make(1.0f, 0.0f, 0.0f);
}
/* A box on the band: centered at s along its row, its face-side edge `out`
* meters from the cliff face, `along` long and `depth` deep, from `bottom` to
* `top`. At the corner a row's last south box and first east box meet. */
static Box band_box(float s, float out, float along, float depth, float bottom, float top)
{
Box b;
float turn = corner_s(out, depth);
b.allows_wall_hang = false;
b.style = BOX_STYLE_PLATFORM;
b.min.y = bottom;
b.max.y = top;
if (s < turn) {
float x = BAND_START_X + s;
b.min.x = x - 0.5f * along; b.max.x = x + 0.5f * along;
b.min.z = CLIFF_SOUTH_Z - out - depth; b.max.z = CLIFF_SOUTH_Z - out;
} else {
float z = CLIFF_SOUTH_Z - out - 0.5f * depth + (s - turn);
b.min.x = CLIFF_EAST_X + out; b.max.x = CLIFF_EAST_X + out + depth;
b.min.z = z - 0.5f * along; b.max.z = z + 0.5f * along;
}
return b;
}
/* ---- 3. The cliff course: moving platforms ----------------------------- */
#define MOTION_MIN_PERIOD 3.5f /* s, quickest cycle */
#define MOTION_MAX_PERIOD 7.0f /* s, slowest cycle */
#define MOTION_TRIES 6 /* motions tried for a moving platform before it stays still */
/* A random looping motion: slide along the band, bob up and down, or loop
* round a flat or upright circle. `along` and `out` orient it. */
static BoxMotion random_motion(Vec3 along, Vec3 out)
{
Vec3 up = vec3_make(0.0f, 1.0f, 0.0f);
BoxMotion m = no_motion();
m.period = random_range(MOTION_MIN_PERIOD, MOTION_MAX_PERIOD);
m.phase = random_range(0.0f, 1.0f);
switch (next_random() % 4) {
case 0: /* back and forth along the way */
m.kind = MOTION_SLIDE;
m.a = vec3_scale(along, random_range(1.5f, 3.0f));
break;
case 1: /* up and down */
m.kind = MOTION_SLIDE;
m.a = vec3_scale(up, random_range(1.2f, 2.5f));
break;
case 2: { /* round a flat circle */
float r = random_range(1.2f, 2.0f);
m.kind = MOTION_LOOP;
m.a = vec3_scale(along, r);
m.b = vec3_scale(out, r);
break;
}
default: { /* round an upright circle, like a ferris wheel seat */
float r = random_range(1.2f, 2.0f);
m.kind = MOTION_LOOP;
m.a = vec3_scale(up, r);
m.b = vec3_scale(along, r);
break;
}
}
return m;
}
/* Tries to add a platform, moving if `want_moving` and a random motion fits,
* otherwise still. Returns whether it was added, and whether it moves. */
static bool try_add_platform(Box b, bool want_moving, Vec3 along, Vec3 out, bool *moved)
{
*moved = false;
for (int attempt = 0; want_moving && attempt < MOTION_TRIES; attempt++) {
BoxMotion m = random_motion(along, out);
if (is_clear(reach_of(b, m), true)) {
add_box(b, m);
*moved = true;
return true;
}
}
if (!is_clear(b, false))
return false;
add_box(b, no_motion());
return true;
}
/* ---- 3. The cliff course: height tiers --------------------------------- */
/* Every generated platform's top sits on a grid of TIER_HEIGHT steps measured
* down from the cliff top. So a platform one tier up is a single jump, two
* tiers up is a double (second) jump, and the difference reads at a glance. */
#define TIER_HEIGHT 1.5f /* m; a single jump's step (a full jump lifts the feet 2.33) */
#define CLIMB_TOP (CLIFF_TOP - TIER_HEIGHT) /* the route's last platform: one tier below the top */
/* The nearest height on the tier grid. */
static float snap_to_tier(float y)
{
return CLIFF_TOP - roundf((CLIFF_TOP - y) / TIER_HEIGHT) * TIER_HEIGHT;
}
/* ---- 3. The cliff course: the route (one guaranteed way) --------------- */
/* How far apart two platforms may be for the route: a gap and a rise that a
* normal jump (or a second jump) makes comfortably. Checked by the headless
* course test with margin; these are deliberately cautious. */
#define ROUTE_SECOND_MAX_GAP 1.3f /* m; a second jump from standing covers less ground */
#define ROUTE_DOUBLE_SHARE 0.3f /* usual chance a step is a double (two tiers); never two in a row */
#define ROUTE_MOVING_SHARE 0.35f /* chance a route platform moves (never two in a row) */
#define ROUTE_TRIES 60 /* candidates per step before trying easier hops */
#define ROUTE_MAX 64
#define ROUTE_MIN_OUT 1.5f /* m; route platforms keep at least this far from the face... */
#define ROUTE_WIDEST_OUT 13.0f /* m ...and at most this far (the last one comes in close) */
#define ROUTE_MIN_SIZE 4.0f /* m; generated platforms are this big or bigger... */
#define ROUTE_MAX_SIZE 6.0f /* m ...up to this: room to land and skid with the player's weight */
#define ROUTE_SIDESTEP_SHARE 0.4f /* chance a route step switches rows (out/in) instead of going along */
#define HOP_HALF_WIDTH 0.45f /* m; the player's half width, plus a little, for the clear-path check */
#define HOP_CLEARANCE 2.2f /* m above the higher platform the hop's path must be open (body + arc) */
#define ROUTE_ARRIVE_BY 86.0f /* m along the band the route aims to reach the top by (the face ends ~110) */
#define ROUTE_PULL_IN_HEIGHT 12.0f /* m below the top where the route starts drifting in to the face */
#define ROUTE_SCHEDULE_SLACK 8.0f /* m ahead of schedule along the band that adds 40% to the row-switch chance */
/* How far a normal jump comfortably clears for a given rise. */
static float normal_max_gap(float rise)
{
return 2.4f - 0.5f * fmaxf(rise, 0.0f);
}
/* The route's platforms, so the scatter can sit beside them. */
typedef struct {
float s, out, along, depth; /* where it is on the band, and its size */
Box box;
} RouteStep;
static RouteStep s_route[ROUTE_MAX];
static int s_route_count;
static void remember_route_step(float s, float out, float along, float depth, Box box)
{
if (s_route_count < ROUTE_MAX) {
RouteStep step = { s, out, along, depth, box };
s_route[s_route_count++] = step;
}
}
/* Has the band run past the north end of the east face? The route stays
* beside the faces, so its last hop is always onto the top. */
static bool past_the_faces(Box b)
{
return b.max.z > CLIFF_SOUTH_Z + CLIFF_STRIP_WIDTH * CLIFF_STRIP_COUNT;
}
/* Does `outer` (a box, or everywhere a moving box goes) hold all of `inner`? */
static bool contains(Box outer, Box inner)
{
return outer.min.x <= inner.min.x && outer.min.y <= inner.min.y && outer.min.z <= inner.min.z &&
outer.max.x >= inner.max.x && outer.max.y >= inner.max.y && outer.max.z >= inner.max.z;
}
/* Is the way from `prev` to `next` open? Sweeps the player's box along the
* straight line between their centers, over the height the hop passes
* through, and checks nothing else (a pillar, the cliff, another platform)
* is in the way. A hangable rock in the way would even grab a heightened
* jump out of the air. */
static bool hop_path_clear(Box prev, Box next)
{
float low = fminf(prev.max.y, next.max.y);
float high = fmaxf(prev.max.y, next.max.y) + HOP_CLEARANCE;
for (int step = 0; step <= 10; step++) {
float t = (float)step / 10.0f;
float x = prev.min.x + 0.5f * (prev.max.x - prev.min.x) +
t * (0.5f * (next.min.x + next.max.x) - 0.5f * (prev.min.x + prev.max.x));
float z = prev.min.z + 0.5f * (prev.max.z - prev.min.z) +
t * (0.5f * (next.min.z + next.max.z) - 0.5f * (prev.min.z + prev.max.z));
Box body = { { x - HOP_HALF_WIDTH, low, z - HOP_HALF_WIDTH },
{ x + HOP_HALF_WIDTH, high, z + HOP_HALF_WIDTH }, false, BOX_STYLE_PLATFORM };
for (int i = 0; i < s_count; i++) {
Box other = s_reach[i];
bool is_end = contains(other, prev) || contains(other, next); /* the hop's own platforms */
if (!is_end && footprints_overlap(body, other) && vertical_gap(body, other) < 0.0f)
return false;
}
}
return true;
}
/* Is `next` one comfortable hop from `prev`? */
static bool route_hop_ok(Box prev, Box next, bool second)
{
float gap = footprint_gap(prev, next);
float rise = next.max.y - prev.max.y;
if (second ? gap > ROUTE_SECOND_MAX_GAP : gap > normal_max_gap(rise))
return false;
return hop_path_clear(prev, next);
}
/* The route being walked: where it's got to, and its last platform. */
typedef struct {
float s, top, out, along; /* position along the band, height, distance out, last platform's length */
float depth; /* last platform's depth (out from the face) */
Box last; /* the last platform placed */
bool last_moving;
bool last_double; /* the last step was a double: the next one isn't */
float out_min, out_max; /* the strip of the band this route wanders in */
} RouteWalk;
/* Places the route's next platform if it fits and is a comfortable hop. */
static bool place_route_step(RouteWalk *w, float s, float out, float along, float depth,
float top, bool double_jump, bool may_move)
{
Box b = band_box(s, out, along, depth, top - PLATFORM_THICKNESS, top);
if (past_the_faces(b) || (w->top > 0.0f && !route_hop_ok(w->last, b, double_jump)))
return false;
bool moving;
if (!try_add_platform(b, may_move, band_along(s, out, depth), band_out(s, out, depth), &moving))
return false;
w->s = s; w->top = top; w->out = out; w->along = along; w->depth = depth;
w->last = b; w->last_moving = moving; w->last_double = double_jump;
remember_route_step(s, out, along, depth, b);
return true;
}
/* Tries one random next platform for the route: one tier up (a single jump)
* or, now and then, two tiers up (a double jump, never twice in a row).
* `easy` asks for a short, level or one-tier hop close to the last platform:
* the fallback when normal picks keep failing. */
static bool try_route_step(RouteWalk *w, float double_share, float sidestep_share, bool easy, float skip)
{
bool double_jump = w->top > 0.0f && !easy && !w->last_double && random_chance(double_share);
int tiers = double_jump ? 2 : (easy && random_chance(0.5f)) ? 0 : 1;
float top = w->top > 0.0f ? fminf(w->top + (float)tiers * TIER_HEIGHT, CLIMB_TOP)
: snap_to_tier(TIER_HEIGHT); /* the first platform, up from the ground */
float rise = top - w->top;
bool last = top >= CLIMB_TOP - 0.01f;
float gap = easy ? random_range(0.4f, 0.9f)
: double_jump ? random_range(0.6f, ROUTE_SECOND_MAX_GAP)
: random_range(0.8f, normal_max_gap(rise));
float along = random_range(ROUTE_MIN_SIZE, ROUTE_MAX_SIZE);
float depth = random_range(ROUTE_MIN_SIZE, ROUTE_MAX_SIZE);
float out, s;
bool pulling_in = CLIMB_TOP - w->top < ROUTE_PULL_IN_HEIGHT;
bool sidestep = !easy && random_chance(pulling_in ? 0.6f : sidestep_share);
if (!last && sidestep) {
/* A switchback: hop out to the next row (or back in) instead of along,
* which climbs without using up the band. Near the top, always in. */
/* Coming in toward the face, size the platform to fit the space left. */
float in_depth = fminf(depth, w->out - gap - ROUTE_MIN_OUT);
float out_row = w->out + w->depth + gap; /* the row further out... */
float in_row = w->out - gap - in_depth; /* ...or the row further in */
bool can_out = !pulling_in && out_row <= w->out_max;
bool can_in = in_depth >= ROUTE_MIN_SIZE && in_row >= w->out_min;
if (!can_out && !can_in)
return false;
bool outward = can_out && (!can_in || random_chance(0.5f));
out = outward ? out_row : in_row;
if (!outward)
depth = in_depth;
/* Same spot along the face (give or take a meter), in the new row.
* Each row turns the corner at its own s, so convert through the
* position along the face rather than reusing s. */
bool east = w->s >= corner_s(w->out, w->depth);
float spot = (east ? 0.5f * (w->last.min.z + w->last.max.z)
: 0.5f * (w->last.min.x + w->last.max.x)) + random_range(-1.0f, 1.0f);
s = east ? corner_s(out, depth) + spot - (CLIFF_SOUTH_Z - out - 0.5f * depth)
: spot - BAND_START_X;
/* Hopping in toward the (hangable) face is a single jump: it's lower
* and shorter than a double, so it's less likely to overshoot the
* ledge into the face. */
if (!outward && double_jump)
return false;
} else {
/* Along the band, wandering in and out; the last platform comes in
* close to the face so the top is one hop away. */
out = last ? random_range(0.0f, 0.8f)
: clampf(w->out + random_range(easy ? -1.0f : -2.0f, easy ? 1.0f : 2.0f), w->out_min, w->out_max);
s = w->s + 0.5f * w->along + gap + 0.5f * along + skip;
}
bool may_move = !w->last_moving && !last && !easy && random_chance(ROUTE_MOVING_SHARE);
return place_route_step(w, s, out, along, depth, top, double_jump, may_move);
}
/* The last resort when random picks keep failing: scan nearby spots in order
* (every row out from the face, a range of distances along the band, one
* tier up or level) and take the first that is a comfortable hop and fits. */
static bool rescue_route_step(RouteWalk *w)
{
float size = 0.5f * (ROUTE_MIN_SIZE + ROUTE_MAX_SIZE);
for (int tiers = 1; tiers >= 0; tiers--) {
float top = w->top > 0.0f ? fminf(w->top + (float)tiers * TIER_HEIGHT, CLIMB_TOP)
: snap_to_tier(TIER_HEIGHT);
bool last = top >= CLIMB_TOP - 0.01f;
for (float ds = -4.0f; ds <= 8.0f; ds += 1.0f)
for (float out = last ? 0.0f : w->out_min; out <= (last ? 0.8f : ROUTE_WIDEST_OUT);
out += (last ? 0.4f : 1.0f))
if (place_route_step(w, w->s + ds, out, size, size, top, false, false))
return true;
}
return false;
}
/* Walks the band from the ground to one tier below the top, placing one
* platform per hop, ROUTE_MIN_OUT..ROUTE_WIDEST_OUT out from the face. Steps
* are mostly single jumps (one tier), with doubles (two tiers) mixed in as
* the remaining height needs, never two doubles in a row. When a step can't
* be placed, easier hops are tried, then easy hops a little further along,
* then a scan of nearby spots; the route never leaves a gap it can't cross. */
static void add_climb_route(void)
{
RouteWalk w = { 0.0f, 0.0f, ROUTE_MIN_OUT, 0.0f, 0.0f,
band_box(0.0f, 0.0f, 0.0f, 0.0f, -1.0f, 0.0f), false, false,
ROUTE_MIN_OUT, ROUTE_WIDEST_OUT };
s_route_count = 0;
while (w.top < CLIMB_TOP - 0.01f) {
/* More doubles when there's a lot of height left per meter of band,
* aiming to arrive well before the east face ends. */
float needed = (CLIMB_TOP - w.top) / fmaxf(ROUTE_ARRIVE_BY - w.s, 4.0f) * 4.0f;
float double_share = clampf((needed - TIER_HEIGHT) / TIER_HEIGHT, ROUTE_DOUBLE_SHARE, 0.45f);
/* Row switches climb without moving along the band. The route should
* be about this far along for its height: ahead of that, switch rows
* more; behind it, go along more. */
float on_schedule = ROUTE_ARRIVE_BY * w.top / CLIMB_TOP;
float ahead = w.s - on_schedule;
float sidestep_share = clampf(ROUTE_SIDESTEP_SHARE + ahead / ROUTE_SCHEDULE_SLACK * 0.4f, 0.15f, 0.85f);
/* Near the top, drift in toward the face: the last hop is onto the top. */
if (CLIMB_TOP - w.top < ROUTE_PULL_IN_HEIGHT) {
w.out_min = 0.0f;
w.out_max = fmaxf(0.8f, w.out_max - 3.0f);
w.out = fminf(w.out, w.out_max);
}
bool placed = false;
for (int tries = 0; tries < ROUTE_TRIES && !placed; tries++)
placed = try_route_step(&w, double_share, sidestep_share, false, 0.0f);
for (int tries = 0; tries < ROUTE_TRIES && !placed; tries++)
placed = try_route_step(&w, double_share, sidestep_share, true, 0.0f);
for (float skip = 0.5f; skip <= 3.0f && !placed; skip += 0.5f)
for (int tries = 0; tries < ROUTE_TRIES && !placed; tries++)
placed = try_route_step(&w, double_share, sidestep_share, true, skip);
if (!placed)
placed = rescue_route_step(&w);
if (!placed)
return; /* truly stuck: the course test reports the top as unreachable */
}
}
/* ---- 3. The cliff course: pillars and scatter -------------------------- */
#define PILLAR_COUNT 7
#define SCATTER_COUNT 6
#define SCATTER_MOVING_SHARE 0.6f
#define SCATTER_TRIES 400
/* Does every hop along the climb route still have a clear path? */
static bool route_paths_clear(void)
{
for (int i = 1; i < s_route_count; i++)
if (!hop_path_clear(s_route[i - 1].box, s_route[i].box))
return false;
return true;
}
/* Tall hangable rock pillars a few meters out from the face: each makes a
* chimney with the cliff for wall jumps, and its top is a place to stand.
* They're fitted in AFTER the route, so they never block it: a pillar that
* would stand in the way of one of the route's hops is taken out again. */
static void add_rock_pillars(void)
{
for (int i = 0, tries = 0; i < PILLAR_COUNT && tries < 300; tries++) {
float s = random_range(8.0f, BAND_LENGTH - 8.0f);
float top = CLIFF_TOP * s / BAND_LENGTH + random_range(0.0f, 4.0f);
Box b = band_box(s, random_range(4.0f, 6.0f), random_range(2.0f, 3.5f),
random_range(2.0f, 3.0f), 0.0f, top);
b.allows_wall_hang = true;
b.style = BOX_STYLE_CLIFF;
if (!is_clear(b, false))
continue;
add_box(b, no_motion());
if (route_paths_clear())
i++;
else
s_count--; /* it blocked a hop: take it back out */
}
}
/* Extra platforms beside the route: each sits a single hop from a route
* platform (along the band, or out a row), usually level with it or one tier
* up or down. They're other ways up, shortcuts and dead ends, and most are
* reachable with a single jump. */
static void add_scatter(void)
{
for (int i = 0, tries = 0; i < SCATTER_COUNT && tries < SCATTER_TRIES && s_route_count > 1; tries++) {
RouteStep r = s_route[1 + (int)(next_random() % (uint32_t)(s_route_count - 1))];
int tiers = (int)(next_random() % 3) - 1; /* -1, 0 or +1 */
float top = r.box.max.y + (float)tiers * TIER_HEIGHT;
float gap = random_range(0.8f, 1.5f);
float along = random_range(ROUTE_MIN_SIZE, ROUTE_MAX_SIZE);
float depth = random_range(ROUTE_MIN_SIZE, ROUTE_MAX_SIZE);
float s = r.s, out = r.out;
switch (next_random() % 3) {
case 0: s = r.s + 0.5f * (r.along + along) + gap; break; /* further along */
case 1: s = r.s - 0.5f * (r.along + along) - gap; break; /* back along */
default: out = r.out + r.depth + gap; break; /* out a row */
}
if (top < 1.0f || top > CLIMB_TOP || out < ROUTE_MIN_OUT || out > ROUTE_WIDEST_OUT)
continue;
Box b = band_box(s, out, along, depth, top - PLATFORM_THICKNESS, top);
bool moving;
if (try_add_platform(b, random_chance(SCATTER_MOVING_SHARE), band_along(s, out, depth),
band_out(s, out, depth), &moving))
i++;
}
}
/* ---- 3. The cliff course: the crossing --------------------------------- */
#define CROSS_START_X -15.0f /* m, the top's north-west corner... */
#define CROSS_START_Z 60.0f
#define CROSS_END_X -32.0f /* m ...to the far cliff's nearest corner */
#define CROSS_END_Z 80.0f
#define CROSS_SCATTER 2
#define CROSS_MOVING_SHARE 0.5f
#define CROSS_ROUTE_MAX 16
/* A square platform centered at (x, z) with the given top. */
static Box square_platform(float x, float z, float size, float top)
{
Box b = { { x - 0.5f * size, top - PLATFORM_THICKNESS, z - 0.5f * size },
{ x + 0.5f * size, top, z + 0.5f * size }, false, BOX_STYLE_PLATFORM };
return b;
}
/* The crossing's route: hop by hop along the line from the top's corner to
* the far cliff, on the tier grid (level, one tier up or down, or now and
* then a double), until the far cliff is one single hop away. Remembers its
* platforms in `route` for the extras. Returns how many it placed. */
static int add_crossing_route(Vec3 start, Vec3 along, Vec3 side, Box *route)
{
Box prev = square_platform(CROSS_START_X + 2.5f, CROSS_START_Z - 2.5f, 5.0f, CLIFF_TOP); /* the corner of the top */
float t = 0.0f;
bool prev_moving = false, prev_double = false;
int placed_count = 0;
for (int step = 0; step < CROSS_ROUTE_MAX; step++) {
float to_finish = FAR_CLIFF.max.y - prev.max.y;
if (to_finish <= TIER_HEIGHT + 0.01f && footprint_gap(prev, FAR_CLIFF) <= normal_max_gap(to_finish))
return placed_count;
bool placed = false;
for (int tries = 0; tries < 2 * ROUTE_TRIES && !placed; tries++) {
bool easy = tries >= ROUTE_TRIES; /* second half: short hops */
bool double_jump = !easy && !prev_double && random_chance(0.25f);
/* Mostly up or level while there's height to gain, now and then down. */
float roll = random_range(0.0f, 1.0f);
int tiers = double_jump ? 2 : to_finish <= 0.01f ? (roll < 0.5f ? 0 : -1)
: roll < 0.55f ? 1 : roll < 0.9f ? 0 : -1;
float top = clampf(prev.max.y + (float)tiers * TIER_HEIGHT,
CLIFF_TOP - TIER_HEIGHT, FAR_CLIFF.max.y);
float size = random_range(ROUTE_MIN_SIZE, ROUTE_MAX_SIZE);
float next_t = t + (easy ? random_range(4.0f, 5.5f) : random_range(5.5f, 7.0f));
Vec3 c = vec3_add(vec3_add(start, vec3_scale(along, next_t)),
vec3_scale(side, random_range(-4.0f, 4.0f)));
Box b = square_platform(c.x, c.z, size, top);
if (!route_hop_ok(prev, b, double_jump))
continue;
bool moving;
bool want_moving = !prev_moving && !easy && random_chance(CROSS_MOVING_SHARE);
if (!try_add_platform(b, want_moving, along, side, &moving))
continue;
t = next_t; prev = b; prev_moving = moving; prev_double = double_jump;
route[placed_count++] = b;
placed = true;
}
if (!placed)
return placed_count; /* stuck: the course test reports the finish as unreachable */
}
return placed_count;
}
/* The same idea as the climb on the straight line from the top's corner to
* the far cliff: a guaranteed way across, plus a couple of extras beside it. */
static void add_crossing(void)
{
Vec3 start = vec3_make(CROSS_START_X, 0.0f, CROSS_START_Z);
Vec3 line = vec3_sub(vec3_make(CROSS_END_X, 0.0f, CROSS_END_Z), start);
Vec3 along = vec3_scale(line, 1.0f / vec3_length(line));
Vec3 side = vec3_make(-along.z, 0.0f, along.x);
Box route[CROSS_ROUTE_MAX];
int route_count = add_crossing_route(start, along, side, route);
/* The extras: a single hop to one side of a crossing platform, level with
* it or one tier up or down. */
for (int i = 0, tries = 0; i < CROSS_SCATTER && tries < 200 && route_count > 0; tries++) {
Box r = route[next_random() % (uint32_t)route_count];
float size = random_range(ROUTE_MIN_SIZE, ROUTE_MAX_SIZE);
float dir = random_chance(0.5f) ? 1.0f : -1.0f;
float gap = random_range(0.8f, 1.5f);
Vec3 c = vec3_add(vec3_make(0.5f * (r.min.x + r.max.x), 0.0f, 0.5f * (r.min.z + r.max.z)),
vec3_scale(side, dir * (0.5f * (r.max.x - r.min.x) + gap + 0.5f * size)));
float top = r.max.y + (float)((int)(next_random() % 3) - 1) * TIER_HEIGHT;
Box b = square_platform(c.x, c.z, size, top);
bool moving;
if (try_add_platform(b, random_chance(CROSS_MOVING_SHARE), along, side, &moving))
i++;
}
}
/* ---- Public interface -------------------------------------------------- */
int level_build(LevelBox *out, int capacity)
{
s_out = out;
s_capacity = capacity < LEVEL_MAX_BOXES ? capacity : LEVEL_MAX_BOXES;
s_count = 0;
add_random_platforms();
for (int i = 0; i < WALL_COURSE_COUNT; i++)
add_box(WALL_COURSE[i], no_motion());
seed_random(CLIFF_COURSE_SEED);
add_triangle_cliff();
add_box(FAR_CLIFF, no_motion());
add_river();
add_climb_route();
add_rock_pillars();
add_scatter();
add_crossing();
return s_count;
}
Vec3 level_motion_offset(BoxMotion m, float time)
{
float angle = 2.0f * M3D_PI * (time / m.period + m.phase);
switch (m.kind) {
case MOTION_SLIDE:
return vec3_scale(m.a, sinf(angle));
case MOTION_LOOP:
return vec3_add(vec3_scale(m.a, cosf(angle) - 1.0f), vec3_scale(m.b, sinf(angle)));
default:
return vec3_make(0.0f, 0.0f, 0.0f);
}
}
Vec3 level_spawn_point(void)
{
return vec3_make(0.0f, 0.0f, 0.0f);
}
|