Проверка координат на повторы

Lictor
Offline
Зарегистрирован: 01.10.2015

Добрый день,

Пробую написать своего сапера, процесс идет вполне ровно, но застрял на том как проверить что бы координаты мин не повторялись (т.е. что бы не было двух мин в одной клетке). Плюс, буду благодарен за общие замечания по коду и за советы по его оптимизации. 

P.S. проверку цифр получаемых с ком порта на допустимость веду позже.

 


int MineX[8];  // Массив с координатами X мин, 8 штук
int MineY[8];  // Массив с координатами Y мин, 8 штук
int Move[2]; // Ход, координата Х, Y
int MoveCounter;  // Счетчик ходов
byte Flag = 0;  // Флаг хода, если 0 - запрос кол-ва мин, если 1 - флажок мины
int FlagCounter = 0;  // Счетчик флагов
int MineCounter = 8; // Счетчик оставшихся мин, вспомогательный
int VisibleMine; // Видимые мины с точки хода
int MineFound[9] = {1, 1, 1, 1, 1, 1, 1, 1, 8};  //Найденные мины, в [8] записываем сумму массива = оставшиеся мины

void setup() {

  Serial.begin(115200); // Открываем последовательное соединение

  randomSeed(analogRead(0));  // Запускаем функцию рандом случайным образом

  for (int i = 0; i < 8; i++) {  // Случайным образом расположим мины, две мины НЕ могут быть в одной точке
    MineX[i] = random(10); // Поле с лисами размером 10*10 квадратов, координаты от 0 до 9
    MineY[i] = random(10); // Поле с лисами размером 10*10 квадратов, координаты от 0 до 9

    // Как организовать проверку на повторяемость координат?

    Serial.print("Мина Х= ");
    Serial.print(MineX[i]);
    Serial.print(" Y= ");
    Serial.println(MineY[i]);
  }

  Serial.println("Начали");
}

void loop() {

  ///////////////////////// Делаем ход, ставим флаг мина (1) или запрос кол-ва мин вокруг (0)
  while (1) {  // ждем ход - вводим координаты по Х и У
    static int q;
    if (Serial.available() > 0) {
      Move[q] = Serial.parseInt();
      q++;
      if (q == 2) {

        while (1) {
          if (Serial.available() > 0) {
            Flag = Serial.parseInt();
            if (Flag == 1) FlagCounter++;
            break;
          }
        }

        q = 0;
        MoveCounter++;
        VisibleMine = 0;

        Serial.print("Ход сделан ");
        Serial.print(Move[0]);
        Serial.print(" ");
        Serial.print(Move[1]);
        Serial.print(" Флаг ");
        Serial.println(Flag);

        break;
      }
    }
  }

  ///////////////////////// Проверяем кол-во мин которые еще надо найти
  if (Flag == 1) {

    for (int i = 0; i < 8; i++) {
      if (Move[0] == MineX[i] && Move[1] == MineY[i]) MineFound[i] = 0;
    }

    MineFound[8] = 0;
    for (int i = 0; i < 8; i++) {
      MineFound[8] = MineFound[8] + MineFound[i];  // Сумма оставшихся мин, которых еще нужно найти
    }
  }

  ///////////////////////// Конец игры, выводим кол-во ходов
  for (int i = 0; i < 8; i++) {
    if (Move[0] == MineX[i] && Move[1] == MineY[i] && Flag == 0) {
      Serial.print("Сапер ошибся ");
      Serial.print(MoveCounter);
      while (1);
    }
  }

  if (MineFound[8] == 0) {
    Serial.print("Победа, кол-во ходов ");
    Serial.print(MoveCounter);
    Serial.print(" кол-во флагов ");
    Serial.print(FlagCounter);
    while (1);
  }

  if (MoveCounter > 99) {
    Serial.print("Слишком долго...");
    while (1);
  }

  ///////////////////////// Проверяем кол-во Мин вокруг точки хода
  if (Flag == 0) {

    while (1) {
      static int q;

      if ((Move[0] + 1 == MineX[q]) || (Move[0] - 1 == MineX[q]) || (Move[0] == MineX[q])) {  // Проверка наличия мин на соседних клетках
        if ((Move[1] + 1 == MineY[q]) || (Move[1] - 1 == MineY[q]) || (Move[1] == MineY[q])) VisibleMine++;
      }

      q++;
      if (q > 7) {
        Serial.print("Мин вокруг ");
        Serial.println(VisibleMine);
        q = 0;
        break;
      }
    }

  }

}

 

