A-Stern ist zu langsam
Übersicht
BlitzMax, BlitzMax NG Allgemein
ToninatorBetreff: A-Stern ist zu langsam |
 Mi, März 12, 2014 16:32Antworten mit Zitat 
|
|
|---|---|---|
|
Hallo Leute!
Ich habe mich neulich daran gemacht, anhand das A-Stern-Algorithmus ein Wegfindungs-Programm zu schreiben (ich glaube, dass es etwas zu lang dauern würde, diesen jetzt zu erklären, deshalb hoffe, ich dass er einigen Leuten bereits bekannt ist). Eigentlich wird eine Openlist und eine Closedlist benötigt, um den Algorithmus zu realisieren, doch da ich noch relativ neu in BlitzMax bin und mit Listen bisher kaum etwas realisiert habe, benutze ich ein Array, in welchem jede Zelle ein Feld der Karte darstellt. Unter anderem hat jedes Feld einen Wert das aktuellen Status, was meint, dass dieses Feld entweder unbekannt, auf der Openlist oder auf der Closedlist ist. So weit, so gut. Der Nachteil an der Geschichte: Um das Feld, welches als nächstes untersucht werden muss zu finden, muss jedes mal das ganze Array abgearbeitet werden. Und das etliche Male pro Wegfindung. Bei großen Karten sollte die, so meinte ich jedenfalls, ziemlich lange dauern. Da wären Listen doch bestimmt schneller. Nun, ich programmierte die ganze Sache zuerst nur mit einem allumfassenden Array und natürlich dauerte es bei großen Karten lange, bis der Weg gefunden wurde. Jetzt setzte ich mich doch ein bisschen mit den Listen auseinander und kam zum Entschluss, dass es das effektivste wäre, das Array zu behalten, doch die Openlist zusätzlich als Liste zu realisieren. Die sollte nun dazu verwendet werden, das aktuell zu bearbeitende Feld zu finden. Ich erwartete einen großen Geschwindigkeitszuwachs, da ja nur ein Bruchteil der sonst zu untersuchenden Felder abzusuchen waren. Nachdem ich das Programm entsprechend umgeschrieben habe, setzte ich beide Programme, also die alte und die neue Version, nebeneinander und testete die Geschwindigkeit. Das Ergebnis: beide waren genau gleichschnell, sowohl bei kleinen, als auch bei größeren Karten. Enttäuschend! Nun frage ich euch: Wie kann das sein? Was habe ich falsch gemacht? Und wie kann ich die Sache noch beschleunigen? Am Ende sollte eine Wegfindung herauskommen, wie sie bei Civilization funktioniert, da ich ein ähnliches Spiel programmieren möchte. Doch mit einer derart langsamen Wegfindung geht dies kaum. Ich hoffe, das ihr mir helfen könnt. Hier noch beide Quelltextexte, bei dem vor allem die Funktion A_STAR von belang ist. Der Rest ist nur Bedienungs- und Visualisierungszeug. Nur mit einem Array Code: [AUSKLAPPEN] Strict
Global width:Short = 800 Global height:Short = 600 Global depth:Byte = 0 Global hz:Byte = 10 Graphics width,height,depth,hz Global a:Byte = 50 Global col_count:Byte = 16 Global row_count:Byte = 12 Global waypoints:TList = CreateList() Global start:TCell = TCell.Create(0,0) Global target:TCell = TCell.Create(col_count-1,row_count-1) waypoints.Clear() Global map:Byte[][] map = map[..col_count] For Local x:Byte = 0 To col_count-1 map[x] = map[x][..row_count] For Local y:Byte = 0 To row_count-1 map[x][y] = 1 Next Next Repeat Cls If MouseHit(MOUSE_LEFT) Then map[MouseX()/a][MouseY()/a] :+ 1 ElseIf MouseHit(MOUSE_RIGHT) And (map[MouseX()/a][MouseY()/a] > 0) Then map[MouseX()/a][MouseY()/a] :- 1 EndIf If KeyHit(KEY_1) Then start.x = MouseX()/a start.y = MouseY()/a EndIf If KeyHit(KEY_2) Then target.x = MouseX()/a target.y = MouseY()/a EndIf If KeyHit(KEY_ENTER) Then A_STAR() For Local x:Byte = 0 To col_count-1 For Local y:Byte = 0 To row_count-1 If map[x][y] = 0 Then SetColor 0,0,0 Else SetColor 30,160,60 EndIf DrawRect x*a,y*a,a,a SetColor 0,0,0 DrawText map[x][y],x*a+a/2-TextWidth(map[x][y])/2,y*a+a/2-TextHeight(map[x][y])/2 Next Next For Local z:TCell = EachIn waypoints SetColor 230,230,0 DrawRect z.x*a,z.y*a,a,a Next SetColor 160,160,255 DrawRect start.x*a,start.y*a,a,a SetColor 255,120,120 DrawRect target.x*a,target.y*a,a,a Flip Until KeyHit(KEY_ESCAPE) End Type TCell Field x Field y Function Create:TCell(_x:Byte,_y:Byte) Local c:TCell = New TCell c.x = _x c.y = _y ListAddLast waypoints,c Return c EndFunction End Type Function A_STAR() Local a_star_map:Short[][][] Rem 0 - Status 1 - f-Wert 2 - g-Wert 3 - x-Wert des Vorgängers 4 - y-Wert des Vorgängers Statuse 0 - Unbekannt 1 - OpenList 2 - ClosedList End Rem Const LAYER_COUNT = 5 Const STATUS_LAYER = 0 Const F_VALUE_LAYER = 1 Const G_VALUE_LAYER = 2 Const X_PREDECESSOR_LAYER = 3 Const Y_PREDECESSOR_LAYER = 4 Const UNKNOWN = 0 Const ON_OPENLIST = 1 Const ON_CLOSEDLIST = 2 waypoints.Clear() Local w:TCell = Null Local x:Int Local y:Int Local check_order:Int[][] = [[-1,0],[0,-1],[0,1],[1,0],[-1,-1],[1,-1],[-1,1],[1,1]] a_star_map = a_star_map[..col_count] For x = 0 To col_count-1 a_star_map[x] = a_star_map[x][..row_count] For y = 0 To row_count-1 a_star_map[x][y] = a_star_map[x][y][..LAYER_COUNT] a_star_map[x][y][STATUS_LAYER] = UNKNOWN Next Next a_star_map[start.x][start.y][STATUS_LAYER] = ON_OPENLIST a_star_map[start.x][start.y][F_VALUE_LAYER] = 0 a_star_map[start.x][start.y][G_VALUE_LAYER] = 0 Local lowest_f_value:Int Local lowest_f_x:Byte Local lowest_f_y:Byte Local new_f_value:Short Local x_distance:Byte Local y_distance:Byte Repeat Cls lowest_f_value = -1 For x = 0 To col_count-1 For y = 0 To row_count-1 If a_star_map[x][y][STATUS_LAYER] = ON_OPENLIST Then If (a_star_map[x][y][F_VALUE_LAYER] < lowest_f_value) Or (lowest_f_value = -1) Then lowest_f_value = a_star_map[x][y][F_VALUE_LAYER] lowest_f_x = x lowest_f_y = y EndIf EndIf Next Next a_star_map[lowest_f_x][lowest_f_y][STATUS_LAYER] = ON_CLOSEDLIST If (lowest_f_value >= 0) And Not((lowest_f_x = target.x) And (lowest_f_y = target.y)) For Local i:Byte = 0 To 7 x = lowest_f_x+check_order[i][0] y = lowest_f_y+check_order[i][1] If (x >= 0) And (x < col_count) And (y >= 0) And (y < row_count) Then'And ((x <> 0) Or (y <> 0)) Then If (a_star_map[x][y][STATUS_LAYER] <> ON_CLOSEDLIST) And (map[x][y] <> 0) Then 'bisherige Kosten new_f_value = a_star_map[lowest_f_x][lowest_f_y][G_VALUE_LAYER] 'Kosten, um auf das Feld zu rücken new_f_value :+ map[x][y] 'Kosten der Heuristik des kürzesten Weges x_distance = Abs(target.x-x) y_distance = Abs(target.y-y) If x_distance >= y_distance Then new_f_value :+ x_distance Else new_f_value :+ y_distance EndIf If a_star_map[x][y][STATUS_LAYER] = UNKNOWN Then a_star_map[x][y][STATUS_LAYER] = ON_OPENLIST a_star_map[x][y][F_VALUE_LAYER] = new_f_value a_star_map[x][y][G_VALUE_LAYER] = a_star_map[lowest_f_x][lowest_f_y][G_VALUE_LAYER] + map[x][y] a_star_map[x][y][X_PREDECESSOR_LAYER] = lowest_f_x a_star_map[x][y][Y_PREDECESSOR_LAYER] = lowest_f_y ElseIf new_f_value < a_star_map[x][y][F_VALUE_LAYER] Then a_star_map[x][y][F_VALUE_LAYER] = new_f_value a_star_map[x][y][G_VALUE_LAYER] = a_star_map[lowest_f_x][lowest_f_y][G_VALUE_LAYER] + map[x][y] a_star_map[x][y][X_PREDECESSOR_LAYER] = lowest_f_x a_star_map[x][y][Y_PREDECESSOR_LAYER] = lowest_f_y EndIf EndIf EndIf Next ElseIf (lowest_f_x = target.x) And (lowest_f_y = target.y) x = lowest_f_x y = lowest_f_y Local ram_x:Byte Repeat ram_x = x w = TCell.Create(x,y) x = a_star_map[x][y][X_PREDECESSOR_LAYER] y = a_star_map[ram_x][y][Y_PREDECESSOR_LAYER] Until (x = start.x) And (y = start.y) EndIf Flip 'WaitKey Until (lowest_f_value = -1) Or (w <> Null) End Function Mit einem Array und einer Openlist Code: [AUSKLAPPEN] Strict
Global width:Short = 800 Global height:Short = 600 Global depth:Byte = 0 Global hz:Byte = 10 Graphics width,height,depth,hz Global a:Byte = 50 Global col_count:Byte = 16 Global row_count:Byte = 12 Global waypoints:TList = CreateList() Global start:TCell = TCell.Create(0,0) Global target:TCell = TCell.Create(col_count-1,row_count-1) waypoints.Clear() Global map:Byte[][] map = map[..col_count] For Local x:Byte = 0 To col_count-1 map[x] = map[x][..row_count] For Local y:Byte = 0 To row_count-1 map[x][y] = 1 Next Next Global ol:TList = CreateList() Repeat Cls If MouseHit(MOUSE_LEFT) Then map[MouseX()/a][MouseY()/a] :+ 1 ElseIf MouseHit(MOUSE_RIGHT) And (map[MouseX()/a][MouseY()/a] > 0) Then map[MouseX()/a][MouseY()/a] :- 1 EndIf If KeyHit(KEY_1) Then start.x = MouseX()/a start.y = MouseY()/a EndIf If KeyHit(KEY_2) Then target.x = MouseX()/a target.y = MouseY()/a EndIf If KeyHit(KEY_ENTER) Then A_STAR() For Local x:Byte = 0 To col_count-1 For Local y:Byte = 0 To row_count-1 If map[x][y] = 0 Then SetColor 0,0,0 Else SetColor 30,160,60 EndIf DrawRect x*a,y*a,a,a SetColor 0,0,0 DrawText map[x][y],x*a+a/2-TextWidth(map[x][y])/2,y*a+a/2-TextHeight(map[x][y])/2 Next Next For Local w:TWaypointCell = EachIn waypoints SetColor 230,230,0 DrawRect w.x*a,w.y*a,a,a Next SetColor 160,160,255 DrawRect start.x*a,start.y*a,a,a SetColor 255,120,120 DrawRect target.x*a,target.y*a,a,a Flip Until KeyHit(KEY_ESCAPE) End Type TCell Field x:Byte Field y:Byte Function Create:TCell(_x:Byte,_y:Byte) Local c:TCell = New TCell c.x = _x c.y = _y Return c EndFunction End Type Type TListCell Field x:Byte Field y:Byte Field link:TLink Function Create:TListCell(_x:Byte,_y:Byte) Local c:TListCell = New TListCell c.x = _x c.y = _y c.link = ol.AddLast(c) Return c EndFunction End Type Type TWaypointCell Field x:Byte Field y:Byte Function Create:TWaypointCell(_x:Byte,_y:Byte) Local w:TWaypointCell = New TWaypointCell w.x = _x w.y = _y waypoints.AddLast(w) Return w End Function EndType Function A_STAR() Local a_star_map:Short[][][] Rem 0 - Status 1 - f-Wert 2 - g-Wert 3 - x-Wert des Vorgängers 4 - y-Wert des Vorgängers Statuse 0 - Unbekannt 1 - OpenList 2 - ClosedList End Rem Const LAYER_COUNT = 5 Const STATUS_LAYER = 0 Const F_VALUE_LAYER = 1 Const G_VALUE_LAYER = 2 Const X_PREDECESSOR_LAYER = 3 Const Y_PREDECESSOR_LAYER = 4 Const UNKNOWN = 0 Const ON_OPENLIST = 1 Const ON_CLOSEDLIST = 2 waypoints.Clear() Local c:TListCell Local x:Int Local y:Int Local mission_complete:Byte = False Local check_order:Int[][] = [[-1,0],[0,-1],[0,1],[1,0],[-1,-1],[1,-1],[-1,1],[1,1]] a_star_map = a_star_map[..col_count] For x = 0 To col_count-1 a_star_map[x] = a_star_map[x][..row_count] For y = 0 To row_count-1 a_star_map[x][y] = a_star_map[x][y][..LAYER_COUNT] a_star_map[x][y][STATUS_LAYER] = UNKNOWN Next Next a_star_map[start.x][start.y][STATUS_LAYER] = ON_OPENLIST a_star_map[start.x][start.y][F_VALUE_LAYER] = 0 a_star_map[start.x][start.y][G_VALUE_LAYER] = 0 c = TListCell.Create(start.x,start.y) Local lowest_f_value:Int Local lowest_f_x:Byte Local lowest_f_y:Byte Local link:TLink Local new_f_value:Short Local x_distance:Byte Local y_distance:Byte Repeat DebugLog "------------------------" Cls lowest_f_value = -1 For c = EachIn ol DebugLog c.x+" - "+c.y+ " | " If (a_star_map[c.x][c.y][F_VALUE_LAYER] < lowest_f_value) Or (lowest_f_value = -1) Then lowest_f_value = a_star_map[c.x][c.y][F_VALUE_LAYER] lowest_f_x = c.x lowest_f_y = c.y link = c.link EndIf Next a_star_map[lowest_f_x][lowest_f_y][STATUS_LAYER] = ON_CLOSEDLIST RemoveLink(link) If (lowest_f_value >= 0) And Not((lowest_f_x = target.x) And (lowest_f_y = target.y)) For Local i:Byte = 0 To 7 x = lowest_f_x+check_order[i][0] y = lowest_f_y+check_order[i][1] If (x >= 0) And (x < col_count) And (y >= 0) And (y < row_count) Then If (a_star_map[x][y][STATUS_LAYER] <> ON_CLOSEDLIST) And (map[x][y] <> 0) Then 'bisherige Kosten new_f_value = a_star_map[lowest_f_x][lowest_f_y][G_VALUE_LAYER] 'Kosten, um auf das Feld zu rücken new_f_value :+ map[x][y] 'Kosten der Heuristik des kürzesten Weges x_distance = Abs(target.x-x) y_distance = Abs(target.y-y) If x_distance >= y_distance Then new_f_value :+ x_distance Else new_f_value :+ y_distance EndIf If a_star_map[x][y][STATUS_LAYER] = UNKNOWN Then a_star_map[x][y][STATUS_LAYER] = ON_OPENLIST a_star_map[x][y][F_VALUE_LAYER] = new_f_value a_star_map[x][y][G_VALUE_LAYER] = a_star_map[lowest_f_x][lowest_f_y][G_VALUE_LAYER] + map[x][y] a_star_map[x][y][X_PREDECESSOR_LAYER] = lowest_f_x a_star_map[x][y][Y_PREDECESSOR_LAYER] = lowest_f_y c = TListCell.Create(x,y) ElseIf new_f_value < a_star_map[x][y][F_VALUE_LAYER] Then a_star_map[x][y][F_VALUE_LAYER] = new_f_value a_star_map[x][y][G_VALUE_LAYER] = a_star_map[lowest_f_x][lowest_f_y][G_VALUE_LAYER] + map[x][y] a_star_map[x][y][X_PREDECESSOR_LAYER] = lowest_f_x a_star_map[x][y][Y_PREDECESSOR_LAYER] = lowest_f_y EndIf EndIf EndIf Next ElseIf (lowest_f_x = target.x) And (lowest_f_y = target.y) x = lowest_f_x y = lowest_f_y Local ram_x:Byte Local w:TWaypointCell mission_complete = True Repeat ram_x = x w = TWaypointCell.Create(x,y) x = a_star_map[x][y][X_PREDECESSOR_LAYER] y = a_star_map[ram_x][y][Y_PREDECESSOR_LAYER] Until (x = start.x) And (y = start.y) EndIf Flip 'WaitKey Until (lowest_f_value = -1) Or (mission_complete) ol.clear() End Function |
||
| Я люблю тебя, Россия!! <333 | ||
PhillipK |
Mi, März 12, 2014 17:10 Antworten mit Zitat
|
|
|---|---|---|
|
Was mir als erstes auffällt:
BlitzMax: [AUSKLAPPEN] For c = EachIn ol Damit suchst du den nächsten, kleinsten wert, der zu checken ist, oder? Hier sehe ich einen fetten speedkiller: Im worst case wird für jede node noch jede andere node gecheckt. Im allgemeinen kann man sagen, das alles mit der art der sortierung steht und fällt. Durch zufall bin ich heute hierauf gestoßen: https://www.blitzforum.de/foru...hp?t=39213 Hier hat dak einen sehr schönen binären baum geschrieben, welcher perfekt für AStar geeignet ist. Um das zu testen, hatte ich damals auch einen AStar damit geschrieben. Um seinen Tree zu nutzen, brauchst du im prinzip nur folgende funktionen: BlitzMax: [AUSKLAPPEN] Method insert(obj:Object, key:Int) Key ist in dem fall der f-value (geschätze wegkosten zum ziel pro node) Sowie BlitzMax: [AUSKLAPPEN] Method extractMin:TBANode()
Welches dir die niedrigsten kosten ausspuckt. Diese liste, die DAK da geschrieben hat, ist nach dem kleinsten wert sortiert, dh du musst immer nur den ersten rausholen. Falls es dir hilft, kannst du dir auch meinen code (3ter post im thread) zum AStar ansehen. Ich verwende eine Open, eine Close und eine Todo-list. open und close sind arrays, die das spielfeld repräsentieren, todo ist der Binärbaum. Hab grade leider wenig zeit, aber ich werd heute abend mal reinschauen und mir deinen code durchgucken  AStar ist zwar etwas her, aber solche algos sind wie fahrradfahren, die verlernt man nicht ^^
|
||
|
DAK |
Mi, März 12, 2014 22:56 Antworten mit Zitat
|
|---|---|---|
|
Find ich ziemlich cool, dass da mein Code raus kommt^^
(Nur zur Selbstkorrektur: ist wohl einer ein binärer Heap als ein binärer Baum.) Bei solchen Aufgaben kommt es sehr stark auf die Datenstruktur an, die du verwendest. Eine Suche auf einem normalen Array mit n Elementen hat eine Laufzeit von O(n), das heißt, man muss ungefähr so viele Vergleiche machen wie es Elemente gibt (das O ist dazu da um zu sagen, dass es irgendwo in der Größenordnung von n ist). Eine Suche nach dem geringsten Element in einem binären Heap (inklusive Entfernen dieses Elements) geht dagegen in O(log(n)), was deutlich schneller ist. Nur so als ungefährer Größenvergleich: n bei 800x600 Elementen ist 480000 log(n) ist 5.7 Man muss dabei bedenken, dass ein Schritt beim Heap mehr Aufwand bedeutet als bei dem Array, aber selbst wenn der Aufwand 1000 Mal höher ist, ist der Heap immer noch um Größenordnungen schneller. Und je größer der zu durchsuchende Bereich wird, desto größer wird der Unterschied. Bei 1024x768 schaut das dann so aus: n = 1474560 (~3 Mal so viel wie bei 800x600) log(n) = 6.2 (nur minimale Veränderung) Was auch eventuell Sinn macht ist einen anderen Suchalgo zu verwenden. Wenn du keine pixelgenaue Suche brauchst funktioniert es ganz gut auf einer Karte Waypoints zu setzen, und dann den Dijkstra-Algorithmus zu verwenden, um die Wege zu finden. Der Dijkstra ist dem A* sehr ähnlich und lässt sich genauso leicht implementieren. Der Vorteil davon ist, dass jetzt nicht mehr jedes Pixel ein Knoten ist, sondern dass du deutlich weniger zu durchsuchen hast. Statt (800x600 =) 480000 Knoten hast du auf einer ähnlich großen Karte oft weniger als 200 Knoten beim Dijkstra. Eventuell tut es auch ein Tile-basiertes Pathfinding, wo du dann für die gleiche Kartengröße deutlich weniger Knoten brauchst und immer noch den A* verwenden kannst. |
||
| Gewinner der 6. und der 68. BlitzCodeCompo | ||
PhillipK |
Mi, März 12, 2014 23:48 Antworten mit Zitat
|
|
|---|---|---|
|
Also.. wow.
Ich bin nun echt geschockt oO Nachdem ich grade dein algo durchgeschaut habe, hab ich mal DAK's heap eingebaut. Ergebnis? WOHA- LAHM. Das konnte ich mir nicht erklären und bin hingegangen und hab den code wie folgt aufgemöbelt: BlitzMax: [AUSKLAPPEN] Function A_STAR() Ergo, ich habe mir (da du praktischerweise cls / flip schon eingebaut hattest...) alles per draw text ausgeben lassen. Aber: Die map ist SOWAS VON KLEIN das ich mir den zeitkiller nicht erklären konnte. Selbst mit dem schlechtesten algo dürfte das nichtmal eine millisekunde auf heutigen computern dauern. Und ich hatte recht: Grademal das finden der günstigsten kosten zum weitersuchen dingens kirchens, weißt schon, hat zwischen 0 und 1 ms gedauert. Nun kommt der clou: Eine einzelne zeile in dem algo, welche absolut nichts mit dem algo selber zu tun hat, hat für den kill gesorgt.. Es ist... Trommelwirbel... Flip oO Hier, nimmst du den unteren teil: BlitzMax: [AUSKLAPPEN] EndIf und kommentierst dort Flip aus, hast du das ganze echtzeittauglich. Und ohne Flip ist auch kein Cls von nöten. Gehen wir nun ein bisschen mehr ins detail: Deine Variante mit dem Array + Layern finde ich sehr ausgefallen und ideenreich, machts allerdings unheimlich schwer zu kapieren. Zugute kommt allerdings das nutzen von konstanten und die anmerkungen dazu. Allerdings wäre es hier vielleicht sinnvoller, ein type zu verwenden. Wenn du nicht weiß, was ein Type ist, rate ich allerdings davon ab, das nun auf teufel komm raus dort einzupflegen - lieber erstmal gesondert lernen und später mal in einem neuen AStar verwenden
Zweitens: BlitzMax: [AUSKLAPPEN] a_star_map[x][y][G_VALUE_LAYER] = a_star_map[lowest_f_x][lowest_f_y][G_VALUE_LAYER] + map[x][y] Du nimmst pur die wegkosten die eine Kachel kostet. Ist zwar nur minimal, aber eins hast du vergessen: Schrägschritte brauchen etwa 1,4x mehr "zeit" bzw distanz zum "überqueren". Genauer: Sqr( 1*1 + 1*1 ). wirklich korrekt wäre der algo also, wenn du pro kachel noch 1 als schritt an sich bzw 1.4 als schrägschritt hinzufügst. Allerdings: Dein dateityp ist integer was die kosten angeht. Hier wäre also ein faktor 10 angebracht - alle "kosten" der kacheln mit 10 multiplizieren, sowie 10 und 14 als schrittkosten einfügen. Drittens: Wenn es WIRKLICH speedkritisch wird, musst du bei sowas aufpassen: BlitzMax: [AUSKLAPPEN]
Das ist deine map, mit der du in wirklich allem arbeitest. Der grundgedanke Short zu verwenden ist richtig - spart einiges an ram. Aber soweit mir bekannt wird intern ein short wie ein int behandelt, dh zum rechnen etc muss der short erstmal umgewandelt, dann verrechnet und zurückgewandelt werden. Ich weiß nicht genau ob das eine blitzmax beschränkung ist, aber hier kann man bei (WIRKLICH SPEEDKRITISCHEN) sachen noch ein wenig was rauskitzeln. Viertens: Du verwendest "DebugLog". Die solltest du aber dennoch entfernen, wenn du etwas auf speed testet (wie zum beispiel einen A*) Bei deiner kleinen map ist das noch okay, aber wenn sie größer wird, kannst du hier auch wieder was sparen. Ist nur wieder eine mininininini... verbesserung, aber immerhin. Im Releasemode steht hinter DebugLog ein sinnloser funktionsaufruf, welcher immernoch cpu zeit braucht. Verachtenswert wenig, aber mit steigenderzahl kanns trotzdem was ausmachen
Ansonsten fällt mir nicht viel auf. Wie gesagt, das meiste ist echt nicht zu beachten. Einzig die suche könntest du durch einen Binären Heap (oder was auch immer) optimieren, aber sonst ist es erstaunlich gut gelungen als erster algo
|
||
Übersicht
BlitzMax, BlitzMax NG Allgemein
Powered by phpBB © 2001 - 2006, phpBB Group