Sola Rola: напишем свою версию

[nil0q]

В этой игрушке (Sola Rola) довольно необычный физический движок, но всего 25 уровней. Хотел написать свою версию, добавить что-нибудь новое (в т.ч. редактор уровней). Вот пробная версия моего движка

program SRR;

// время везде в секундах, единицы длины - пиксели,
// формат real имеет точность 3-4 знака после запятой, предел значения около 500000

type ground=record
	x,y,r:real;
	t:integer; // 1 - простой, 2 - камень, 3 - радиация
end;

type ball=record
	x,y,vx,vy,ax,ay:real;
	r: real;
	l1,l2: real; // исходная длина связи
	b1,b2: integer; // номер связанного или 0
	t: integer; // 1 - простой, 2 - камень, 3 - радиация
end;

const g=100; // ускорение силы тяжести
const k=5000; // жёсткость

var gr: array [1..1023] of ground;
var ngr: integer;
var b: array [1..255] of ball;
var nb: integer;

var i,j:integer;

var x,y,ax,ay: real; // для расчёта столкновений
var dx,dy,r,rr,a,da:real;


var t0:integer; // учёт времени
var t:integer;
var dt:real;


var w,h:integer; // размеры экрана
var cx,cy:integer; // камера


begin

	// initium
	w:=getwidth;
	h:=getheight;
	
	ngr:=10;
	for i:=1 to ngr do begin
		gr[i].x:=random(150);
		gr[i].y:=random(333)+100.0;
		gr[i].r:=random(30)+5.0;
		gr[i].t:=1;
	end;
	nb:=10;
	for i:=1 to nb do begin
		b[i].x:=random(150);
		b[i].y:=random(111);
		b[i].vx:=0;
		b[i].vy:=0;
		b[i].ax:=0;
		b[i].ay:=0;
		b[i].r:=random(20)+5.0;
		b[i].b1:=0;
		b[i].b2:=0;
		b[i].t:=1;
	end;
	t:=getrelativetimems;
	
  repeat
  
		for i:=1 to nb do begin
			x:=b[i].x;
			y:=b[i].y;
			r:=b[i].r;
			ax:=0.0;
			ay:=g;
			for j:=1 to ngr do begin
				dx:=x-gr[j].x;
				dy:=y-gr[j].y;
				if (dx<400.0) and (dx>-400.0) and (dy<400.0) and (dy>-400.0) then begin // ограничение, чтобы при возведении в квадрат не было переполнения
					rr:=sqrt(dx*dx+dy*dy);
					a:=r+gr[j].r-rr;
					if (a>0.0) and (rr>0) then begin
						ax:=ax+a*k*dx/rr/r;
						ay:=ay+a*k*dy/rr/r;
					end;
				end;
			end;
			for j:=1 to nb do begin
				if i<>j then begin
					dx:=x-b[j].x;
					dy:=y-b[j].y;
					if (dx<400.0) and (dx>-400.0) and (dy<400.0) and (dy>-400.0) then begin
						rr:=sqrt(dx*dx+dy*dy);
						a:=r+b[j].r-rr;
						if (a>0.0) and (rr>0) then begin
							ax:=ax+a*k*dx/rr/r;
							ay:=ay+a*k*dy/rr/r;
						end;
					end;
				end;
			end;
			b[i].ax:=ax;
			b[i].ay:=ay;
		end;
		
		
		setcolor(110,200,255);
		fillrect(0,0,w,h);
		
		//cx:=w/2-trunc(b[1].x);
		//cy:=h/2-trunc(b[1].y);
		
		setcolor(0,0,0);
		for i:=1 to ngr do begin
			r:=gr[i].r;
			fillellipse(trunc(gr[i].x-r)+cx,trunc(gr[i].y-r)+cy,trunc(r*2),trunc(r*2));
		end;
		setcolor(10,110,20);
		for i:=1 to ngr do begin
			r:=gr[i].r;
			fillellipse(trunc(gr[i].x-r)+cx+3,trunc(gr[i].y-r)+cy+3,trunc(r*2)-6,trunc(r*2)-6);
		end;
		
		
		t0:=t;
		t:=getrelativetimems;
		dt:=(t-t0)/1000.0;
		
		for i:=1 to nb do begin
			r:=b[i].r;
			b[i].vx:=b[i].vx+b[i].ax*dt;
			b[i].vy:=b[i].vy+b[i].ay*dt;
			b[i].x:=b[i].x+b[i].vx*dt;
			b[i].y:=b[i].y+b[i].vy*dt;
			setcolor(0,0,0);
			fillellipse(trunc(b[i].x-r)+cx,trunc(b[i].y-r)+cy,trunc(r*2),trunc(r*2));
			setcolor(150,150,140);
			fillellipse(trunc(b[i].x-r)+cx+3,trunc(b[i].y-r)+cy+3,trunc(r*2)-6,trunc(r*2)-6);
		end;
		
		setcolor(0,0,0);
		drawtext(integertostring(t-t0)+' ms',0,0);
		
		repaint;
		
  until false;
end.

Здесь массив gr - "земляные" (неподвижные) шары, ngr - их количество, массив b - подвижные шары; l1, l2, b1, b2 - предполагается использовать для связывания одного шарика с другим.
Алгоритм - мягкое столкновение: если два шарика столкнулись, они отталкиваются, сила пропорциональна глубине столкноветия.

Запустил я его на КЭмуляторе (кол-во подвижных шариков=10), работает, время цикла 40-70 мс. Запустил на телефоне, время цикла 90-120 мс, тормозит заметно.

Как оптимизировать алгоритм, чтобы скорость была как в самой игрушке?
(Реально больше всего времени занимает расчёт столкновения каждого шарика с каждым, строки 90-103; репаинт занимает 4-7 мс, остальное 1-2 мс)
Думаю, надо от квадратного корня избавляться, но без него нельзя рассчитать силы.


Для тех, кто не играл в оригинальную игру, см. во вложении.

[cherepets]

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