Морской бой: расстановка кораблей на поле.

[kondra007]

Здравствуйте, уважаемые форумчане!

Интересует вопрос: какой правильный алгоритм расстановки кораблей на поле в Морском бое?
Я пытаюсь написать свой, но он, очевидно, не работает.
Прошу прощения за быдлокод, догадываюсь, что можно всё поставить одним циклом, но этим займусь позже, пусть хоть как-то работает.
На данный момент кораблям можно стоять рядом, но проблема их коллизий меня волнует сильно.

Например, расстановка трехпалубника:

[syntax=java] private static void place_third() {
int x = 0;
int y = 0;
int rand = (Math.random()<0.5)?0:1; // Выбираем случайное направление: вниз или вправо
// Log.d(TAG, "Направление = " + rand);
switch(rand) {
case DIRECTION_RIGHT:
x = (int) ((Math.random() * 7)); // до 7, чтобы не выйти за границы поля ненароком
y = (int) ((Math.random() * 9));
for (int i=0; i<3; i++) {
if (field[x+i][y] == IS_WATER) // если клетка не занята...
field[x+i][y] = IS_SHIP; // ... то займем её!
else {
rollback_firstCoord(x+i, y, i); // функция отката
place_third(); // пересоздание корабля
}
Log.d(TAG, "Координаты трехпалубника: [" + (x + i + 1) + "] [" + (y + 1) + "];" );
}
break;
case DIRECTION_DOWN:
x = (int) ((Math.random() * 9));
y = (int) ((Math.random() * 7)); // до 7, чтобы не выйти за границы поля ненароком
for (int i=0; i<3; i++) {
if (field[x][y+i] == IS_WATER) // если клетка не занята...
field[x][y+i] = IS_SHIP; // ... то займем её!
else {
rollback_secondCoord(x, y+i, i); // функция отката
place_third(); // пересоздание корабля
// break;
}
Log.d(TAG, "Координаты трехпалубника: [" + (x+1) + "] [" + (y + 1 + i) + "];" );
}
break;
}
}[/syntax]

функция отката, упоминавшаяся выше, выглядит так (приведу пример одной из них)

[syntax=java]private static void rollback_firstCoord (int x, int y, int stage) { // на вход получаем координаты "плохой" клетки и сколько участков корабля уже успели установить (для удаления)
Log.d(TAG,"rollback по первой координате");
for (int j=0; j<stage; j++)
field[x-j-1][y] = 0; // -1, чтобы не удалить клетку существующего уже корабля
}[/syntax]

Но в итоге получаются и пересечения, и какие-то разрывы (по одной клетке)...и почему-то периодически возникает мифическая клетка в (1;1), которая даже не передается на отрисовку.

Может, кто-нибудь подскажет, что исправить надо? Или дайте линк на уже готовый алгоритм.
Спасибо.

[Yoric]

После вызова метода

Код: Выделить всё

place_third(); 

нужен

Код: Выделить всё

break;

в обоих местах, в одном у вас закомментировано.

[kondra007]

Блин, точно, спасибо!

[kondra007]

Я сейчас пытаюсь сделать так, чтобы корабли разделялись одной клеткой (как в нормальном МБ), но вот проблема - не знаю, как учитывать выходы за массив (ведь если корабль "у стеночки", то часть его окружения будет выпадать за пределы поля).

Подскажите, как обойти это?

[Yoric]

Возможно добавить условие для проверки не выходит ли проверяемое поле за размер массива, и если выходит то не проверять просто. Или покажите свои текущие наработки и будем думать

[kondra007]

Вот частичка этого быдлокода тут)
http://pastebin.com/tNkvTPJz

[Yoric]

Судя по коду выход за пределы массива возможны только тут

Код: Выделить всё

if(field[x+i][y] != IS_SHIP) {

Что если добавить еще одно условие

Код: Выделить всё

if(x+i < field.length && field[x+i][y] != IS_SHIP) {

Тогда не должны проверятся точки за пределами массива.

[kondra007]

Спасибо) попробую завтра.

То есть, добавляю условие и дописываю обход всех точек вокруг?

[Yoric]

Условие для того чтобы не проверялись точки за пределами массива. А вот что вы в методе делать собираетесь незнаю)

