Optimierung?
-
WIe kann ich diese Funktion optimieren?
BOOL TileCollision(int x,int y,int x2,int y2,int rangex,int rangey) { x+=40; for(int i=1;i<161;i++) { if((x2+rangex)>x) if(x2<(x)) if(y2<y) if((y2+rangey)>y) return TRUE; if(i<40) { x++; if(((i%2)==1))y++; } if(i==40)y++; if((i<80)&&(i>40)) { x--; if((i%2)==1)y++; } if((i<120)&&(i>79)) { x--; if((i%2)==1)y--; } if(i==120)y--; if((i<161)&&(i>120)) { x++; if((i%2)==1)y--; } } return FALSE; }
-
Was genau soll denn die Funktion machen? Schon klar, es geht um Tile Kollision. Aber ein paar mehr Infos bzw eine kurze Erläuterung von dem, was du da machst, ist sicherlich hilfreicher als den Code zu interpretieren.
So spontan fallen mir beim Überfliegen zwei Sachen auf:
1. Wir sind im C++ Forum, also nutze bool und nicht BOOL
if(((i%2)==1))y++; if((i%2)==1)y--;Vermutlich wird ein guter Compiler das selbst optimieren. Du könntest aber auch gleich
y+=i%2; y-=i%2;schreiben.
-
ein einziger kommentar,nur ein einziger, ist das zuviel verlangt?
-
Der der Fragen fragt schrieb:
WIe kann ich diese Funktion optimieren?
BOOL TileCollision(int x,int y,int x2,int y2,int rangex,int rangey) { x+=40; for(int i=1;i<161;i++) { if((x2+rangex)>x) if(x2<(x)) if(y2<y) if((y2+rangey)>y) return TRUE; if(i<40) { x++; if(((i%2)==1))y++; } if(i==40)y++; if((i<80)&&(i>40)) { x--; if((i%2)==1)y++; } if((i<120)&&(i>79)) { x--; if((i%2)==1)y--; } if(i==120)y--; if((i<161)&&(i>120)) { x++; if((i%2)==1)y--; } } return FALSE; }wie bereits vorgeschlagen, zuerst mal bool statt BOOL.
bool TileCollision(int x,int y,int x2,int y2,int rangex,int rangey) { x+=40; for(int i=1;i<161;i++) { if((x2+rangex)>x) if(x2<(x)) if(y2<y) if((y2+rangey)>y) return true; if(i<40) { x++; if(((i%2)==1))y++; } if(i==40)y++; if((i<80)&&(i>40)) { x--; if((i%2)==1)y++; } if((i<120)&&(i>79)) { x--; if((i%2)==1)y--; } if(i==120)y--; if((i<161)&&(i>120)) { x++; if((i%2)==1)y--; } } return false; }dann mal bereichsabfragen der guten alten range (erstmals gesichtet beim borland 3.1) aufbürden. das dient jetzt nur der klarheit, damit ich den hauch einer chance habe, zu raffen, wie die funktion geht.
bool range(int min,int x,int max) { return min<=x && x<=max; } bool TileCollision(int x,int y,int x2,int y2,int rangex,int rangey) { x+=40; for(int i=1;i<161;i++) { if((x2+rangex)>x) if(x2<(x)) if(y2<y) if((y2+rangey)>y) return true; if(range(0,i,39)) { x++; if(((i%2)==1))y++; } if(i==40)y++; if(range(41,i,79)) { x--; if((i%2)==1)y++; } if(range(80,i,119)) { x--; if((i%2)==1)y--; } if(i==120)y--; if(range(121,i,160)) { x++; if((i%2)==1)y--; } } return false; }ich kapiere: die grenzen sind so schräg, daß sie bestimmt nicht immer das sind, was beabsichtigt war. naja, ich muß sie mal als arbeitshypothese annehmen.
mist, das hat nicht gehelft. ich muss mich mal von einem testprogramm verklugen lassen.
#include <iostream> using namespace std; bool range(int min,int x,int max) { return min<=x && x<=max; } bool TileCollision(int x,int y,int x2,int y2,int rangex,int rangey) { x+=40; for(int i=1;i<161;i++) { cout<<x<<' '<<y<<endl; if((x2+rangex)>x) if(x2<(x)) if(y2<y) if((y2+rangey)>y) return true; if(range(0,i,39)) { x++; if(((i%2)==1))y++; } if(i==40)y++; if(range(41,i,79)) { x--; if((i%2)==1)y++; } if(range(80,i,119)) { x--; if((i%2)==1)y--; } if(i==120)y--; if(range(121,i,160)) { x++; if((i%2)==1)y--; } } return false; } int main(){ TileCollision(100,100,10000,10000,10,10); }ausgabe:
140 100 141 101 142 101 143 102 144 102 145 103 146 103 147 104 148 104 149 105 150 105 151 106 152 106 153 107 154 107 155 108 156 108 157 109 158 109 159 110 160 110 161 111 162 111 163 112 164 112 165 113 166 113 167 114 168 114 169 115 170 115 171 116 172 116 173 117 174 117 175 118 176 118 177 119 178 119 179 120 179 121 178 122 177 122 176 123 175 123 174 124 173 124 172 125 171 125 170 126 169 126 168 127 167 127 166 128 165 128 164 129 163 129 162 130 161 130 160 131 159 131 158 132 157 132 156 133 155 133 154 134 153 134 152 135 151 135 150 136 149 136 148 137 147 137 146 138 145 138 144 139 143 139 142 140 141 140 140 141 139 141 138 140 137 140 136 139 135 139 134 138 133 138 132 137 131 137 130 136 129 136 128 135 127 135 126 134 125 134 124 133 123 133 122 132 121 132 120 131 119 131 118 130 117 130 116 129 115 129 114 128 113 128 112 127 111 127 110 126 109 126 108 125 107 125 106 124 105 124 104 123 103 123 102 122 101 122 100 121 100 120 101 119 102 119 103 118 104 118 105 117 106 117 107 116 108 116 109 115 110 115 111 114 112 114 113 113 114 113 115 112 116 112 117 111 118 111 119 110 120 110 121 109 122 109 123 108 124 108 125 107 126 107 127 106 128 106 129 105 130 105 131 104 132 104 133 103 134 103 135 102 136 102 137 101 138 101 139 100raff ich nicht.
mal test | sort machen.100 120 100 121 101 119 101 122 102 119 102 122 103 118 103 123 104 118 104 123 105 117 105 124 106 117 106 124 107 116 107 125 108 116 108 125 109 115 109 126 110 115 110 126 111 114 111 127 112 114 112 127 113 113 113 128 114 113 114 128 115 112 115 129 116 112 116 129 117 111 117 130 118 111 118 130 119 110 119 131 120 110 120 131 121 109 121 132 122 109 122 132 123 108 123 133 124 108 124 133 125 107 125 134 126 107 126 134 127 106 127 135 128 106 128 135 129 105 129 136 130 105 130 136 131 104 131 137 132 104 132 137 133 103 133 138 134 103 134 138 135 102 135 139 136 102 136 139 137 101 137 140 138 101 138 140 139 100 139 141 140 100 140 141 141 101 141 140 142 101 142 140 143 102 143 139 144 102 144 139 145 103 145 138 146 103 146 138 147 104 147 137 148 104 148 137 149 105 149 136 150 105 150 136 151 106 151 135 152 106 152 135 153 107 153 134 154 107 154 134 155 108 155 133 156 108 156 133 157 109 157 132 158 109 158 132 159 110 159 131 160 110 160 131 161 111 161 130 162 111 162 130 163 112 163 129 164 112 164 129 165 113 165 128 166 113 166 128 167 114 167 127 168 114 168 127 169 115 169 126 170 115 170 126 171 116 171 125 172 116 172 125 173 117 173 124 174 117 174 124 175 118 175 123 176 118 176 123 177 119 177 122 178 119 178 122 179 120 179 121also mal per hand die werte sortieren...
100 121 101 122 102 122 103 123 104 123 105 124 106 124 107 125 108 125 109 126 110 126 111 127 112 127 113 128 114 128 115 129 116 129 117 130 118 130 119 131 120 131 121 132 122 132 123 133 124 133 125 134 127 135 128 135 130 136 131 137 132 137 133 138 134 138 135 139 136 139 137 140 138 140 139 141 140 141 141 140 142 140 144 139 143 139 145 138 146 138 147 137 148 137 149 136 150 136 151 135 152 135 153 134 154 134 155 133 156 133 157 132 158 132 159 131 160 131 161 130 162 130 163 129 164 129 165 128 166 128 167 127 168 127 169 126 170 126 171 125 172 125 173 124 174 124 175 123 176 123 177 122 178 122 179 121 100 120 101 119 102 119 103 118 104 118 105 117 106 117 107 116 108 116 109 115 110 115 111 114 112 114 113 113 114 113 115 112 116 112 117 111 118 111 119 110 120 110 121 109 122 109 123 108 124 108 125 107 126 107 126 134 127 106 128 106 129 105 129 136 130 105 131 104 132 104 133 103 134 103 135 102 136 102 137 101 138 101 139 100 140 100 141 101 142 101 143 102 144 102 145 103 146 103 147 104 148 104 149 105 150 105 151 106 152 106 153 107 154 107 155 108 156 108 157 109 158 109 159 110 160 110 161 111 162 111 163 112 164 112 165 113 166 113 167 114 168 114 169 115 170 115 171 116 172 116 173 117 174 117 175 118 176 118 177 119 178 119 179 120aha.
mal in eine bitmap eintragen.
volkard.de/analyse.png
aha.mal schauen, ob ich dieses muster einfacher hinkriege. ja. nur einen streifen malen und gleichzeitig auf die anderen drei spiegeln. die abfrage auslagern.
das innere ding mal angucken.
if(x>x2 && x<(x2+rangex)) if(y>y2 && y<(y2+rangey)) return true;jeder meiner x/y-punkte spannt also in wirklichkeit ein kleines quadrat auf, das dann genummen wird, um gegen x2/y2 zu testen.
oder ein eher großes quadrat? welche größenordnungen habe ich für rangex und rangey zu erwarten? deutlich größer als 20? also wird in wirklichkeit ein sechseck aufgespannt, und dann nur geschaut, ob x2/y2 in diesem sechseck liegt?
falls ja, kann man den code sogar ganz erheblich beschleinigen.
den einen strich kriege ich pixelgenau so hin:
bool TileCollision(int x,int y,int x2,int y2,int rangex,int rangey) { for(int dx=40;dx;--dx) { int dy=dx/2; cout<<x+40-dx<<' '<<y+dy<<endl; getch(); } return false; }das macht dann zusammen
bool check(int x,int y,int x2,int y2,int rangex,int rangey) { // cout<<x<<' '<<y<<endl; if(x2<x && x<x2+rangex) if(y2<y && y<y2+rangey) return true; return false; } bool TileCollision(int x,int y,int x2,int y2,int rangex,int rangey) { for(int dx=40;dx;--dx) { int dy=dx/2; if(check(x+40-dx,y+dy,x2,y2,rangex,rangey)) return true; if(check(x+39+dx,y+dy,x2,y2,rangex,rangey)) return true; if(check(x+40-dx,y+41-dy,x2,y2,rangex,rangey)) return true; if(check(x+39+dx,y+41-dy,x2,y2,rangex,rangey)) return true; } return false; }aber wie gesagt, wenn in wirklichkeit ein sechseck gemeint ist, und nur getestet wird, ob x2/y2 innerhalb des sehsecks liegt, kanns's erheblich schneller gehen. ganz ohne schleife, fürchte ich.
-
Don Volkard hats malwieder geschafft
also das das jetzt rauskommt hab ich echt nicht gedacht
-
supervolkard
-
Hat down
-
@volkard
Du bist DER PATE!!! Achja, es war nur für ein Isometisches viereck wie du es auf deiner Grafik gezeigt hast
-
ich teste nochmal ne kleinigkeit.
(wie immer, erst einfach machen, auch wenn der code ineffizient wird. denn nur einfachen code kann man begreifen und optimieren.)
ich zerlege die schleife mal in vier einzelne.bool TileCollision(int x,int y,int x2,int y2,int rangex,int rangey) { for(int dx=40;dx;--dx) { int dy=dx/2; if(check(x+40-dx,y+dy,x2,y2,rangex,rangey)) return true; } //die anderen drei schleifen return false; }und betrachte nur die erste davon. die anderen gehen dann genauso.
und ich messe mit dieser main:
int main(){ for(int x=900;x<1100;++x) for(int y=900;y<1100;++y) if(TileCollision(x,y,1000,1000,10,10)!=TileCollision2(x,y,1000,1000,10,10)) cout<<x<<' '<<y<<'\n'; }und jetzt will ich, daß die reihe von quadraten nicht mehr schräg verläuft, sondern waagerecht. dazu pople ich mal an den schleifen rum.
bool TileCollision2(int x,int y,int x2,int y2,int rangex,int rangey) { for(int dx=40;dx;--dx) { int dy=dx/2; for(int rx=1;rx<rangex;++rx) { for(int ry=1;ry<rangey;++ry) { if(x+40-dx==x2+rx && y+dy==y2+ry) return true; } } } //die anderen drei schleifen return false; }nu kann ich die schleifen vertauschen
bool TileCollision2(int x,int y,int x2,int y2,int rangex,int rangey) { for(int rx=1;rx<rangex;++rx) { for(int ry=1;ry<rangey;++ry) { for(int dx=40;dx;--dx) { int dy=dx/2; if(x+40-dx==x2+rx && y+dy==y2+ry) return true; } } } //die anderen drei schleifen return false; }mal zwischenvariablen bauen
bool TileCollision2(int x,int y,int x2,int y2,int rangex,int rangey) { for(int rx=1;rx<rangex;++rx) { for(int ry=1;ry<rangey;++ry) { for(int dx=40;dx;--dx) { int dy=dx/2; int tx=x+40-dx; int ty=y+dy; if(tx==x2+rx && ty==y2+ry) return true; } } } //die anderen drei schleifen return false; }nochmal tauschen und berechnungen so weit wie möglich nach aussen legen.
bool TileCollision2(int x,int y,int x2,int y2,int rangex,int rangey) { for(int rx=1;rx<rangex;++rx) { for(int dx=40;dx;--dx) { int tx=x+40-dx; int dy=dx/2; int ty=y+dy; for(int ry=1;ry<rangey;++ry) { if(tx==x2+rx && ty==y2+ry) return true; } } } //die anderen drei schleifen return false; }einen test nach außen legen
bool TileCollision2(int x,int y,int x2,int y2,int rangex,int rangey) { for(int rx=1;rx<rangex;++rx) { for(int dx=40;dx;--dx) { int tx=x+40-dx; if(tx==x2+rx){ int dy=dx/2; int ty=y+dy; for(int ry=1;ry<rangey;++ry) { if(ty==y2+ry) return true; } } } } //die anderen drei schleifen return false; }oh!
ich kann den wert von tx behaupten. und danach dx berechnen.
in kleinen schritten:
bool TileCollision2(int x,int y,int x2,int y2,int rangex,int rangey) { for(int rx=1;rx<rangex;++rx) { int tx=x2+rx; for(int dx=40;dx;--dx) { if(tx==x+40-dx){ int dy=dx/2; int ty=y+dy; for(int ry=1;ry<rangey;++ry) { if(tx==x2+rx && ty==y2+ry) return true; } } } } //die anderen drei schleifen return false; }und
bool TileCollision2(int x,int y,int x2,int y2,int rangex,int rangey) { for(int rx=1;rx<rangex;++rx) { int tx=x2+rx; for(int dx=40;dx;--dx) { if(dx==x+40-tx){ int dy=dx/2; int ty=y+dy; for(int ry=1;ry<rangey;++ry) { if(tx==x2+rx && ty==y2+ry) return true; } } } } //die anderen drei schleifen return false; }bool TileCollision2(int x,int y,int x2,int y2,int rangex,int rangey) { for(int rx=1;rx<rangex;++rx) { int tx=x2+rx; int dx=x+40-tx; if(0<dx && dx<=40) { if(dx==x+40-tx){ int dy=dx/2; int ty=y+dy; for(int ry=1;ry<rangey;++ry) { if(tx==x2+rx && ty==y2+ry) return true; } } } } //die anderen drei schleifen return false; }naja, jetzt was einfaches:
bool TileCollision2(int x,int y,int x2,int y2,int rangex,int rangey) { for(int rx=1;rx<rangex;++rx) { int tx=x2+rx; int dx=x+40-tx; if(0<dx && dx<=40) { int dy=dx/2; int ty=y+dy; for(int ry=1;ry<rangey;++ry) { if(tx==x2+rx && ty==y2+ry) return true; } } } //die anderen drei schleifen return false; }ups, irgendwo oben vergessen, den ersten test rauszumachen.
das hier ist gemeint:bool TileCollision2(int x,int y,int x2,int y2,int rangex,int rangey) { for(int rx=1;rx<rangex;++rx) { int tx=x2+rx; int dx=x+40-tx; if(0<dx && dx<=40) { int dy=dx/2; int ty=y+dy; for(int ry=1;ry<rangey;++ry) { if(ty==y2+ry) return true; } } } //die anderen drei schleifen return false; }wollen wie versuchen, noch eine schleife wegzupopeln?
na, klaro.for(int ry=1;ry<rangey;++ry) { if(ry==ty-y2) return true; }und
int ry=ty-y2; if(0<ry && ry<rangey) return true;und noch eine?
na, klaro. deswegen war ja der ganze aufstand.
aber ich sehe nicht, wie.
also erstmal ganz viel umformen und vereinfachen.
da motto ist ja "erst vereinfachen, dann kommt das optimieren schon von allein".bool TileCollision2(int x,int y,int x2,int y2,int rangex,int rangey) { for(int rx=1;rx<rangex;++rx) { int tx=x2+rx; int dx=tx-x; if(-40<-dx && -dx<=0) { int ry=y+(40-dx)/2-y2; if(0<ry && ry<rangey) return true; } } //die anderen drei schleifen return false; }bool TileCollision2(int x,int y,int x2,int y2,int rangex,int rangey) { for(int rx=1;rx<rangex;++rx) { int dx=x2+rx-x; if(0<=dx && dx<40) { int ry=y+(40-dx)/2-y2; if(0<ry && ry<rangey) return true; } } //die anderen drei schleifen return false; }gebracht hat das zwar nix, aber es erinnerte mich ans ziel. die schleife wegpopeln.
bool TileCollision2(int x,int y,int x2,int y2,int rangex,int rangey) { // rx=dx+x-x2; for(int dx=x2+1-x;dx+x-x2<rangex;++dx) { // int dx=x2+rx-x; if(0<=dx && dx<40) { int ry=y+(40-dx)/2-y2; if(0<ry && ry<rangey) return true; } } //die anderen drei schleifen return false; }bool TileCollision2(int x,int y,int x2,int y2,int rangex,int rangey) { int begin1=x2+1-x; int end1=rangex-x+x2; int begin2=0; int end2=40; for(int dx=begin1;dx<end1;++dx) { if(begin2<=dx && dx<end2) { int ry=y+(40-dx)/2-y2; if(0<ry && ry<rangey) return true; } } //die anderen drei schleifen return false; }bool TileCollision2(int x,int y,int x2,int y2,int rangex,int rangey) { int begin=max(x2+1-x,0); int end=min(rangex-x+x2,40); for(int dx=begin;dx<end;++dx) { cout<<'.'; int ry=y+(40-dx)/2-y2; if(0<ry && ry<rangey) return true; } //die anderen drei schleifen return false; }naja, einigermaßen flott isses ja. aber nicht optimal. das muß auch ohne schleife gehen. hab aber jetzt keine lust mehr.
-
naja, einer noch.
es könnte sein, daß man nur die grenzen testen muss. ale begin und end-1. nach dem min/max-zeugs könnten das wirklich die einzigen relevaten fragen sein. müßtest du noch nachweisen. vielleicht so ähnlich:int main(){ int c=0; for(int sx=1;sx<1000;++sx){ for(int sy=1;sy<1000;++sy){ cout<<sx<<sy<<'\r'; for(int x=0;x<10000;++x){ for(int y=0;y<10000;++y){ if(TileCollision(x,y,1000,1000,sx,sy)!=TileCollision2(x,y,1000,1000,sx,sy)){ cout<<++c<<'\t'<<x<<' '<<y<<'\n'; } } } } } }(bei mir hat er noch keinen fehler gefunden, aber echt schnell ich mein rechnerchen auch nicht gerade).
dann wären nämlich
bool TileCollision2(int x,int y,int x2,int y2,int rangex,int rangey) { int begin=max(x2+1-x,0); int end=min(rangex-x+x2,40); if(end>begin){ { int dx=begin; int ry=y+(40-dx)/2-y2; if(0<ry && ry<rangey) return true; } { int dx=end-1; int ry=y+(40-dx)/2-y2; if(0<ry && ry<rangey) return true; } } //die anderen drei schleifen return false; }alle schleifen weg.
-
WOW! Jetzt weiß ich wieso man Volkard "Der Pate" nennt.
