Pathfinding mit A-Stern - Let's GameDev

แชร์
ฝัง
  • เผยแพร่เมื่อ 3 ม.ค. 2025

ความคิดเห็น •

  • @Kleinernervenkeks
    @Kleinernervenkeks 11 ปีที่แล้ว

    ich mags echt sehr wie du einen so direkt ansprcihst. du siehst mich als deinen einzigen zuschauer. das is wunderbar. tom vergiss die andern und lass uns für immer glücklich werden

  • @TunaAlert
    @TunaAlert 8 ปีที่แล้ว +3

    ich hab den algorithmus nicht mit kacheln, sondern mit einem navigation mesh ausprobiert. das war wesentlich einfacher als was ich da vorher hatte...
    Danke, Tom.

  • @CppProgrammierer
    @CppProgrammierer 11 ปีที่แล้ว

    Also, ich muss mal sagen best Programmierer denn ich bis jetzt gesehen habe, Daumen hoch!!!

  • @LetsGameDev
    @LetsGameDev  11 ปีที่แล้ว

    aber du bist doch mein lieblingsbesserwisser ;P die entfernungsschätzung ist sehr einfach in diesem fall. die differenz der x koordinaten plus die differenz der y koordinaten

  • @Flehwah
    @Flehwah 11 ปีที่แล้ว

    Das hat mich überzeugt. Ich werde noch Heute damit anfangen!

  • @CppProgrammierer
    @CppProgrammierer 11 ปีที่แล้ว

    Spitze Tom, es scheint zu gehen, danke nochmal

  • @ScriptStudios
    @ScriptStudios 11 ปีที่แล้ว

    Video angeschaut → Beschreibung gelesen → Will dich noch öfter als einmal abonnieren :D Sehr schönes Tut. Ich habe mir vorher den Wiki Eintrag durchgelesen und nur Bahnhof verstanden(bzw. nur teilweise verstanden). Dank dir verstehe ich auch nun, warum der den Optimalen Weg findet und nicht den kürzesten^^.

  • @1234beta1234
    @1234beta1234 11 ปีที่แล้ว

    Danke, gut erklärt Tom !
    Ich dachte erst da kommt was in Richtung Pledge-Alg., der das Ziel sucht, aber so etwas, das den schnellsten weg herrausfindet ist auch cool ! Wie sieht es bei dem so mit der effektivität aus ? :)

  • @Rennteufel
    @Rennteufel 11 ปีที่แล้ว

    Ich bedanke mich für all deine Mühe :)

  • @CppProgrammierer
    @CppProgrammierer 11 ปีที่แล้ว

    Sehr gut erklärt,mit dem ersten Schritt zur KI...

  • @ralph_meier
    @ralph_meier 11 ปีที่แล้ว

    Das beste an dem Algorithmus ist ja, dass er schon vor über 2000 Jahren funktioniert hat. *g*
    "Wir sind dem Stern gefolgt" - "Sternhagelvoll seid ihr!"

  • @KemirenDesigns
    @KemirenDesigns 11 ปีที่แล้ว

    Stimmt schon, man lässt die Heuristik (also das Schätzen) weg, aber man kann bei Dijkstra entweder single-pair shortest path oder single-source shortest path machen. D.h. entweder man untersucht nur solange, bis der Ziel-Knoten gefunden wurde oder so lange bis alle Knoten in der Closed-List sind. Kann ganz praktisch sein, wenn zum Beispiel in nem Strategiespiel ne Einheit das nächste Ressourcenfeld finden soll, also gar kein konkretes Ziel vorhanden ist.

  • @ba03030
    @ba03030 11 ปีที่แล้ว +1

    Sag mal, wie weit biste eigentlich mit Hearteater?:)

  • @ChristianA283
    @ChristianA283 9 ปีที่แล้ว

    Meeeega gut erklärt. Dank dir dafür.

  • @TheLPMovie
    @TheLPMovie 11 ปีที่แล้ว

    Wieder super informativ gestaltet (:

  • @pfbjjz
    @pfbjjz 11 ปีที่แล้ว

    jap, hab grad das andere Video gesehen, dann ist mir das auch klar geworden. Viel Erfolg bei der Spieleschmiede wo du anfängst ;)

  • @georgmasuhr306
    @georgmasuhr306 8 ปีที่แล้ว

    Super Video! Hat mir echt geholfen den A*Algorithmus zu
    verstehen. Kam heute in der Klausur vor. :)

  • @pfbjjz
    @pfbjjz 11 ปีที่แล้ว

    hast du die nummerierung deies LetsGameDevs abgeschafft, oder gehört dieses Video (und das Conan Game of Life) nicht in die Reihe? verwirrend :S

  • @ralph_meier
    @ralph_meier 11 ปีที่แล้ว

    Macht es dann Sinn, dem Pathfinding einen eigenen Thread zuzuordnen, der sich nur damit beschäftigt? Oder denke ich falsch und sollte das Pathfinding immer bei einer Positionsänderung der Spielfigur auslösen?

  • @Climuff
    @Climuff 11 ปีที่แล้ว

    hmm also ich habs mir jetzt 2 mal angeschaut und nicht verstanden, wie berechnest du denn den ungefähren Weg bis zum Ziel wenn es keine Hindernisse gäbe und was für Positionen werden denn durchprobiert? Alle die in der open List stehen? Wenn man eine Sache in die closed List schreibt, könnte es nicht sein dass man den Punkt in einem anderen Weg nochmal brauchen könnte aber dann nicht mehr zur verfügung hat? Ich hab einfach nix kapiert, bin wohl zu blöd dazu^^

  • @CppProgrammierer
    @CppProgrammierer 11 ปีที่แล้ว

    Mal ne Frage...Ich arbeite auch zurzeit an einem Spiel(Minecraft),jetzt will ich die KI zu denn einzelnen Figuren herstellen,aber jezt weiss ich nicht den Code dafür das der Crepper den besten Weg zu mir geht, aber er darf auch über die Blöcke springen.... Wäre schön wenn wer eine Antwort hätte, wenn nicht dann nicht so schlimm...

  • @LetsGameDev
    @LetsGameDev  11 ปีที่แล้ว +1

    sehr gut^^

  • @hummelwalker
    @hummelwalker 11 ปีที่แล้ว

    Wieder mal ein echt gelungenes und sehr unterhaltsames Video, Tom. Thumb up :)

  • @ManuProduktions
    @ManuProduktions 11 ปีที่แล้ว

    Tolles Video und viel gelernt. Nur dein Programm läuft auf meinem PC ein bisschen zu schnell um es visuell nachzuempfinden, aber macht nichts. Einfach sleep reinballern und gut ist.

  • @CppProgrammierer
    @CppProgrammierer 11 ปีที่แล้ว

    Kannst du eigentlich auch Netzwerk Programmierung(Server, Socket, Client)?

  • @LetsGameDev
    @LetsGameDev  11 ปีที่แล้ว

    du kannst doch einen individuellen takt nehmen. bzw mache es wie alle großen erfinder: tüftle rum ;P

  • @LetsGameDev
    @LetsGameDev  11 ปีที่แล้ว

    schön dir mal was beigebracht zu haben XD

  • @JoshuaBehrens
    @JoshuaBehrens 11 ปีที่แล้ว

    Danke, MeatCake *hust* Tom :D, für die Erklärung ;) Ich vergleich mal meine Implementierung mit deiner. Nette Darstellung übrigends.

  • @Kreedzfreak
    @Kreedzfreak 11 ปีที่แล้ว

    Fachliteratur zu Algorithmen und Datenstrukturen gibt es haufenweise, sehr empfehlenswert. ;)

  • @LetsGameDev
    @LetsGameDev  11 ปีที่แล้ว

    also wenn sich die welt ändert, würde ich den schon neu berechnen (kommt halt darauf an wie schau die ki sein soll) an sich werden solche pathfinding sachen nur selten genutzt. zum beispiel einmal die sekunde aber nie jeden frame

  • @julschge
    @julschge 11 ปีที่แล้ว

    Danke für deine Erklärung, hatte so eben die Erleuchtung, was den A*-Algorithmus angeht ! :D

  • @AxelWerner
    @AxelWerner 11 ปีที่แล้ว

    bin noch immer programmier noob. um so mehr ich mich allerdings damit beschäftige erkenne ich dass es für viele probleme bereits sehr clevere algorythmen gibt. da man das rad ja nicht neu erfinden will macht es sinn diese zu verwenden. mein problem dabei ist meist einen solchen ausfindig zu machen. irgend welche tips/empfehlungen für nicht-akademiker?

  • @GralsPlayer
    @GralsPlayer 11 ปีที่แล้ว

    Yeah ein Video!!

  • @nyasaki_at
    @nyasaki_at 11 ปีที่แล้ว

    Hast du auch ne Facebook Seite?

  • @MrDivad006
    @MrDivad006 9 ปีที่แล้ว

    Sympathisches video! :)

  • @LetsGameDev
    @LetsGameDev  11 ปีที่แล้ว

    kommt darauf an wie doll lange das dauert.. stellt sich heraus, dass es länger dauert als ein frame so würde ich einen neuen thread nutzen

  • @LetsGameDev
    @LetsGameDev  11 ปีที่แล้ว

    da ich denke, das es eine freie bewegung gibt, nimm doch einfach den direktesten weg^^ bzw. nimm die blockmittelpunkte als fixpunkte, dann geht das genau wie hier im video nur mit allen 8 nachbarfeldern

  • @schuwi4
    @schuwi4 11 ปีที่แล้ว

    Ahhhja hab ich jetzt alles verstanden. Aber eine Frage hab ich noch: Wie funktioniert dieser A* Algorithmus? xD

  • @JoshuaBehrens
    @JoshuaBehrens 11 ปีที่แล้ว

    Viel Spaß ;)

  • @SuperIgill
    @SuperIgill 11 ปีที่แล้ว

    Gibts da nen unterschied zum Dijkstra-Algorithmus ?? :D

  • @nachoman1905
    @nachoman1905 10 ปีที่แล้ว

    Super Video.
    Wohnst du auch in Berlin oder bist du nur hier aufgewachsen?

  • @svens3722
    @svens3722 5 ปีที่แล้ว

    1:59 hat das einen grund, dass du die y achse von unten hochzählst ? normal das ist dies doch umgekehrt? Danke für dein Tutorial und den Code. Das macht das lernen um vieles einfacher x).

    • @LetsGameDev
      @LetsGameDev  5 ปีที่แล้ว

      Nein das hat keinen Grund. Ob y+ nach oben oder unten zeigt ist ja immer vom erfinde definiert so lange man innerhalb eines Systems konsistent bleibt, sollte es da auch keine Probleme geben^^

    • @svens3722
      @svens3722 5 ปีที่แล้ว

      @@LetsGameDev Oh Hi Tom. Danke für die schnelle Befriedigung meiner Anfrage.
      Okay alles klar, ich habe nur ca. 10 Minuten damit verbracht wie die Koordinaten zustande kommen, da ich mir die Koordinaten ausgehend von Oben Links angewöhnt habe. In deinem Code machst du es aber genauso. Außer ich bin jetzt komplett durch den wind. Das Ziel ist bei Standard ja bei x25 y25. Naja egal. Ich gucke mir dein Video jetzt noch 17 mal an, dann sollte ich den A Star auf mein tolles Spiel übertragen können x). Danke noch einmal für deine Mühe. Ach dank deinem Code habe ich auch endlich den Sinn von Rekursion verstanden. Die benutzt du doch oder xD? Gruss.

  • @aser8711
    @aser8711 11 ปีที่แล้ว

    du bist 10x witziger als die meisten comedy channels......lol

  • @LetsGameDev
    @LetsGameDev  11 ปีที่แล้ว

    hm ich kann das wort zutzen (und nutzen) nicht finden.

  • @LetsGameDev
    @LetsGameDev  11 ปีที่แล้ว

    Ja ich habe die Nummerierung abgeschafft, weils ja gar keine richtige reihenfolge gibt wenn ich so losgeöste sachen mache.

  • @TNGOMinecraft
    @TNGOMinecraft 11 ปีที่แล้ว

    Kannst du mir helfen Tom?
    Ich habe versucht den A-Stern Algorithmus bei mir zu implementieren. Bei größeren Strecken, fängt er jedoch erstmal schön an zu laggen. Jetzt hab ich versucht Heaps zu benutzen, so wie du es in deiner Datei meintest, jetzt laggt es noch mehr. Was kann ich dagegen tun?

    • @crazygamezockerXD
      @crazygamezockerXD 8 ปีที่แล้ว

      man könnte den Algorithmus in einem extra Thread laufen lassen

  • @AceAcid666
    @AceAcid666 11 ปีที่แล้ว

    im nächsten video sag bitte: "hi ich bin tom und ich programmiere immernoch ein spiel" XD

  • @gerritweiermann79
    @gerritweiermann79 9 ปีที่แล้ว +1

    Kannst du auch ein Algorithmus für Jump and Run erklären?

    • @LetsGameDev
      @LetsGameDev  9 ปีที่แล้ว

      +Husi 012 Ich habe auch ein Video über das Springen in Videospielen geamcht.

    • @gerritweiermann79
      @gerritweiermann79 9 ปีที่แล้ว

      Habs nicht gefunden...

    • @LetsGameDev
      @LetsGameDev  9 ปีที่แล้ว

      +Husi 012 Dann hast du nicht gesucht. Gehe auf meinen Kanal und nutze die suche, wenn du dort "springen" eingibst kommt das video direkt.

    • @gerritweiermann79
      @gerritweiermann79 9 ปีที่แล้ว

      Achso ich hatte irgendwas auf den Augen.
      Aber ich meinte einen Algorithmus für Gegner die auf einen zu rennen. Ich Habs schon gut geschafft das der Gegner auf eine einfache platform kommt und nicht von unten gegen springt weil der Gegner oben drüber steht. Wenn es aber komplexer wird dann schafft der das nicht.
      Gibt es dafür einen Algorithmus?

    • @LetsGameDev
      @LetsGameDev  9 ปีที่แล้ว

      das klingt eher nach kollisionsabfrage und auch nach ki. un din sachen ki bin ich nicht so bewandert

  • @ralph_meier
    @ralph_meier 11 ปีที่แล้ว

    Diskette???

  • @hanspeter2210
    @hanspeter2210 11 ปีที่แล้ว

    immer diese gierigen Algorithmen...
    Habe ich das jetzt richtig verstanden, am ende sind wir, wenn entfernung aller grünen Punkte vom start aus + idealer weg zum ziel ohne hindernisse größer sind als unser Zielknoten?
    Kannst du villeicht auch noch kurz was sagen, wie es laufzeit mäßig mit dem a Stern im verhältnis zum dijkstra aussieht? ist der der a Stern effizienter/schneller?

    • @Serij92
      @Serij92 11 ปีที่แล้ว

      Der Dijkstra Algorithmus kann wenn man will, mal komplett durchlaufen lassen, um dann den kürzesten Weg zu jedem Knoten zu finden. Der Dijkstra verbreitet sich kreisförmig und der A* richtet sich immer mehr in Richtung des Ziels. Weil er eine Heuristik benutzt z.B. Luftlinie, oder auch wie im Video geschätzte Kosten, kann man schätzen in welche Richtung man sich bewegen muss. Laut meinen Messungen ist der A* (auf jeden Fall bei Größeren Karten, wie Karlifornien) 70 bis 90% (+/-) schneller.

  • @LetsGameDev
    @LetsGameDev  11 ปีที่แล้ว

    Bitteschön^^

  • @LetsGameDev
    @LetsGameDev  11 ปีที่แล้ว +9

    ficken, ganz viel ficken!!!!

  • @omniskop
    @omniskop 11 ปีที่แล้ว

    Alles SEHR gut erklärt! Doch das dann mal umzusetzen ist dann doch komplizierter als es kling.

  • @unterweltgeist
    @unterweltgeist 7 ปีที่แล้ว

    Was ist eigentlich, wenn das Ziel in einem abgesperrten Bereich ist? Muss der Algorithmus dann alle 10k+ Schleifendurchläufe durch laufen, um zu merken das es da nicht rein geht? Bei einem Spielfeld von 240x240 sind das schon ~60k Felder, was dann die Open- und Close-Liste auf diese Größe aufbläht. Kann man das dann nicht irgendwie verkürzen?

    • @bastercall6586
      @bastercall6586 7 ปีที่แล้ว

      Nein, das ist ja auch Teil des Witzes. Der Algorhymtus findet die optimalste Lösung. Wenn es keine Lösung gibt, wird er auch nichts finden, und dann wird es vom Aufwand her teuer. Normalerweise wendest du den Algorhytmus auch nur auf Probleme an, die Lösbar sind. Das ist auch der zweite Punkt zu diesem Algoryhtmus: Er funtkioniert nur mit perfekten Informationen, ohne Zufall, in einem endlich großen Raum. Perfekt also für Navigationssyteme.

    • @unterweltgeist
      @unterweltgeist 7 ปีที่แล้ว

      Die Antwort kam aber schnell. Hab ich nicht mit gerechnet. Hm, aber wenn das Ziel umschlossen ist, dann würde man ja eigentlich merken, dass man nicht weiter kommt. Irgendeine Lösung muss ich dafür finden.

    • @bastercall6586
      @bastercall6586 7 ปีที่แล้ว

      unterweltgeist wenn dein Ziel umschlossen ist, ist alles im umschlossenen tot. Sonst kannst du a* nicht anwenden

    • @unterweltgeist
      @unterweltgeist 7 ปีที่แล้ว

      Dann muss ich wohl Türen und das Sprengen von Wänden als Kosten mit einberechnen. Dann ist der Weg immer frei.

    • @LetsGameDev
      @LetsGameDev  7 ปีที่แล้ว

      Auf die Schnelle würde mir das floating einfallen um vorher zu berechnen ob es überhaupt einen Weg gibt. Also den Algorithmus mit dem auch das Farbeimertool in Bildbearbeitungsprogrammen funktioniert.

  • @LetsGameDev
    @LetsGameDev  11 ปีที่แล้ว

    dazu gibts nächste woche was

  • @LightTheMars
    @LightTheMars 11 ปีที่แล้ว

    Eine gute Sitzgelegenheit und gute Sitzhaltung sollten schon helfen ;)

  • @PlayJunkey
    @PlayJunkey 3 ปีที่แล้ว

    Schade, dass die Links nicht mehr funktionieren
    Aber echt ne schöne Erklärung

  • @LetsGameDev
    @LetsGameDev  11 ปีที่แล้ว

    ja das habe ich befürchtet dass es nur auf meinem rechner schön langsam läuft XD

  • @LetsGameDev
    @LetsGameDev  11 ปีที่แล้ว

    soweit ich das verstanden habe verzichtet der dijkstra auf eine heuristik

  • @Exulett
    @Exulett 11 ปีที่แล้ว

    als du mit Videos angefangen hast hattest du noch keine graue Haare O.o

  • @LetsGameDev
    @LetsGameDev  11 ปีที่แล้ว

    XD ahja das steht dann wohl in jedem video so

  • @daniellionel01
    @daniellionel01 11 ปีที่แล้ว +1

    danke danke danke danke danke danke :DDD :DD :DD

  • @RaisingAgent
    @RaisingAgent 11 ปีที่แล้ว

    "Zum Runterholen: bit.ly/a-stern" xD

  • @crolex6443
    @crolex6443 7 ปีที่แล้ว

    das ist der dijkstra Algorithmus

    • @LetsGameDev
      @LetsGameDev  7 ปีที่แล้ว +1

      Soweit ich weiß, ist der A Stern schneller aber Dijkstra ist schöner und findet bessere Pfade. Aber sie sind ähnlich.

    • @danielf.7151
      @danielf.7151 7 ปีที่แล้ว +1

      Meines Wissens nach fügt A Stern hauptsächlich dieses "wie weit ist es noch zum Ziel?" hinzu. Dabei geht es vor allem um: "Komm ich meinem Ziel überhaupt näher?", was vor allem dann interessant wird, wenn nicht alle Felder die gleichen Kosten haben.

  • @LetsGameDev
    @LetsGameDev  11 ปีที่แล้ว

    im prinzip schon^^

  • @FlexxVision
    @FlexxVision 9 ปีที่แล้ว

    Sehr cool,
    finster wird es, wenn millionen von Stellen untersucht werden müssen, und das in unter 100[ms]. Dann den kürzesten Weg zu lokalisieren, kann man mit einer Anzahl Versuche machen, oft ist nicht der beste Weg wesentlich besser als der 5t beste.
    th-cam.com/video/xgBrp65D0Y8/w-d-xo.html
    Sehr gut der Beitrag.
    Grüßi K.

  • @LetsGameDev
    @LetsGameDev  11 ปีที่แล้ว

    ich setze mich gleich ans schreiben!

  • @Flehwah
    @Flehwah 11 ปีที่แล้ว

    Verrate mir BITTE dein Geheimnis: Wie hast du es geschafft, trotz jahrelangem Programmieren, keinen Buckel zu bekommen?

  • @JoshuaBehrens
    @JoshuaBehrens 11 ปีที่แล้ว

    Wo ich grad in der Beschreibung geguckt habe... was soll zutzen sein :? "(Also wenn ich's mal zutze^^)"

  • @vertox4837
    @vertox4837 7 ปีที่แล้ว

    So könnte man in einem Spiel ja einen Navi machen.

  • @AppleCakeGames
    @AppleCakeGames 11 ปีที่แล้ว

    SETZ DEINE BRILLE WIEDER AUF!!! :D

  • @Mobin92
    @Mobin92 11 ปีที่แล้ว

    lol er hat "runterholen" gesagt... *höhö*

  • @TheJaseku
    @TheJaseku 11 ปีที่แล้ว

    goil

  • @JoshuaBehrens
    @JoshuaBehrens 11 ปีที่แล้ว

    gaaaaanz unten beim Mikro ^^

  • @LetsGameDev
    @LetsGameDev  11 ปีที่แล้ว

    Bitte keine so komplizierten Fragen!

  • @MrReallifexp
    @MrReallifexp 11 ปีที่แล้ว

    Na ihr Nudeln xD

  • @SliverTW
    @SliverTW 11 ปีที่แล้ว

    ...