Fast Voxel Traversal Algorithm

[Zespire]

Grüße stecke gerade seit einigen Stunden fest ohne vorwärts zu kommen bei dem versuch den Fast Voxel Travers Algorithm zu implementieren.

public bool RayHitWall(Vector3 startPosition, Vector3 endPosition,int[,] map)
{
	float angle = Quaternion.FromToRotation(Vector3.forward,endPosition - startPosition).eulerAngles.y;
	float distance = 0.0f;

	Vector2 direction = new Vector2(Mathf.Cos(angle * 0.01745329f),Mathf.Sin(angle * 0.01745329f));
	Vector2 currentPosition = new Vector2(startPosition.x,startPosition.z);
	Vector2 directionNormalized = new Vector2(direction.x > 0 ? 1 : -1,direction.y > 0 ? 1 : -1);
	Vector2 offset = Vector2.zero;
	Vector2Int targetTile = new Vector2Int(Mathf.CeilToInt(endPosition.x),Mathf.CeilToInt(endPosition.z));
	Vector2Int tilePosition = Vector2Int.zero;


	while(tilePosition.x != targetTile.x && tilePosition.y != targetTile.y)
	{
		tilePosition.x = Mathf.FloorToInt(currentPosition.x);
		tilePosition.y = Mathf.FloorToInt(currentPosition.y);

		if(!IsInsideBounds(tilePosition,map.GetLength(0),map.GetLength(1)) || map[tilePosition.x,tilePosition.y] == 1)
			return true;

		offset.x = ((float)tilePosition.x + directionNormalized.x - currentPosition.x) / direction.x;
		offset.y = ((float)tilePosition.y + directionNormalized.y - currentPosition.y) / direction.y;

		if(offset.x < offset.y)
			distance += offset.x + 0.0001f;
		else
			distance += offset.y + 0.0001f;

		currentPosition.x = startPosition.x + direction.x * distance;
		currentPosition.y = startPosition.y + direction.y * distance;
	}
	return false;
}

Jemand eine Idee was hier falsch läuft am liebsten wäre mir ja ein Hinwies und keine Lösung.

Quellen

http://theshoemaker.de/2016/02/ray-casting-in-2d-grids/
http://www.cse.yorku.ca/~amana/research/grid.pdf

 

[fhtagn]

Ein bisschen mehr Kontext wäre hilfreich. Was genau soll die Funktion berechnen?

Was im Code so auffällt:
- von außen kommen Vector3-Werte rein, intern wird nur Vector2 verwendet, Grund?
- direction kann man einfacher berechnen: endPosition - startPosition
- directionNormalized ist Quark. Um einen Vektor zu normalisieren, teilt man durch seine Länge. Vector2 hat wahrscheinlich eine Methode dafür.
- du rechnest viel mit Vektor-Komponenten. Richtige Vektorrechnung würde vieles vereinfachen.
- currentPosition Berechnung sieht falsch aus. Ausgehend von der aktuellen Position und dem aktuellen Tile muss geprüft werden, welches angrenzende Tile aus welcher Richtung als nächstes vom Strahl geschnitten wird. Der Schnittpunkt des Strahls und der Tile-Grenze (oben, unten, links, rechts) ergibt die neue currentPosition.

 

[Zespire]

Die Funktion soll einfach schauen ob der Strahl einen Knoten mit dem wert 1 passiert oder außerhalb der Karte landet.

Ist eine3d Umgebung aber die Wegfindung und die meiste Logik findet auf einem einfachen 2 dimensionalen Array statt.

Quaternion.FromToRotation() liefert auch bereits die Richtung entschlackt wird wen es läuft

Hast recht der Name ist falsch geht einfach darum die Richtung noch einmal als Ganzzahl zu haben.

Im Taschenrechner sieht das an sich ganz richtig aus habe mal 1 – 2 Bilder angefügt scheint prinzipiell zu funktionieren nur ignoriert er scheinbar Schnittpunkte entlang der Welt z Achse.


Genau so neigt er dazu gelegentlich knoten zu überspringen.


Grün = strahl von start nach ende.
Grau = punkt an dem der nächste knoten vermutet wird.
Code änderungen.

		if(offset.x < offset.y)
			distance += offset.x - 0.001f;// - anstatt +
		else
			distance += offset.y - 0.001f;// - anstatt +
		currentPosition.x = startPosition.x + direction.x * distance;
		currentPosition.y = startPosition.z + direction.y * distance; // z mit y vertauscht

 

[fhtagn]

Vielleicht hilft dir das hier weiter.

Gegeben sind folgende Variablen:

tile: (u, v)  // int
pos: (x, y)   // double
dir: (dx, dy) // double, am besten Einheitsvektor

Idee ist folgende Gleichung. Wie oft muss man die Richtung zur Position addieren, um zu einem bestimmten Tile zu kommen:

(x,y) + t*(dx, dy) = (u', v')

Also folgende vier Gleichungen für die vier möglichen angrenzenden Tiles nach t auflösen:

x + t*dx = u+1
x + t*dx = u-1
y + t*dy = v+1
y + t*dy = v-1

Zwei Werte sind negativ, also rückwärts gerichtet. Der kleinere der beiden positiven Werte bestimmt das nächste angrenzende Tile und die neue Position.

 

[Zespire]

Danke werde mich spätestens Montag nochmal ran setzen.

 

[Zespire]

Läuft aber leider zu gut.



Er schneidet Ecken perfekt was zu clipping Fehlern führen würde.





Also müsste ich 2 strahlen nehmen um eine gewisse dicke zu simulieren oder eine andere Lösung suchen wobei ich es jetzt erst einmal so lasse...

 

[The Ripper]

Oder du machst die Objekte größer

 

[Zespire]

Auch wen ein Strahl keine Größe hat und es keine Objekte gibt war die Idee an sich nicht verkehrt.

	float widthOffsetLeftX = -directionZ * width, widthOffsetLeftZ = directionX * width;
		float widthOffsetRightX = directionZ * width, widthOffsetRightZ = -directionX * width;

Damit kann man die Position Links und Rechts relativ zur Richtung des Strahls bestimmen und wen man jetzt jedes mal zusätzlich die currentPosition + widthOffsetLeft und currentPosition + widthOffsetRight prüft scheint es ganz gut zu funktionieren.



Und konnte es doch nicht so lassen