Fragen zum A*-Algorithmus



  • Hallo,
    möchte ein relativ simples 2D-RTS programmieren.

    Naja habe festgestellt, dass ich das Wörtchen "simpel" wohl wieder streichen darf.
    Allein die Pfadfindung mit dem A*-Algorithmus dürfte relativ aufwendig werden.

    Habe mich entschieden meine Levels aus Sechsecken zusammenzubauen. Sechsecke für Wasser, Land, Gebirge usw. Wobei Wasser und Gebirge hier Hindernisse darstellen würden.
    Also führe ich die A*-Suche auch auf eben diesen Sechsecken durch. Meine Knoten würde ich in der Mitte der Sechsecke platzieren.

    Nun zu meiner Frage:
    Nehmen wir an ich habe einen kürzesten Pfad gefunden und möchte eine ganze Truppe von Einheiten entlang dieses Pfades zum Ziel schicken. Wie bewegen diese sich entlang des Pfades, ohne dass sie sich in die Quere kommen ?

    Eine Einheit wäre ja kein Problem. Einfach den Pfad ablaufen oder ?

    Danke


  • Mod

    Blue5teel schrieb:

    Hallo,
    möchte ein relativ simples 2D-RTS programmieren.

    Naja habe festgestellt, dass ich das Wörtchen "simpel" wohl wieder streichen darf.

    ja weil das, was du sagst, dass du vorhast im kontrast zu dem stehst was du wirklich vor hast:

    Pfadfindung mit dem A*
    Levels aus Sechsecken

    also. ein simples 2d rts
    - quadratische flaechen
    - wegfindung statisch vorberechnen, (fast) egal wie langsam das ist

    wenn eine gruppe von einheiten einen 'weg' befehl bekommt. laufen alle einfach in die richtung der 'leiteinheit'. esseiden sie fallen ausserhalb eines bestimmten radius (weil sie z.b. an einem hinderniss ankommen), dann suchen sie sich selbst den weg.

    ansonsten hast du das problem dass alle im entenschritt zum ziel laufen und das ist weniger der sinn der sache, denk ich mir. (ist theoretisch prefekt, spieltechnisch seltsam).

    zudem sollten die einheiten nicht alle einen winzigen punkt als richtig ansehen, sondern eine flaeche, sodass ein paar 'lead' einheiten ein paar wege laufen.



  • Im Prinzip kommt es auf die Größe des Spielfelds an wie variabel die einzelnen Einheiten sich bewegen sollen.
    Aber am einfachsten ist es du packst sie in ein Raster - also einen fixen Abstand zu einander (in alle Richtungen) - und verwendest beim A* direkt die Abstände zu den Hindernissen mit der Erweiterung um die Breite des Rasters.
    Sollte eine Einheit trotzdem einmal nicht weiterkommen berechnest du für sie den Weg einfach erneut.

    Wenn du die Einheiten über ein großes Gebiet verschickst, solltest du das ganze Spielfeld in größeren Kacheln, Quadraten, Whatever betrachten.
    Beim Zielgebiet kannst du (Falls Formation gewünscht) einfach das Raster stehen lassen.
    Falls du sie irgendwie angeordnet haben willst, verwende einfach zufällig ausgewählte Positionen (In Ergänzung zum Raster können dann auch keine zwei Einheiten an der selben Stelle stehen)



  • Danke für eure Anmerkungen.

    Habe noch nen interessanten Artikel bzgl. Gruppen-Movement gefunden. Werde ich mir mal heute Abend anschauen:

    http://www.gamasutra.com/features/19990129/implementing_01.htm


Log in to reply