Алгоритмы и формулы Опции

[gamecreator]

Его же потом еще закрасить придется .

ну так обвести линией, а потом FloodFill
хотя если учесть что где-то в массиве наверняка хранится поле, то можно и напрямую

[Guevara-chan]

ну так обвести линией, а потом FloodFill

А если FloodFill и его аналоги недоступны по каким-то причнам ? Тогда придется закрашивать сомстоятельно. Ну а уж коли идет закраска - почему бы не посчитать пиксели мимоходом ?

[Гость_Д'якон_*]

Есть такое предложение. Понятно, что поле состоит из квадратов (в зависимости от размера человека, например 5х5 пикселей), каждый квадрат имеет свои координаты (например координаты у нас от 0 до 100 по 2-ум координатным прямым). Хотя это не суть важно.

Ну а дальше можно так сделать (надеюсь не сильно сложно):
1) Создаем массив из координат поля
2) Запоминаем в одномерный массив все координаты передвижения человека, кроме углов (т.е. там где менялось направление движения).
3) После того как человек повторно пересек границу поля (т.е. момент отсечения фигуры), запускаем цикл, который проверяет все координаты поля, т.е.

For y:= 1 to 100 do begin
For x:=1 to 100 do begin

Т.е. как бы проводим линии через все поле паралельно оси х-ов по каждой координате у.

При этом проверяем количество координат которые посещал игрок на каждой линии. Далее:
если координат на линии больше 1-ой, то вытираем участки поля которые находятся по координатам между 1 и2 3 и 4 5 и 6 и т.д.
если координата 1-на, то подсчитывае расстояние от начала и конца поля до координаты, т.е. Х или 100-Х, и вытираем участки поля которые оказались на меньшей стороне (т.е. либо от 0 до Х, либо от Х до 100).

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

Надеюсь понятно объяснил

[Гость_Д'якон_*]

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

[Гость_Д'якон_*]

Немного не так. Для начала нужно определить еще одну вещь, но смысл в том чтобы удалять поля которые находятся между двумя отрезками пути, которые пересекает прямая параллельная оси

[sergroj]

Д'якон, твой алгоритм в таком виде не сработает, т.к. не сможет различить 2 таких случая:
1)
00000____00000
00000000000000
00000000000000

2)
00000____88888
00000000_88888
00000000_88888

т.е. в первом случае игрок пошел по горизонтали и вернулся наверх, а во 2м - пошел вниз и отсек поле, закрашенное 8-ми. В твоем алгоритме первая строка будет одинаковой.
Дамаю, надо, наоборот, оперировать вертикальными и горизонтальными отрезками. Идя по горизонтали надо считать кол-во пересечений вертикальных отрезков, а при переходе на след. линию учитывать пересечение горизонтального отрезка в точке x=0. Вообще, в дискретном случае получается много тонкостей:
1) Надо считать пересечения не отрезков, а полуинтервалов. Исключать либо меньшую по координате вершину отрезка, либо большую. Например, не будем учитывать пересечения большей по координате вершины.
2) Тогда, при переходе на след. строку надо менять "ориентацию" сразу, как только мы коснулись горизонтального полуинтервала.

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

Чтобы учесть то, что от области уже отрезаны какие-то куски,надо учитывать движение человека и в этих областях.

А простой алгоритм такой: находим первую незакрашенную точку и шуруем от нее чем-то типа FloodFill'а. Т.е. закрашиваем ее, просматриваем соседей и с незкраенными рекуррентно делаем то же самое. Потом так же закрашиваем 2ю часть области, а потом убираем меньшую по кол-ву точек. Скорость уменьшится максимум раз в 10.

[Guevara-chan]

А простой алгоритм такой: находим первую незакрашенную точку и шуруем от нее чем-то типа FloodFill'а. Т.е. закрашиваем ее, просматриваем соседей и с незкраенными рекуррентно делаем то же самое. Потом так же закрашиваем 2ю часть области, а потом убираем меньшую по кол-ву точек. Скорость уменьшится максимум раз в 10.

1) А если отсечена большая часть поля ?
2) А в случае самопересечения что делать ?

[Гость_Д'якон_*]

Да я и сам понял, что метод не совсем полный. Но я придумал как сделать полным.

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

[Гость_Д'якон_*]

Добавлено ([mergetime]1204971458[/mergetime]):
1 - это движение игрока по полю
А потом пять методов из которого выбираем меньшую площадь (т.е. меньшее кол-во координат было удалено)

[gamecreator]

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

[Гость_Д'якон_*]

//считаем две площади по обе стороны и закрашиваем меньшую.

А как посчитать?

[gamecreator]

ну писали уже. поле наверняка хранится в массиве булевском. а там уж посчитать размеры не составит проблем.

[Гость_Д'якон_*]

А как выделить нужную часть поля. Как программа поймет какую часть нужно посчитать?

Добавлено ([mergetime]1204984484[/mergetime]):
Допустим взять мой рисунок. Как программа поймет, что там всего две фигуры?

[gamecreator]

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

я вообще не понял твоего рисунка.

[Гость_Д'якон_*]

волновой алгоритм? Как? Разъясни

[gamecreator]

помечаешь одну вершину каким-либо числом (обычно 0). увеличиваем счетчик на 1. все вершины смежные с вершинами, у которых метка равна счетчик-1, и не имеющие метки помечаем числом счетчик. делаем это пока можно пометить хоть что-то.

Добавлено ([mergetime]1204992873[/mergetime]):
зы. разъясни свой рисунок

[Гость_Д'якон_*]

Все равно не понял, что это даст.

Разъясняю рисунки.

На 1-ом рисунке, более жирной линией отмечен путь человека.

На 2-ом рисунке запускаем цикл
F:=1 - устанавливаем флаг в true
For y:=1 to 100 do begin
For x:=1 to 100 do begin

где от 1 до 100 - координаты поля (допустим!)

Если при прохождении цикла координата X;Y - совпадет с координатой на которой был человек флаг устанавливается в 0. При этом каждая координата проходит проверку на удаление. Если F=1, то координата удаляется. Если опять попали на координату игрока, то F=1.

Стрелочки на линии показвают направление в котором мы запускаем цикл.

Дальше еще 3-ри цикла в разных направлениях, при этом считаем удаленные координаты в каждом направлении.

И 5-ый рисунок. Запускаем сразу в двух направлениях по х и по у, но с начальным флагом 0. И там где пересекутся удаленные координаты в двух направлениях, те и удаляем (рисунок немного не правильный, извеняюсь). В принципе 5-ый цикл нужен для проверки самопересечений.

Понятно?

[gamecreator]

неа

[Гость_Д'якон_*]

Хорошо, давай так. Флаг F=true, говорит нам о том, что координату нужно удалить.

Рассмотрим рисунок№2

Представь, что ты ведешь прямую линию СЛЕВА НАПРАВО паралельно оси Х, с координатой по у=20 (как линия на рисунке примерно).
Переходишь на координату 1;20 , проверяешь равено ли F единице, если да, то уделяешь эту координату. Дальше 2;20, то же самое. И так до тех пор пока координато на который ты в данный момент не совпадет с координатой на которой был игрок, т.е. где-то 85;20. Ставишь флаг в 0. И продолжаешь до конца поля тем же макаром.

На 3-рисунке, Справа Налево, 4-ый - сверху вниз, 5-ый снизу вверх.

А на 6-ом в двух направлениях, но с начальным флагом 0

[gamecreator]

вот вам. разбирайтесь.
http://gcr.by.ru/game01.7z