Lictor
Offline
Зарегистрирован: 01.10.2015

Немного дополню, поле 10 на 10, мин всегда 8 штук, кол-во флагов не ограниченно, победа присуждается игроку с наименьшим кол-вом ходов и флагов за раунд. 

mykaida
mykaida аватар
Offline
Зарегистрирован: 12.07.2018

Есть такие массивы типа boolean Mine[n][m]; - вот в них ничего не будет повторяться.

Lictor
Offline
Зарегистрирован: 01.10.2015

mykaida пишет:

Есть такие массивы типа boolean Mine[n][m]; - вот в них ничего не будет повторяться.

Честно говоря, не понял.

Вы предлагаете создать двухмерный массив (это еще ладно, но легче от этого не становится, повторы по прежнему возможны) типа boolean, где есть лишь два варианта значений истина или ложь. Как туда координаты-то вводить?

DIYMan
DIYMan аватар
Offline
Зарегистрирован: 23.11.2015

Чтобы координаты мин не повторялись - надо при генерации координат проверять, были ли ранее выданы такие координаты. В вашем случае самое простое - это вместо строк 18 и 19, где вы присваиваете в массив координату сразу - получить рандомное число, пробежать массив от нуля до текущего значения итератора цикла, и проверить - если такая координата в массиве уже есть, генерить новую, до победного. Навскидку - как-то так, на примере координаты по X:

for (int i = 0; i < 8; i++) 
{
	int xCoord = random(10);
	
	while(1)
	{
		bool found = false;

		for(int k=0;k<i;k++)
		{
			if(MineX[k] == xCoord)
			{
				xCoord = random(10);
				found = true;
				break;
			}	
		}

		if(!found)
		{
			break;
		}
	}

	MineX[i] = xCoord;
}

 

Lictor
Offline
Зарегистрирован: 01.10.2015

DIYMan пишет:

Чтобы координаты мин не повторялись - надо при генерации координат проверять, были ли ранее выданы такие координаты. В вашем случае самое простое - это вместо строк 18 и 19, где вы присваиваете в массив координату сразу - получить рандомное число, пробежать массив от нуля до текущего значения итератора цикла, и проверить - если такая координата в массиве уже есть, генерить новую, до победного. Навскидку - как-то так, на примере координаты по X:

for (int i = 0; i < 8; i++) 
{
	int xCoord = random(10);
	
	while(1)
	{
		bool found = false;

		for(int k=0;k<i;k++)
		{
			if(MineX[k] == xCoord)
			{
				xCoord = random(10);
				found = true;
				break;
			}	
		}

		if(!found)
		{
			break;
		}
	}

	MineX[i] = xCoord;
}

 

 

Но ведь нет проблем если координата Х повторится сама по себе, т.к. Мина(5:4) и Мина(5:5) все таки не в одной клетке.  А в вашем коде, если я его правильно понял, не будет повторов именно по каждой координате в отдельности. В этом случае играть буде проще, т.к. никогда не будет двух и более мин в по горизонтали или вертикали.

Lictor
Offline
Зарегистрирован: 01.10.2015

Написал такой код, вроде работает, но выглядит как-то странно:

void setup() {

  Serial.begin(115200); // Открываем последовательное соединение

  randomSeed(analogRead(0));  // Запускаем функцию рандом случайным образом
label:
  for (int i = 0; i < 8; i++) {  // Случайным образом расположим мины, две мины НЕ могут быть в одной точке
    MineX[i] = random(10); // Поле с минами размером 10*10 квадратов, координаты от 0 до 9
    MineY[i] = random(10); // Поле с минами размером 10*10 квадратов, координаты от 0 до 9
  }

  // Как организовать проверку на повторяемость координат?
  Serial.println("начинаем проверку повторов");
  for (int i = 0; i < 8; i++) { // Проверяем совпадения
    Serial.print("i= ");
    Serial.println(i);
    for (int j = 0; j < 8; j++) {
      Serial.print("j= ");
      Serial.println(j);
      if (MineX[i] == MineX[j] && MineY[i] == MineY[j] && i != j) {
        Serial.print("label");
        goto label;
      }
    }
  }

  for (int i = 0; i < 8; i++) {
    Serial.print("Мина Х= ");
    Serial.print(MineX[i]);
    Serial.print(" Y= ");
    Serial.println(MineY[i]);
  }


  Serial.println("Начали");
}

 

плюс непонятно как долго он будет гонять по кругу автозаполнение массива

DIYMan
DIYMan аватар
Offline
Зарегистрирован: 23.11.2015

