LINUX.ORG.RU
ФорумTalks

Yer another goto 10 labirint generator


1

1

Сегодня по интернетам гуляет переделка старой софтины для генерации лабиринтов. Однако, она использует юникодные символы и, потому, подходит не для всех терминалов. Решил написать свою версию, генерирующую другой вариант лабиринтов, который прекрасно отображается на всех типах терминалов, и который я прекрасно помню по Dungeon Crawl Stone Soup в консоли:

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

int main(){
        srand(time(0));
        for(;;)putchar(((int)(2.0*rand()/(RAND_MAX+1.0))) ? '#' : ' ');
}
PS. Вывод лучше перенаправлять в файл, а то софтина генерирует лабиринты очень шустро. На моей машине за 10 секунд генерируется ~450 Мбайт лабиринтов. PS2. main() всегда int, даже когда в ней бесконечный цикл. Поскольку, дальше бесконечного цикда дело не пойдёт, то нет смысла добавлять «return 0;», в любом случае в оболочку будет возвращено число отличное от нуля.

★★★★★

но ведь это не лабиринты получаются, а отстой

anonymous_sapiens ★★★★★ ()

Ничего интересного в нем не нашел. В предыдущем варианте благодаря слешей хоть была прикольная визуальная иллюзия.

observer ★★★ ()
Последнее исправление: observer (всего исправлений: 1)
Ответ на: комментарий от alman

Есть проходы. И в Dungeon Crawl Stone Soup и в Cryptrover всё есть, и лабиринты отображаются именно таким образом. И в Nethack, можно сказать, всё тоже самое, только там стены строятся из '|' и '-', что может некоторых путать.

saahriktu ★★★★★ ()
Ответ на: комментарий от observer

Вот только работала предыдущая версия только в юникоде. А обычные слеши давали какую-то лабуду.

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от Sadler

Всегда ориентировался на этот кусок мана:

Версия функций rand() и srand() в библиотеке С для Linux использует тот же генератор чисел, что и в функциях random() и srandom(), так что младшие биты в числе случайны настолько, насколько и старшие. В то же время в старой реализации rand() младшие биты являются гораздо менее случайными, чем старшие 

В книге Numerical Recipes in C: The Art of Scientific Computing (William H. Press, Brian P. Flannery, Saul A. Teukolsky, William T. Vetterling; New York: Cambridge University Press, 1992 (2nd ed., p. 277)) даны следующие комментарии:

    "Если Вы желаете получить случайное число в промежутке от 1 до 10, Вы всегда должны использовать старшие биты, например:

        j=1+(int) (10.0*rand()/(RAND_MAX+1.0));

    не следует выполнять такое действие:

        j=1+(rand() % 10);

    (т.е. использовать младшие биты)." 

saahriktu ★★★★★ ()
Ответ на: комментарий от Eddy_Em

И?! Даже если в GNU/Linux описанной проблемы нет, то это вопрос написания хорошо переносимого кода, который будет хорошо работать и на тех системах, где младшие биты являются гораздо менее случайными, чем старшие. От пользователей систем, где младшие биты в числе случайны настолько, насколько и старшие, не убудет, но при этом оно будет работать и у других.

saahriktu ★★★★★ ()
Ответ на: комментарий от saahriktu

это вопрос написания хорошо переносимого кода, который будет хорошо работать и на тех системах, где младшие биты являются гораздо менее случайными, чем старшие

например?

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от Eddy_Em

Во-первых, lrand48() будет наименее предпочтительным выбором там, где RAND_MAX больше чем 2^31-1. Во-вторых, в мане написано:

These functions are declared obsolete by SVID 3, which states that rand(3) should be used instead.

Т.е. ещё в 1986-м году lrand48() была объявлена устаревшей, и было предписано использовать вместо неё rand().

saahriktu ★★★★★ ()
Ответ на: комментарий от saahriktu

lrand48() будет наименее предпочтительным выбором там, где RAND_MAX больше чем 2^31-1

С фига ли гости понаехали? lrand48 возвращает long int, а не int, как rand!

Во-вторых, в мане написано:

These functions are declared obsolete by SVID 3, which states that rand(3) should be used instead.

Т.е. ещё в 1986-м году lrand48() была объявлена устаревшей, и было предписано использовать вместо неё rand().

Бредятина сивой кобылятины! Как ты из rand сгенерируешь нормальный double? Будешь лепить структуру-объединение из double и двух int'ов??? А с drand48 все элементарно. Я даже в лоровики статейку воткнул про ГСЧ.

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от Eddy_Em

А толку, что long int, если значение в диапазоне int? Не скажу как было в 1986-м, но в том же glibc RAND_MAX == INT_MAX == 2^31-1. А, при таком раскладе, lrand48() и rand() возвращают числа из одного и того же диапазона. С другой стороны, с увеличением разрядности архитектур увеличивается и размер int, а, значит, появляется возможность увеличивать INT_MAX и RAND_MAX, в то время как диапазон lrand48() всегда будет ограничен 2^31-1.

