Wie kann man zwei Menschen sich gegenseitig ausweichen lassen?

XMAMan

Hallo,

ich versuche ja momentan mein Leute-Projekt, bei dem man 2D-Mäßig von Oben Leute beim rumlaufen beobachten kann. Momentan können meine Leute ein Pfad auf der Karte finden und wenn sie Kollidiert sind, dann suchen sie ein neuen Pfad.

Hier erstmal der Stand, um zu verstehen was ich meine:

https://www.youtube.com/watch?v=t02BDYWlFNs&feature=youtu.be

Meine Frage: Habt ihr eine Idee, wie ich die Kollision vermeiden kann? Das sie also 1-2 M nach vorne schauen und dort schon gucken, ob da was ist und dann eine neue Route suchen.

Am Ende des Videos seht ihr, wie ich momentan eine Ausweichroute berechne. Ich erstelle einen Suchgraph, indem ich viele Punkte Kreisförmig um die Person erzeuge.

Die Sache ist, das ist relativ rechenaufwendig. Wenn ich das nur bei einer Kollision mache dann ist das ok. Wenn ich das aber für jeden einzelnen Pixel, den eine Figur läuft mache, dann ist das zu viel.

Ich bräuchte also eine Idee, wie ich eine Ausweichroute ohne ein so feines Gitter erzeugen könnte.

du hast ja 2d Koordinaten von allen Objekten, nehme ich an!?
Wenn es sich so verhält, wie in den letzten Sekunden im Video gezeigt, ist es einfach:
du weißt wohin sich deine Person 1 bewegt, und alle anderen Personen stehen.
D.h. du hast für Person 1 die Gleichung pos(t)=pos+tdirection.
Und alle anderen Personen sind Kreise mit Radius r und Mittelpunkt m, die Gleichung eines Kreises ist somit (p-m)(p-m)-r^2=0, d.h. alle Punkte p die diese Gleichung erfüllen liegen am Kreis.

Jetzt schneidest du einfach die Gerade und die Kreise (*), d.h. du schneidest jeweils pos(t) für die erste Person mit jeweils einem Kreis von einer Person x, und falls es eine Lösung für t gibt, so schneiden sich die beiden. Anhand der Größe von t weißt du außerdem, wann das passiert. Passiert das jetzt gleich, oder gar in der Vergangenheit (ignorieren), oder erst sehr sehr viel später (ignorieren).
Die Berechnung ist ziemlich "billig", und sollte kein Performance Problem darstellen.

(*) https://de.wikipedia.org/wiki/Schnittpunkt

achso und Ausweichroute wäre im Falle einer erkannten Kollision dann z.B. das Weiterdrehen von direction um einen zufälligen Winkel - wobei man das sicher auch intelligenter lösen könnte, aber ein zufälliger Winkel ist grundsätzlich sicher mal eine brauchbare Lösung, vor allem bei der geringen Dichte an "Verkehr".

XMAMan

Damit wäre das Problem, was passiert, wenn zwei Personen frontal (z.B. auf ein dünnen Weg) zulaufen gelößt/gemildert.

Was noch bleiben würde ist das Kreuzungsproblem. Person 1 geht auf eine Straßenkreuzung zu. Person 2 kommt aus einer Querstraße. Wenn beide nur das beachten, was sie sehen, wenn sie geradeaus schauen, dann kollidieren sie dann bei solchen Kreuzungssituationen.

Man könnte den Schnittpunkt von den beiden Lauflinien von beiden Personen nehmen und dann schauen, ob beide zu diesen Schnittpunkt dann ungefähr den gleichen Abstand haben. Wenn ja -> Kollisionswarnung.

Ich denke diese Aufgabe besteht aus zwei Unteraufgaben:
1. Kollisionsvorwarung
2. Ausweichmanöver erstellen

Deine Idee, die Person zum ausweichen einfach sich zufällig drehen zu lassen finde ich schonmal gut. So muss ich kein Pfad generieren sondern lediglich eine einzelne Zufallszahl. Das spart schonmal viel Rechenzeit.

Was noch bleiben würde ist das Kreuzungsproblem. Person 1 geht auf eine Straßenkreuzung zu. Person 2 kommt aus einer Querstraße. Wenn beide nur das beachten, was sie sehen, wenn sie geradeaus schauen, dann kollidieren sie dann bei solchen Kreuzungssituationen.

wenn sich beide bewegen dann kannst du natürlich pro Person eine Linie ziehen (Geradengleichung aufstellen), entlang sich diese bewegt. Dann schaust du, ob und wo sich die beiden Personen treffen. Du hast in beiden Fällen einen Zeitparameter (sagen wir t1 und t2), welcher angibt, wann der Schnittpunkt stattfindet.
Aus der Differenz abs(t1-t2) kannst du berechnen, wie knapp die beiden sich verfehlen.

XMAMan

