Эта задача жрет мой мозг уже несколько суток)
ДАНО:
- У нас есть СЕТКА.
- На этой сетке живет КАРТА, ограниченная прямоугольником. Нам известны координаты его углов.
- На карте есть ОСТРОВА произвольной формы, на которые можно ставить объекты.
- Область внутри островов задается набором ПРЯМОУГОЛЬНИКОВ единичной ширины и произвольной высоты. Нам известны их координаты и размеры.
- Набор ПРЯМОУГОЛЬНИКОВ один на всю карту, мы не знаем, какой прямоугольник к какому острову принадлежит.
- На островах стоят ОБЪЕКТЫ прямоугольной формы. Для каждого объекта мы знаем координаты и размеры.
- На нашу сетку наложена сетка побольше, которая состоит из КВАДРАТОВ размером 32х32 клетки.
- Для каждого острова у нас есть ДЕФ (дефинишен, конфиг), в котором перечислены все квадраты, пересекающие этот остров.
- У нас есть список квадратов, пересекающихся с хотябы одним объектом.
- Для каждого такого квадрата нам известны все пересекающие его объекты.
- Нам дана некая точка
- Нам даны некие размеры
НАЙТИ:
- Найти свободную область заданных размеров как можно ближе к заданным координатам, если она есть.
- Сделать это как можно быстрее.
- Область считается свободной, если она полностью лежит внутри острова и не пересекается с другими объектами.
РЕШЕНИЕ:
- Из заданной точки движемся по расширяющейся спирали, проверяя область заданного размера в текущих координатах.
- Заканчиваем поиск, когда все углы спирали (она типа квадратная) окажутся за пределами границ карты.
ОПТИМИЗАЦИИ (вот тут начинается дрочево):
- В каждой итерации первым делом проверяем, не вылезли ли мы за карту, т.к. это самая дешевая проверка (очевидно).
- При проверке пересечений с объектами перебираем не все объекты, а только объекты в квадратах, которые пересекает проверяемая область (тоже очевидно).
- При пересечении с объектом, зная текущее направление движения, перепрыгиваем этот объект (с учетом размеров объекта и искомой области). При этом учитываем, что координата за объектом может оказаться дальше угла спирали, и в этом случае прыгаем только до угла, после чего, как обычно, поворачиваем, снова делаем проверку, снова бъемся об этот объект, и выпрыгиваем за его пределы уже в новом направлении.
- При пересечении границы карты, параллельной движению (после поворота оказалось, что мы смотрим вверх и наполовину ушли за правую границу) прыгаем до угла спирали.
- При пересечении границы, перпендикулярной движению у нас 2 кейса: движение к карте и от карты. При движении от карты (смотрим вверх и пересекаем верхнюю границу) прыгаем до угла спирали. При движении к карте (смотрим вверх и находимся внутри нижней границы) прыгаем до попадания в карту или до угла спирали, если он оказывается ближе (в случае когда мы немножко ебанулись и начали раскручивать спираль за пределами карты).
- ВНЕЗАПНО поиск все равно слишком долгий, и мы вводим послабление: ищем свободное место только в пределах острова, внутри которого лежит начальная точка поиска (на самом деле это точка в центре экрана юзера). Зная координаты точки, вычисляем квадрат. Имея дефы островов, вычисляем остров, к которому принадлежит этот квадрат (если квадрат принадлежит более чем к одному острову, то берем первый попавшийся; если не принадлежит ни к одному, то сразу фейлимся). Зная остров, берем из его дефа все квадраты. Зная все квадраты, строим ограничивающий их прямоугольник. После чего используем этот прямоугольник вместо границ карты.
- (не реализовано) При пересечении с небом (в пределах прямоугольника, грубо ограничивающего остров, но за пределами самого острова, составленного из мелких прямоугольников) и движении в сторону острова, ищем ближайший набор прямоугольников, который перекрывает по размерам нашу область, и прыгаем внутрь него (или до угла спирали, если он ближе).
- (не реализовано) Применить к прямоугольникам, описывающим форму островов, какой-нибудь алгоритм упаковки ранца, чтобы получить меньшее количество прямоугольников с бОльшими размерами.
ДАНО:
- У нас есть СЕТКА.
- На этой сетке живет КАРТА, ограниченная прямоугольником. Нам известны координаты его углов.
- На карте есть ОСТРОВА произвольной формы, на которые можно ставить объекты.
- Область внутри островов задается набором ПРЯМОУГОЛЬНИКОВ единичной ширины и произвольной высоты. Нам известны их координаты и размеры.
- Набор ПРЯМОУГОЛЬНИКОВ один на всю карту, мы не знаем, какой прямоугольник к какому острову принадлежит.
- На островах стоят ОБЪЕКТЫ прямоугольной формы. Для каждого объекта мы знаем координаты и размеры.
- На нашу сетку наложена сетка побольше, которая состоит из КВАДРАТОВ размером 32х32 клетки.
- Для каждого острова у нас есть ДЕФ (дефинишен, конфиг), в котором перечислены все квадраты, пересекающие этот остров.
- У нас есть список квадратов, пересекающихся с хотябы одним объектом.
- Для каждого такого квадрата нам известны все пересекающие его объекты.
- Нам дана некая точка
- Нам даны некие размеры
НАЙТИ:
- Найти свободную область заданных размеров как можно ближе к заданным координатам, если она есть.
- Сделать это как можно быстрее.
- Область считается свободной, если она полностью лежит внутри острова и не пересекается с другими объектами.
РЕШЕНИЕ:
- Из заданной точки движемся по расширяющейся спирали, проверяя область заданного размера в текущих координатах.
- Заканчиваем поиск, когда все углы спирали (она типа квадратная) окажутся за пределами границ карты.
ОПТИМИЗАЦИИ (вот тут начинается дрочево):
- В каждой итерации первым делом проверяем, не вылезли ли мы за карту, т.к. это самая дешевая проверка (очевидно).
- При проверке пересечений с объектами перебираем не все объекты, а только объекты в квадратах, которые пересекает проверяемая область (тоже очевидно).
- При пересечении с объектом, зная текущее направление движения, перепрыгиваем этот объект (с учетом размеров объекта и искомой области). При этом учитываем, что координата за объектом может оказаться дальше угла спирали, и в этом случае прыгаем только до угла, после чего, как обычно, поворачиваем, снова делаем проверку, снова бъемся об этот объект, и выпрыгиваем за его пределы уже в новом направлении.
- При пересечении границы карты, параллельной движению (после поворота оказалось, что мы смотрим вверх и наполовину ушли за правую границу) прыгаем до угла спирали.
- При пересечении границы, перпендикулярной движению у нас 2 кейса: движение к карте и от карты. При движении от карты (смотрим вверх и пересекаем верхнюю границу) прыгаем до угла спирали. При движении к карте (смотрим вверх и находимся внутри нижней границы) прыгаем до попадания в карту или до угла спирали, если он оказывается ближе (в случае когда мы немножко ебанулись и начали раскручивать спираль за пределами карты).
- ВНЕЗАПНО поиск все равно слишком долгий, и мы вводим послабление: ищем свободное место только в пределах острова, внутри которого лежит начальная точка поиска (на самом деле это точка в центре экрана юзера). Зная координаты точки, вычисляем квадрат. Имея дефы островов, вычисляем остров, к которому принадлежит этот квадрат (если квадрат принадлежит более чем к одному острову, то берем первый попавшийся; если не принадлежит ни к одному, то сразу фейлимся). Зная остров, берем из его дефа все квадраты. Зная все квадраты, строим ограничивающий их прямоугольник. После чего используем этот прямоугольник вместо границ карты.
- (не реализовано) При пересечении с небом (в пределах прямоугольника, грубо ограничивающего остров, но за пределами самого острова, составленного из мелких прямоугольников) и движении в сторону острова, ищем ближайший набор прямоугольников, который перекрывает по размерам нашу область, и прыгаем внутрь него (или до угла спирали, если он ближе).
- (не реализовано) Применить к прямоугольникам, описывающим форму островов, какой-нибудь алгоритм упаковки ранца, чтобы получить меньшее количество прямоугольников с бОльшими размерами.
This task has been eating my brain for several days)
DANO:
- We have a GRID.
- A MAP limited to a rectangle lives on this grid. We know the coordinates of its angles.
- On the map there are ISLANDS of arbitrary shape on which objects can be placed.
- The area inside the islands is defined by a set of RECTANGLES of unit width and arbitrary height. We know their coordinates and sizes.
- The set of RECTANGLES is one for the whole map, we don’t know which rectangle belongs to which island.
- On the islands are OBJECTS of rectangular shape. For each object, we know the coordinates and sizes.
- A larger grid is imposed on our grid, which consists of SQUARES 32x32 cells in size.
- For each island, we have DEF (definition, config), which lists all the squares crossing this island.
- We have a list of squares intersecting with at least one object.
- For each such square, we know all the objects intersecting it.
- We are given a certain point
- We are given certain sizes
TO FIND:
- Find the free area of the given sizes as close as possible to the given coordinates, if any.
- Do it as quickly as possible.
- An area is considered free if it lies completely inside the island and does not intersect with other objects.
DECISION:
- From a given point, we move along an expanding spiral, checking the area of a given size in current coordinates.
- Finish the search when all the corners of the spiral (it’s like a square) are outside the borders of the map.
OPTIMIZATIONS (here it starts drosho):
- In each iteration, the first thing we check is whether we got out of the map, because this is the cheapest check (obviously).
- When checking intersections with objects, we do not sort through all the objects, but only objects in the squares that the area being checked intersects (also obvious).
- At the intersection with the object, knowing the current direction of movement, we jump over this object (taking into account the size of the object and the desired area). At the same time, we take into account that the coordinate behind the object can be beyond the angle of the spiral, and in this case we jump only to the angle, after which, as usual, we turn, do the check again, again we clash on this object, and jump out of it already in a new direction .
- When crossing the border of the map parallel to the movement (after the turn it turned out that we were looking up and half left behind the right border) we jump to the corner of the spiral.
- When crossing the border perpendicular to the movement, we have 2 cases: movement to and from the map. When moving from the map (look up and cross the upper border), we jump to the angle of the spiral. When moving to the map (look up and are inside the lower border), we jump until it hits the map or to the corner of the spiral if it is closer (in the case when we fucked a little and started to unwind the spiral outside the map).
- SUDDENLY the search is still too long, and we introduce relief: we are looking for free space only within the island, inside which lies the starting point of the search (in fact, this is the point in the center of the user’s screen). Knowing the coordinates of the point, we calculate the square. Having island defs, we calculate the island to which this square belongs (if the square belongs to more than one island, then we take the first one; if it does not belong to any, then we immediately feil). Knowing the island, we take all the squares from its def. Knowing all the squares, we construct a bounding rectangle. Then we use this rectangle instead of the borders of the map.
- (not implemented) At the intersection with the sky (within the rectangle that roughly borders the island, but outside the island itself, made up of small rectangles) and moving towards the island, we look for the closest set of rectangles that covers our region in size, and jump inside him (or to the angle of the spiral, if it is closer).
- (not implemented) Apply to the rectangles describing the shape of the islands some sort of packing algorithm for the knapsack to get fewer rectangles with larger sizes.
DANO:
- We have a GRID.
- A MAP limited to a rectangle lives on this grid. We know the coordinates of its angles.
- On the map there are ISLANDS of arbitrary shape on which objects can be placed.
- The area inside the islands is defined by a set of RECTANGLES of unit width and arbitrary height. We know their coordinates and sizes.
- The set of RECTANGLES is one for the whole map, we don’t know which rectangle belongs to which island.
- On the islands are OBJECTS of rectangular shape. For each object, we know the coordinates and sizes.
- A larger grid is imposed on our grid, which consists of SQUARES 32x32 cells in size.
- For each island, we have DEF (definition, config), which lists all the squares crossing this island.
- We have a list of squares intersecting with at least one object.
- For each such square, we know all the objects intersecting it.
- We are given a certain point
- We are given certain sizes
TO FIND:
- Find the free area of the given sizes as close as possible to the given coordinates, if any.
- Do it as quickly as possible.
- An area is considered free if it lies completely inside the island and does not intersect with other objects.
DECISION:
- From a given point, we move along an expanding spiral, checking the area of a given size in current coordinates.
- Finish the search when all the corners of the spiral (it’s like a square) are outside the borders of the map.
OPTIMIZATIONS (here it starts drosho):
- In each iteration, the first thing we check is whether we got out of the map, because this is the cheapest check (obviously).
- When checking intersections with objects, we do not sort through all the objects, but only objects in the squares that the area being checked intersects (also obvious).
- At the intersection with the object, knowing the current direction of movement, we jump over this object (taking into account the size of the object and the desired area). At the same time, we take into account that the coordinate behind the object can be beyond the angle of the spiral, and in this case we jump only to the angle, after which, as usual, we turn, do the check again, again we clash on this object, and jump out of it already in a new direction .
- When crossing the border of the map parallel to the movement (after the turn it turned out that we were looking up and half left behind the right border) we jump to the corner of the spiral.
- When crossing the border perpendicular to the movement, we have 2 cases: movement to and from the map. When moving from the map (look up and cross the upper border), we jump to the angle of the spiral. When moving to the map (look up and are inside the lower border), we jump until it hits the map or to the corner of the spiral if it is closer (in the case when we fucked a little and started to unwind the spiral outside the map).
- SUDDENLY the search is still too long, and we introduce relief: we are looking for free space only within the island, inside which lies the starting point of the search (in fact, this is the point in the center of the user’s screen). Knowing the coordinates of the point, we calculate the square. Having island defs, we calculate the island to which this square belongs (if the square belongs to more than one island, then we take the first one; if it does not belong to any, then we immediately feil). Knowing the island, we take all the squares from its def. Knowing all the squares, we construct a bounding rectangle. Then we use this rectangle instead of the borders of the map.
- (not implemented) At the intersection with the sky (within the rectangle that roughly borders the island, but outside the island itself, made up of small rectangles) and moving towards the island, we look for the closest set of rectangles that covers our region in size, and jump inside him (or to the angle of the spiral, if it is closer).
- (not implemented) Apply to the rectangles describing the shape of the islands some sort of packing algorithm for the knapsack to get fewer rectangles with larger sizes.
У записи 2 лайков,
0 репостов.
0 репостов.
Эту запись оставил(а) на своей стене Михаил Гаенков
