Kreiselmäßige - Forschleife

Übersicht BlitzMax, BlitzMax NG Beginners-Corner

Neue Antwort erstellen

 

PhillipK

Betreff: Kreiselmäßige - Forschleife

BeitragFr, Sep 23, 2011 14:57
Antworten mit Zitat
Benutzer-Profile anzeigen
Heyho!

Ich habe grade ein etwas komisches Problem:

Mein versuch ist, ein paar schleifen möglichst schnell zu verschachteln, um ein 2D Raster Kreiselmäßig bzw schneckenhaus mäßig durchzugehen.

Das klingt erstmal verwirrend, ist aber (eigentlich) ganz einfach ^^

Hier mal das ganze als kleines Ascii bildchen: (codebox für einrückung!)
Code: [AUSKLAPPEN]
 
10-11-12-13
|        |
9  2--3  14
|  |  |  |
8  1  4  15
|     |  |
7--6--5  16
         |
   19-18-17
 


(1) ist hier mein ausgangspunkt der durch meine Spieler/Kameraposition bestimmt ist.

Das ganze soll nun in 3 schleifen die schritte verschieben und jeweils den nächsten punkt in eine Update-Liste packen.
Nun wirds auch klar warum das kreiselförmig ist:
Es soll möglichst um den spieler herum geupdatet werden.

Allerdings bin ich zu dämlich, das ganze anständig zu verschachteln.

Mein erster versuch sah so aus, das ich mehrere variablen bestimme:

StepY, StepX - entweder -1 oder +1, je nachdem was ich als "Nächstes" brauche

CountY, CountX - anzahl, wie oft Step* angewendet werden soll (erst 1,dann 2, dann drei, dann vier...)

TotalCountY, TotalCountX - die anzahl, wie oft als letztes in eine richtung durchgegangen wurde.

Hier der erste testcode:
BlitzMax: [AUSKLAPPEN]
		Local cX:Int = sekCntX / 2
Local cY:Int = sekCntY / 2
Local stepX:Int = 0
Local stepZ:Int = -1
Local cntX:Int = 1
Local cntZ:Int = 1
Local totalCntX:Int = 1
Local totalCntY:Int = 1
Local cnt:Int = 0
Self.sektorUpdateList.AddLast(Self.sektor[cX, cY])

While 1
While 1
'Z schleife!
If cntZ <= 0 Then Exit

If cY < 0 Or cY >= sekCntY Or cX < 0 Or cX >= sekCntX Then Continue
cY:+stepZ
cntZ:-1

If cY >= 0 And cY < sekCntY Then
Self.sektorUpdateList.AddLast(Self.sektor[cX, cY])
cnt:+1
EndIf
Wend
While 1
'x schleife
If cntX <= 0 Then Exit

If cY < 0 Or cY >= sekCntY Or cX < 0 Or cX >= sekCntX Then Continue

cX:+stepX
cntX:-1

If cX >= 0 And cX < sekCntX Then
Self.sektorUpdateList.AddLast(Self.sektor[cX, cY])
cnt:+1
EndIf
Wend
If cnt >= sekCntX * sekCntY Then Exit

stepZ = stepZ * -1
stepX = stepX * -1

totalCntX:+1
totalCntY:+1
cntX = totalCntX
cntZ = totalCntY
Wend


Um das noch zu erklären:
sekCntX und sekCntY sind errechnete werte, wieviele Sektoren Tatsächlich vorhanden sind.
SekCntX*SekCntY ist folglich die totale anzahl auf der gesamten Map.

Intention in diesem Code:

eine über-schleife die das ganze am laufen hält.

2 unterschleifen, einmal zum zählen von X und einmal zum zählen von Z (bzw Y, hab ich ein wenig dämlich benannt)

Jede unterschleife geht Count* durch und zählt step auf cX / cZ - welches für CenterX / CenterZ steht - am anfang der ausgangspunkt.

Sind beide schleifen beendet ( if cnt <= 0 then Exit ), folgt die prüfung, ob 'cnt' - hier eine zählvariable - schon die Sektoranzahl erreicht hat, dh alle wurden in die liste eingefügt.
Ist dem nicht so - wird stepX und stepZ umgedreht (*-1)

