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!
Werbeanzeige
Zitat von »"dot"«
verwende bounding volumes. ist sicher einmal der erste schritt (falls du das noch nicht machst)
Zitat von »"dot"«
der nächste wäre es, eine hierarchie, hier z.b. einen quad oder bsp/kd-tree, zu verwenden und dann nurmehr die einheiten, die sich im selben leaf des trees befinden zu testen...
Zitat
Meinst du damit "Bounding Box"?
Zitat von »"dot"«
ich könnte mir dann so einige weiterentwicklungen eines systems mit rechtecken vorstellen. z.b. dass man erst nur die mittelpunkte der boxen überprüft (wenn abstand im verhältnis zur ausdehnung groß dann weg damit) und so schneller potentielle kollisionspartner aussortiert (also im prinzip erstmal mit kreisen testet).
in strategiespielen werden einheiten ja oft gruppiert, wobei die gruppe ja meist zusammenbleibt. man könnte also auch eine bounding box für eine ganze gruppe nehmen und erst die testen usw...
Zitat
Hmm, sollte doch eigentlich nicht, wenn man nach dem Box Kontrolltest auch noch einen Pixelgenauen Test macht~
Zitat
Was evt. noch wichtig wäre.
Wenn ich 4 Einheiten auf der Map habe, funktioniert meine Methode.
Bei > 200 gibt es aber Probleme, das die Kollision nicht erkannt wird bzw. übersprungen wird.
C-/C++-Quelltext |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include <iostream> #include <list> #include <stdlib.h> #include <windows.h> #include <conio.h> const int rectCount = 2000000; float rnd() { return 15.0f * static_cast<float>(rand()) / static_cast<float>(RAND_MAX); }; class rect { float left; float top; float right; float bottom; public: bool overlaps(const rect& r) const { if( r.left > right ) return false; if( r.top > bottom ) return false; if( r.bottom < top ) return false; if( r.right < left ) return false; return true; }; rect() : left(rnd()), top(rnd()), right(left+rnd()), bottom(top+rnd()) {}; }; int main() { __int64 freq, tick1, tick2; srand(GetTickCount()); rect* rects = new rect[rectCount]; QueryPerformanceFrequency( reinterpret_cast<LARGE_INTEGER*>(&freq) ); QueryPerformanceCounter( reinterpret_cast<LARGE_INTEGER*>(&tick1) ); for( int i = 0; i < 10 ; ++i ) { for( int i = 1; i < rectCount; ++i ) rects[i].overlaps(rects[0]); } QueryPerformanceCounter( reinterpret_cast<LARGE_INTEGER*>(&tick2) ); double timedif = static_cast<double>(tick2 - tick1) / static_cast<double>(freq) * 100.0f; std::cout << "average: " << timedif << "ms"; delete[] rects; while( !_kbhit() ); return 0; } |
Zitat von »"dot"«
was macht denn deine methode genau?
wenn du einfach jede einheit gegen jede andere testest, dann sollte eigentlich nur die geschwindigkeit, aber nicht das ergebnis des tests von der anzahl der einheiten abhängen...bug im kollisionstest?
C-/C++-Quelltext |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
public bool IsCollides(GameObject obj) { foreach (GameObject item in this._gameObjects) { // Verhindern dass sich das Objekt mit sich selber vergleicht // Ansonsten ist die Kollision immer true if(!obj.Equals(item)) { return Tools.Intersect( new Rectangle((int)obj.Position.X, (int)obj.Position.Y, obj.Size.Width, obj.Size.Height), new Rectangle((int)item.Position.X, (int)item.Position.Y, item.Size.Width, item.Size.Height) ); } } return false; } |
C-/C++-Quelltext |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
/// <summary> /// Prüft die Kollision zweier rechteckigen Objekte anhand der Koordinaten /// </summary> /// <param name="rect1, der linke obere Punkt eines Rechteckes muss übergeben werden"></param> /// <param name="rect2 DITO"></param> /// <returns>Kollision true/false</returns> public static bool Intersect(RectangleF rect1, RectangleF rect2) { if (((rect1.X < (rect2.X + rect2.Width)) && (rect2.X < (rect1.X + rect1.Width))) && (rect1.Y < (rect2.Y + rect2.Height))) { return (rect2.Y < (rect1.Y + rect1.Height)); } return false; } |
Zitat von »"dot"«
ich brauch für 2000000 tests in der debug version ca 110 ms und im release build 18 ns (das kommt mir aber etwas zu wenig vor...) (AMD Athlon 64 X2 3800+)
Werbeanzeige