Проверьте замкнутый путь в числовой карте высот

Question

Я работаю над игрой, и мне нужно проверить замкнутый путь в данной числовой карте высот: Сервер и клиент используют эту карту высот, чтобы установить правильные координаты для перемещения и т.д. Теперь, когда пользователь ходит по «особой» плитке, она загорается ... Моя проблема: Когда пользователь, проходя по этим плиткам, создает закрытый путь с пустыми плитками, сервер должен автоматически заполнить плитки по этому пути ...

Это должно сделать что-то вроде этого: http://www.youtube.com/watch?v=kAVUNE2NTUQ - 1: 32

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

PS: я использую C #

РЕДАКТИРОВАТЬ: Когда пользователь ходит по плитке, сервер автоматически заменяет карту высот [X, Y] на целое число, которое представляет цвет пользователя

Answer 1

Задачу можно разделить на две части:

1. Обнаружение, когда путь закрыт. Один из способов сделать это - создать ссылки между последовательными плитками на пути: когда вы делаете шаг, если один из ваших новых соседей был ранее, и вы не можете проследить свой путь к нему среди ваших текущих соседей затем вы закрыли путь (вам, возможно, придется установить дополнительные ссылки, чтобы справиться со случаем возврата вдоль вашего пути). Это также скажет, на какой стороне вашего пути (слева или справа) лежит внутренняя область. Поиграйте с этим на миллиметровке, и это должно стать ясно. Это O (1) с каждым шагом.
2. Заполнение закрытого региона. Как только вы нашли одну плитку, которая находится в регионе, выполните итерации по ее соседям, а затем по их соседям и так далее. Для области области n это O (n) во времени и в среднем O (sqrt (n)) в памяти, в зависимости от геометрии (в худшем случае O (n)).

Answer 2

Предположим, у вас есть прямоугольное поле с верхним левым углом в (0, 0) и нижним правым в (M, N). Тогда вы можете использовать следующий алгоритм заполнения псевдокода:

find the upper and bottom cells of the path (yTop, yBottom)

for (int y = yTop; y != yBottom; ++y)
{
    find leftmost and rightmost path cells (xLeft, xRight) for that y
    bool isInside = true;
    for (int x = xLeft+1; x<xRight; ++x)
    {
        if ((x, y) is path cell)
            isInside = !isInside;
        if (isInside)
            fill(x, y);
    }
}

Answer 3

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

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