Du bist nicht angemeldet.

Werbeanzeige

DeKugelschieber

Community-Fossil

  • »DeKugelschieber« ist der Autor dieses Themas

Beiträge: 2 668

Wohnort: Rheda-Wiedenbrück

Beruf: Software-Entwickler

  • Private Nachricht senden

1

14.02.2011, 22:03

Kollision mit Boden bei Minecraft artigem Spiel

Überschrift beschreibts ja schon ganz gut, wie setzt man die Kollision mit dem Boden bei einem Spiel wie Minecraft um? Dabei hab ich jetzt nur die Vertex Daten der Blöcke, mehr nicht. Dabei dachte ich das ich zusätzlich noch ein Array mit den Höhendaten anlegen könnte und so an der Position des Spielers auslesen kann wie hoch das Terrain ist...

Hier mal ein Bild:

[Gelöscht]

Das Array würde ja auch nicht viel Speicher verbrauchen (z.B. 2 Dimensionen array[x][z] = y).

MfG

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »DeKugelschieber« (21.02.2011, 11:10)


Schorsch

Supermoderator

Beiträge: 5 188

Wohnort: Wickede

Beruf: Student

  • Private Nachricht senden

2

14.02.2011, 22:48

Du könntest doch einfach über nen Ray testen ob ne Kollision vorhanden ist. Wie auf nem Model auch. Wenn du deine Blöcke in irgendwelche klugen Strukturen einteilst kannste da bestimmt auch an Performance was raus holen. Ansonsten ist der Ansatz mit dem Array aber garnicht so schlecht. Ist ja dann wie ne Tilemap in 2D und du kannst zusätzlich auch die Kollision für die Bewegung durch die Höhenunterschiede bewerkstelligen.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

3

14.02.2011, 23:23

Na, aber wenn es Höhlen gibt, reich ein 2D Array mit Höhenangabe nicht.
Rechne mal durch, wie schlimm ein 3D Array wäre. Die Kollision dabei wäre auf jeden Fall superschnell (konstante Suchzeit) und es ist sehr simpel zu implementieren.

Evtl. kannst du auch ne Art Octree bauen, indem du große Luft oder große Erdblöcke zu einem zusammenfasst und dafür dann keine n^3 Elemente mit dem selben Wert speichern musst.
Lieber dumm fragen, als dumm bleiben!

Fred

Supermoderator

Beiträge: 2 132

Beruf: Softwareentwickler

  • Private Nachricht senden

4

14.02.2011, 23:33

Du könntest auch die Welt in einzelne Würfelfelder unterteilen. So ist die Welt von Minecraft ja ohnehin aufgebaut. Dann könntest du einfach prüfen, ob ein bestimmtes Feld frei ist oder nicht.

DeKugelschieber

Community-Fossil

  • »DeKugelschieber« ist der Autor dieses Themas

Beiträge: 2 668

Wohnort: Rheda-Wiedenbrück

Beruf: Software-Entwickler

  • Private Nachricht senden

5

15.02.2011, 17:09

Zitat

Rechne mal durch, wie schlimm ein 3D Array wäre.


Jeder Block mit 3 Koordinaten/Floats: 32x3xAnzahl_der_Blöcke

Beispiel: 5 Mio Blöcke = 57.22046 MB, allerdings brauch ich denn ein 3D Array? man kann ja für "Luft" einfach eine Zahl auserhalb der maximalen Kartenhöhe angeben (z.B. 101, oder so).

Zitat

Du könntest doch einfach über nen Ray testen ob ne Kollision vorhanden ist.


Was ist ein Ray?

Zitat

Ist ja dann wie ne Tilemap in 2D und du kannst zusätzlich auch die Kollision für die Bewegung durch die Höhenunterschiede bewerkstelligen.


Hab ich mir auch gedacht :) Und hätte dann (wieder bei 5 Mio Blöcke, allerdings mit int [reicht ja]): 28.61023 MB, perfekt! Allerdings speicher ich dann die Vertex Daten immer noch im VRAM mit 12x3 Floats.

Zitat

Du könntest auch die Welt in einzelne Würfelfelder unterteilen. So ist die Welt von Minecraft ja ohnehin aufgebaut. Dann könntest du einfach prüfen, ob ein bestimmtes Feld frei ist oder nicht.


Versteh ich nicht so ganz, guck mal aufs Bild.

6

15.02.2011, 22:00

Jeder Block mit 3 Koordinaten/Floats: 32x3xAnzahl_der_Blöcke

Nein die Positionsdaten ergeben sich aus der Position im Array.

Ist wohl nicht ganz klar geworden, was ich meine, deshalb nochmal detaillierter:

Du hast eine 64*64 Felder große Welt, die sagen wir 16 Felder hoch ist. Jetzt hast du ein 3D Array [64][64][32] und speicherst jeweils, was für ein Block sich dort befindet. Z.B. "Luft", "Erde", "Gras" usw.
Wenn du jetzt Kollision testen willst, musst du nur z.B. die Spielerposition in Arraykoordinaten umrechnen. Natürlich wird das ganze komplizierter, wenn der Spieler kein Punkt sondern selber ein Viereck oder eine Kugel ist, aber trotzdem kriegst du mit einfacher modulo Rechnung direkt die Arrayindexe, die du testen musst.

Das mit den größeren Wurfeln. Du reduzierst z.B. die Auflösung um 8, hast also nur noch ein Array mit [8][8][2]. In jedem Element steht jetzt, ob dort alle Felder gleich sind oder unterschiedlich, wenn sie unterschiedlich sind, speicherst du wieder ein kleineres Array, wo dann die einzelnen Werte stehen.
Lieber dumm fragen, als dumm bleiben!

Fred

Supermoderator

Beiträge: 2 132

