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!

#03: "Kreisschnitt", Geschwindigkeit, 17.02.2008

Werbeanzeige

CodingCat

1x Contest-Sieger

Beiträge: 420

Beruf: Student (KIT)

  • Private Nachricht senden

51

16.02.2008, 12:02

Nun, deine UI Ausgabe sieht auf jeden Fall sehr interessant aus. :shock:

Allerdings werde ich, wenn ich eine Weile Kreise durch die Gegend schiebe, irgendwann mit Memory Exceptions beworfen. Kann allerdings nicht sagen, ob das direkt an deinem Algo liegt, wahrscheinlich eher an einem nicht bedachten Ausnahmefall in der Darstellung (.NET Graphics kann da ja ganz schön empfindlich sein mit invertierten Rechtecken o.ä.). Ich hab dir trotzdem mal die Exception kopiert:

Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Informationen über das Aufrufen von JIT-Debuggen
anstelle dieses Dialogfelds finden Sie am Ende dieser Meldung.

************** Ausnahmetext **************
System.OutOfMemoryException: Nicht genügend Arbeitsspeicher.
   bei System.Drawing.Graphics.CheckErrorStatus(Int32 status)
   bei System.Drawing.Graphics.DrawArc(Pen pen, Single x, Single y, Single width, Single height, Single startAngle, Single sweepAngle)
   bei Prototyp.ExactAlgorithm.Calculate(List`1 circles, Graphics graphics)
   bei Prototyp.MainForm.image_Paint(Object sender, PaintEventArgs e)
   bei System.Windows.Forms.Control.OnPaint(PaintEventArgs e)
   bei System.Windows.Forms.PictureBox.OnPaint(PaintEventArgs pe)
   bei System.Windows.Forms.Control.PaintWithErrorHandling(PaintEventArgs e, Int16 layer, Boolean disposeEventArgs)
   bei System.Windows.Forms.Control.WmPaint(Message& m)
   bei System.Windows.Forms.Control.WndProc(Message& m)
   bei System.Windows.Forms.Control.ControlNativeWindow.OnMessage(Message& m)
   bei System.Windows.Forms.Control.ControlNativeWindow.WndProc(Message& m)
   bei System.Windows.Forms.NativeWindow.Callback(IntPtr hWnd, Int32 msg, IntPtr wparam, IntPtr lparam)


************** Geladene Assemblys **************
[...]

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

52

16.02.2008, 12:48

Danke! Das ist wohl ein Bug in den Grafikfunktionen von .NET. Über Google findet man viele Problemhinweise, aber keine Lösungen.
Ich fange die Exception jetzt einfach.

Mittlerweile habe ich meinen Algorithmus auch in C++ implementiert. Er ist in fast allen Testfällen sehr schnell (meistens ist die Zeit nicht messbar). Nur im O(N²)-Fall braucht er sehr lange. Da kommt wahrscheinlich kein exakter Algorithmus drum herum.

Ich muss mir auch mal überlegen, wie ich eigentlich testen und die Geschwindigkeit messen soll. Bislang sieht der Plan so aus, dass zunächst die vordefinierten Testfälle zum Testen der Korrektheit verwendet werden. Dann zum Bestimmen der Geschwindigkeit eine Reihe zufälliger Konfigurationen mit 10, 100, 1000 und 10000 Kreisen, die sich alle schneiden. Fälle zu messen, wo die Kreise sich nicht schneiden, dürfte sinnlos sein, weil (bislang) alle Algorithmen diesen Fall quasi sofort entdecken und abbrechen.
Die Punktevergabe könnte dann so erfolgen wie im ersten Contest.
David Scherfgens Website | Konzentrationstest Polizei

S.Seegel

2x Contest-Sieger

Beiträge: 95

  • Private Nachricht senden

53

16.02.2008, 14:08

Zitat von »"TGGC"«

Tja, wie ich schon mal im Channel sagte, das ist diesmal etwas zu kompliziert geraten. Ich kann mich noch nicht wirklich durchringen, damit anzufangen. Schliesslich soll es Spass machen und nicht in Arbeit ausarten.

Zitat von »"David Scherfgen"«

Also mir macht sowas Spaß, sonst würde ich es nicht machen! :D

Also ich hab gerade an etwas kniffligeren Aufgaben richtig Spaß *thumbs up*

Zitat von »"David Scherfgen"«

Mittlerweile habe ich meinen Algorithmus auch in C++ implementiert. Er ist in fast allen Testfällen sehr schnell (meistens ist die Zeit nicht messbar). Nur im O(N²)-Fall braucht er sehr lange. Da kommt wahrscheinlich kein exakter Algorithmus drum herum.

Kann ich leider so bestätigen. An dem 10.000-sich-schneidende-Kreise-Testfall (von rklaffehn) hängt meine Lösung um die 10 Sekunden (!) :cry:.

Anonymous

unregistriert

54

16.02.2008, 14:48

Zitat von »"S.Seegel"«

Zitat von »"TGGC"«

Tja, wie ich schon mal im Channel sagte, das ist diesmal etwas zu kompliziert geraten. Ich kann mich noch nicht wirklich durchringen, damit anzufangen. Schliesslich soll es Spass machen und nicht in Arbeit ausarten.

Zitat von »"David Scherfgen"«

Also mir macht sowas Spaß, sonst würde ich es nicht machen! :D

Also ich hab gerade an etwas kniffligeren Aufgaben richtig Spaß *thumbs up*
Wie gesagt, das hab ich doch schon auf Arbeit genug. Ich hab da auch dann einfach keine Zeit dazu, dann bastele ich lieber an anderen Projekten weiter. f'`8k

Gruß, TGGC (making great games since 1992)

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

55

17.02.2008, 17:43

Leider muss ich meinen schönen Algorithmus in die Tonne werfen. Er funktioniert in den allermeisten Fällen, aber in ganz bestimmten Konstellationen reicht leider die Genauigkeit von Fließkommazahlen nicht aus.

Für die Tests habe ich mir aber schon einen neuen Algorithmus ausgedacht, der deutlich einfacher ist und auch nicht unter der Ungenauigkeiten leiden dürfte. Allerdings läuft er, so glaube ich, in O(N³) ...
David Scherfgens Website | Konzentrationstest Polizei

drakon

Supermoderator

Beiträge: 6 513

Wohnort: Schweiz

Beruf: Entrepreneur

  • Private Nachricht senden

56

17.02.2008, 18:24

:D

Da hatte ich wohl doch recht, als ich nachdem ich die Aufgabenstellung gelesen habe entschlosse habe, dass ich da mal nicht mitmache.. ;)
http://www.drakon.ch | Weltweit 31. Bester Solitär Spieler (Standard XP)

