Float Nachkommastellen auf Unendlich setzten

TGGC

Die Frage ist ein bisschen unklar, dazu muesstest du naemlich erstmal definieren, was "sämtliche Nachkommastellen auf Maximum" bedeutet. Binaer betrachtet: Ein float stellt nicht alle Nachkommastellen dar, sondern nur einen Teil, die restlichen Stellen der Zahl sind implizit 0. Du kannst also nie "sämtliche Nachkommastellen" auf 1 setzen (1 ist das Maximum), sondern nur:
a) die Nachkommastellen auf 1 setzen, die gerade von dem float dargestellt werden
b) den float so veraendern, das die Nachkommastellen moeglichst grosse Zahlen darstellen und sie dann auf 1 setzen

Beides macht man normalerweise nicht, da es nur zu Problemen fuehrt, du solltest eine saubere Loesung fuer dein Problem finden.

Ok, aber es muss doch in C++ einen Weg geben alle Nachkommastellen einer Float Zahl die möglich sind auf Maximum zu setzten, also wenn es bei einer 13 nur 4 Nachkommastellen maximal möglich währen dann eben 13.9999 oder wenn es bei einer 2117 nur 2 währen dann eben 200.99 usw...

Und natürlich funktioniert das ganze ja binär, ich weiß das die Nachkommastellen eines Float nicht einfach so im Speicher stehen sondern über Mantisse und Exponent abgebildet werden wodurch die Anzahl variable ist, dass ändert aber ja nichts daran, das man nicht alle möglichen Nachkommastellen auf das Maximum setzten könnte.

Ich kann für mein Problem aber keine andere wirkliche Lösung finden.
Falls jemand eine bessere Idee hat, hier warum ich das überhaupt brauche:

http://fs1.directupload.net/images/150720/temp/t64x7huk.png