Beruf: Softwareentwickler

  • Private Nachricht senden

7

15.02.2011, 22:23

Ja ich sehe aufs Bild, aber das ändert nichts an meinem Vorschlag ;)
Mein Vorschlag ließe sich durchaus mit einem 3D-Array vergleichen, in dem sich alle Würfel befinden. Nur dass ich eben nur die relevanten Blöcke in dieses Array packen würde. Also ein leeres Feld braucht man nicht auf Kollision prüfen und 256 leere Felder auch nicht 1734 Felder, die leer sind brauchen auch keine Kollision. Ich würde also im Prinzip einen std::vector anlegen, in dem ich die Feld-Positionen speichere, auf denen sich Blöcke befinden. Dafür würde ich ggf. eine extra struct für die Würfel erstellen, die bspw. alle Positions-Daten eines Feldes, sowie einen Zeiger auf das Blockobjekt enthält, der sich auf dem Feld befindet.
Dann kommen alle diese erstellten Felder in einen std::vector und du kannst bequem die Kollision mit den einzelnen Einträgen dieses vectors prüfen.

NachoMan

Community-Fossil

Beiträge: 3 909

Wohnort: Berlin

Beruf: (Nachhilfe)Lehrer (Mathematik, C++, Java, C#)

  • Private Nachricht senden

8

15.02.2011, 22:51

wenn man speicher sparen will reicht doch eigentlich ein array aus 1byte integern. damit kannst du 256 verschiedene steine darstellen. die position im spiel kann man aus der position im array errechnen(und anders herum) und das verhalten und aussehen, also die blockart, über den integer speichern. mehr brauch man meiner meinung nach nicht. dafür benötigt man zwar ein oder mehrere hässliches switch/case konstrukte, dafür benötigt man nur einen zwölftel(2*4byte für floatposition und 4 für einen 32bit zeiger) des speichers von freds vorschlag. wenn ich das richtig verstanden habe.
lohnt sich vorallem für sehr große maps wie die von minecraft.^^
"Der erste Trunk aus dem Becher der Erkenntnis macht einem zum Atheist, doch auf dem Grund des Bechers wartet Gott." - Werner Heisenberg
Biete Privatunterricht in Berlin und Online.
Kommt jemand mit Nach oMan?

Schorsch

Supermoderator

Beiträge: 5 188

Wohnort: Wickede

Beruf: Student

  • Private Nachricht senden

9

16.02.2011, 11:04

Naja 2D abspeichern könntest du es solange du dich nur Oberhalb der Welt befindest und keine Lücken vorhanden sind. Dann würdest du halt nur die Höhenwerte der Obersten Flächen speichern für die Kollision. War das nicht auch die Frage? Der Rest geht ja dann eher um allgemeine Speicherung der Map;) Naja gut wie du die Map speicherst ist ja erstmal egal. Kommt ja auch drauf an ob du nun nen Minecraftclon erstellen willst oder was du vorhast bzw. wie der Spieler mit dieser Welt interagieren kann und wie dynamisch die Welt ist. Die Kollision musst du aber nicht zwangsweise über eine Map in Arrayform lösen. Ein Ray ist ein Strahl. Und man kann berechnen ob ein Strahl eine Ebene schneidet. Ein Model besteht aus vielen Dreiecken, welche ja Teile einer Ebene sind. Du kannst darüber also checken, ob dein Strahl die Menge der Dreiecke deines Models schneidet. Wenn das der Fall ist, guckst du an welcher Stelle vom Strahl das passiert ist. In deinem Beispiel könnte das so Ablaufen:
Dein Spieler ist eine Kugel. Du willst die Kollision nach unten Checken. Du feuerst einen Ray aus dem Mittelpunkt der Kugel senkrecht nach unten(feuern im Sinne von du erstellst ihn ;) ). Du berechnest ob es zu einem Schnittpunkt kommt. du berechnest die Koordinaten des Schnittpunkts. Jetzt hast du zwei Vektoren v1 und v2. v1 Ist der Startpunkt deines Rays, also der Mittelpunkt deines Spielers/der Kugel. v2 Ist der Schnittpunkt zwischen Ray und Model. Du berechnest den Abstand der beiden Vektoren. Wenn der kleiner als der Radius deiner Kugel ist dann handelt es sich wohl um eine Kollision. Du Testest quasi immer einen Punkt auf Kollision. Um die Kollision genauer zu machen kannst du natürlich mehrere Rays an verschiedenen Positionen feuern. Rays kannst du nicht nur nach unten zeigen lassen sondern in alle Richtungen. Von daher kannst du damit auch deine Kollision auf der horizontalen Ebene berechnen. Rays werden normal auch von Engines oder Frameworks unterstützt, sodass du das nicht alles selbst programmieren müsstest. Dann könntest du zum Beispiel sagen erstelle nen Ray an Position(x,y) mit Richtung (x,y). Berechne einen Schnittpunkt mit Model1. Und hättest dann schon den Schnittpunkt. einige Frameworks liefern auch noch mehr informationen. Würde ich mich einfach informieren was das Framework/die Engine kann die du nutzt. Aber das ist nur eine Lösung;)
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

10

16.02.2011, 13:20

Ja, und da es hier nur um Blöcke und nicht um beliebige Geometrie geht, dürfte es ohne Strahl/Ebene Test um einiges einfacher und schneller sein.
Bei wenigen Höhlen kann man natürlich auch ein 2D Array nehmen und statt Höhendaten eine Liste speichern, in der steht von wo bis wo vertikal gesehen Boden/Luft ist. Solange man wenig Höhlen hat ist die Liste meist sehr kurz, und man spart wieder Speicher.
Lieber dumm fragen, als dumm bleiben!

Werbeanzeige