Как я могу закодировать эту проблему? (C ++)

Question

Я пишу простую игру, в которой наборы данных хранятся в двумерной сетке (например, шахматная доска). Каждая ячейка в сетке может содержать одно целое число (0 означает, что ячейка пуста). Если ячейка содержит число> 0, она называется «заполненной». Набор «заполненных» ячеек в сетке называется «конфигурацией».

Моя проблема в том, что я могу «распознать» конкретную конфигурацию, независимо от того, где находится конфигурация ячеек в сетке MxN.

Проблема (на мой взгляд) разбивается на следующие 2 подзадачи:

1. Каким-то образом "нормализует" положение конфигурации (например, для "перебазирования" ее положения в (0,0), так что самый маленький прямоугольник, содержащий все ячейки в конфигурации, имеет свою левую вершину в (0,0). ) в сетке MxN

2. Вычисление некоторой метрики подобия (или, может быть, просто установить разность?), Чтобы определить, является ли текущая "нормализованная" конфигурация одной из известных конфигураций (т.е. "распознана")

Я подозреваю, что мне нужно будет использовать std :: set (один из немногих контейнеров STL, которые я до сих пор не использовал, за все мои годы как кодер C ++!). Буду признателен за любые идеи / советы от тех, кто решил такую ​​проблему раньше. Любые фрагменты кода, псевдокод и / или ссылки были бы очень полезны.

Answer 1

Метрики сходства являются обширной областью научных исследований.Вам нужно решить, какой уровень сложности требуется для вашей задачи.Может случиться так, что вы можете просто перетащить «шаблон» на доску, стиль растра, и для каждого местоположения наберите +1 за удар и -1 за промах и сложите счет.Затем найдите место, где шаблон получил наибольшее количество баллов.Затем этот Score_max является вашей метрикой сходства для этого шаблона.Если этот метод неадекватен, вам, возможно, потребуется более подробно рассказать о точном характере игры.

Answer 2

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

Если вы храните двумерную сетку в одномерном массиве, вам нужно будет найти первую заполненную ячейку и начать вычислять хеш отсюда до последней заполненной ячейки.

Ex:

-----------------
|   |   |   |   |
-----------------
|   | X | X |   |
-----------------
|   |   | X |   |
-----------------
|   |   |   |   |
-----------------

----------------+---------------+---------------+----------------
|   |   |   |   |   | X | X |   |   |   | X |   |   |   |   |   |
----------------+---------------+---------------+----------------
                    |_______________________|
                                |
               Compute hash based on this part of the array

Однако есть случаи, когда это не сработает, например, когда рисунок смещен по линиям:

-----------------
|   |   |   | X |
-----------------
| X |   |   |   |
-----------------              Different configuration in 2D.
| X |   |   |   |
-----------------
|   |   |   |   |
-----------------

----------------+---------------+---------------+----------------
|   |   |   | X | X |   |   |   | X |   |   |   |   |   |   |   |
----------------+---------------+---------------+----------------
            |_______________________|
               Seems similar in 1D

Так что вам понадобится способ разобраться с этими случаями. У меня пока нет решения, но я постараюсь что-то найти, если мой график это позволяет!

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

Answer 3

Что касается первой части вопроса, т. Е. Принижение, попробуйте это:

создать структуру с 2 целыми числами. Определить указатель этого типа структуры. Введите (или вычислите количество живых ячеек) и назначьте столько памяти (используя процедуры, такие как calloc). Введите координаты в структуре. Вычислить минимальную координату х и минимальную координату у. В юниверсе присвойте [x] [y] ( заданные пользователем значения или текущую координату ) значение [x-minx] [y-miny] Хоть и дорого при чтении из уже заполненной сетки, но работает и помогает Следующая часть вопроса.

Answer 4

Это напоминает мне о HashLife, который использует QuadTrees. Посетите страницы википедии по HashLife и Quadtrees.

В нижней части страницы Википедии есть также ссылка на статью DrDobbs о фактической реализации такого алгоритма: http://www.ddj.com/hpc-high-performance-computing/184406478

Надеюсь, эти ссылки помогут. Они интересны, если не сказать ничего.

Answer 5

вы можете использовать нейронную сеть для этой работы.

Если вы ищете распознавание форм нейронной сети, я думаю, что вы можете найти что-то полезное. Вы можете найти тонны библиотек, которые могут вам помочь, но если у вас нет опыта работы с NN, это может быть немного сложно, но я думаю, что это самый простой способ

Answer 6

Звучит так, будто вы хотите передать свою шахматную доску нейронной сети, обученной распознавать конфигурацию.

Это очень похоже на классические примеры классификации изображений, единственное осложнение состоит в том, что вы не знаете точно, где ваша конфигурация появится в сетке, если вы не всегда рассматриваете всю сетку - в этом случае должна работать классическая двухслойная сеть.

Внедрения HTM нейронных сетей решают проблему смещения "из коробки". Вы можете найти множество готовых к использованию реализаций, начиная с здесь . Очевидно, вам придется настроить черту на реализацию, которую вы найдете, но вы должны быть в состоянии достичь именно того, что вы просите, насколько я понимаю.

Если вы хотите продолжить изучение этого маршрута, форум Numenta будет хорошей отправной точкой.

Answer 7

Это может быть излишним для небольшого приложения, но OpenCV имеет некоторые отличные процедуры распознавания изображений и поиска больших объектов. Если вы рассматриваете 2D-доску как изображение, а целое число как яркость, можно использовать функции из этой библиотеки.

и ссылка: http://opencv.willowgarage.com/documentation/index.html