Verschieben Objekt zum nächsten leeren Raum auf einer Ebene

Question

überprüfen Sie den folgenden gif: https://i.gyazo.com/72998b8e2e3174193a6a2956de2ed008.gif

Ich mag der Zylinder sofort Lage zum nächsten leeren Raum auf der Ebene ändern, sobald ich auf dem Zylinder einen Würfel setzen. Die Würfel und der Zylinder sind mit Box Collidern verbunden.

Momentan bleibt der Zylinder stecken, wenn ich einen Würfel darauf lege, und ich muss in eine Richtung klicken, damit er durch die Würfel zu "schwimmen" beginnt.

Gibt es eine einfache Lösung oder muss ich eine Art Gitter mit leeren Spielobjekten erstellen, die ein Tag haben, das mir sagt, ob ein Objekt auf ihnen ist oder nicht?

Answer 1

Dies ist ein häufiges Problem in RTS-ähnlichen Videospielen, und ich löse es selbst. Dies erfordert einen breadth-first search Algorithmus, was bedeutet, dass Sie zuerst die nächsten Nachbarn überprüfen. Sie haben das Glück, dieses Problem nur in einer Grid-Umgebung lösen zu müssen.

Normalerweise erstellt ein Programmierer eine Warteschlange und fügt jeden Knoten (Leerzeichen) im gesamten Spiel dieser Warteschlange hinzu, bis ein leerer Bereich gefunden wird. Es wird mit z.B. die oben genannten, darunter und angrenzende Leerzeichen an den Startplatz und dann rekursiv ausziehen, die gleiche Funktion innerhalb von sich selbst aufrufen und die Warteschlange verwenden, um zu verfolgen, welche Leerzeichen noch überprüft werden müssen. Es muss auch eine Möglichkeit geben zu wissen, ob ein Leerzeichen bereits überprüft wurde und diese Leerzeichen vermeiden.

---

Eine andere Lösung, die ich bin zu begreifen wäre eine (konzeptionelle) Archimedean spiral vom Startpunkt zu erzeugen, und irgendwie jeden Raum entlang dieser Spirale zu überprüfen. Der schwierige Teil wäre, die richtige Spirale zu erzeugen und genau an den richtigen Punkten zu prüfen, um jeden Raum einmal zu treffen.

Hier ist meine quick-and-dirty-Lösung für die archimedische Spirale Ansatz in C++:

float x, z, max = 150.0f; 
vector<pair<float, float>> spiral; 

//Generate the spiral vector (run this code once and store the spiral). 
for (float n = 0.0f; n < max; n += (max + 1.0f - n) * 0.0001f) 
{ 
    x = cos(n) * n * 0.05f; 
    z = sin(n) * n * 0.05f; 

    //Change 1.0f to 0.5f for half-sized spaces. 
    //fmod is float modulus (remainder). 
    x = x - fmod(x, 1.0f); 
    z = z - fmod(z, 1.0f); 

    pair<float, float> currentPoint = make_pair(x, z); 

    //Make sure this pair isn't at (0.0f, 0.0f) and that it's not already in the spiral. 
    if ((x != 0.0f || z != 0.0f) && find(spiral.begin(), spiral.end(), currentPoint) == spiral.end()) 
    { 
     spiral.push_back(currentPoint); 
    } 
} 


//Loop through the results (run this code per usage of the spiral). 
for (unsigned int n = 0U; n < spiral.size(); ++n) 
{ 
    //Draw or test the spiral. 
} 

Es einen Vektor von einzigartigen Punkten erzeugt (float Paare), die um iterativ durchlaufen werden können, die es Ihnen erlaubt jeden Raum um den Startplatz herum in einer schönen, nach außen gewandten Spirale zu zeichnen oder zu testen. Mit Feldern der Größe 1,0f erzeugt es einen Kreis von 174 Testpunkten, und mit Feldern der Größe 0,5f erzeugt es einen Kreis von 676 Testpunkten. Sie müssen diese Spirale nur einmal generieren und anschließend für den Rest des Programms mehrfach speichern.

Anmerkung:

1. Diese Spirale Proben unterschiedlich, wie es wächst weiter und weiter von der Mitte (in der for-Schleife: n += (max + 1.0f - n) * 0.0001f).
2. Wenn Sie die falschen Nummern verwenden, können Sie diesen Code sehr leicht brechen oder eine Endlosschleife verursachen! Gebrauch auf eigene Gefahr.
3. Obwohl es speicherintensiver ist, ist es wahrscheinlich viel zeiteffizienter als die herkömmlichen warteschlangenbasierten Lösungen, da jedes Leerzeichen genau einmal durchlaufen wird.
4. Es ist jedoch keine 100% genaue Lösung des Problems, da es sich um eine Gitterspirale handelt; in einigen Fällen kann es die Diagonale über den seitlichen bevorzugen. Dies ist jedoch wahrscheinlich in den meisten Fällen vernachlässigbar.

Ich habe diese Lösung für ein Spiel verwendet, an dem ich gerade arbeite.More on that here. Hier sind einige Bilder (die orangefarbenen Linien in dem ersten für Illustration von mir in Paint gezogen werden, und das zweite Bild ist nur zu zeigen, was die Spirale aussieht, wenn erweitert):