danach wird die totale anzahl an schritten pro richtung um 1 erhöht und die neuen cntX und cntZ variablen gesetzt.

So beginnt das ganze von vorn.

Ich erkenne allerdings keinerlei fehler in dem Code- allerdings bin ich mir auch nicht ganz sicher, ob die Exit-fällt richtig eintreten.

Es passiert einfach nix, es gibt kein ende. Entweder ist mein ansatz doch ziemlich dämlich gewählt und die Schleifen sind langsam, oder aber er findet nie ein ende - was mich allerdings wundert, da es sonst nach ein paar sekunden zumindest einen Array-index out of bounds gegeben haben müsste.

Ich bin gespannt, ob ihr meinen Denkfehler finden könnt - ich kanns nicht.
Alternativ wäre ich auch gespannt, ob jemand eine bessere idee hat, kreisförmig um cX / cZ herum die sektoren ausfindig zu machen in die liste zu schmeißen.

Allerdings: Das ganze muss sehr schnell gehen, da es sehr häufig vorkommen kann und die sektoren unmittelbar um den spieler herum als erstes in die liste müssen.
Welche die weiter weg sind, sagen wir, 4 sektoren als radius, können getrost später rein.

Vielleicht mag der eine oder andere mir helfen Smile

Gruß, PhillipK

Xeres

Moderator

BeitragFr, Sep 23, 2011 15:07
Antworten mit Zitat
Benutzer-Profile anzeigen
Was willst du mit diesem komplizierten System erreichen? Ein Rechteck oder Kreis wäre deutlich einfacher, wenn du nur einen Teil um den Spieler neu berechnen willst.
Win10 Prof.(x64)/Ubuntu 16.04|CPU 4x3Ghz (Intel i5-4590S)|RAM 8 GB|GeForce GTX 960
Wie man Fragen richtig stellt || "Es geht nicht" || Video-Tutorial: Sinus & Cosinus
T
HERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)
 

PhillipK

BeitragFr, Sep 23, 2011 15:19
Antworten mit Zitat
Benutzer-Profile anzeigen
Ein rechteck oder kreis..
Nun, das soll nicht nur ein teil um den Spieler werden, sondern alles, allerdings das um den Spieler umbedingt zuerst.

Im moment dauert alles, was ein Update der sektoren erfordert, viel zu lange.
Darum soll umbedingt mit dem ersten "Sichtbaren" krams angefangen werden und nacher ganz gemütlich (und vielleicht auch nur Teilweise) der kram weiter ausserhalb geupdatet werden.

Mir kam grade allerdings noch eine 2te Version in den Sinn, die teste ich mal fix =)

(ich glaube, auch hier denke ich mal wieder zu kompliziert.. Dämliche angewohnheit!)

Noobody

BeitragFr, Sep 23, 2011 15:27
Antworten mit Zitat
Benutzer-Profile anzeigen
Da ich vor kurzem genau die gleiche Funktion brauchte, hier eine hoffentlich relativ flotte Implementierung davon BlitzMax: [AUSKLAPPEN]
Function WalkInSpiral(Array:Int[,])
Local DirX:Int[] = [0, 1, 0, -1]
Local DirY:Int[] = [-1, 0, 1, 0]

Local SizeX:Int = Array.Dimensions()[0]
Local SizeY:Int = Array.Dimensions()[1]

Local X:Int = SizeX/2 'CenterX/Y
Local Y:Int = SizeY/2

Local WalkDir:Int, StepAmount:Int = 1, StepsLeft:Int = 1, IncrementSteps:Int

While X >= 0 And Y >= 0 And X < SizeX And Y < SizeY
Print Array[X, Y] 'Hier das Listenverkettungszeug machen

X :+ DirX[WalkDir]
Y :+ DirY[WalkDir]

StepsLeft :- 1

If Not StepsLeft Then
StepAmount :+ IncrementSteps
StepsLeft = StepAmount
IncrementSteps = Not IncrementSteps 'Schneller als IncrementSteps = (IncrementSteps + 1) Mod 2

WalkDir = (WalkDir + 1) & 3 'Schneller als WalkDir = (WalkDir + 1) Mod 4
EndIf
Wend
End Function