[kondra007]

хм..странное условие...ведь за пределы массива может попасть аж 7 точек (четырехпалубник начинается в 1.1 и идет до 1.4 вниз)

[Yoric]

Это условие только для точек по горизонтали. Нету смысла проверять точки за пределами игрового поля. Хотя неясно какие значения может принимать переменная Х, если она может принимать отрицательные значения то нужно еще условия для них.

[kondra007]

У меня была мысль такая:
начинаем проверять все точки вокруг. Если успех, то плюсуем счетчик.
В итоге получаем некоторое число, которое сравниваем с наперед высчитанным для данного типа корабля. Если равно - то ставим корабль, если нет, то запускаем поиск заново. Тупо, но работает.
Проблема в том, что при выходе за границы массива ловится IndexOutOfBoundException.
Назревает вопрос: если я в этом эксепшене допишу инкремент счетчика, то после выхода из исключения разве продолжится поиск?
Ведь если нет, то заведомо нормальное положение (в углу, например) будет всегда восприниматься как неподходящее.

Надеюсь, Вы понимаете мою мысль.

[Yoric]

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

[kondra007]

Я понимаю, но другого выхода не вижу в данной ситуации. У Вас есть идея лучше?

[Yoric]

Уверен что можно что-то придумать, но уже завтра

[kondra007]

Хорошо

[kondra007]

Возникла проблема.

Написал метод расстановки (чтобы не соприкасались), так теперь корабли отказываются вставать на края карты!
Код:
[syntax=java]
private static boolean checkIfShipAvailable(int x, int y, int dir, int length) {
int counter = 0;
switch(dir) {
case DIRECTION_RIGHT:
try {
if(field[x-1][y] == IS_WATER) counter++; // слева
if(field[x-1][y-1] == IS_WATER) counter++; // лево-вниз
if(field[x-1][y+1] == IS_WATER) counter++; // лево-вверх
if(field[x][y-1] == IS_WATER) counter++; // внизу
if(field[x][y+1] == IS_WATER) counter++; // вверху
if(field[x+1][y-1] == IS_WATER) counter++; // право-вниз
if(field[x+1][y+1] == IS_WATER) counter++; // право-вверх

if(field[x+length-1][y-1] == IS_WATER) counter++;
if(field[x+length-1][y+1] == IS_WATER) counter++;
if(field[x+length][y] == IS_WATER) counter++;
if(field[x+length][y-1] == IS_WATER) counter++;
if(field[x+length][y+1] == IS_WATER) counter++;
} catch (IndexOutOfBoundsException e) {
counter++;
}
Log.d(TAG, "Direction: Right. Counter = " + counter);
if (counter == 12)
return true;
counter = 0;
break;

case DIRECTION_DOWN:
try {
if(field[x-1][y-1] == IS_WATER) counter++ ;
if(field[x][y-1] == IS_WATER) counter++ ;
if(field[x+1][y-1] == IS_WATER) counter++ ;
if(field[x-1][y] == IS_WATER) counter++ ;
if(field[x+1][y] == IS_WATER) counter++ ;
if(field[x-1][y+1] == IS_WATER) counter++ ;
if(field[x+1][y+1] == IS_WATER) counter++ ;

if(field[x-1][y+length-1] == IS_WATER) counter++ ;
if(field[x+1][y+length-1] == IS_WATER) counter++ ;
if(field[x-1][y+length] == IS_WATER) counter++ ;
if(field[x][y+length] == IS_WATER) counter++ ;
if(field[x+1][y+length] == IS_WATER) counter++ ;

} catch (IndexOutOfBoundsException e) {
counter++;
}
Log.d(TAG, "Direction: Down. Counter = " + counter);
if (counter == 12)
return true;
counter = 0;
break;
}
return false;
}

[/syntax]