|
|
|||||
А нельзя взять самый крупный дом Х на У. Взять квадрат с максимальной стороной самого крупного дома, например Y на Y. Разбить на такие квадраты все поле. Остатки поля разделить на кол-во влезших квадратов и добавить в квадраты (Y+offsetX, Y+offsetY). В получившиеся квадраты напихать домики из расчета 1 домик - 1 квадрат. Ну и домики в рамках их квадратов можно подвигать получив некий хаос.
Добавлено через 1 минуту Ну и мелкие домики можно пихать в один квадрат.
__________________
Чтобы доказать, что вы не робот, причините вред другому человеку. |
|
|||||
Регистрация: May 2011
Сообщений: 221
|
GBee
Задачу поставили в таком ключе, что в рантайме надо уметь добавлять домик в произвольное свободное место (то есть если использовать сетку, то появляется ограничение, не позволяющее разместить домик на стыке) + сами домики могут быть произвольного размера, так что выбрать шаг сетки неудастся Короч, я написал МОНСТРА, который ПОЧТИ выполняет свою задачу (пока еще отлаживаю, но хочу поделиться) По клику добавляется новый прямоугольник (иногда неправильно рассчитываются области, выясняю почему) Вот код package { import flash.display.Sprite; import flash.display.StageAlign; import flash.display.StageScaleMode; import flash.events.Event; import flash.events.MouseEvent; import flash.geom.Rectangle; [SWF(width = "800", height = "600", backgroundColor = "#FFFFFF", frameRate = "60")] public class Slicing extends Sprite { private var canvas:Sprite = new Sprite(); private var rectsCanvas:Sprite = new Sprite(); private var areasCanvas:Sprite = new Sprite(); private var baseArea:Rectangle = new Rectangle(0, 0, 700, 500); private var freeAreas:Vector.<Rectangle> = new <Rectangle>[]; private var rects:Vector.<Rectangle> = new <Rectangle>[]; public function Slicing() { addEventListener(Event.ADDED_TO_STAGE, onAddedToStage); } private function onAddedToStage(event:Event):void { removeEventListener(Event.ADDED_TO_STAGE, onAddedToStage); stage.scaleMode = StageScaleMode.NO_SCALE; stage.align = StageAlign.TOP_LEFT; canvas.x = (stage.stageWidth - baseArea.width) >> 1; canvas.y = (stage.stageHeight - baseArea.height) >> 1; addChild(canvas); canvas.addChild(rectsCanvas); canvas.addChild(areasCanvas); init(); } private function init():void { freeAreas.push(baseArea); drawAreas(); stage.addEventListener(MouseEvent.CLICK, onClick); } private function drawAreas():void { for (var i:int = 0, length:int = freeAreas.length; i < length; i++) { drawArea(freeAreas[i]); } } private function drawArea(area:Rectangle):void { areasCanvas.graphics.lineStyle(1, Math.round(Math.random() * 0xFFFFFF)); areasCanvas.graphics.drawRect(area.x, area.y, area.width, area.height); } private function createRandomRect():Rectangle { var rect:Rectangle = new Rectangle(); rect.width = 30 + Math.round(Math.random() * 50); rect.height = 30 + Math.round(Math.random() * 50); return rect; } private function drawRect(rect:Rectangle):void { rectsCanvas.graphics.beginFill(0); rectsCanvas.graphics.drawRect(rect.x, rect.y, rect.width, rect.height); rectsCanvas.graphics.endFill(); } private function onClick(event:MouseEvent):void { putRectIntoFreeArea(); recalculateFreeAreas(); drawAreas(); } private function putRectIntoFreeArea():void { var rect:Rectangle = createRandomRect(); var suitableAreas:Vector.<Rectangle> = new <Rectangle>[]; for (var i:int = 0, length:int = freeAreas.length; i < length; i++) { var area:Rectangle = freeAreas[i]; if (area.width >= rect.width && area.height >= rect.height) { suitableAreas.push(area); } } if (suitableAreas.length == 0) return; rects.push(rect); var randomSuitableArea:Rectangle = suitableAreas[Math.floor(Math.random() * suitableAreas.length)]; rect.x = randomSuitableArea.x + Math.round(Math.random() * (randomSuitableArea.width - rect.width)); rect.y = randomSuitableArea.y + Math.round(Math.random() * (randomSuitableArea.height - rect.height)); drawRect(rect); } private function recalculateFreeAreas():void { areasCanvas.graphics.clear(); freeAreas.length = 0; for (var i:int = 0, length:int = rects.length; i < length; i++) { var rect:Rectangle = rects[i]; var topArea:Rectangle = new Rectangle(); topArea.copyFrom(baseArea); topArea.bottom = rect.top; var bottomArea:Rectangle = new Rectangle(); bottomArea.copyFrom(baseArea); bottomArea.top = rect.bottom; var leftArea:Rectangle = new Rectangle(); leftArea.copyFrom(baseArea); leftArea.right = rect.left; var rightArea:Rectangle = new Rectangle(); rightArea.copyFrom(baseArea); rightArea.left = rect.right; checkForTopIntersections(rect, topArea); checkForBottomIntersections(rect, bottomArea); checkForLeftIntersections(rect, leftArea); checkForRightIntersections(rect, rightArea); if (topArea.width * topArea.height > 0) { freeAreas.push(topArea); } if (bottomArea.width * bottomArea.height > 0) { freeAreas.push(bottomArea); } if (leftArea.width * leftArea.height > 0) { freeAreas.push(leftArea); } if (rightArea.width * rightArea.height > 0) { freeAreas.push(rightArea); } } } private function checkForTopIntersections(targetRect:Rectangle, area:Rectangle):void { var sideCompareRects:Vector.<Rectangle> = new <Rectangle>[]; var i:int = 0; var length:int = 0; var currentRect:Rectangle = null; for (i = 0, length = rects.length; i < length; i++) { currentRect = rects[i]; if (currentRect === targetRect) continue; if (area.intersects(currentRect)) { sideCompareRects.push(currentRect); } } var nearestLeft:Rectangle = null; var nearestRight:Rectangle = null; for (i = 0, length = sideCompareRects.length; i < length; i++) { currentRect = sideCompareRects[i] if (currentRect.right <= targetRect.left) { if (nearestLeft) { nearestLeft = nearestLeft.right < currentRect.right ? currentRect : nearestLeft; } else { nearestLeft = currentRect; } } if (currentRect.left >= targetRect.right) { if (nearestRight) { nearestRight = nearestRight.left > currentRect.left ? currentRect : nearestRight; } else { nearestRight = currentRect; } } } area.left = nearestLeft ? nearestLeft.right : area.left; area.right = nearestRight ? nearestRight.left : area.right; var topCompareRects:Vector.<Rectangle> = new <Rectangle>[]; for (i = 0, length = sideCompareRects.length; i < length; i++) { currentRect = sideCompareRects[i]; if (area.intersects(currentRect)) { topCompareRects.push(currentRect); } } var nearestTop:Rectangle = null; for (i = 0, length = topCompareRects.length; i < length; i++) { currentRect = topCompareRects[i]; if (currentRect.bottom < targetRect.top) { if (nearestTop) { nearestTop = nearestTop.bottom < currentRect.bottom ? currentRect : nearestTop; } else { nearestTop = currentRect; } } } area.top = nearestTop ? nearestTop.bottom : area.top; } private function checkForBottomIntersections(targetRect:Rectangle, area:Rectangle):void { var sideCompareRects:Vector.<Rectangle> = new <Rectangle>[]; var i:int = 0; var length:int = 0; var currentRect:Rectangle = null; for (i = 0, length = rects.length; i < length; i++) { currentRect = rects[i]; if (currentRect === targetRect) continue; if (area.intersects(currentRect)) { sideCompareRects.push(currentRect); } } var nearestLeft:Rectangle = null; var nearestRight:Rectangle = null; for (i = 0, length = sideCompareRects.length; i < length; i++) { currentRect = sideCompareRects[i] if (currentRect.right <= targetRect.left) { if (nearestLeft) { nearestLeft = nearestLeft.right < currentRect.right ? currentRect : nearestLeft; } else { nearestLeft = currentRect; } } if (currentRect.left >= targetRect.right) { if (nearestRight) { nearestRight = nearestRight.left > currentRect.left ? currentRect : nearestRight; } else { nearestRight = currentRect; } } } area.left = nearestLeft ? nearestLeft.right : area.left; area.right = nearestRight ? nearestRight.left : area.right; var bottomCompareRects:Vector.<Rectangle> = new <Rectangle>[]; for (i = 0, length = sideCompareRects.length; i < length; i++) { currentRect = sideCompareRects[i]; if (area.intersects(currentRect)) { bottomCompareRects.push(currentRect); } } var nearestBottom:Rectangle = null; for (i = 0, length = bottomCompareRects.length; i < length; i++) { currentRect = bottomCompareRects[i]; if (currentRect.top < targetRect.bottom) { if (nearestBottom) { nearestBottom = nearestBottom.top > currentRect.top ? currentRect : nearestBottom; } else { nearestBottom = currentRect; } } } area.bottom = nearestBottom ? nearestBottom.bottom : area.bottom; } private function checkForLeftIntersections(targetRect:Rectangle, area:Rectangle):void { var verticalCompareRects:Vector.<Rectangle> = new <Rectangle>[]; var i:int = 0; var length:int = 0; var currentRect:Rectangle = null; for (i = 0, length = rects.length; i < length; i++) { currentRect = rects[i]; if (currentRect === targetRect) continue; if (area.intersects(currentRect)) { verticalCompareRects.push(currentRect); } } var nearestTop:Rectangle = null; var nearestBottom:Rectangle = null; for (i = 0, length = verticalCompareRects.length; i < length; i++) { currentRect = verticalCompareRects[i] if (currentRect.bottom <= targetRect.top) { if (nearestTop) { nearestTop = nearestTop.bottom < currentRect.bottom ? currentRect : nearestTop; } else { nearestTop = currentRect; } } if (currentRect.top >= targetRect.bottom) { if (nearestBottom) { nearestBottom = nearestBottom.top > currentRect.top ? currentRect : nearestBottom; } else { nearestBottom = currentRect; } } } area.top = nearestTop ? nearestTop.bottom : area.top; area.bottom = nearestBottom ? nearestBottom.top : area.bottom; var leftCompareRects:Vector.<Rectangle> = new <Rectangle>[]; for (i = 0, length = verticalCompareRects.length; i < length; i++) { currentRect = verticalCompareRects[i]; if (area.intersects(currentRect)) { leftCompareRects.push(currentRect); } } var nearestLeft:Rectangle = null; for (i = 0, length = leftCompareRects.length; i < length; i++) { currentRect = leftCompareRects[i]; if (currentRect.right < targetRect.left) { if (nearestLeft) { nearestLeft = nearestLeft.right < currentRect.right ? currentRect : nearestLeft; } else { nearestLeft = currentRect; } } } area.left = nearestLeft ? nearestLeft.right : area.left; } private function checkForRightIntersections(targetRect:Rectangle, area:Rectangle):void { var verticalCompareRects:Vector.<Rectangle> = new <Rectangle>[]; var i:int = 0; var length:int = 0; var currentRect:Rectangle = null; for (i = 0, length = rects.length; i < length; i++) { currentRect = rects[i]; if (currentRect === targetRect) continue; if (area.intersects(currentRect)) { verticalCompareRects.push(currentRect); } } var nearestTop:Rectangle = null; var nearestBottom:Rectangle = null; for (i = 0, length = verticalCompareRects.length; i < length; i++) { currentRect = verticalCompareRects[i] if (currentRect.bottom <= targetRect.top) { if (nearestTop) { nearestTop = nearestTop.bottom < currentRect.bottom ? currentRect : nearestTop; } else { nearestTop = currentRect; } } if (currentRect.top >= targetRect.bottom) { if (nearestBottom) { nearestBottom = nearestBottom.top > currentRect.top ? currentRect : nearestBottom; } else { nearestBottom = currentRect; } } } area.top = nearestTop ? nearestTop.bottom : area.top; area.bottom = nearestBottom ? nearestBottom.top : area.bottom; var leftCompareRects:Vector.<Rectangle> = new <Rectangle>[]; for (i = 0, length = verticalCompareRects.length; i < length; i++) { currentRect = verticalCompareRects[i]; if (area.intersects(currentRect)) { leftCompareRects.push(currentRect); } } var nearestRight:Rectangle = null; for (i = 0, length = leftCompareRects.length; i < length; i++) { currentRect = leftCompareRects[i]; if (currentRect.left > targetRect.right) { if (nearestRight) { nearestRight = nearestRight.left < currentRect.left ? currentRect : nearestRight; } else { nearestRight = currentRect; } } } area.right = nearestRight ? nearestRight.left : area.right; } } } Вкратце алгоритм делает следующее (на примере верхней области): - Берем прямоугольник всей области - Отсекаем его низ по верхней границе вставленного прямоугольника - Берем множество прямоугольников, которые эта область пересекает - Находим ближайший левый (не пересекающийся проекциями на ось Х) прямоугольник (если есть) и по его правой границе отсекаем область - Такая же история для правой стороны - Еще раз находим множество прямоугольников, теперь уже попадающих в новую область - Находи ближайший верхний и по его границе отсекаем область Как-то так. Как закончу - выложу окончательный вариант. Последний раз редактировалось Фенёк; 31.01.2016 в 23:37. |
|
|||||
Может, проще просто рандомно выбирать на карте точку и ставить туда дом? Если место занято, запускать поиск ближайшего свободного места возле этой точки. С сеткой это будет легче всего сделать.
Вроде как, обычно так в играх происходит, если место занято, объект вставляется в ближайшее свободное место или не вставляется.
__________________
Дети не должны знать о своих родителях |
|
|||||
Регистрация: May 2011
Сообщений: 221
|
Tails
Собственно моя реализация для задания так делает. Но этот алгоритм не кажется мне эффективным. Во-первых, на достаточно заполненном поле неизвестно сколько итераций потребуется чтобы таким образом отыскать свободное место. Во-вторых, такой алгоритм не может ответить на вопрос о том есть ли вообще свободное место. |
|
|||||
По сути, это будет некоторая разновидность алгоритма A*. Попробуйте почитать о способах их реализаций и оптимизаций, думаю, решение найдётся.
__________________
Дети не должны знать о своих родителях |
|
|||||
Регистрация: May 2011
Сообщений: 221
|
Интересная мысль, хотя мне кажется что поиск пути это скорее история о том как дойти из точки в точку обходя препятствия, а не выйти из пересечения в свободную область.
Но да, поищу информацию. |
|
|||||
Посмотрите как именно происходит поиск в этих алгоритмах. Конкретно на ум приходит волновой алгоритм. Поиск свободного места будет очень похож на поиск пути, ищите начиная от исходной позиций в разные стороны.
Если волновой алгоритм обошёл все свободные клетки от исходной точки и больше клеток не осталось -значит места нету. Если остались не проверенные пустые места, запустите поиск в них.
__________________
Дети не должны знать о своих родителях |
Часовой пояс GMT +4, время: 18:40. |
|
« Предыдущая тема | Следующая тема » |
Опции темы | |
Опции просмотра | |
|
|