Stehende Personen bekomme ich detektiert. Laufende noch nicht. Wenn ich den Schnittpunkt zwischen den beiden Lauflinien bilde und dann dann Abstand dazu, dann sagt der eine, ich habe den Abstand X und der andere, ich habe den Abstand -X. Ich verstehe momentan noch nciht, wo mein Fehler hier liegt:

//Es gibt zwei gefahren: Person die vor einen rumsteht und Person, die in einen reinläuft
        private bool IsPotentiellDanger(IMoveableCreature ownObject, IMoveableCreature otherObject)
        {
            if (ownObject == otherObject) return false;
            if (ownObject.LastMovedDirection == null || ownObject.LastMovedDistance == 0) return false;

            //Da steht jemand vor mir
            if (otherObject.MovingState == MovingState.Standing || otherObject.LastMovedDistance == 0)
            {
                Vektor2D v = Vektor2D.Projektion(otherObject.Position - ownObject.Position, ownObject.LastMovedDirection);
                Vektor2D v1 = otherObject.Position - (ownObject.Position + v);
                float v1Length = v1.Betrag();
                if (v1Length < GlobalSettings.PersonSize * 2)
                {
                    return true; //Person direkt vor einen
                }
            }

            //Da läuft jemand vor mir
            if (otherObject.MovingState == MovingState.Moving && otherObject.LastMovedDistance > 0 && otherObject.LastMovedDirection != null)
            {
                var p = TwoPointLine.GetIntersectionPoint(new TwoPointLine(ownObject.Position, ownObject.Position + ownObject.LastMovedDirection),
                                                          new TwoPointLine(otherObject.Position, otherObject.Position + otherObject.LastMovedDirection));

                if (p != null)
                {
                    Vektor2D v1 = p - ownObject.Position;
                    float v1Length = v1.Betrag();
                    if ((v1 / v1Length) * ownObject.LastMovedDirection < 0) v1Length = -v1Length;
                    float t1 = v1Length / ownObject.Speed;

                    Vektor2D v2 = p - otherObject.Position;
                    float v2Length = v2.Betrag();
                    if ((v2 / v2Length) * otherObject.LastMovedDirection < 0) v2Length = -v2Length;
                    float t2 = v2Length / otherObject.Speed;

                    float tDiff = Math.Abs(t1 - t2);
                    float maxtDiff = GlobalSettings.PersonSize * 2 / ownObject.Speed;

                    if (/*t1 > 0 && t2 > 0 &&*/ tDiff < maxtDiff)
                    {
                        return true;
                    }
                }
            }

            return false;
        }

schaut nach Vorzeichenfehler aus. Habs jetzt nicht im Code angeschaut, aber kurz am Papier gerechnet.

Du hast jeweils den Startpunkt von Person 1 und 2 mit den x y Koordinaten, z.B. für Person 1: $p_{1x}$ und $p_{1y}$ .
d ist die Richtung sowie die Geschwindigkeit, mit der sich die Personen bewegen.
Schließlich hab ich u und v als die Zeitparameter der Kollision verwendet, d.h. abs(u-v) gibt dir an, wie knnap die beiden sich verfehlen.

Das Gleichungssystem sieht wie folgt aus:
$p_{1x}+u \cdot d_{1x}=p_{2x}+v \cdot d_{2x}$
$p_{1y}+u \cdot d_{1y}=p_{2y}+v \cdot d_{2y}$

Löse es einfach nach u und v auf (händisch oder mit Taschenrechner/CAS/Internet) und tippe es in C# ab. Dann sollte es passen.

XMAMan

Ok, die Kollisionsvorerkennung klappt nun. Ich habe mir dafür diese Mammutfunktion geschrieben^^

//Den Schnittpunkt erhalte ich durch p1 + direcdtion1 * t1      oder p2 + direction2 * t2
        public static void GetDistanceToIntersectionPoint(Vektor2D p1, Vektor2D direction1, Vektor2D p2, Vektor2D direction2, out float t1, out float t2)
        {
            Vektor2D V = direction1;
            Vektor2D L = direction2;
            Vektor2D C = p2 - p1;

            t2 = (V.Y * C.X / V.X - C.Y) / (L.Y - L.X * V.Y / V.X);
            if (float.IsNaN(t2) || float.IsInfinity(t2))
            {
                t2 = (C.Y * V.X / V.Y - C.X) / (L.X + L.Y * V.X / V.Y);
            }

            t1 = (C.X * L.Y / L.X - C.Y) / (V.X * L.Y / L.X - V.Y);
            if (float.IsNaN(t1) || float.IsInfinity(t1))
            {
                t1 = (C.Y * L.X / L.Y - C.X) / (V.Y * L.X / L.Y - V.X);
            }
        }

Kommen wir nun zur zweiten Aufgabe. Das Ausweichmanöver. Meine Figuren folgen ja einen Pfad (Menge von Punkten, wo er dann Punkt für Punkt ansteuert)