Deviloper

Community-Fossil

Beiträge: 2 872

  • Private Nachricht senden

57

17.02.2008, 19:50

Hab mitgemacht, wohl keine Zeit zur Optimierung gehabt und deswegen nciht eingereicht ^^ Mein Programm ist aber NOCH wesentlich langsamer :D
Devil Entertainment :: Your education is our inspiration
Der Spieleprogrammierer :: Community Magazin
Merlin - A Legend awakes :: You are a dedicated C++ (DirectX) programmer and you have ability to work in a team? Contact us!
Siedler II.5 RttR :: The old settlers-style is comming back!

Also known as (D)Evil

CodingCat

1x Contest-Sieger

Beiträge: 420

Beruf: Student (KIT)

  • Private Nachricht senden

58

17.02.2008, 20:11

Nunja, ich bin gespannt, wie viele (funktionierende) Lösungen es überhaupt gibt, von daher könnte sich Einschicken dennoch lohnen. ;-)

Deviloper

Community-Fossil

Beiträge: 2 872

  • Private Nachricht senden

59

17.02.2008, 20:48

Bis wann hab ich Zeit? Weiß nicht ob ich alle extremfälle abgedeckt habe ... müsste dann nochmal nachgucken ^^
Devil Entertainment :: Your education is our inspiration
Der Spieleprogrammierer :: Community Magazin
Merlin - A Legend awakes :: You are a dedicated C++ (DirectX) programmer and you have ability to work in a team? Contact us!
Siedler II.5 RttR :: The old settlers-style is comming back!

Also known as (D)Evil

spacegaier

Alter Hase

Beiträge: 572

Beruf: Student

  • Private Nachricht senden

60

17.02.2008, 20:56

Bis in ca. 3 Stunden. Heute um Mitternacht ist Deadline!

Werbeanzeige