saahriktu ★★★★★ ()
Ответ на: комментарий от saahriktu

А толку, что long int, если значение в диапазоне int?

А если надо long? А если double?

Не скажу как было в 1986-м, но в том же glibc RAND_MAX == INT_MAX == 2^31-1. А, при таком раскладе, lrand48() и rand() возвращают числа из одного и того же диапазона

Ничего подобного: lrand48 нормальный long возвращает.

диапазон lrand48() всегда будет ограничен 2^31-1.

Это в какой такой вселенной long == int?

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от Eddy_Em

lrand48() возвращает числа не из [0;LONG_MAX]. В документации написано, что lrand48() возвращает числа из [0;2^31). Возможно, где-то когда-то не INT_MAX был равен 2^31-1, а LONG_MAX, потому и функция стандартизирована с типом long int. Однако, сегодня на практике [0;2^31) вписывается в int, long int здесь избыточен. Что касается случайного double, то простейший вариант:

double y = (double) rand();
y = y / (double) pow(10, 1+floor(log10(y)));
Конструкцию можно дополнять до необходимой точности:
double y1 = (double) rand();
double y2 = (double) rand();
int l1 = 1.0+(int) floor(log10(y1));
int l2 = 1.0+(int) floor(log10(y2));
y1 = y1 / (double) pow(10, (double)l1);
y1 += y2 / (double) pow(10, (double)(l1+l2));

saahriktu ★★★★★ ()
Ответ на: комментарий от saahriktu

Точность будет хреновая. В общем, сейчас накалякаю, как надо делать.

А пока, подтверждаю, что ты был прав:

cat 2.c 
#include <stdio.h>		// printf
#include <stdlib.h>		// random number functions
#include <sys/time.h>		// gettimeofday
#include <limits.h>		// LONG_MAX
#include <math.h>		// floor
#include <unistd.h>		// read
#include <sys/types.h>		// open
#include <sys/stat.h>		// open
#include <fcntl.h>		// open

double dtime(){
	double t;
	struct timeval tv;
	gettimeofday(&tv, NULL);
	t = tv.tv_sec + ((double)tv.tv_usec)/1e6;
	return t;
}

void urandom_ini(){
	double tt = dtime() * 1e6;
	double mx = (double)LONG_MAX;
	srand48((long)(tt - mx * floor(tt/mx)));
}

void dev_random_ini(){
	long r_ini;
	int fd = open("/dev/random", O_RDONLY);
	if(-1 == fd){fprintf(stderr,"Error open /dev/random!\n"); urandom_ini(); return;}
	if(sizeof(long) != read(fd, &r_ini, sizeof(long))){
		fprintf(stderr,"Error read /dev/random!\n"); urandom_ini();
		close(fd); return;
	}
	close(fd);
	srand48(r_ini);
}

int main(int argc, char **argv){
	int i, hist[10];
	long part = LONG_MAX / 10, R;
	dev_random_ini();
	for(i = 0; i < 10; i++) hist[i] = 0;
	for(i = 0; i < 1000000; i++){
		R = lrand48();
		hist[(int)(R / part)]++;
	}
	for(i = 0; i < 10; i++)
		printf("%ld < X < %ld: %d\n", part*i, part*(i+1), hist[i]);
	return 0;
}

gcc -lm 2.c && ./a.out 
0 < X < 922337203685477580: 1000000
922337203685477580 < X < 1844674407370955160: 0
1844674407370955160 < X < 2767011611056432740: 0
2767011611056432740 < X < 3689348814741910320: 0
3689348814741910320 < X < 4611686018427387900: 0
4611686018427387900 < X < 5534023222112865480: 0
5534023222112865480 < X < 6456360425798343060: 0
6456360425798343060 < X < 7378697629483820640: 0
7378697629483820640 < X < 8301034833169298220: 0
8301034833169298220 < X < 9223372036854775800: 0

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от Eddy_Em

Вот:

cat 3.c 
#include <stdio.h>		// printf
#include <stdlib.h>		// random number functions
#include <sys/time.h>		// gettimeofday
#include <limits.h>		// LONG_MAX
#include <math.h>		// floor
#include <unistd.h>		// read
#include <sys/types.h>		// open
#include <sys/stat.h>		// open
#include <fcntl.h>		// open

double dtime(){
	double t;
	struct timeval tv;
	gettimeofday(&tv, NULL);
	t = tv.tv_sec + ((double)tv.tv_usec)/1e6;
	return t;
}

void urandom_ini(){
	double tt = dtime() * 1e6;
	double mx = (double)UINT_MAX;
	srand((unsigned int)(tt - mx * floor(tt/mx)));
}

void dev_random_ini(){
	unsigned int r_ini;
	int fd = open("/dev/random", O_RDONLY);
	if(-1 == fd){fprintf(stderr,"Error open /dev/random!\n"); urandom_ini(); return;}
	if(sizeof(int) != read(fd, &r_ini, sizeof(int))){
		fprintf(stderr,"Error read /dev/random!\n"); urandom_ini();
		close(fd); return;
	}
	close(fd);
	srand(r_ini);
}

