- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
function findeFreePlace()
{
try
{
var x = random(gs.cells.x - 1),
y = random(gs.cells.y - 1);
if (gs.balls[y][x] != null)
{
return findeFreePlace();
}
else
{
return [x, y];
}
}
catch (e)
{
isEndGame = true;
showfinish();
return false;
}
}
Follow us!
>finde
староанглийским каким-то отдает, по-моему.
И автора метода Монте-Карло тоже надо уебать?
> детерминированным алгоритмом
Ага. Самое тупое - посчитать сколько клеток пустых, сгенерить один ранд, и отсчитать клеточки до нужной.
А ещё надо уебать тех, кто обрывает фразы, меняя их смысл.
Но ведь вырывать фразы из контекста так весело... хотя, с другой стороны, уебать того, кто их вырывает не менее весело.
Если же это не ГСЧ а ГПСЧ - то ничего сказать нельзя. И тут уже вероятность того, что мы попадем в свободную клетку может быть равной нулю.
И за сколько? Гарантированно за 100 выборок, да?
В среднем за 100 выборок ;) Гарантий тут никто не даст.
С вероятностью, не равной нулю, сия фигня переполнит стек даже если есть пустые ячейки.
Но так как всё делается на ГПСЧ, то достаточной всего лишь доказать, что максимальное число выборок для любого начального положения, содержащего свободную клетку, и любого исходного состояния генератора не превышает некоторой константы, и что при любом состоянии интерпретатора, могущем возникнуть в процессе игры, данная глубина стека не вызовет его переполнение.
В общем, не верю я, что автор сего творения проделал сей матан, и если его хорошенько припугнуть необходимостью всё это доказывать, то он глядишь и переделает этот код как надо.
...зависнет винда.
...в тщательно вылизанном куске кода все же будет ошибка.
...проявится 0-day бага в интерпретаторе JS, вызванная совсем другой процедурой.
...на голову упадет метеорит.
...пролетевшая космическая частица переключит ячейку памяти.
На доске 9х9 одна свободная клетка за одну итерацию не найдется с вероятностью 0.9877.
Вероятность того, что клетка не найдется за 100 итераций - 0.289
за 1000 итераций - 4/1'000'000.
Так что я, конечно, понимаю уродство решения, но с практической точки зрения придраться не к чему. (по крайней мере, если принять числа истинно случайными)
если ГСЧ хуевый, игра может навечно уйти в поиск, так что по уму - лучше сгенерить список координат клеток, и перемешать, а потом проходить по списку типа "случайная клетка"
Либо держать пул пустых клеток и выполнять операцию за O(1), либо, если уж очень хочется использовать ГСЧ, использовать случайные координаты как начальное приближение, а дальше искать детерминированным алгоритмом.
какую?
Освобождение клетки: клетка добавляется в случайное место списка (фактически, добавляется в конец, а потом меняется местом со случайным элементом). О(1)
Выбор случайной клетки: берем (с удалением) из списка последний элемент. О(1)
Только вот занятие заданной пользователем клетки - нужно ее найти и удалить из списка. O(n)
В коридоре на работе есть комната с табличкой "АХО". Когда я прохожу мимо неё, в моём мозгу всегда отзывается эхом одно и тоже слово. "Ульман".