Einfaches Pathfinding
lima-city → Forum → Programmiersprachen → C/C++ und D
algorithmus
beispiel
code
karte
knoten
list
point
pos
problem
punkt
queue
roboter
routine
sagen
speichern
start
startpunkt
status
url
weg
-
Soderla, noch ein Nachschlag zum Verständnis des Codes: Deine Routine "DoHeartbeat()" ist meine Routine "tick()".
Ich fass mal zusammen, was ich jetzt weiß:
- Auf einer Map bewegen sich verschiedene NPC voneinander unabhängig horizontal oder vertikal.
- Die Marker einer Map können (neben anderen Eigenschaften) aktiviert und deaktiviert werden.
- Die Map ist orthogonal und diskret, also jeder Punkt hat eine x- und eine y-Koordinate und beiden sind Integer und keine Gleitkommazahlen.
- Man kann die Marker so wählen (auch wenn das ein paar mehr erzeugt), dass verbundene Marker entweder horizontal oder vertikal auf einer Linie liegen.
- Das Pathfinding muss effizient sein, da viele NPC sich gleichzeitig verlaufen und wir kein takking wollen.
Korrigiere mich hier bitte, falls ich etwas falsch verstanden habe.
Hieraus ergeben sich für mich folgende Folgerungen:
- Die Map wird einmal im Speicher gehalten und ist für alle NPC identisch.
- Jeder NPC hat seinen persönlichen Pfad, das heißt eine Reihe von Markern, die er ablaufen wird.
- Der Pfad für einen NPC wird nur dann berechnet, wenn er losläuft oder wenn sich der Status eines Marker ändert.
- Es gibt also keine Routine GetNextPoint (), sondern nur GetWayPoints () und der NPC muss dann die Punkte nacheinander abkaspern.
- Die Map wird als C++Klasse gehalten, das Pathfinding selbst aber als dirty old-school C, um Performanz rauszuschlagen. Das Constructor-Chaining und das VFT-Druchforsten von C++ dauert einfach Jahre.
Das könnte ich dir gerne schreiben, aber ich bräuchte vorher noch ein paar Infos um das ganze optimieren zu können:
- Schätze wieviele NPC minimal, maximal und durchschnittlich auf einer Map unterwegs sind.
- Schätze wieviele Marker eine Map minimal, maximal und durchschnttlich hat.
- Schätze wie häufig Marker ihren Status ändern.
Falls meine Aussagen oben richtig sind und du mir diese Fragen beantwortest, setz ich mich hin und schreib dir das Ding in C/C++. -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
-
>> - Die Map wird einmal im Speicher gehalten und ist für alle NPC identisch.
Dazu sei zu sagen: Es gibt auch mehrere Map's, welche notfalls parallel laufen sollten. Die Maps unterscheiden sich in Größe, Form, Marker- und NPC-Anzahl. Ich weiss nicht, in wiefern das relevant ist.
>> - Es gibt also keine Routine GetNextPoint (), sondern nur GetWayPoints () und der NPC muss dann die Punkte nacheinander abkaspern.
Es gibt eine Routine "GetnearestPoint()" - in wiefern die allerdings hilfreich oder von Nöten ist, ist mir unklar.
>> - Schätze wieviele NPC minimal, maximal und durchschnittlich auf einer Map unterwegs sind.
>> - Schätze wieviele Marker eine Map minimal, maximal und durchschnttlich hat.
Ich würde sagen maximal gibt es immer 500500 NPC's/Waypoints. Minimal halt einen NPC und schätzungsweise 4 Waypoints. (Es gibt auf jeder Karte mindestens einen Eingang und ein Ziel, welche in den seltensten Fällen, per Luftlinie erreichbar sind. Der Fall ist eigentlich trivial und kann ignoriert werden)
>> - Schätze wie häufig Marker ihren Status ändern.
Das lässt sich schwierig schätzen, da mir momentan nicht ganz klar ist, was du mit "Status" meinst. Aber beispielsweise gibt es einen "Offen-Geschlossen"-Status für Türen. Dieser kann sich imens häufig ändern, sollte sich aber nicht ändern zwischen zwei "Ticks". Im Grunde muss dieser Status auch erst abgefragt werden, wenn der NPC direkt vor der Tür steht und sieht, dass sie "zu" ist. Der NPC kann sich dann den nächstbesten weg suchen.
Und wie ich dir schon per Mail geschrieben habe: Möglichst viel in gesonderten Funktionen "auskoppeln", damit es notfalls auf andere Threads "abgelegt" werden kann. -
census schrieb:
- Die Map wird als C++Klasse gehalten, das Pathfinding selbst aber als dirty old-school C, um Performanz rauszuschlagen. Das Constructor-Chaining und das VFT-Druchforsten von C++ dauert einfach Jahre.
Interessant, wie würde sowas aussehen?
Sry für Thread-Hijacking -
@evil-devil: Dreckiges, hemmungsloses global_alloc und direkt auf dem Speicher agieren.
@nerdinator: Super. Ich schau mir das die Tage an und schick dir was. Ich nehme an du meintest "500 / 500" und nicht "500500" (fünfhunderttausendfünfhunder). -
census schrieb:
@evil-devil: Dreckiges, hemmungsloses global_alloc und direkt auf dem Speicher agieren.
Hast du da rein zufällig ein Beispiel für? Das würde mich mal interessieren. Ich schreib zwar wenig bis kein C/C++, aber als Java Progger bin ich die VFT eh gewohnt und machtlos gegen : / -
census schrieb:
Ups, ja natürlich. Das kommt davon, wenn man zu eiftrig und blind tippt ^^ Natürlich nur je fünfhundert ;) Fünhunderttausend wäre schon ein bisschen übel viel ;)
@evil-devil: Dreckiges, hemmungsloses global_alloc und direkt auf dem Speicher agieren.
@nerdinator: Super. Ich schau mir das die Tage an und schick dir was. Ich nehme an du meintest "500 / 500" und nicht "500500" (fünfhunderttausendfünfhunder).
-
Um es mit den Worten Jean Pütz' zu sagen: "Ich hab da mal was vorbereitet".
Der folgende Code ist hässlich, dreckig und unlöblich (nota bene das "goto"). Aber er ist schnell. Die Idee ist folgende:
Du instanziierst dir pro Map eine Objekt der Klasse Map. Dort schiebst du deine Punkte rein und verbindest sie. Jeder NPC hat einen Zeiger oder eine Referenz auf die Map, auf der er sich gerade befindet.
Wenn der NPC
- loslaufen will oder
- vor einem verschlossenen Marker steht und nicht weiß wohin,
ruft er die Routine findPath auf. Diese Routine verändert die Map nicht und kann zig-Mal gleichzeitig und konkurrierend (in verschiedenen Threads) laufen. Irgendwann (und das ziemlich schnell) liefert diese Routine einen Vektor über Punkte zurück. Das sind die Wegpunkte des NPC zu seinem Ziel. Die kann er dann abkaspern, bis er entweder am Ziel ist oder vor einer Tür steht, die während der Berechnung offen war, nun aber zu ist. Sprich die Routine wird nicht bei jedem Heartbeat gerufen, sondern nur wenn der NPC nicht weiterweiß.
Der Heartbeat würde dann in etwa so aussehen (Pseudocode):
void doHeartbeat () { if ( ! myWayPoints.empty () ) { if (moveCloserToNextWayPoint () ) if (myPosition == myWayPoints.next ().position) myWayPoints.pop (); else // geschlossene Tür gefunden myWayPoints = findPath (myPosition.x, myPosition.y, destination.x, destination.y, &myMap); } else myWayPoints = findPath (myPosition.x, myPosition.y, destination.x, destination.y, &myMap); }
Hier nun der erste Entwurf des Codes. Meines Erachtens funktioniert der komplett, aber ich werde noch mal genauer testen und vllt find ich ja noch Optimierungspotential. Weder Startpunkt noch Endpunkt müssen Marker sein, aber sie müssen jeweils auf einer Kante zwischen zwei Markern liegen.
#include <iostream> #include <list> #include <cmath> #include <malloc.h> #include <memory.h> using namespace std; typedef struct { int id; int x; int y; bool active; bool isOpen; bool isClosed; double f; int neighborCount; int* neighbors; int predecessor; } Point; typedef struct { double f; Point* point; void* next; } QueueEntry, *Queue; class Map { public: Point* points; int pointCount; Map () { points = (Point*) malloc (sizeof (Point) * 2); pointCount = 2; } ~Map () { Point* current = points; for (int i = 0; i < pointCount; ++ i, ++ current) free (current->neighbors); free (points); } int addPoint (int x, int y, bool active) { Point *newPoints = (Point*) malloc (sizeof (Point) * (pointCount + 1) ); if (points) { memcpy (newPoints, points, sizeof (Point) * pointCount); free (points); } newPoints [pointCount].id = pointCount; newPoints [pointCount].x = x; newPoints [pointCount].y = y; newPoints [pointCount].active = active; newPoints [pointCount].f = 0.0f; newPoints [pointCount].isOpen = false; newPoints [pointCount].isClosed = false; newPoints [pointCount].neighbors = 0; newPoints [pointCount].neighborCount = 0; points = newPoints; pointCount ++; return pointCount - 1; } void activatePoint (int id) { Point* current = points; for (int i = 0; i < pointCount; ++ i, ++ current) if (current-> id == id) current->active = true; } void deactivatePoint (int id) { Point* current = points; for (int i = 0; i < pointCount; ++ i, ++ current) if (current-> id == id) current->active = false; } bool connectPoints (int id1, int id2) { Point* p1 = &points [id1]; Point* p2 = &points [id2]; int* newNeighbors = (int*) malloc (sizeof (int) * (p1->neighborCount + 1) ); if (p1->neighbors) { memcpy (&newNeighbors [1], p1->neighbors, sizeof (int) * p1->neighborCount); free (p1->neighbors); } *newNeighbors = id2; p1->neighbors = newNeighbors; p1->neighborCount ++; newNeighbors = (int*) malloc (sizeof (int) * (p2->neighborCount + 1) ); if (p2->neighbors) { memcpy (&newNeighbors [1], p2->neighbors, sizeof (int) * p2->neighborCount); free (p2->neighbors); } *newNeighbors = id1; p2->neighbors = newNeighbors; p2->neighborCount ++; return true; } }; Queue insertQueue (Queue queue, Point* point) { Queue qe = (Queue) malloc (sizeof (QueueEntry) ); qe->f = point->f; qe->point = point; qe->next = 0; if (queue == 0) return qe; Queue cur = queue; Queue prev = 0; while (cur) { if (cur->f > qe->f) if (prev == 0) { qe->next = cur; return qe; } else { prev->next = qe; qe->next = cur; return queue; } prev = cur; cur = (Queue) cur->next; } prev->next = qe; return queue; } Queue removeQueue (Queue queue, Point* point) { if (queue->point == point) { Queue next = (Queue) queue->next; free (queue); return next; } Queue cur = queue; Queue prev = 0; while (cur) { if (cur->point == point) { prev->next = cur->next; free (cur); return queue; } prev = cur; cur = (Queue) cur->next; } return queue; } list <int> findPath (int sx, int sy, int ex, int ey, Map* map) { list <int> retVal; Queue openList = 0; int pointCount = map->pointCount; Point* points = (Point*) malloc (sizeof (Point) * pointCount); memcpy (points, map->points, sizeof (Point) * pointCount); Point* current = points; for (int i = 0; i < pointCount; ++ i, ++ current) { int* neighbors = (int*) malloc (sizeof (int) * current->neighborCount); memcpy (neighbors, current->neighbors, sizeof (int) * current->neighborCount); current->neighbors = neighbors; } points->id = 0; points->x = sx; points->y = sy; points->active = true; points->isOpen = true; points->isClosed = false; points->f = 0.0f; points->neighborCount = 0; points->neighbors = 0; points [1].id = 1; points [1].x = ex; points [1].y = ey; points [1].active = true; points [1].isOpen = false; points [1].isClosed = false; points [1].f = 0.0f; points [1].neighborCount = 0; points [1].neighbors = 0; int* neighborID; current = points; Point* neighbor; int* sNeighbors = 0; int sNeighborCount = 0; int* eNeighbors = 0; int eNeighborCount = 0; for (int i = 0; i < map->pointCount; ++ i, ++ current) { neighborID = current->neighbors; for (int j = 0; j < current->neighborCount; ++ j, ++ neighborID) { neighbor = &points [*neighborID]; if (sx == current->x && current->y <= sy && sy <= neighbor->y) // cur -> y -> nei { if (ex == current->x && current->y <= ey && ey <= neighbor->y) { retVal.push_front (1); goto end; } else { int* neighbors = (int*) malloc (sizeof (int) * (sNeighborCount + 2) ); memcpy (&neighbors [2], sNeighbors, sizeof (int) * sNeighborCount); free (sNeighbors); sNeighborCount += 2; sNeighbors = neighbors; sNeighbors [0] = current->id; sNeighbors [1] = *neighborID; } } else if (ex == current->x && current->y <= ey && ey <= neighbor->y) { int* neighbors = (int*) malloc (sizeof (int) * (eNeighborCount + 2) ); memcpy (&neighbors [2], eNeighbors, sizeof (int) * eNeighborCount); free (eNeighbors); eNeighborCount += 2; eNeighbors = neighbors; eNeighbors [0] = current->id; eNeighbors [1] = *neighborID; } if (sy == current->y && current->x <= sx && sx <= neighbor->x) // cur -> y -> nei { if (ey == current->y && current->x <= ex && ex <= neighbor->x) { retVal.push_front (1); goto end; } else { int* neighbors = (int*) malloc (sizeof (int) * (sNeighborCount + 2) ); memcpy (&neighbors [2], sNeighbors, sizeof (int) * sNeighborCount); free (sNeighbors); sNeighborCount += 2; sNeighbors = neighbors; sNeighbors [0] = current->id; sNeighbors [1] = *neighborID; } } else if (ey == current->y && current->x <= ex && ex <= neighbor->x) { int* neighbors = (int*) malloc (sizeof (int) * (eNeighborCount + 2) ); memcpy (&neighbors [2], eNeighbors, sizeof (int) * eNeighborCount); free (eNeighbors); eNeighborCount += 2; eNeighbors = neighbors; eNeighbors [0] = current->id; eNeighbors [1] = *neighborID; } } } free (points [0].neighbors); points [0].neighbors = sNeighbors; points [0].neighborCount = sNeighborCount; for (int i = 0; i < eNeighborCount; i++) { int* neighbors = (int*) malloc (sizeof (int) * (points [eNeighbors [i] ].neighborCount + 1) ); memcpy (&neighbors [1], points [eNeighbors [i] ].neighbors, sizeof (int) * points [eNeighbors [i] ].neighborCount); free (points [eNeighbors [i] ].neighbors); points [eNeighbors [i] ].neighborCount ++; points [eNeighbors [i] ].neighbors = neighbors; points [eNeighbors [i] ].neighbors [0] = 1; } openList = insertQueue (openList, &points [0]); double f; Queue qe; while (openList) { current = openList->point; qe = openList; openList = (Queue) openList->next; free (qe); if (current->id == 1) { qe = openList; while (openList) { qe = openList; openList = (Queue) openList->next; free (qe); } current = &points [1]; while (current->id) { retVal.push_front (current->id); current = &points [current->predecessor]; } goto end; } neighborID = current->neighbors; for (int i = 0; i < current->neighborCount; ++ i, ++ neighborID) { neighbor = &points [*neighborID]; if ( ! neighbor->isClosed && neighbor->active) { f = current->f + abs (0.0f + current->x - neighbor->x) + abs (0.0f + current->y - neighbor->y) + sqrt ( (ex - neighbor->x) * (ex - neighbor->x) + (ey - neighbor->y) * (ey - neighbor->y) ); if (! (neighbor->isOpen && f > neighbor->f) ) { neighbor->predecessor = current->id; neighbor->f = f; if (neighbor->isOpen) openList = removeQueue (openList, neighbor); openList = insertQueue (openList, neighbor); neighbor->isOpen = true; } } } current->isClosed = true; } end: current = points; for (int i = 0; i < pointCount; ++ i, ++ current) if (current->neighbors) free (current->neighbors); free (points); return retVal; } int main () { Map m; m.addPoint (0, 0, true); m.addPoint (100, 0, true); m.addPoint (0, 100, true); m.addPoint (100, 100, true); m.connectPoints (2, 3); m.connectPoints (2, 4); m.connectPoints (3, 5); m.connectPoints (4, 5); list <int> way = findPath (10, 0, 20, 100, &m); for (list <int>::iterator it = way.begin (); it != way.end (); ++ it) cout << *it << endl; return 0; }
evil-devil schrieb:
census schrieb:
- Die Map wird als C++Klasse gehalten, das Pathfinding selbst aber als dirty old-school C, um Performanz rauszuschlagen. Das Constructor-Chaining und das VFT-Druchforsten von C++ dauert einfach Jahre.
Interessant, wie würde sowas aussehen?
Sry für Thread-Hijacking
So sieht hässliches C aus.
Beitrag zuletzt geändert: 3.9.2009 0:05:39 von census -
Also ich habe das nun mal versucht zu verwenden - irgendwo ist da noch der Wurm drin. Aber ich arbeite da mal noch ein weilchen weiter dran. Wahrscheinlich liegt das Problem eher daran, dass praktisch der "Rest" schon fertig ist und ich da irgendwas noch nicht ganz richtig verstanden habe oder so... Ich arbeite mich da noch ein bisschen weiter ein - dank eurer Hilfe bin ich da ein ganz schönes Stück weiter.
Vielen Dank. Meinetwegen kann das Thema geschlossen werden - oder man wartet auf noch weitere Fragen/Antworten. Mir momentan relativ. ^^
Ich melde mich dann wieder, wenn sich was ergeben hat - sei es die Endlösung oder die Erkenntnis über das Problem. ^^ Ich denke aber an euch liegt es nicht. -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