typedef union {
	long L;
	double D;
	unsigned int I[2];
} LD;

long rnd(){
	LD r;
	r.I[0] = (rand() << 1 | rand());
	r.I[1] = rand();
	return r.L;
}

int main(int argc, char **argv){
	int i, hist[10], s = 0;
	long part = LONG_MAX / 10, R;
	dev_random_ini();
	for(i = 0; i < 10; i++) hist[i] = 0;
	for(i = 0; i < 1000000; i++){
		R = rnd();
		hist[(int)(R / part)]++;
	}
	for(i = 0; i < 10; i++){
		printf("%ld < X < %ld: %d\n", part*i, part*(i+1), hist[i]);
		s += hist[i];
	}
	printf("Total: %d numbers\n", s);
	return 0;
}

gcc -lm 3.c && ./a.out 
0 < X < 922337203685477580: 99989
922337203685477580 < X < 1844674407370955160: 100490
1844674407370955160 < X < 2767011611056432740: 100048
2767011611056432740 < X < 3689348814741910320: 99839
3689348814741910320 < X < 4611686018427387900: 99679
4611686018427387900 < X < 5534023222112865480: 99907
5534023222112865480 < X < 6456360425798343060: 100391
6456360425798343060 < X < 7378697629483820640: 99900
7378697629483820640 < X < 8301034833169298220: 99698
8301034833169298220 < X < 9223372036854775800: 100059
Total: 1000000 numbers

вот — для десяти миллионов:

Make distribution of 10000000 random numbers
0 < X < 922337203685477580: 999239
922337203685477580 < X < 1844674407370955160: 1000186
1844674407370955160 < X < 2767011611056432740: 1000296
2767011611056432740 < X < 3689348814741910320: 1001116
3689348814741910320 < X < 4611686018427387900: 1000714
4611686018427387900 < X < 5534023222112865480: 998833
5534023222112865480 < X < 6456360425798343060: 999500
6456360425798343060 < X < 7378697629483820640: 1000769
7378697629483820640 < X < 8301034833169298220: 1000420
8301034833169298220 < X < 9223372036854775800: 998927
Total: 10000000 numbers
Вполне себе равномерненько получается.

Eddy_Em ☆☆☆☆☆ ()

Проводить свои тесты вряд ли имеет смысл, т.к. все это уже сделано до нас. Есть набор статистических тестов TestU01 для ГПСЧ, статья про него — http://www.iro.umontreal.ca/~lecuyer/myftp/papers/testu01.pdf. Там есть интересная табличка результатов сравнения различных ГПСЧ, выпишу несколько строчек из нее для Ъ. Первые две колонки — время генерации 100 миллионов случайных чисел в секундах на 32-битном Pentium 4 и 64-битном Athlon 64 соответственно. Три следующих колонки — число проваленных тестов в наборах SmallCrush, Crush (тесты последовательностей из ~2^35 чисел) и BigCrush (2^38 чисел).

LCG(2^48, 25214903917, 11) | 4.1 | 0.65 |  4 |  21 | -- *"LCG(2^48, 25214903917, 11) is the drand48" 
                                                         from the Unix standard library.
LCG(2^31–1, 16807, 0)      | 3.8 | 3.6  |  3 |  42 | -- *rand() в BSD-шном libc
LCG(2^32, 69069, 1)        | 3.2 | 0.67 | 11 | 106 | -- *часто используется из-за простоты запоминания
Unix-random-32             | 4.7 | 1.6  |  5 | 101 | -- *это все rand() в glibc. "The Unix-random’s are RNGs of 
Unix-random-64             | 4.7 | 1.5  |  4 |  57 | --  different sizes derived from BSD Unix and available 
Unix-random-128            | 4.7 | 1.5  |  2 |  13 | 19  as function random() on several Unix-Linux platforms. 
Unix-random-256            | 4.7 | 1.5  |  1 |   8 | 11  They are LFib(232, 7, 3, +), LFib(232, 15, 1, +), 
                                                         LFib(232, 31, 3, +) and LFib(232, 63, 1, +), with 
                                                         the least significant bit of each random number dropped."
ran3 / LFib(10^9,55,24,−)  | 2.2 | 0.9  |    |  11 | 17 *вариации используются много где, напр., Mono / .NET
Java.util.Random           | 6.3 | 0.76 |  1 |   9 | 21
MT19937                    | 4.3 | 1.6  |    |   2 |  2 *очень много где, включая c++11, Питон, Ruby и т.д.
LFib(2^48, 607, 273, +)    | 2.4 | 1.4  |    |   2 |  2 *есть в бусте

Там же указаны хорошие ГПСЧ — быстрые и проходящие все тесты. В общем, значительная часть стандартных библиотечных генераторов основаны на допотопных алгоритмах и проваливает те или иные статистические тесты, использовать их можно с определенной осторожностью. Там, где по умолчанию используется MT19937, можно использовать его.

trycatch ★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.