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!

#15: "Rutschige Angelegenheit", Geschwindigkeit, 03.03.2013

Werbeanzeige

Schrompf

Alter Hase

Beiträge: 1 470

Wohnort: Dresden

Beruf: Softwareentwickler

  • Private Nachricht senden

11

09.02.2013, 19:01

Ja, das war auch meine Sorge. Die Möglichkeiten, den Suchbaum möglichst schnell abzuklappern, dürften bald ausgeschöpft werden. Weiter kommt man dann nur noch mit Heuristiken, um kurze Bäume zu erkennen und zu bevorzugen. Von daher ist es evtl. eine gute Idee, dass ein Teil der Prüfungskarten vorher nicht bekannt ist.
Häuptling von Dreamworlds. Baut aktuell an nichts konkretem, weil das Vollzeitangestelltenverhältnis ihn fest im Griff hat. Baut daneben nur noch sehr selten an der Open Asset Import Library mit.

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

12

09.02.2013, 19:10

Wenn ihr besonders "interessante" Levels erstellt habt, wäre es nett, wenn ihr diese auch teilen würdet ;)
David Scherfgens Website | Konzentrationstest Polizei

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

13

09.02.2013, 20:03

Nun, sagen wir mal Karten mit sehr hoher Rekursionstiefe zu erstellen ist kein großes Problem. Die Anzahl der minimal notwendigen Züge dagegen... mal schauen, ich kann ja mal eine Karte bauen, die große Rekursion erfordert und ein paar der Heuristiken/Optimierungen sprengt, an die ich bisher so gedacht habe.
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]

stef

Treue Seele

Beiträge: 246

Wohnort: Kassel

Beruf: Softwareentwickler

  • Private Nachricht senden

14

09.02.2013, 23:17

Frage: Liegen zu Beginn alle Spielsteine an einer Mauer oder können diese sich auch frei auf dem Eis befinden ?
"In C++ it's harder to shoot yourself in the foot, but when you do, you blow off your whole leg." — Bjarne Stroustrup.

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

15

10.02.2013, 00:22

Die Spielfiguren können irgendwo liegen, nicht zwingenderweise an einer Mauer.
Gleiches gilt auch für die Zielfelder. Ich habe das noch in den Text eingebaut.
David Scherfgens Website | Konzentrationstest Polizei

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

16

10.02.2013, 09:59

Zuerst dachte ich ja, man könnte es ähnlich wie den Contest "Reisekosten" lösen, indem man gleichzeitig vorwärts und rückwärts sucht und aufhört, wenn die beiden Suchen sich treffen (bidirektionale Suche). Aber leider gibt es für die meisten Zustände extrem viele mögliche Vorgängerzustände, so dass sich die Rückwärtssuche enorm auffächern würde. Oder sieht das jemand anders? ;)

Übrigens, was die Levels zum Testen angeht, ist mir schon etwas eingefallen.
Ich baue einige Level-Templates und platziere dann dort zufällig die Figuren und Zielfelder. Jedes Template wird dann, sagen wir mal, 1000-mal mit verschiedenen Stellungen benutzt.
David Scherfgens Website | Konzentrationstest Polizei

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

17

10.02.2013, 10:50

Rückwärts suchen geht bei diesem Spiel nicht. Denn es gibt End-Positionen, die man "rückwärts" eben nicht erreichen könnte. Z.B:

Quellcode

 
1
2
3
4
5
6

#......#
#......#
#..b...#
#......#
#......#
########
Wo soll da der vorletzte Zug sein?

Quellcode

 
1
2
3
4
5
6

#......#
#......#
#..B..b#
#......#
#......#
########

Quellcode

 
1
2
3
4
5
6

#......#
#......#
#b.B...#
#......#
#......#
########

Quellcode

 
1
2
3
4
5
6

#......#
#......#
#..B...#
#......#
#..b...#
########
Sind alle falsch.

Möglich wären aber z.B.

Quellcode

 
1
2
3
4
5
6

#......#
#......#
#..Br..#
#g.....#
#......#
########
Oder

Quellcode

 
1
2
3
4
5
6

#......#
#..g...#
#..B...#
#......#
#...r..#
########
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]

Dieser Beitrag wurde bereits 5 mal editiert, zuletzt von »BlueCobold« (10.02.2013, 10:57)

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

18

10.02.2013, 12:01

Ja, stimmt. Rückwärts geht wohl nicht.

Mir ist noch ein Gedanke gekommen.
Es könnte ja Levels geben, in denen die Spielfiguren durch Mauern komplett voneinander getrennt sind, so wie im Beispiel-Level Nr. 2.
Hier kann man natürlich eine ganz einfache Optimierung vornehmen: wenn man diesen Fall erkennt, kann man für jede Spielfigur eine separate Lösung bestimmen, ohne dabei die Bewegung der anderen mit zu berücksichtigen. Das heißt: nur dreimal einfacher Kürzeste-Weg-Algorithmus, gelöst im Null-komma-nix. (Leichte Abwandlung des Falls: eine Figur ist getrennt von den beiden anderen.)

Nun erfordert es ja einen gewissen Aufwand, diese Fälle zu erkennen und abzuhandeln.
Außerdem würde ich durch die Auswahl meiner Test-Levels willkürlich einen Anteil dieser Fälle festlegen müssen, also z.B. 10% aller Levels beinhalten diesen Fall.

Darum denke ich, dass man diese Fälle von vornherein ausschließen und Level Nr. 2 daher für ungültig erklären sollte.
Es käme also eine zusätzliche Bedingung hinzu, und zwar dass die Spielfiguren nicht "baulich" voneinander getrennt sind.

Einwände?
David Scherfgens Website | Konzentrationstest Polizei

Helmut

5x Contest-Sieger

Beiträge: 692

Wohnort: Bielefeld

  • Private Nachricht senden

19

10.02.2013, 12:03

Die Rückwärtssuche geht prinzipiell schon, man muss aber natürlich alle Steine berücksichtigen. Mindestens ein Zielfeld muss ja zB an einer Wand liegen. Deshalb geht dein Beispiel auch nicht.

Ich habe schon mal einen relativ simplen Algo implementiert und bin irgendwie darüber überrascht, wie lange er für manche Levels braucht. Im dritten Level braucht er für einen Durchlauf 15 Sekunden... :)
Sei stets geduldig gegenüber Leuten, die nicht mit dir übereinstimmen. Sie haben ein Recht auf ihren Standpunkt - trotz ihrer lächerlichen Meinung. (F. Hollaender)

domin

1x Contest-Sieger

Beiträge: 65

  • Private Nachricht senden

20

10.02.2013, 12:10

@David: Selbst bei Beispiel-Level Nr. 2 darf man die Spielsteine aber nicht seperat betrachten. Es gibt doch bestimmt Levels, die die Spielsteine zwar komplett getrennt voneinander getrennt lösen können, aber vielleicht trotzdem weniger Züge benötigen, wenn sie sich gegenseitig "helfen"?!
Meine Projekte:
LightBulb, TurtleRun

Werbeanzeige

Ähnliche Themen