Objektauswahl à la Lemmings
Übersicht
BlitzBasic Allgemein
|
Bura.TinoBetreff: Objektauswahl à la Lemmings |
 Do, Feb 23, 2012 15:34Antworten mit Zitat 
|
|---|---|---|
Keine Angst...Ich möchte keinen Lemming-Klon programmieren, sondern hab nur eine Verständnisfrage.  Und dieses Spiel beschreibt meine Frage wohl am anschaulichsten.
In dem Spiel klickt man einzelne Objekte an (die Lemminge) und weist ihnen somit verschiedene Funktionen zu. Aber wie kann man am effektivsten registrieren welches Objekt ausgewählt wurde ? Also nehmen wir mal an wir hätten eine Type-Struktur mit 10 Einträgen. Wenn jetzt die Maustaste gedrückt wird, könnte man alle Types der Reihe nach durchgehen und abfragen welches der Objekte im Bereich der Mauskoordinaten liegt. Bei 1000 Objekte wäre das aber sehr ineffektiv. Gibt es für sowas eine bessere Lösung ? |
||
 <- Ich liebe dieses Smilie ! 
|
||
|
XeresModerator |
Do, Feb 23, 2012 15:41 Antworten mit Zitat
|
|---|---|---|
|
Man kann die Möglichen Objekte einschränken, indem man die Spielfläche in Sektoren unterteilt und nur die darin enthalten Types überprüft. Der Aufwand für die Unterteilung könnte aber größer sein, als es Sinn macht.
1000 Types sind schnell überprüft, wenn man es optimiert. |
||
|
Win10 Prof.(x64)/Ubuntu 16.04|CPU 4x3Ghz (Intel i5-4590S)|RAM 8 GB|GeForce GTX 960
Wie man Fragen richtig stellt || "Es geht nicht" || Video-Tutorial: Sinus & Cosinus THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld) |
||
|
|
Bura.Tino |
Do, Feb 23, 2012 15:51 Antworten mit Zitat
|
|---|---|---|
|
Daran hab ich auch schon gedacht, aber das dürfte noch umständlicher werden.
Generell ist es so das ich bis jetzt immer alle Objekte durchgegangen bin und selbst bei einer größeren Menge an Objekten keine zeitlichen Probleme hatte, aber als ich gestern mal wieder Lemmings gespielt habe, kam in mir die Frage auf, ob das auch effektiver zu lösen ist. Wenn man tatsächlich 10000 (oder mehr) dieser Objekte hat und im ungünstigsten Fall das letzte der Liste anklickt, dann muss man alle davor sinnloserweise durchgehen. Und wirklich effektiv ist das ja eben nicht. |
||
|
<- Ich liebe dieses Smilie !
|
||
|
|
XeresModerator |
Do, Feb 23, 2012 16:06 Antworten mit Zitat
|
|---|---|---|
|
Wenn man wirklich so viele Objekte verwaltet, führt kaum ein Weg an übergeordneten Strukturen wie Sektoren oder einem Baum vorbei.
Oooder gleich BlitzMax benutzen, da kann man die Objekte & Listen selbst verwalten. |
||
|
Win10 Prof.(x64)/Ubuntu 16.04|CPU 4x3Ghz (Intel i5-4590S)|RAM 8 GB|GeForce GTX 960
Wie man Fragen richtig stellt || "Es geht nicht" || Video-Tutorial: Sinus & Cosinus THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld) |
||
|
|
Bura.Tino |
Do, Feb 23, 2012 16:12 Antworten mit Zitat
|
|---|---|---|
|
Meine Frage bezog sich nicht auf eine bestimmte Programmiersprache, sondern war eher allgemeingültig gemeint.
Wie machst Du das denn, wenn Du sowas programmierst ? Gehst Du auch die ganze Typestruktur durch ? |
||
|
<- Ich liebe dieses Smilie !
|
||
|
|
XeresModerator |
Do, Feb 23, 2012 16:35 Antworten mit Zitat
|
|---|---|---|
|
Ich weiß nicht, ob man da eine allgemeingültige Antwort geben kann.
In BB ist es die simpelste Methode, alle Einträge durch zu gehen, wenn es keine weiteren Abhängigen Strukturen gibt. Wenn es eine Parent-Child Beziehung gibt, kann man alle Childs hinter einem Parent einfügen und nur die paar Objekte kontrollieren (vorausgesetzt, man kennt das Parent). Das ist mit Positionen recht einfach um zu setzen. |
||
|
Win10 Prof.(x64)/Ubuntu 16.04|CPU 4x3Ghz (Intel i5-4590S)|RAM 8 GB|GeForce GTX 960
Wie man Fragen richtig stellt || "Es geht nicht" || Video-Tutorial: Sinus & Cosinus THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld) |
||
|
|
Bura.Tino |
Do, Feb 23, 2012 16:47 Antworten mit Zitat
|
|---|---|---|
|
Aber selbst in einer Parent-Child-Beziehung ist es schwierig das Parent-Objekt zu kennen.
Wenn wir uns das Tor wo die Lemminge rausfallen als Emitter und die Lemminge selbst als Partikel vorstellen, und es mehrere dieser Emitter geben würde, so wäre das noch umfangreicher, weil man in einer Schleife alle Emitter und in einer untergeordneten Schleife alle Partikel durchgehen müsste. Vom Prinzip her würde man dann auch alle Objekte durchgehen müssen, aber man hätte mehr Schleifen. Das wäre sozusagen noch komplizierter. |
||
|
<- Ich liebe dieses Smilie !
|
||
|
|
XeresModerator |
Do, Feb 23, 2012 16:58 Antworten mit Zitat
|
|---|---|---|
|
Noch komplizierter nicht, höchstens genauso kompliziert. Ob du 25 Objekte oder 5 Parents mit je 5 Childs hast, ist ja egal.
Bei den Lemmingen würde ich darum Sektoren benutzen. Wenn sie in einen rein laufen, werden sie diesem zugeordnet, und mit den Mauskoordinaten kann man den richtigen Sektor bestimmen. |
||
|
Win10 Prof.(x64)/Ubuntu 16.04|CPU 4x3Ghz (Intel i5-4590S)|RAM 8 GB|GeForce GTX 960
Wie man Fragen richtig stellt || "Es geht nicht" || Video-Tutorial: Sinus & Cosinus THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld) |
||
PhillipK |
Do, Feb 23, 2012 17:17 Antworten mit Zitat
|
|
|---|---|---|
|
Sektoren wären auch mein erster ansatz.
Das durchiterieren mag zwar schnell genug sein, aber ich bin ein mensch, der gerne bastelt. Deshalb halte ich mir mögliche "Schnittstellen" offen. Da man eh pro Schleifendurchlauf einmal alle objekte durchgehen muss (zeichnen, updaten, what ever), oder zumindest alle 2-3 schleifendurchläufe, kann man auch grade 2 arrayzugriffe wagen. Aus dem "alten Array" einfach direkt rauslöschen (hierzu bietet sich zb eine Linked List an) und in den neuen reinschmeißen. Wenn du nun einen Mausklick machst, mappst du die Koordinaten des Klicks auf deine Sektoren und kommst an die Spezifischen inhalte. Statt 10.000 objekte musst du am ende vielleicht nurnoch 1.000 stück durchgehen und den "nächsten" zum klick rausfinden. Im worst Case sind alle objekte trotzdem in diesem einen Sektor, so muss der Computer die array zugriffe verarbeite und _trotzdem_ alles durchsuchen. Aber naja, wenn das passiert, läuft was schief
|
||
|
|
Bura.Tino |
Do, Feb 23, 2012 18:11 Antworten mit Zitat
|
|---|---|---|
|
Unterteilungen wären natürlich eine Möglichkeit. Heutzutage ist es ja kein Problem tausende von Objekten durchgehen zu können. Aber damals war das wohl eine Höchstleistung für die Computer.
Ob das damals auch mit Unterteilungen gemacht worden ist ? |
||
|
<- Ich liebe dieses Smilie !
|
||
|
BladeRunnerModerator |
Do, Feb 23, 2012 18:54 Antworten mit Zitat
|
|---|---|---|
Man hatte damals ja selten mehr als ein paar Dutzend Lemminge, und das ist selbst für einen programmierbaren Taschenrechner noch nicht zuviel 
|
||
|
Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92 |
||
|
|
Bura.Tino |
Do, Feb 23, 2012 19:04 Antworten mit Zitat
|
|---|---|---|
| Ich bin mir grad nicht sicher, aber ich glaube es waren damals maximal 100 Lemminge. Aber wenn man bedenkt das die damals nicht nur ausgewählt worden sind, sondern auch viele andere Aufgaben abarbeiten mussten, dann sind 100 Objekte für einen 286er schon ziemlich viel. | ||
|
<- Ich liebe dieses Smilie !
|
||
- Zuletzt bearbeitet von Bura.Tino am Do, Feb 23, 2012 19:56, insgesamt einmal bearbeitet
|
|
BladeRunnerModerator |
Do, Feb 23, 2012 19:13 Antworten mit Zitat
|
|---|---|---|
| Glaube mir, die Verarbeitungsgeschwindigkeit für 100 Objekte ist da nicht das Problem. Lemmings und ähnliches gab es auch auf dem C64 (1MHz, ca. 40kB RAM für Programme nutzbar), und wenn es da eine Limitierung gab war es der Speicher, nicht die Rechengeschwindigkeit. Selbst 1MHz bedeutet ja noch 1 Million Operationen pro Sekunde. Du hättest, vorausgesetzt dein Programm hat nichts anderes zu tun, pro Objekt und Sekunde 10.000 Zyklen zur Verfügung, das sind 2500-5000 Assembler-Operationen. Da geht Dir der Arbeitsspeicher für die Befehle schneller aus als die Rechenkapazität. | ||
|
Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92 |
||
|
|
Bura.Tino |
Do, Feb 23, 2012 19:55 Antworten mit Zitat
|
|---|---|---|
|
Stimmt. Da hast Du natürlich Recht.
Eigentlich ging es ja auch eher um eine Alternativlösung. Wenn man beispielsweise eine Linie hat die durch zwei Punkte vorgegeben ist, so kann man ja auch die Linie zu einem Punkt bestimmen und anders herum die Punkte die zur Linie gehören. Deswegen dachte ich, daß es vielleicht eine Möglichkeit gibt bei der man nicht alle Objekte (oder einen Teil davon) durchgehen muss. |
||
|
<- Ich liebe dieses Smilie !
|
||
|
|
BladeRunnerModerator |
Do, Feb 23, 2012 19:58 Antworten mit Zitat
|
|---|---|---|
| Jop, gibt es ja schon (s.o.), es ist halt immer nur die Frage nach dem Kosten-Nutzen-Verhältnis. | ||
|
Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92 |
||
|
|
Bura.Tino |
Do, Feb 23, 2012 20:48 Antworten mit Zitat
|
|---|---|---|
| Aber selbst bei oberem Beispiel muss man ja einige der Objekte durchgehen. | ||
|
<- Ich liebe dieses Smilie !
|
||
|
|
XeresModerator |
Do, Feb 23, 2012 20:59 Antworten mit Zitat
|
|---|---|---|
| Wenn es nicht gerade ein Array ist, dass nur exakt ein Objekt beinhalten kann, muss man immer noch ein paar andere Objekte überprüfen. | ||
|
Win10 Prof.(x64)/Ubuntu 16.04|CPU 4x3Ghz (Intel i5-4590S)|RAM 8 GB|GeForce GTX 960
Wie man Fragen richtig stellt || "Es geht nicht" || Video-Tutorial: Sinus & Cosinus THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld) |
||
|
|
Bura.Tino |
Do, Feb 23, 2012 21:07 Antworten mit Zitat
|
|---|---|---|
|
Ja eben. Das dachte ich mir.
Kommen wir also zu der Feststellung, daß man ein angeklicktes Objekt nicht besser identifizieren kann, als alle (oder einige) Objekte durchzugehen.
|
||
|
<- Ich liebe dieses Smilie !
|
||
Übersicht
BlitzBasic Allgemein
Powered by phpBB © 2001 - 2006, phpBB Group