Lictor пишет:

Но ведь нет проблем если координата Х повторится сама по себе, т.к. Мина(5:4) и Мина(5:5) все таки не в одной клетке.  А в вашем коде, если я его правильно понял, не будет повторов именно по каждой координате в отдельности. В этом случае играть буде проще, т.к. никогда не будет двух и более мин в по горизонтали или вертикали.

А вы ожидали готового решения? Я вам дал удочку, выловить рыбу - дело техники ;)

Lictor
Offline
Зарегистрирован: 01.10.2015

DIYMan пишет:

Lictor пишет:

Но ведь нет проблем если координата Х повторится сама по себе, т.к. Мина(5:4) и Мина(5:5) все таки не в одной клетке.  А в вашем коде, если я его правильно понял, не будет повторов именно по каждой координате в отдельности. В этом случае играть буде проще, т.к. никогда не будет двух и более мин в по горизонтали или вертикали.

А вы ожидали готового решения? Я вам дал удочку, выловить рыбу - дело техники ;)

 

А можете посмотреть код из поста №6. Суть в том, что приналичии повторов с помощью goto массив заполняется вновь  с самого начала и так до тех пор пока повторов не будет. Но сколько раз это произойдет непонятно (перезапускал раз двадцать, обычно не больше 1-2 перезаполнений). Он работает, но я читал, что использование goto "дурной тон". Или ничего?

DetSimen
DetSimen аватар
Offline
Зарегистрирован: 25.01.2017

Этот "код" goto не испортит. 

У тя с артихектурой проблемы. 

Lictor
Offline
Зарегистрирован: 01.10.2015

DetSimen пишет:

Этот "код" goto не испортит. 

У тя с артихектурой проблемы. 

 

А как нужно? Хотя бы в общих словах.

DetSimen
DetSimen аватар
Offline
Зарегистрирован: 25.01.2017

по хорошему, как бы я делал, создал бы массив размером с игровое поле, в данном случае 10х10, с данными типа 

struct TCell {

   uint8_t  MinesAround: 4; // мин вокруг ячейки

   bool      Opened: 1         // ячейка открыта

   bool      Marked: 1;       // ячейка помечена

   bool      Mine: 1;          // в ячейке стоит мина

}

структура занимает 1 байт, поэтому весь массив в ОЗУ влазит легко.  Вначале забиваем весь массив нулями, а при генерации положения мин, берем рандомные координатыи смотрим, если в ячейке уже стоит мина TCell:Mine == true, то генерируем новые координаты, а если мины еще нет, то ставим мину и увеличиваем на 1 TCell::MinesAround всех 8 окружающих ячеек. так у тебя и поле и циферки вокруг мин сгенерируются отоматически. 

Lictor
Offline
Зарегистрирован: 01.10.2015

DetSimen пишет:

по хорошему, как бы я делал, создал бы массив размером с игровое поле, в данном случае 10х10, с данными типа 

struct TCell {

   uint8_t  MinesAround: 4; // мин вокруг ячейки

   bool      Opened: 1         // ячейка открыта

   bool      Marked: 1;       // ячейка помечена

   bool      Mine: 1;          // в ячейке стоит мина

}

структура занимает 1 байт, поэтому весь массив в ОЗУ влазит легко.  Вначале забиваем весь массив нулями, а при генерации положения мин, берем рандомные координатыи смотрим, если в ячейке уже стоит мина TCell:Mine == true, то генерируем новые координаты, а если мины еще нет, то ставим мину и увеличиваем на 1 TCell::MinesAround всех 8 окружающих ячеек. так у тебя и поле и циферки вокруг мин сгенерируются отоматически. 

 

Спасибо, попробую так.

DetSimen
DetSimen аватар
Offline
Зарегистрирован: 25.01.2017

ах, да, не забываем перед структурой написать 

#pragma pack(push,1) 

а после 

#pragma pack(pop) 

а то меня DIY-Man пришибёть. 

sadman41
Offline
Зарегистрирован: 19.10.2016

С прагмапаком - полезная тема.

Я вчера полвечера протрахался с натягиванием структуры на массив... Никак uint32, пришедший из потока, не отображался на структурный uint32_t. Структурный массив uint8_t[4] на месте uint_32 показывает правильные байты, а число в uint32 - неправильно. В Юнион уже запихал оба - нихрена. Отдельные байты ОК, число - хрен.

Токо прагмапак заюзал - и все красиво стало.

Правда, это не на Wiring, а на MiniGW, но все равно случай поучительный.