Форум Flasher.ru
Ближайшие курсы в Школе RealTime
Список интенсивных курсов: [см.]  
  
Специальные предложения: [см.]  
  
 
Блоги Правила Справка Пользователи Календарь Поиск рулит! Сообщения за день Все разделы прочитаны
 

Вернуться   Форум Flasher.ru > Flash > ActionScript 3.0

Версия для печати  Отправить по электронной почте    « Предыдущая тема | Следующая тема »  
Опции темы Опции просмотра
 
Создать новую тему Ответ
Старый 31.01.2016, 22:05
GBee вне форума Посмотреть профиль Отправить личное сообщение для GBee Найти все сообщения от GBee
  № 11  
Ответить с цитированием
GBee
 
Аватар для GBee

Регистрация: Jan 2009
Сообщений: 3,067
Записей в блоге: 3
Отправить сообщение для GBee с помощью Skype™
А нельзя взять самый крупный дом Х на У. Взять квадрат с максимальной стороной самого крупного дома, например Y на Y. Разбить на такие квадраты все поле. Остатки поля разделить на кол-во влезших квадратов и добавить в квадраты (Y+offsetX, Y+offsetY). В получившиеся квадраты напихать домики из расчета 1 домик - 1 квадрат. Ну и домики в рамках их квадратов можно подвигать получив некий хаос.

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

Старый 31.01.2016, 22:46
Фенёк вне форума Посмотреть профиль Отправить личное сообщение для Фенёк Найти все сообщения от Фенёк
  № 12  
Ответить с цитированием
Фенёк

Регистрация: May 2011
Сообщений: 221
GBee
Задачу поставили в таком ключе, что в рантайме надо уметь добавлять домик в произвольное свободное место (то есть если использовать сетку, то появляется ограничение, не позволяющее разместить домик на стыке) + сами домики могут быть произвольного размера, так что выбрать шаг сетки неудастся

Короч, я написал МОНСТРА, который ПОЧТИ выполняет свою задачу (пока еще отлаживаю, но хочу поделиться)
По клику добавляется новый прямоугольник (иногда неправильно рассчитываются области, выясняю почему)
Slicing.swf   (3.7 Кб)


Вот код
Код AS3:
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;
		}
	}
 
}
Выглядит он совершенно люто, так что если у кого-то есть предложения по правкам - пожалуйста.

Вкратце алгоритм делает следующее (на примере верхней области):
- Берем прямоугольник всей области
- Отсекаем его низ по верхней границе вставленного прямоугольника
- Берем множество прямоугольников, которые эта область пересекает
- Находим ближайший левый (не пересекающийся проекциями на ось Х) прямоугольник (если есть) и по его правой границе отсекаем область
- Такая же история для правой стороны
- Еще раз находим множество прямоугольников, теперь уже попадающих в новую область
- Находи ближайший верхний и по его границе отсекаем область

Как-то так.

Как закончу - выложу окончательный вариант.
Вложения
Тип файла: swf Slicing.swf (3.7 Кб, 56 просмотров)


Последний раз редактировалось Фенёк; 31.01.2016 в 23:37.
Старый 01.02.2016, 10:20
Tails вне форума Посмотреть профиль Отправить личное сообщение для Tails Найти все сообщения от Tails
  № 13  
Ответить с цитированием
Tails
 
Аватар для Tails

блогер
Регистрация: Dec 2008
Адрес: г. Чебоксары
Сообщений: 2,259
Записей в блоге: 6
Может, проще просто рандомно выбирать на карте точку и ставить туда дом? Если место занято, запускать поиск ближайшего свободного места возле этой точки. С сеткой это будет легче всего сделать.

Вроде как, обычно так в играх происходит, если место занято, объект вставляется в ближайшее свободное место или не вставляется.
__________________
Дети не должны знать о своих родителях

Старый 01.02.2016, 10:54
Фенёк вне форума Посмотреть профиль Отправить личное сообщение для Фенёк Найти все сообщения от Фенёк
  № 14  
Ответить с цитированием
Фенёк

Регистрация: May 2011
Сообщений: 221
Tails
Собственно моя реализация для задания так делает. Но этот алгоритм не кажется мне эффективным. Во-первых, на достаточно заполненном поле неизвестно сколько итераций потребуется чтобы таким образом отыскать свободное место. Во-вторых, такой алгоритм не может ответить на вопрос о том есть ли вообще свободное место.

Старый 01.02.2016, 11:20
Tails вне форума Посмотреть профиль Отправить личное сообщение для Tails Найти все сообщения от Tails
  № 15  
Ответить с цитированием
Tails
 
Аватар для Tails

блогер
Регистрация: Dec 2008
Адрес: г. Чебоксары
Сообщений: 2,259
Записей в блоге: 6
По сути, это будет некоторая разновидность алгоритма A*. Попробуйте почитать о способах их реализаций и оптимизаций, думаю, решение найдётся.
__________________
Дети не должны знать о своих родителях

Старый 01.02.2016, 11:46
Фенёк вне форума Посмотреть профиль Отправить личное сообщение для Фенёк Найти все сообщения от Фенёк
  № 16  
Ответить с цитированием
Фенёк

Регистрация: May 2011
Сообщений: 221
Интересная мысль, хотя мне кажется что поиск пути это скорее история о том как дойти из точки в точку обходя препятствия, а не выйти из пересечения в свободную область.

Но да, поищу информацию.

Старый 01.02.2016, 12:39
Tails вне форума Посмотреть профиль Отправить личное сообщение для Tails Найти все сообщения от Tails
  № 17  
Ответить с цитированием
Tails
 
Аватар для Tails

блогер
Регистрация: Dec 2008
Адрес: г. Чебоксары
Сообщений: 2,259
Записей в блоге: 6
Посмотрите как именно происходит поиск в этих алгоритмах. Конкретно на ум приходит волновой алгоритм. Поиск свободного места будет очень похож на поиск пути, ищите начиная от исходной позиций в разные стороны.

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

Создать новую тему Ответ Часовой пояс GMT +4, время: 18:40.
Быстрый переход
  « Предыдущая тема | Следующая тема »  
Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


 


Часовой пояс GMT +4, время: 18:40.


Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2024, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.