Je nach dem musst du die Startposition und die Abbruchbedingung anpassen, damit die äussersten Zeilen/Spalten auch abgelaufen werden.
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun

Xeres

Moderator

BeitragFr, Sep 23, 2011 15:30
Antworten mit Zitat
Benutzer-Profile anzeigen
Wenn du die Spielerkoordinaten hast, sind die angrenzenden Sektoren ja offensichtlich. Zur Not kann man auch die Entfernung oder Manhatten-Distanz zum Spieler berechnen und die Liste danach sortieren.
Wenn das Updaten aber zu lange braucht, würde ich alles außer den nötigen Feldern sowieso außen vor lassen.
Win10 Prof.(x64)/Ubuntu 16.04|CPU 4x3Ghz (Intel i5-4590S)|RAM 8 GB|GeForce GTX 960
Wie man Fragen richtig stellt || "Es geht nicht" || Video-Tutorial: Sinus & Cosinus
T
HERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)
 

PhillipK

BeitragFr, Sep 23, 2011 15:50
Antworten mit Zitat
Benutzer-Profile anzeigen
@Xeres:

Eben weil es länger dauert, aber ich noch keine genauen bedingungen ausgearbeitet habe (Maximale Sichtweite, Höhe der Kamera, etc) werde ich erstmal alle Sektoren wie gewohnt updaten.
Nur die reihenfolge ist wichtig -
Ein einzelner Sektor ist kein akt, das geht schnell. Aber ein ganzer batzen sektoren (ich glaube, im moment sinds 32x32 stück) verursacht dann doch unschöne 2-3 sekunden ruckler.

Darum habe ich eine - eh überfällige - liste beigefügt, die alle paar Frames (nach Millisecs() abgefragt) einen sektor aus der liste holt und ihn updatet.

Später werde ich das System mit einer Priorität ausarbeiten, die die Sichtbaren Sektoren (Sofern ich sie dann endlich bestimmen kann) sofort updatet und den rest teilweise und über zeit.
Wenn ich dann auch eine Maximale Sichtweite habe, kommt der rest auch garnicht dran - die daten habe ich so oder so im Speicher (danke für den hinweis im Worklog ^^)

@Noobody:
Cool danke Very Happy Ich werde mich gleich mit Zettel und Stif hinsetzen und die genauen Konditionen ausfindig machen, wann meine Schleife aufhören muss. Im kopfe schaffe ich es nicht so recht.
Alles in allem liest sich der Code zwar anfangs verworren, ist aber dann doch einfacher.
Ich werde ihn gleich mal umformen und einen Speedtest durchführen Smile
Grundsätzlich kann er nur bedingt langsamer sein als die alte for-verschachtelung, die einfach das Komplette feld von 0,0 bis SekCntX, SekCntY durchgeht und updatet.


Die Manhatten-Distanz sieht mir auf den ersten blick nach dem von annixa getauften 'Pixelweg' aus ^^
Das ganze hatten wir immer brav als funktion:
BlitzMax: [AUSKLAPPEN]
Function Pixelweg:Int(x1:Int, y1:Int, x2:Int, y2:Int) 
Return Abs(x2-x1)+Abs(y2-y1)
End Function

so, glaube ich. Werde gleich mal die funktion wieder ausgraben Smile

Midimaster

BeitragFr, Sep 23, 2011 17:11
Antworten mit Zitat
Benutzer-Profile anzeigen
so eine spiralenartige bewegung bewegt sich immer so:

Zitat:
******************
1. Richtung N: y um -1*1 schritt , X bleibt
2. Richtung O: x um +1*1 schritt, y bleibt

3. Richtung S: y um +1*2 , X bleibt
4. Richtung W: x um -1*2, Y bleibt
******************
5. N: y um -1*3 ,...
6. O: x um +1*3

7. S: y um +1*4
8. W: x um -1*4
******************


also wird jedes zweite mal die Anzahl der nötigen Steps um 1 größer!

nach dem viertel mal geht es mit den vorzeichen wieder von vorne los.
Gewinner des BCC #53 mit "Gitarrist vs Fussballer" http://www.midimaster.de/downl...ssball.exe

Neue Antwort erstellen


Übersicht BlitzMax, BlitzMax NG Beginners-Corner

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group