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
|
/*
* ============================================================
* 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 a few meters out
* from the faces, so they form chimneys with the cliff.
* 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`. On it:
* - one ROUTE: big platforms (ROUTE_MIN_SIZE..MAX) placed
* one hop after another (a normal jump or a second
* jump, with the path between them clear) from the
* ground to one hop below the top. It guarantees the
* climb is possible but isn't marked: it wanders in
* and out and takes switchbacks (hopping out to the
* next row or back in instead of along). Hops in
* toward the hangable face are normal jumps, so an
* overshoot can't grab the face. Each row turns the
* corner at its own spot (corner_s) so `s` is
* continuous round the turn. The route paces itself
* to arrive by ROUTE_ARRIVE_BY, stays beside the faces,
* drifts in for its last hop, and when boxed in tries
* easier hops, a scan of nearby spots, then (once) a
* wider strip.
* - the SCATTER: a few more platforms (SCATTER_COUNT) at
* random spots and heights around the route: other ways up,
* shortcuts, dead ends, and jumps that look possible
* but aren't. That ambiguity is WANTED: the player
* should have to judge which paths are feasible.
* The river overlapping water tiles along the diagonal, parallel
* to the cliff's third side.
* The crossing the same idea (a route plus a couple of extras) on
* the straight line from the
* top's north-west corner over the river to the far
* cliff (60 m, 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 in all.
* ============================================================
*/
#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, 60 m up, across the river. */
static const Box FAR_CLIFF = { { -70.0f, 0.0f, 80.0f }, { -32.0f, 60.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 -34.0f /* m; the climb starts west of the south face */
#define BAND_LENGTH 110.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: 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_NORMAL_MAX_RISE 1.7f /* m; a full jump lifts the feet 2.33 */
#define ROUTE_SECOND_MIN_RISE 2.0f /* m; second-jump steps rise at least this... */
#define ROUTE_SECOND_MAX_RISE 2.9f /* m ...and at most this (it lifts the feet 4.08) */
#define ROUTE_SECOND_MAX_GAP 1.3f /* m; a second jump from standing covers less ground */
#define ROUTE_MOVING_SHARE 0.4f /* 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_WIDEST_OUT 9.0f /* m; how far out a boxed-in route may wander */
#define ROUTE_MIN_SIZE 3.0f /* m; generated platforms are this big or bigger... */
#define ROUTE_MAX_SIZE 4.5f /* m ...up to this: room to land and skid with the player's weight */
#define ROUTE_SIDESTEP_SHARE 0.35f /* 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 80.0f /* m along the band the route aims to reach the top by (the face ends ~104) */
#define ROUTE_PULL_IN_HEIGHT 12.0f /* m below the top where the route starts drifting in to the face */
#define CLIMB_TOP (CLIFF_TOP - 1.2f) /* the route's last platform: a hop below the top */
/* 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 height at each s, for placing the scatter around it. */
static float s_route_s[ROUTE_MAX], s_route_top[ROUTE_MAX];
static int s_route_count;
static float route_height_at(float s)
{
if (s_route_count == 0 || s <= s_route_s[0])
return 0.0f;
for (int i = 1; i < s_route_count; i++) {
if (s <= s_route_s[i]) {
float t = (s - s_route_s[i - 1]) / (s_route_s[i] - s_route_s[i - 1]);
return s_route_top[i - 1] + t * (s_route_top[i] - s_route_top[i - 1]);
}
}
return s_route_top[s_route_count - 1];
}
static void remember_route_point(float s, float top)
{
if (s_route_count < ROUTE_MAX) {
s_route_s[s_route_count] = s;
s_route_top[s_route_count] = top;
s_route_count++;
}
}
/* 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;
float out_min, out_max; /* the strip of the band this route wanders in */
bool remember; /* record its heights for placing the scatter */
} RouteWalk;
/* Tries one random next platform for the route. `easy` asks for a short,
* low hop close to the last platform: the fallback when normal picks keep
* failing (at the corner, or next to a pillar). */
static bool try_route_step(RouteWalk *w, float second_share, bool easy, float skip)
{
bool second = w->top > 0.0f && !easy && random_chance(second_share);
float rise = second ? random_range(ROUTE_SECOND_MIN_RISE, ROUTE_SECOND_MAX_RISE)
: easy ? random_range(0.2f, 1.0f)
: random_range(0.9f, ROUTE_NORMAL_MAX_RISE);
rise = fminf(rise, CLIMB_TOP - w->top);
bool last = w->top + rise >= CLIMB_TOP - 0.01f;
float gap = easy ? random_range(0.3f, 0.9f)
: second ? random_range(0.6f, ROUTE_SECOND_MAX_GAP)
: random_range(0.6f, 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;
if (!last && !easy && random_chance(pulling_in ? 0.6f : ROUTE_SIDESTEP_SHARE)) {
/* 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. */
bool outward = !pulling_in &&
(w->out < 1.0f || (w->out + w->depth + gap + depth < w->out_max && random_chance(0.5f)));
out = outward ? w->out + w->depth + gap : w->out - gap - depth;
s = w->s + random_range(-1.0f, 1.0f);
if (out < 0.0f || out > ROUTE_WIDEST_OUT)
return false;
/* Hopping in toward the (hangable) face is a normal jump: a second
* jump keeps heightened_movement on, so an overshoot would grab the
* face instead of landing. */
if (!outward && second)
return false;
} else {
/* Along the band, wandering in and out; the last platform hugs the face
* so the top is a hop away. */
out = last ? random_range(0.0f, 0.6f)
: clampf(w->out + random_range(easy ? -1.0f : -2.5f, easy ? 1.0f : 2.5f), w->out_min, w->out_max);
s = w->s + 0.5f * w->along + gap + 0.5f * along + skip;
}
float top = w->top + rise;
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, second)))
return false;
bool moving;
bool want_moving = !w->last_moving && !last && !easy && random_chance(ROUTE_MOVING_SHARE);
if (!try_add_platform(b, want_moving, 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;
if (w->remember)
remember_route_point(s, top);
return true;
}
/* 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, a few
* rises) and take the first that is a comfortable hop and fits. */
static bool rescue_route_step(RouteWalk *w)
{
static const float RISES[] = { 1.4f, 1.0f, 0.6f, 0.3f };
float size = 0.5f * (ROUTE_MIN_SIZE + ROUTE_MAX_SIZE);
for (int r = 0; r < 4; r++) {
float rise = fminf(RISES[r], CLIMB_TOP - w->top);
bool last = w->top + rise >= CLIMB_TOP - 0.01f;
for (float ds = -3.0f; ds <= 7.0f; ds += 1.0f) {
for (float out = 0.0f; out <= (last ? 0.6f : ROUTE_WIDEST_OUT); out += (last ? 0.3f : 1.0f)) {
float s = w->s + ds, top = w->top + rise;
Box b = band_box(s, out, size, size, top - PLATFORM_THICKNESS, top);
bool moving;
if (past_the_faces(b) || !route_hop_ok(w->last, b, false) ||
!try_add_platform(b, false, band_along(s, out, size), band_out(s, out, size), &moving))
continue;
w->s = s; w->top = top; w->out = out; w->along = size; w->depth = size;
w->last = b; w->last_moving = false;
if (w->remember)
remember_route_point(s, top);
return true;
}
}
}
return false;
}
/* Walks the band from the ground to one hop below the top, placing one
* platform per hop, wandering between out_min and out_max from the face.
* Steps are mostly normal-jump rises, with second-jump rises mixed in as
* often as the remaining height needs. 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(float out_min, float out_max, bool remember)
{
RouteWalk w = { 0.0f, 0.0f, out_min, 0.0f, 0.0f, band_box(0.0f, 0.0f, 0.0f, 0.0f, -1.0f, 0.0f), false,
out_min, out_max, remember };
bool widened = false;
if (remember) {
s_route_count = 0;
remember_route_point(0.0f, 0.0f);
}
while (w.top < CLIMB_TOP - 0.01f) {
/* Mix in more second jumps when there's a lot of height left per meter,
* aiming to arrive well before the east face ends. */
float needed = (CLIMB_TOP - w.top) / fmaxf(ROUTE_ARRIVE_BY - w.s, 4.0f) * 3.8f;
/* 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.6f, w.out_max - 2.0f);
w.out = fminf(w.out, w.out_max);
}
float second_share = clampf((needed - 1.2f) / 1.3f, 0.15f, 0.9f);
bool placed = false;
for (int tries = 0; tries < ROUTE_TRIES && !placed; tries++)
placed = try_route_step(&w, second_share, false, 0.0f);
for (int tries = 0; tries < ROUTE_TRIES && !placed; tries++)
placed = try_route_step(&w, second_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, second_share, true, skip);
if (!placed)
placed = rescue_route_step(&w);
if (!placed && !widened) {
/* Boxed in (by pillars or the other route): wander wider from here
* on (once; near the top the pull-in narrows it again). */
widened = true;
w.out_min = 0.0f;
w.out_max = ROUTE_WIDEST_OUT;
continue;
}
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 5
#define SCATTER_MOVING_SHARE 0.8f
#define SCATTER_TRIES 6000
/* 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. */
static void add_rock_pillars(void)
{
for (int i = 0, tries = 0; i < PILLAR_COUNT && tries < 200; 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(3.5f, 5.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)) {
add_box(b, no_motion());
i++;
}
}
}
/* Extra platforms at random spots and heights around the route: other ways
* up, shortcuts, and dead ends. */
static void add_scatter(void)
{
for (int i = 0, tries = 0; i < SCATTER_COUNT && tries < SCATTER_TRIES; tries++) {
float s = random_range(0.0f, BAND_LENGTH);
float top = clampf(route_height_at(s) + random_range(-3.0f, 2.5f), 0.8f, CLIFF_TOP - 0.5f);
float out = random_range(0.0f, 10.0f);
float depth = random_range(ROUTE_MIN_SIZE, ROUTE_MAX_SIZE);
Box b = band_box(s, out, random_range(ROUTE_MIN_SIZE, ROUTE_MAX_SIZE), 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.6f
/* 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;
}
/* One guaranteed way across: hop by hop along the crossing line, keeping
* between side_min and side_max of it, until the far cliff is one hop away.
* Like the climb, it falls back to shorter hops rather than leaving a gap. */
static void add_crossing_route(Vec3 start, Vec3 along, Vec3 side, float side_min, float side_max)
{
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;
for (int step = 0; step < 20; step++) {
if (footprint_gap(prev, FAR_CLIFF) <= normal_max_gap(FAR_CLIFF.max.y - prev.max.y))
return;
bool placed = false;
for (int tries = 0; tries < 2 * ROUTE_TRIES && !placed; tries++) {
bool easy = tries >= ROUTE_TRIES; /* second half: short, low hops */
bool second = !easy && random_chance(0.3f);
float rise = second ? random_range(ROUTE_SECOND_MIN_RISE, 2.6f)
: easy ? random_range(-0.5f, 0.8f) : random_range(-1.0f, 1.2f);
float top = clampf(prev.max.y + rise, CLIFF_TOP, FAR_CLIFF.max.y - 0.5f);
float size = random_range(ROUTE_MIN_SIZE + 0.2f, ROUTE_MAX_SIZE);
float next_t = t + (easy ? random_range(2.5f, 4.0f) : random_range(4.0f, 5.5f));
Vec3 c = vec3_add(vec3_add(start, vec3_scale(along, next_t)),
vec3_scale(side, random_range(side_min, side_max)));
Box b = square_platform(c.x, c.z, size, top);
if (!route_hop_ok(prev, b, second && top - prev.max.y >= ROUTE_SECOND_MIN_RISE))
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;
placed = true;
}
if (!placed)
return; /* stuck: the course test reports the finish as unreachable */
}
}
/* 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. */
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);
float length = vec3_length(line);
Vec3 along = vec3_scale(line, 1.0f / length);
Vec3 side = vec3_make(-along.z, 0.0f, along.x);
add_crossing_route(start, along, side, -3.0f, 3.0f);
/* The scatter: more platforms either side of the line. */
for (int i = 0, tries = 0; i < CROSS_SCATTER && tries < 300; tries++) {
Vec3 c = vec3_add(vec3_add(start, vec3_scale(along, random_range(2.0f, length))),
vec3_scale(side, random_range(-7.0f, 7.0f)));
Box b = square_platform(c.x, c.z, random_range(ROUTE_MIN_SIZE, ROUTE_MAX_SIZE), random_range(54.5f, 61.0f));
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_rock_pillars();
add_climb_route(0.0f, ROUTE_WIDEST_OUT, true);
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);
}
|