Морской бой: расстановка кораблей на поле.
Добавлено: 10 июн 2013, 10:59
Здравствуйте, уважаемые форумчане!
Интересует вопрос: какой правильный алгоритм расстановки кораблей на поле в Морском бое?
Я пытаюсь написать свой, но он, очевидно, не работает.
Прошу прощения за быдлокод, догадываюсь, что можно всё поставить одним циклом, но этим займусь позже, пусть хоть как-то работает.
На данный момент кораблям можно стоять рядом, но проблема их коллизий меня волнует сильно.
Например, расстановка трехпалубника:
[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), которая даже не передается на отрисовку.
Может, кто-нибудь подскажет, что исправить надо? Или дайте линк на уже готовый алгоритм.
Спасибо.
