Избавиться от прохождения по все экземплярам..

[Tfp]

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

for each (target in slug_array) {
				for each (other in slug_array) {
					if (other!=target) {
						bbn=1;
						var tmp_x:int=target.x;
						var tmp_y:int=target.y;
						var tmp2_x:int=other.x;
						var tmp2_y:int=other.y;
						var d:Number = Math.point_distance(tmp2_x,tmp2_y, tmp_x, tmp_y);
						
						if (d < 40) {
						...................
						}
}
}

так как монстры быстро кучкуються и фактически столкновения происходит с одними и теми же екземплярами есть идея для каждого монстра хранить список апример из 6 ближайшых мостров и проверять только их на столкновение, и обновлять его например каждые 10 шагов.
Мож есть какието идеи?

[ramshteks]

да твой предложенный самы верный.
можно например разделить экран на какое то вколичество кусков и когда твой монстр переходит из одного в лругой записывать в один из его параметро его положение(если усков 6 то это число от 1 -6 ну или от 0-5 как удобнее) и потом проходясь по массиву с монстрами проверять этот параметр и только если они совпали только тогда делать ресурсоемкие проверки на столкновение.

[Division]

Есть много алгоритмов оптимизации проверки столкновений на плоскости. Самый простой на мой взгляд - хеширование. То есть делим наше пространство на "клетки". Знаем, кто живёт в какой клетке. То есть при движении врагов записываем его в ту клетку, в которой он находится. Столкновения проверяются только для юнитов, которые находятся в одной или в соседних клетках. Всё очень просто. Более сложный алгоритм - quadtree, его я описывать не буду, в гугле масса информации. Также где-то здесь на форуме была статья про программирование игрушки на AS3. Там объясняется алгоритм хеширования. Плюс исходники (:

[Tfp]

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

[Division]

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

Если правильно сделать, будет работать шустрее.

[BlooDHounD]

http://noregret.org/tutor/n/

[Tfp]

BlooDHounD, енто я прочитал первым делом))

[VovkaMorkovka]

На счет разбития игрового поля, делать это надо так: есть масив локаций (в самом простом случае это квадраты, но могут быть и другие фигуры, главное, что они односвязные) При движении каждый бот проверяет в какой локации он находится и если перешел из одной локации в другую перезаписывает себя. Если бот находится в двух и более локациях одновременно, то соотвктственно вписвает себя в две и более локаций. При проверке столкновений идем циклом не по ботам, а по локациям, соответственно, если в локации ботов нет, то проверять ее не надо. Ну вот, как - то так

[Division]

И ещё кое-что.

Math.point_distance

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

	if (d < 1600) {
	...................
	}

[BlooDHounD]

Tfp, ну если прочитали, тогда почему сделали наоборот?