Обхождение препятствий в многопользовательской игре

[Gal4enochek]

Сразу говорю, что про hitTestObject знаю, но с ним возникла проблема. (В похожих темах ее решения не нашла)
Есть некая карта (размер карты и ячейки могут меняться) - набор прямоугольников и есть несколько чувачков, которые по этой карте ходят и должны не проходить сквозь препятствия. При чем чувачки должны ходить не по сетке, а ПЛАВНО.
Механизм следующий: если чуваку нужно сместиться на dx, dy он запрашивает у поля возможность перемещения, и если все ок - то идет туда.
Поле пробегает массив из всех препятствий и проверяет на столкновение с чувачком.
Лажа в том, что при большом количестве препятствий и чувачков, начинаются дикие тормоза, так как для каждого игрока нужно перелапатить массив и 250 препятствий!!!

Как можно решить проблему?
Спасибо!

[iflamberg]

делать хэширование.
Карта делится на блоки, препятсвия ассоциируются с блоком. Проверяем, какому блоку пренадлежит "чувачок", делаем сравнение только с препятствиями одного блока.

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

[divinus]

Gal4enochek, можно поступить радикально, отрисовать препятствия в BitmapData и уже тупо hitTest юзать, или свою систему написать с использованием getPixel

[Gal4enochek]

divinus, только что так вроде и выкрутилась. Правда с threshold провозилась часа два, какой-то он непонятный. Так и не разобралась до конца как он работает.
В общем вот такой пока не оттестированный вариант:

// контейнер для карты
public class EnvironmentContainer extends Sprite
	{
		private var mask_layer				: Sprite;
		private var bmp_data				: BitmapData;
 
		public function EnvironmentContainer(){
			super();
			mask_layer = new Sprite();
			this.addChild(mask_layer);
			mask_layer.y = 0;
			this.hitArea = mask_layer;
			mask_layer.alpha = 0;
		}
 
                // удаляем все что было и заливаем поле зеленым (прозрачным не работает :( )
		public function clearAll(width :Number, height:Number):void{
			while(this.numChildren>0) this.removeChildAt(this.numChildren - 1);
			mask_layer = new Sprite();
			this.addChild(mask_layer);
			mask_layer.y = 0;
			mask_layer.alpha = 0;
			mask_layer.graphics.beginFill(0xff00);
			mask_layer.graphics.drawRect(0, 0, width, height);
			mask_layer.graphics.endFill();
		}
 
		// рисуем синим маску для прямоугольного элемента карты	
		public function addMask(_x:Number, _y:Number, _width:Number, _height :Number):void{
			mask_layer.graphics.beginFill(0xff);
			mask_layer.graphics.drawRect(_x, _y, _width, _height);
			mask_layer.graphics.endFill();
		}
 
                // когда все добавлено делаем битмапдату
		public function init():void{
			bmp_data = new BitmapData(this.width, this.height);
			bmp_data.draw(mask_layer);
			trace(bmp_data.width, bmp_data.height);
		}
 
                // для данного прямоугольника возвращает со сколькими пикселями припятствий он пересекся
		public function intersectCount(rect:Rectangle):int{
			var bmp :BitmapData = new BitmapData(rect.width, rect.height);
			var n :uint = bmp.threshold(bmp_data, rect, new Point(), "==", 0xffffff, 0xff, 0xff, true);
			bmp.dispose();
			return n;
		}
}

Кривовато как-то
В общем как-то так.
Буду рада замечаниям

[Smrad]

Если нестатических объектов много то силовой вариант проверки столкновений "всех со всеми" не подойдёт. Гуглите по запросу "Quad Tree".

[Gal4enochek]

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

[Smrad]

Сколько в среднем чуваков и сколько препятствий?

[Gal4enochek]

Да принципе сколько угодно. Ну чуваков минимум 10 должно держать, а препятствий - как карту нарисуют, тоже до 500 должно поддерживаться.

[Smrad]

500 * 10 = 5000 хиттестов в кадр. Многовато. Или бить сцену квад деревом либо простой сеткой, как предложил iflamberg.

[willis83]

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