Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

A* Pathfinding

  • 1
  • 2

Werbeanzeige

Todeskola

Frischling

  • »Todeskola« ist der Autor dieses Themas

Beiträge: 2

  • Private Nachricht senden

1

28.06.2014, 10:40

A* Pathfinding

Hallo,
ich schreibe eine Bachelorarbeit über Pathfinding Algorithmen und über die Implementierung eines A* in einer eigenen kleinen KI. Ich soll für diese Bachelorarbeit auch eine Liste erstellen welche Spiele den A* Algorithmus verwenden. Nun lese ich immer wieder das der A* Standard in der Spielentwicklung ist.

Ich bin nun kurz davor die Entwickler anzuschreiben, da ich nirgends eine Quelle dazu finde. Kennt jemand diesbezüglich eine seriöse Quelle?


Grüße Todeskola

MitgliedXYZ

Alter Hase

Beiträge: 1 369

Wohnort: Bayern

  • Private Nachricht senden

2

28.06.2014, 10:54

Hier wären ein paar Spiele aufgelistet, die diesen Algorithmus verwenden. Sind aber nicht sehr bekannte Titel.
http://arongranberg.com/astar/


Ach ja, das ist bei mir der erste Google Treffer für "A*" :P

Todeskola

Frischling

  • »Todeskola« ist der Autor dieses Themas

Beiträge: 2

  • Private Nachricht senden

3

28.06.2014, 11:08

Danke für die Antwort, Das ist schon mal was :)

Zitat von »MitgliedXYZ«

Ach ja, das ist bei mir der erste Google Treffer für "A*" :P
Weniger ist echt manchmal mehr... ich habe bei Google da schon tausend Sachen eingegeben, aber nicht nur das :D

Evrey

Treue Seele

Beiträge: 245

Beruf: Weltherrscher

  • Private Nachricht senden

4

28.06.2014, 16:07

Praktisch jedes Spiel in dem Bots eigenständig von A nach B finden müssen. Das können Truppen in Strategiespielen sein oder auch feindliche Feinde in RPGs mit AKS. A* wird sogar manchmal genutzt, um in manchen Spielen die KI durch einen Technologie-Baum zu navigieren. Oft begleitet wird A* von Dijkstra. A* glänzt besonders dann, wenn Start und Ziel bekannte Positionen sind. Dijkstra hingegen führt dich vom Start aus zum naheliegendsten Ort, der ein bestimmtes Kriterium erfüllt. Ist also zum Bleistift praktisch für eine Worms 3D -KI, in der die Würmchen zur nächsten Medi-Kiste kriechen.

C-/C++-Quelltext

 
1
2
3
4

int main(int _argc, char** _argv) noexcept {
  asm volatile("lock cmpxchg8b %eax");
  return 0;
} // ::main
(Dieses kleine Biest vermochte einst x86-Prozessoren lahm zu legen.)

=> Und er blogt unter Hackish.Codes D:

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

5

28.06.2014, 16:11

Zitat von »Evrey«

zum Bleistift
zum Beispiel*
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

Architekt

Community-Fossil

Beiträge: 2 481

Wohnort: Hamburg

Beruf: Student

  • Private Nachricht senden

6

28.06.2014, 16:28

Zitat von »BlueCobold«

Zitat von »Evrey«

zum Bleistift
zum Beispiel*
Dir ist klar, dass das eine übliche und bekannte Umschreibung (eine Art Gag) ist, oder? ;)
Der einfachste Weg eine Kopie zu entfernen ist sie zu löschen.
- Stephan Schmidt -

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

7

28.06.2014, 18:15

Anno 1992 war es noch lustig. 1995 schon nicht mal mehr in Gebrauch. Und heute, fast 20 Jahre später, ist es einfach nur noch lästig.
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

Architekt

Community-Fossil

Beiträge: 2 481

Wohnort: Hamburg

Beruf: Student

  • Private Nachricht senden

8

28.06.2014, 20:25

Zitat von »BlueCobold«

Anno 1992 war es noch lustig. 1995 schon nicht mal mehr in Gebrauch. Und heute, fast 20 Jahre später, ist es einfach nur noch lästig.

Jedem das seine.
Der einfachste Weg eine Kopie zu entfernen ist sie zu löschen.
- Stephan Schmidt -

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

9

30.06.2014, 15:42

Auch wenn es etwas spät kommt. Wir verlangen als Mods von den Usern dass sie Themen überlesen sollen die sie nicht interessieren und in welchen sie sonst nur pöbeln würden. Ich denke das ist so ein Fall wo wir mit gutem Beispiel vorangehen sollten. Dir gefällt diese Aussage im Moment nicht, dann überließ sie einfach. So mein Vorschlag.
Evrey, es ist richtig dass diese Spiele größtenteils A*, irgendeine Abwandlung davon oder Dijkstra benutzen, aber ohne Quelle wird er dies ja nicht in seiner Bachelorarbeit verwenden können. Meiner Meinung nach stellt A* auch nur eine Erweiterung zu Dijkstra da und ist stark damit verwandt. Die Anwendungsgebiete sind natürlich eher unterschiedlich wie Evrey ja schon klar gestellt hat.
„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.“

Techie

Alter Hase

Beiträge: 717

Wohnort: Bayreuth

Beruf: Student | Hilfswissenschaftler in der Robotik

  • Private Nachricht senden

10

30.06.2014, 17:02

Generell würde ich empfehlen NavMeshes zu nutzen. Diese sind zwar schwieriger zu implementieren, jedoch sparen sie Speicher (RAM) und sind normalerweise effektiver.

NavMeshes sind *glaube ich* auch eine Version des A* Algorithmus. Habe mich mit letzteren nie sonderlich beschäftigt.
I write my own game engines because if I'm going to live in buggy crappy filth, I want it to me my own - Ron Gilbert

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Techie« (30.06.2014, 19:24)

Werbeanzeige

  • 1
  • 2

Ähnliche Themen