Wenn ich nun ausweichen will, dann muss ich sozusagen das Pfadstück modifizieren, wo er gerade ist.

Ideen die mir da einfallen: Ein paar der Pfadpunkt zufällig verschieben.

Ein paar Pfadpunkte entfernen und neue an anderer Stelle einfügen.

Hauptproblem an diesen Ideen: Wie verhindere ich, dass ich die Figur vom Fußweg runter abseits der Straße runterreiße oder das er nicht auf einmal durch eine Hauswand laufen will?

XMAMan

Ok, ich habe dieses Kollisionsthema jetzt erstmal beiseite gelassen. Das ist einfach zu hart für mich. Stattdessen habe ich noch Autos hinzugefügt.

https://youtu.be/Q2DgQICpdhE

Ich habe das Projekt vor 3 Monaten gestartet, um zu prüfen, ob es eine gute Idee ist, wenn man Klassen nur über Interface sich kennen läßt. Meine Lektion: Die Regel ist gut, aber sobalt ich mehr als ein Interface von einer Klasse benutzen will, dann kann/sollte ich auch die Klasse lieber direkt nutzen.

Mein Straßen-Klasse hat z.B. ein Interface für die Anzeige, eins für die Wegesuche und eins, um eine zufällige Startposition für das Auto zu generieren. So lange ich nur ein Interface von dieser Straße nutze, ist es ok, nur dieses zu kennen. Wenn ich aber z.B. mit dem Kartenobjekt sowohl Wegesuche als auch Kollisionserkennung machen will, dann brauche ich entweder ein Interface, was von den beiden anderen Interfacen ableitet oder ich nutze die Karte direkt.

Kann mir jemand noch weitere Tipps geben, was ich in Zukunft an Design-Regeln bei Spielen beachten sollte? Bis jetzt hat mir das Buch 'Clean Code' am Meisten geholfen. Die Design-Patterns, die man so von Wikipedia kennt, sind mir zu allgemein. Ich brauche eher was für jeden Spieltyp, den man so hat.

Th69

Du kannst ja auch einfach ein kombiniertes Interface dann erstellen:

public interface IMap : IRouting, ICollisionDetecting
{
}

Und dieses dann benutzen (geht auch für mehr als 2 und sogar mit weiteren 'Ableitungen').
Das ist jedenfalls kein Grund, dann direkt die Klasse verwenden zu wollen.

Alternativ kannst du auch dynamisch testen, ob ein anderes Interface unterstützt wird:

public void Method(IRouting routing)
{
  // do something with routing
  // ...

  var coll = routing as ICollisionDetecting;
  if (coll != null)
  {
    coll.DoColliisonDetecting();
  }
}

XMAMan

So habe ichs ja auch gemacht aber der Bereitsteller dieser Funktionen(Interface) muss dann wissen, welche Interface alles zusammen verwendet werden sollen. Nicht der Verwender entscheidet dann, was zusammen gehört / was er zusammen braucht.

Außerdem ist mir noch ein zweites Problem aufgetreten, wofür ich bis jetzt keine Lösung habe aber Hilfe benötige:

Wenn ein ein zufälligen Punkt in ein Haus erzeugen will, gehe ich zur Karte und lasse mir ein IHouseSearch-Objekt(Steht für ein Haus) zurück geben, womit ich dann ein Zufallspunkt erzeugen kann.
Wenn ich ein Punkt, der vor einen Haus liegt erzeugen will, gehe ich zur Karte und sage, gib mir für das Haus 'X' den Parkpunkt. (IParkHouse ist dann ein Haus, was diesen Punkt erzeugt)

Wenn der Verwender nun also eine Liste aller Häuser haben will, womit er Zufallspunkte sowohl innerhalb des Hauses erzeugen kann, als auch Parkplatzpunke davor, wie macht er das dann?

Hat er dann bei sich ein Klasse die so aussieht?

class House : IHouseSearch, IParkHouse //Bereitsteller
{
}

//Verwender
class MyHouse
{
  IHouseSearch house1; -> Beide Propertys verweisen auf das gleiche Haus
  IParkHouse house2;
}

Ist das so richtig, oder muss auch hier die House-Klasse bereits sowas hier kennen?

IHouse : IHouseSearch, IParkHouse 
{}

Es klingt jetzt erstmal ähnlich. Aber diesmal soll dasIHouseSearch dann an das Kartenobjekt übergeben werden können. Da sage ich dann, gib mir ein Pfad von IHouseSearch 1 zu IHouseSearch 2. Die Interface arbeiten nicht nur für sich alleine sondern die Karte macht dann mit mehreren davon als INput was.

Ich weiß halt noch nicht so richtig, ob es so klug ist, wenn der Bereitsteller bereits für alle Interface-Kombinationen ein eigenes Zusammenfassungsinterface hat/kennt. Vielleicht mach ich mir auch zu viele Gedanken und diese Abhängkeit zwischen Bereitsteller und Verwender ist voll ok.

D