Wenn man das Bild betrachtet, sieht man nebeneinander Blöcke, alle gleich groß und mit dem selben Abstand, mit anderen Worten ein Gitter.
Jeder Block / jede Zelle ist genau 1 groß.
Jedoch können manche Zellen Blau und andere Grau sein, Grau = Stein, Blau = Luft.
Das ganze bezieht sich eigentlich im 3 Dimensionalen auf eine Voxel Map wie z.B. in Minecraft, jedoch betrachte ich jetzt einfachheitshalber nur die X Achse.
Der Orange Punkt ist der Spieler(Jetzt hier einfach nur ein Punkt).
Nun, wenn man sich Gedanken um Kollision macht, muss man erst mal definieren, ab wann denn der Spieler überhaupt mit einem Block kollidiert, nämlich wenn er in einem Stein Block ist und das ist hier in diesem Fall der Fall, wenn er Größer Gleich 4 (Spieler C) oder kleiner als 3 ist, denn der Luft Block in dem er sich befindet geht ja von [3,4[.
Nun wenn ich die Kollision festgestellt habe, muss ich die Position des Spielers korrigieren, wenn er sich nach Rechts bewegt und mit dem Rechten Block kollidiert ist das ja kein Problem, dann muss ich seine Position einfach auf 3 setzten.
Wenn er sich aber nach Links bewegt, und ich ich die Kollision erkenne, müsste ich seine Position nicht auf 4 sondern auf 3.999999... setzten.
Und da ich die höchste Genauigkeit haben will die möglich ist suche ich nun einen Weg diese X.99999... hinzubekommen.
Ich hoffe ich konnte es halbwegs verständlich erklären.

Fatov schrieb:

Und da ich die höchste Genauigkeit haben will die möglich ist suche ich nun einen Weg diese X.99999... hinzubekommen.

Dann rechne in Vielfachen deiner Genauigkeit und mit Ganzzahlen.
Bei Positionen nicht in Meter sonder Mikrometer

Fatov schrieb:

Ich hoffe ich konnte es halbwegs verständlich erklären.

Na ja.
Unterschlägst du da nicht die Breite/Ausdehnung von deinem Spieler/Objekt?

TGGC

Simple Loesung fuer dein Problem, wenn du wirklich unbedingt floats brauchst: Ueberall wo ein Luftblock ist, gibt es nur eine Kollision, wenn > 4 und fuer alle Werte <=4 gibt es keine Kollision. Nun kannst du die Koordinate einfach auf 4 setzen, fertig.

Ja, das habe ich auch schon in Erwägung gezogen, jedoch kann ich die Positionen des Spieler dann nicht mehr durch einfaches casten(Einfach die Nachkommastellen abschneiden) in Block Position umwandeln, sondern muss jedes mal extra Abfragen machen, was mir nicht so lieb ist.

Wie z.B. von 1.1 auf 1.9... oder von 5.3 auf 5.9...
Aber ungeachtet dessen, muss doch das was ich wollte möglich sein ich meine ich muss doch nur immer alle Bits in der Mantisse die nach dem Komma/Exponenten kommen auf 1 setzten.
Als Algorithmus dann z.B. das 1. Bit ganz rechts in der Mantisse auf 1 setzten,
eins nach links gehen, wenn das Bit schon eins ist abbrechen ansonsten wieder auf eins setzten und wieder von vorne anfangen.

Zahl Vorzeichen Exponent Mantisse
1.1 0 01111111 10000000000000000000000
1.9... 0 01111111 11111111111111111111111
5.3 0 10000001 01110000000000000000000
5.9... 0 10000001 01111111111111111111111

Sowas:
http://www.cplusplus.com/reference/cmath/nextafter/
http://www.cplusplus.com/reference/cmath/nexttoward/
?

Sorry, die Formatierung wird immer verworfen.

Zahl | Vorzeichen | Exponent | Mantisse
1.1 | 0 | 01111111 | 10000000000000000000000
1.9... | 0 | 01111111 | 11111111111111111111111
5.3 | 0 | 10000001 | 01110000000000000000000
5.9... | 0 | 10000001 | 01111111111111111111111

Oh Danke DirkB.
Das ist genau das, was ich suche !!!
Vielen dank.

Finnegan

Fatov schrieb:

Und da ich die höchste Genauigkeit haben will die möglich ist suche ich nun einen Weg diese X.99999... hinzubekommen.

Nur mal so au doof, falls du mit "X.99999..." eine unendliche Folge von Neunen nach dem Komma meinst, dann setz' die Zahl einfach auf X+1 (falls X >= 0), dann hast du es mathematisch exakt, ohne Fehler

Ansonsten würde ich vielleicht eher selbst einen festen Wert definieren, mit dem du die Kollisionsposition korrigierst. Dieser darf ruhig etwas größer sein, als der kleinste Wert, für den die Fließkommanzahl vor und nach dem subtrahieren nicht identisch ist - schließlich möchstest du sicher noch etwas Genauigkeits-Spielraum haben, damit der Wert nach der Korrektur und ein, zwei weiteren Berechnungen nicht allein durch Rundungsfehler wieder "kollidiert". Zumindest die Physik-Bibliothek "Bullet" macht das ebenfalls so: Der Rand eines Kollisionsvolumens hat dort auch eine gewisse "Dicke".

Du kommst ohnehin nicht drumherum, dich auch auf eine solche "Dicke" festzulegen - mathematisch gibt es keinen Punkt der einer gegebenen Ebene "am nächsten" ist, da man immer einen angeben kann, der noch näher ist. Man muss sich also auf eine Distanz festlegen, und da ist es besser das über einen Parameter konfigurierbar zu machen - da hat man dann ein Stellrädchen mit dem man die Effekte von ohnehin unvermeidbaren Rundungsfehlern bei Physik/Kollisionsberechnungen besser bändigen kann.

Finnegan

P.S.: Bei deinem "Null-Toleranz-Ansatz", könnte man vermutlich sogar ein Objekt konstruieren, dass eigentlich an 2 Punkten kollidieren müsste, bei einem der Punkte aber eben nur knapp nicht. Wenn du jetzt das Objekt mit so wenig Spielraum verschiebst, so dass der kollidierende Punkt nicht mehr kollidiert, könnte es sein, dass durch die Verschiebung und damit einhergehenden Rundungsfehlern der Zweite Punkt dann doch kollidiert, aber der erste nicht mehr -> neue Verschiebung -> und paf! der erste kollidiert wieder -> Ping-Pong! ... lieber etwas mehr Puffer lassen

Es entstehen jetzt wie du gesagt hast manchmal komische Fehler die wahrscheinlich durch die Rundungsfehler verursacht werden.
Ich habe aber keine Erfahrung mit Rundungsfehler.
Wo in diesem Quellcode können denn manchmal Rundungsfehler entstehen ?

float xForce = 0;

		if (left)
		{
			xForce += 2000 * deltaTime;
		}
		if (right)
		{
			xForce -= 2000 * deltaTime;
		}

		xVel += xForce * deltaTime;
		float xDelta = xVel * deltaTime;
		float xNext = x + xDelta;
		float xCorr = xNext;

		if (xDelta > 0)
		{
			if (xNext + HERO_SIZE > (unsigned int)(xNext + HERO_SIZE))
			{
				if (map->getVoxel(xNext + HERO_SIZE, y, z)->getSolid() > 0 ||
					map->getVoxel(xNext + HERO_SIZE, y + HERO_SIZE, z)->getSolid() > 0 ||
					map->getVoxel(xNext + HERO_SIZE, y, z + HERO_SIZE)->getSolid() > 0 ||
					map->getVoxel(xNext + HERO_SIZE, y + HERO_SIZE, z + HERO_SIZE)->getSolid() > 0)
				{

					// Definierte dicke
					//xCorr = (unsigned int)xNext - 0.001f + HERO_SIZE;

					// Oder so genau wie es geht
					xCorr = nextafterf((unsigned int)xNext, -1.0f) + HERO_SIZE;

					xVel = 0;
				}
			}
		}
		else if (xDelta < 0)
		{
			if (map->getVoxel(xNext, y, z)->getSolid() > 0 ||
				map->getVoxel(xNext, y + HERO_SIZE, z)->getSolid() > 0 ||
				map->getVoxel(xNext, y, z + HERO_SIZE)->getSolid() > 0 ||
				map->getVoxel(xNext, y + HERO_SIZE, z + HERO_SIZE)->getSolid() > 0)
			{
				xCorr = (unsigned int)xNext + 1;
				xVel = 0;
			}
		}

		x = xCorr;

Bei dem

xCorr = nextafterf((unsigned int)xNext, -1.0f) + HERO_SIZE;

wenn ich z.B. +HERO_SIZE rechne?

TGGC

Gerundet wird bei floats quasi bei jeder Rechnung. wenn irgendwo das genaue Ergebnis wieder als ein float darstellbar ist, ist sowas quasi die Ausnahme. z.b. gilt folgende simple Umformung nicht: x < 10.0f <-> x + 5.0f < 15.0f

Aber wie rechne ich die Optimale "Dicke" aus ?

Fatov schrieb:

Sorry, die Formatierung wird immer verworfen.

Dann nimm Code-Tags (und keine Tabs)

Zahl	| Vorzeichen	| Exponent	| Mantisse 
1.1     | 0             | 01111111	| 10000000000000000000000 
1.9...  | 0             | 01111111	| 11111111111111111111111 
5.3     | 0             | 10000001	| 01110000000000000000000 
5.9...  | 0             | 10000001	| 01111111111111111111111

Finnegan

Hi nochmal! Ich verspüre gerade Lust zu dem Thema etwas weiter auszuholen, also nicht wundern, wenns etwas ausführlicher wird

Vorweg möchte ich nochmal auf die beiden Links die SeppJ zu Anfang gepostet hat verweisen, die sind sehr informativ, auch wenn der zweite ein wenig den Effekt einer Ladung Ziegelsteine haben könnte, die jemand über einem auskippt

Fatov schrieb:

Wo in diesem Quellcode können denn manchmal Rundungsfehler entstehen ?

Deinen Code zerpflück' ich jetzt mal nicht, stattdessen lieber ein paar Informationen, die dir hoffentlich mehr helfen:

Allgemeines zu Rundungsfehlern und deren Größe:

Für Fließkommazahlen gibt es eine Konstante, das Machine Epsilon ( std::numeric_limits<T>::epsilon() ), welche eine obere Schranke für den relativen Fehler angibt, wenn eine reelle Zahl zur nächsten darstellbaren Fließkommazahl gerundet wird. Der relative Fehler ist der Differenzbetrag zwischen der Zahl und ihrer Fließkommadarstellung dividiert durch den Betrag der Zahl: $\frac{\mid x - x_{float} \mid}{\mid x \mid} \leq \epsilon$ . Wobei ε das Machine Epsilon ist. Damit kannst du für eine gegebene Zahl x relativ einfach eine obere Schranke für absoluten Fehler berechnen, das ist der Betrag um den deine Fließkommazahl maximal vom tatsächlichen Wert abweicht: $E(x) \leq {\mid x \mid} \cdot {\epsilon}$ . Dieser Fehler ist abhängig davon, in welcher Größenordnung sich dein x bewegt, und derjenige, der sich bei deinen Kollisions-Vergleichen bemerkbar machen wird.

Ein paar Faustregeln zur Minimierung von Rundungsfehlern:

Alle Rechenoperationen können Rundungsfehler einbringen. Multiplikation und Division sind dabei relativ "gutmütig", Additon und und Subtraktion sind meist die Problemkinder: Je stärker sich die Größenordnung der beiden Operanden voneinander unterscheidet, umso größer auch der Fehler. Bei Addition/Subtraktion wird der Fließkomma-Exponent des betragsmäßig kleineren Operanden auf den den größeren angepasst, wodurch Genauigkeit des kleineren Operanden verloren geht und somit nicht ins Endergebnis eingebracht wird. Also:

1. Darauf achten, dass man wenn immer möglich mit Zahlen in etwa der selben Größenordnung rechnet.
2. Benötigt man besonders viel Genauigkeit, sollten die Zahlen zusätzlich noch besonders klein sein. Das bedeutet für geometrische Berechnungen z.B. dass man diese bevorzugt in lokalen Koordinatensystemen durchführen sollte. Für deine Block-Kollision würde das z.B. bedeuten diese nicht in absoluten Weltkoordinaten durchzuführen, sondern in relativen Block-Koordinaten, wo z.B. das Zentrum des Blocks der Nullpunkt ist.
3. Bei iterativen Berechnungen können sich Rundungsfehler aufaddieren wie zum Beispiel bei deiner Berechnung der x -Bewegung. Da du hier allerdings nur die Bewegung des Objekts durch den Raum berechnest, wird dieser Fehler wahrscheinlich nicht sonderlich auffallen, es sei denn es ist notwendig, dass das Objekt z.B. zu einem exakten Zeitpunkt irgendwo ankommt, wenn es sich mit einer gegebenen Geschwindigkeit durch den Raum bewegt (das wird, so wie du das berechnest wahrscheinlich immer mehr abweichen, je weiter die zurückgelegte Strecke ist). Das lässt sich vermeiden, indem man die Berechnung soweit möglich eben nicht iterativ macht, sondern direkt: Solange das Objekt seinen Geschindigkeitsvektor nicht verändert ist seine aktuelle Position ( $p(t)$ ) immer die Startposition ( $p_0$ ) plus die Geschwindigkeit ( $v$ ) multipliziert mit der Differenz zwischen aktueller ( $t$ ) und der Startzeit ( $t_0$ ): $p(t) = p\_0 + v(t - t\_0)$ . Wenn du also hier mehr Genauigkeit benötigen solltest, dann könntest du z.B. den Fehler minimieren, indem du immer wenn sich $v$ ändert ( xVel ), jeweils $p_0$ und $t_0$ aus aktueller Position und Zeit neu bestimmst und die Position direkt berechnest.
4. Und natürlich: Je weniger Rechenoperationen, umso seltener können Rundungsfehler in das Endergebnis eingebracht werden. Also nur berechnen, was man auch wirklich benötigt, und vor allem "zurückrechnen" vermeiden, also sowas wie:

x = x + 5.0
... // irgendwelche anderen Berechnungen, für die x um 5 erhöht sein muss
x = x - 5.0
// hier brauche ich wieder das ursprüngliche x ...

Stattdessen lieber eine Kopie von x anlegen. Das klingt banal, ist aber manchmal nicht so offensichtlich. Ich habe diesbezüglich z.B. schon Funktionen gesehen, die z.B. die aktuelle ModelView-Matrix in OpenGL mit Rundungsfehlern verseucht haben, indem so etwas hier gemacht wurde:

glTranslatef(x, y, z);
... // blablub irgendwas rendern
glTranslatef(-x, -y, -z);

anstatt eines glPushMatrix() / glPopMatrix() -Paars. Weniger offensichtlich, aber Kategorie "zurückrechnen".

Fatov schrieb:

Aber wie rechne ich die Optimale "Dicke" aus ?

Vielleicht solltest du dir zunächst überlegen, was du unter "optimaler Dicke" verstehst. Auf Anhieb sehe ich da zwei Kriterien nach denen man die "Dicke" auswählen kann:

1. Stabile Simulation: Du möchtest z.B. konkret vermeiden, dass du ein kollidiertes Objekt an eine Position aus dem Block "herausschiebst", die eigentlich selbst wieder das Kriterium einer Kollision erfüllt (Ping-Pong oder auch "permanente Kollision" bei jeder Iteration). Dafür sollte deine Dicke größer sein als der maximale Fehler, den du erwartest. Wenn du es ganz genau haben möchtest, nimmst du die maximalen Werte, die deine Variablen annehmen können (in lokalen Koordinaten - siehe Faustregeln Punkt 2 - kann man dafür halbwegs sinnvolle Werte bestimmen), berechnest für diese die absoluten Fehler (s.o.) und summierst diese Fehler auf. Bedenke, dass dieser Fehler bei jeder Rundungsoperation auftreten kann, daher ist die Toleranz, die du bei deiner Vergleichsoperation benötigst, die Summe aller Fehler die durch die Rechenoperationen auf den am Vergleich beteiligten Variablen aufgetreten sein können. Es macht wohl am meisten Sinn sich einmal grob die Größenordnung auszurechnen und dann einfach eine Toleranz/Dicke zu wählen, die auf jeden Fall gross genug ist (statt den Fehler zu genau zu bestimmen - was man ohnehin jedesmal anpassen müsste, wenn man die Berechnung umstellt).

2. Vermeiden von visuellen Artefakten: Das ist das Kriterium das ich heranziehen würde, und so aus dem Bauch heraus würde ich behaupten, dass diese Toleranz auf jeden Fall deutlich größer ist, als diejenige, die für die Rundungsfehler benötigt wird (zwei Fliegen...). Unter visuellen Artefakten verstehe ich z.B. Z-Fighting beim Rendering wenn eine Fläche flach auf einer anderen liegt als untere Grenze (die Fläche liegt scheinbar "in" der anderen anstatt darauf) und ein für den Spieler wahrnehmbarer Abstand zwischen beiden Flächen (Fläche "schwebt" scheinbar über der anderen) als obere Grenze. Diese Werte kann man entweder experimentell bestimmen (schnell und einfach), oder auch berechnen: Fürs Z-Fighting kann man sich z.B. schlau machen wie mit der aktuellen Rendering-Konfiguration der Z-Test genau berechnet wird und dann eine maximale Entfernung von der "Kamera" wählen, ab der man tolerieren möchte, dass der Z-Test fälschlicherweise fehlschlägt. Daraus lässt sich eine untere Grenze für die "Dicke" berechnen. Für die obere Grenze kann man eine minimale Distanz zur "Kamera" festlegen, ab der man toleriert, dass zwei direkt aufeinander liegende Objekte mehr als einen Bildschirmpixel Abstand voneinander haben (wenn man es genau haben will, kann man das durch inverse Projektion von Bildschirmpixeln auf die Z-Ebene dieser minimalen Distanz bestimmen).

So, das waren jetzt eine menge Infos, ich hoffe sie helfen dir ein wenig weiter

Gruss,
Finnegan

P.S.: Vielleicht noch eine kurze Anmerkung zu dieser Art diskreter Kollisionserkennung, wie du sie machst: Diese kann man so machen, und etliche Spiele tun das auch, sie hat aber ein Problem, wenn z.B. die Geschwindigkeiten der Objekte oder die deltaTime sehr groß werden (lahmer Rechner, kurze Aussetzer weil z.B. das OS grad was wichtiges macht). Tunneling. Ein Objekt kann sich zwischen zwei Iterationen so weit bewegen, dass z.B. eine Kollision mit einem Block der zwischen den beiden Positionen liegt, nicht erkannt wird. Die Lösung hierfür nennt sich CCD (Continuous Collision Detection) und ist etwas komplizierter - wahrscheinlich ist das bei deinem jetzigen Stand der Dinge noch nichts, ich möchte es aber dennoch mal als Stichwort in den Raum geworfen haben, damit du weisst was da in richtung Kollisionserkennung noch alles so "geht" :D. Bei CCD wird die Kollisionserkennung nicht mit dem eigentlichen Objekt an einer diskreten Position gemacht, sondern mit dem Volumen, dass das Objekt "erzeugt", während es sich zwischen den zwei Iterationen durch den Raum bewegt hat.