Морской бой: расстановка кораблей на поле.
Морской бой: расстановка кораблей на поле.
Здравствуйте, уважаемые форумчане!
Интересует вопрос: какой правильный алгоритм расстановки кораблей на поле в Морском бое?
Я пытаюсь написать свой, но он, очевидно, не работает.
Прошу прощения за быдлокод, догадываюсь, что можно всё поставить одним циклом, но этим займусь позже, пусть хоть как-то работает.
На данный момент кораблям можно стоять рядом, но проблема их коллизий меня волнует сильно.
Например, расстановка трехпалубника:
[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), которая даже не передается на отрисовку.
Может, кто-нибудь подскажет, что исправить надо? Или дайте линк на уже готовый алгоритм.
Спасибо.
Интересует вопрос: какой правильный алгоритм расстановки кораблей на поле в Морском бое?
Я пытаюсь написать свой, но он, очевидно, не работает.
Прошу прощения за быдлокод, догадываюсь, что можно всё поставить одним циклом, но этим займусь позже, пусть хоть как-то работает.
На данный момент кораблям можно стоять рядом, но проблема их коллизий меня волнует сильно.
Например, расстановка трехпалубника:
[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), которая даже не передается на отрисовку.
Может, кто-нибудь подскажет, что исправить надо? Или дайте линк на уже готовый алгоритм.
Спасибо.
Re: Морской бой: расстановка кораблей на поле.
После вызова метода нужен в обоих местах, в одном у вас закомментировано.
Код: Выделить всё
place_third();
Код: Выделить всё
break;
Re: Морской бой: расстановка кораблей на поле.
Блин, точно, спасибо!
Re: Морской бой: расстановка кораблей на поле.
Я сейчас пытаюсь сделать так, чтобы корабли разделялись одной клеткой (как в нормальном МБ), но вот проблема - не знаю, как учитывать выходы за массив (ведь если корабль "у стеночки", то часть его окружения будет выпадать за пределы поля).
Подскажите, как обойти это?
Подскажите, как обойти это?
Re: Морской бой: расстановка кораблей на поле.
Возможно добавить условие для проверки не выходит ли проверяемое поле за размер массива, и если выходит то не проверять просто. Или покажите свои текущие наработки и будем думать
Re: Морской бой: расстановка кораблей на поле.
Вот частичка этого быдлокода тут)
http://pastebin.com/tNkvTPJz
http://pastebin.com/tNkvTPJz
Re: Морской бой: расстановка кораблей на поле.
Судя по коду выход за пределы массива возможны только тут Что если добавить еще одно условие Тогда не должны проверятся точки за пределами массива.
Код: Выделить всё
if(field[x+i][y] != IS_SHIP) {
Код: Выделить всё
if(x+i < field.length && field[x+i][y] != IS_SHIP) {
Re: Морской бой: расстановка кораблей на поле.
Спасибо) попробую завтра.
То есть, добавляю условие и дописываю обход всех точек вокруг?
То есть, добавляю условие и дописываю обход всех точек вокруг?
Re: Морской бой: расстановка кораблей на поле.
Условие для того чтобы не проверялись точки за пределами массива. А вот что вы в методе делать собираетесь незнаю)
Re: Морской бой: расстановка кораблей на поле.
хм..странное условие...ведь за пределы массива может попасть аж 7 точек (четырехпалубник начинается в 1.1 и идет до 1.4 вниз)
Re: Морской бой: расстановка кораблей на поле.
Это условие только для точек по горизонтали. Нету смысла проверять точки за пределами игрового поля. Хотя неясно какие значения может принимать переменная Х, если она может принимать отрицательные значения то нужно еще условия для них.
Re: Морской бой: расстановка кораблей на поле.
У меня была мысль такая:
начинаем проверять все точки вокруг. Если успех, то плюсуем счетчик.
В итоге получаем некоторое число, которое сравниваем с наперед высчитанным для данного типа корабля. Если равно - то ставим корабль, если нет, то запускаем поиск заново. Тупо, но работает.
Проблема в том, что при выходе за границы массива ловится IndexOutOfBoundException.
Назревает вопрос: если я в этом эксепшене допишу инкремент счетчика, то после выхода из исключения разве продолжится поиск?
Ведь если нет, то заведомо нормальное положение (в углу, например) будет всегда восприниматься как неподходящее.
Надеюсь, Вы понимаете мою мысль.
начинаем проверять все точки вокруг. Если успех, то плюсуем счетчик.
В итоге получаем некоторое число, которое сравниваем с наперед высчитанным для данного типа корабля. Если равно - то ставим корабль, если нет, то запускаем поиск заново. Тупо, но работает.
Проблема в том, что при выходе за границы массива ловится IndexOutOfBoundException.
Назревает вопрос: если я в этом эксепшене допишу инкремент счетчика, то после выхода из исключения разве продолжится поиск?
Ведь если нет, то заведомо нормальное положение (в углу, например) будет всегда восприниматься как неподходящее.
Надеюсь, Вы понимаете мою мысль.
Re: Морской бой: расстановка кораблей на поле.
Да поиск продолжится, но делать через эксепшены не лучший подход в программировании)
Re: Морской бой: расстановка кораблей на поле.
Я понимаю, но другого выхода не вижу в данной ситуации. У Вас есть идея лучше?
Re: Морской бой: расстановка кораблей на поле.
Уверен что можно что-то придумать, но уже завтра
Re: Морской бой: расстановка кораблей на поле.
Возникла проблема.
Написал метод расстановки (чтобы не соприкасались), так теперь корабли отказываются вставать на края карты!
Код:
[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]
Написал метод расстановки (чтобы не соприкасались), так теперь корабли отказываются вставать на края карты!
Код:
[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]