|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vovanius Uryvaeff 2:5020/175.2 29 Jun 2003 01:40:48
To : Yura Balyuk
Subject : Игpа "Жизнь" в 3Д
--------------------------------------------------------------------------------
Thu Jun 26 2003 18:52, Yura Balyuk wrote to Vovanius Uryvaeff:
YB> Здpавствyйте Vovanius.
RG>>> Слyшай - pаз ты этим занимаешься, не pасскажешь, пожалyйста,
RG>>> какие алгоpитмы сyществyют для обычной игpы? А то я ноpмальных
RG>>> пpоцессоpов видел, пожалyй, только один - но что и где - не помню...
VU>> Я пытался писать хитpый алгоpитм, котоpый обpабатывал поле блоками
VU>> 30х30. Хитpость заключалась в том, что каждая стpока обсчитывалась за
VU>> один пpоход посpедством логических опеpаций (стpока целиком заносилась
VU>> в int) Пpавда потом как-то стало не до этого. Может что-нить такое-же
VU>> pеализовывал? Блоки хpанились списком и дополнительно кэшиpовались, но
VU>> это неважно.
YB> как так кэшиpовались? чё за алгоpитм?
Я же его не дописал.
Суть такая в общем: записал я условие существования клетки на нектором шаге
эволюции через серию логических операций:
пусть
A,B,C,D,E,F,G,H - значения клеток вокруг данной - принимают значения
{true;false}
X - состояние клетки на данном этапе
Y - сотояние клетки на следующем этапе.
остальные буквы-временные переменные.
J = A and B; K = A xor B
J = J xor (K and C); K = K xor C
I = J and K and D; J = J xor (K and D); K = K xor D
I = I or (J and K and E); J = J xor (K and E); K = K xor E
I = I or (J and K and F); J = J xor (K and F); K = K xor F
I = I or (J and K and G); J = J xor (K and G); K = K xor G
I = I or (J and K and H); J = J xor (K and H); K = K xor H
Y = (J and (K or X)) and not I
то есть получается примерно такой итератор блока (на C):
for(i = 1; i<=30; i++) {
J = (X[i-1]>>1)&X[i-1]; K = (X[i-1]>>1)^X[i-1];
<...skipped...>
I |= J&K&(X[i+1]<<1); J ^= K&(X[i+1]<<1); K ^= X[i+1]<<1;
Y[i] = J&(K|X[i])&~I;
}
то есть ~40 логических операций на 30 клеток -> 1.3 операции на клетку вместо
~10 по классическому алгоритму. Да еще и плотная упаковка.
А насчет кэширования я описался, я _Х_ешировал список - разбивал на 256
списков так, чтобы кластеры распределялись по ним согласно младшим битам
координат. N=x&0x0F|(y<<4)&0xF0
для ускорения поиска соседних кластеров.
По подобному методу была написана программа эволюции по закону Y=X xor Left
xor Right xor Upper xor Lower. Которая просто итерировала большой
прямоугольный массив (правда она работала напрямую с железом). ~30fps на 50MHz
(320x240). А жизнь я так и не дописал.
Send Email to vovanius2000<yxo>mail. ru
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
