92 lines
2.4 KiB
C
92 lines
2.4 KiB
C
#include <stdlib.h>
|
|
#include <stdbool.h>
|
|
#include <string.h>
|
|
#include <inttypes.h>
|
|
#include <stdio.h>
|
|
#include <math.h>
|
|
|
|
#include "common.c"
|
|
|
|
|
|
/// This one starts with a small (1024 typically) power of two stack
|
|
/// of sand grains, applies gravity on it, and multiply the resulting
|
|
/// grid by two. This is done iteratively until the needed number of
|
|
/// grains is reached.
|
|
///
|
|
/// The resulting grid is the same, but the performance are not
|
|
/// better.
|
|
|
|
void sandpile_multiply(int width, int **terrain, int mul)
|
|
{
|
|
for (int x = 0; x < width; x++)
|
|
for (int y = 0; y < width; y++)
|
|
terrain[x][y] *= mul;
|
|
}
|
|
|
|
void apply_gravity(int width, int **terrain)
|
|
{
|
|
bool did_something;
|
|
int div;
|
|
|
|
while (1) {
|
|
did_something = false;
|
|
for (int x = 0; x < width; x++) {
|
|
for (int y = 0; y < width; y++) {
|
|
if (terrain[x][y] >= 4) {
|
|
did_something = true;
|
|
div = terrain[x][y] / 4;
|
|
terrain[x][y] %= 4;
|
|
terrain[x - 1][y] += div;
|
|
terrain[x + 1][y] += div;
|
|
terrain[x][y + 1] += div;
|
|
terrain[x][y - 1] += div;
|
|
}
|
|
}
|
|
}
|
|
if (!did_something)
|
|
return;
|
|
}
|
|
}
|
|
|
|
|
|
int **sandpile_new(int width)
|
|
{
|
|
int **terrain = calloc(width, sizeof(int*));
|
|
int *data = calloc(width * width, sizeof(int));
|
|
for (int i = 0; i < width; i++) {
|
|
terrain[i] = data + i * width;
|
|
}
|
|
return terrain;
|
|
}
|
|
|
|
|
|
int main(int argc, char **argv)
|
|
{
|
|
args args = {0};
|
|
|
|
if (parse_args(argc, argv, &args))
|
|
return EXIT_FAILURE;
|
|
|
|
int width = sandpile_width(args.height);
|
|
int **terrain = sandpile_new(width);
|
|
terrain[width / 2][width / 2] = args.height;
|
|
int target_power_of_two = (int)log2(args.height);
|
|
int current_height = args.height > 1024 ? 1024 : args.height;
|
|
terrain[width / 2][width / 2] = current_height;
|
|
|
|
apply_gravity(width, terrain);
|
|
for (int power_of_two = 10; power_of_two < target_power_of_two; power_of_two++) {
|
|
current_height *= 2;
|
|
sandpile_multiply(width, terrain, 2);
|
|
apply_gravity(width, terrain);
|
|
}
|
|
|
|
if (current_height != args.height) {
|
|
terrain[width / 2][width / 2] += args.height - current_height;
|
|
apply_gravity(width, terrain);
|
|
}
|
|
|
|
save_terrain(width, terrain, &args);
|
|
return EXIT_SUCCESS;
|
|
}
|