Sichtbarkeitsprüfung : minimaler Aufwand?

[Janoscharlipp]

Hallo,
ich bin seit längerem mit einem Spiel beschäftigt, bei welchem sich der Spieler durch einen Level mit Gegnern durchschleichen muss. (wie Commandos und Desperados)

Mein Problem ist nun, dass ich ständig prüfen muss, ob der Spieler von einem Gegner gesehen wird.

Es gibt nGegner Gegner, nHindernisse Sichthindernisse und einen Spieler.

Bisher probiere ich für jeden Gegner jedes Hindernis durch, wenn das Hindernis im Weg ist, höre ich auf, da der Gegner den Spieler nicht sieht.
Das ergibt aber, im schlimmsten Fall, nGegner * nHindernisse Sichtbarkeitsprüfungen. Bei 10 Gegnern und 100 Hindernissen macht das schon 1000 Prüfungen pro Frame, was natürlich nicht machbar ist. Zumal die Hindernisse von ganz verschiedener Natur sein können, z.B. Säulen, Wände, Blöcke...

Hat jemand eine Idee, wie ich mir Sichtprüfungen sparen könnte?

Die Hindernisse sind durch Punkte und oder Radien definiert.
Die Sichtprüfung guckt erst, ob der Gegner nah genug ist (das Sichtfeld ist in die Tiefe begrenzt) und in die richtige Richtung blickt (das Sichtfeld ist seitlich begrenzt).
Sind diese beiden Bedingungen erfüllt, prüfe ich mathematisch (kein hitTest) auf Schnittpunkte von der Geraden (Gegner-Spieler) und des Hindernisses.

bin für jeden Vorschlag dankbar,

Janosch

[hgseib]

den spielplan in ein schachbrett aufteilen. in diesem 2D-Array trägst du ein (jede zelle kann selbst wieder ein array mit mehreren einträgen sein), wer sich in welcher zelle befindet.
zum exaten testen prüfst du jetzt nur noch die objekte die sich in die umliegenden zellen eingetragen haben.

-------
a sieht b ist das selbe wie b sieht a
und blick auf sich selbst ist blödsinn,
somit gibt es nicht n * n prüfungen.
trage deine prüfungen in ein 2d-Array ein:
x sind die nicht doppelten prüfungen

0 A B C D
A 
B X
C x x
D x x x

[Janoscharlipp]

vielen Dank für deine Antwort.

Allerdings finde ich das nicht so schön, da diese Einteilung in ein Raster genau meiner anfänglichen Vorstellung widerstrebt; alles komplett mathematisch, Wände z.B. werden nicht auf ein Raster gebaut, sondern durch 2 (oder mehr) Punkte definiert, Gegner finden ihre Wege ohne Wegpunkte...
Natürlich gingen diese Sachen nicht durch das Raster verloren, aber einfach vom Prinzip her....

Gibt es keine verschickte Methode, wie man die ganzen Daten (position Gegner, Wände, Spieler) verwurschteln kann, und dann nur noch ablesen muss?
(ich kenne das aus der Bilderkennung...man führt mit jedem Punkt EINE Transformation durch, und liest einfach ab) (z.B. um Geraden zu finden)

[Janoscharlipp]

was deine Tabelle angeht.
Meine Sichtprüfung ist ja kein x sieht y Test, sondern ein x sieht Spieler trotz y Wände Test.
Das kann man nicht vergleiche, oder??

[hgseib]

"..ich kenne das aus der Bilderkennung.."
ist ja hinlänglich bekannt, wie toll das funktioniert ;-)))

"..man führt mit jedem Punkt EINE Transformation durch, und liest einfach ab.."
jo, aber ganz gewiss nicht mit der speed von flash :-)))))
ausserdem frage ich mich, warum spieleentwicklungen jahre dauern, wenn man doch nur eine Transformation durchführen muss und fertig :-)

eine universelle, alles umfassende gesamtlösung gibt es bestimmt nicht.

das mit dem schachbrett musst du nicht so wörtlich nehmen. wer sagt denn, das der bereich A1 genauso gross sein muss wie B1?
die frage ist halt, kannst du den gesamten spielplan in bereiche aufteilen? Wer z.b. im stockwerk 1 steht kann einfach niemandem im stockwerk 2 sehen usw. Ziel ist es möglichst viele unnütze Tests nicht zu machen.

berechne im 1. frame alle gegner, im 2. frame alle eigenen spieler. wenn du wichten kannst: wer weit weg ist, der wird seltener getestet. spart alles zeit ein. flash ist halt kein C++ :-(

ansonsten musst du zusehen, ob du sachen vorberechnen kannst? und das in tabellen hinterlegen. wie beim schachspielen: "diese stellung hatte doch 1833 der bulgarische landesmeister mit einem bauer schlägt turm beantwortet".
übersetzt: wenn eine figur 5 meter vor der türe steht. dann hast du in einer tabelle erfasst, welche objekte von dieser position aus gesehen werden können. das muss ja nicht von jedem quatratzentimer aus neu erfasst werden. hauptsache es reduziert die gesamtabfragen.

[Janoscharlipp]

Bei der Bilderkennung funktioniert das 1. ausgezeichnet, und 2. ist es verdammt schnell.

Wie wäre es z.B., wenn ich erstmal alle Wände durch gehe, und für jede Wand die Winkel der links und rechts begrenzenden Geraden berechne, und in ein Array schreibe.
Dann hätte ich sowas wie ein Array in dem die "Schattenbereiche" drinn stehen. Allerdings sind Winkelberechnungen langsam, und irgendwie muss ich auch noch die Entfernung zum Spieler mit einbeziehen.

Kann ich denn nicht irgendwie einen Großteil der Wände aussortieren? Die meisten Wände liegen ja sowiso im "Schatten" von anderen.

Nach welchem Kriterium kann ich denn die Wände sortieren? Das würde mir ja auch helfen, wenn ich nicht für jeden Gegner mit JEDER WAND testen müsste.
Die Entfernung der Endpunkte ist leider kein Merkmal, da ja z.B. ein Punkt bei (vom Spieler aus gesehen) 3 Uhr liegt und einer der bei 9:01 Uhr liegt sehr weit entfernt sein können, und trotzdem einen großen Einfluss haben.

hmmm, ich kann nicht glauben, dass das nicht schneller geht.


Wenn ich das doch mit dem Raster mache, wie meintest du das, mit der unterschiedlichen Größe der Felder? Woran sollte ich festmachen, ob eine Spalte breit oder schmal wird?

[hgseib]

"..Bei der Bilderkennung funktioniert das 1. ausgezeichnet.."
cool! du hast also ein programm, das erkennt, ob irgend ein bild einen baum darstellt? damit bist du der weltbeste programmierer. oder was erkennst du da?
der ganze ramsch liegt auf dem selben haufen wie: handschrifterkennung, gesichter erkennung usw. das geistert immer mal durch die presse, wie toll das doch alles funktioniert... ich kenne keine einzige anwendung, die dauerhaft und erfolgreich in der praxis eingesetzt wird! höchstens ein paar superspezielle spazialanwendung: ein handhabungsautomat dreht eine schraube richtig herum. toll, das kann ein seit 200jahren bewährter mechanischer "rüttler" auch: 5000 schrauben pro minute - da guckt er aber, der handhabungsautomat ;-)

"..und 2. ist es verdammt schnell.."
das glaube ich. nur, das problem: Flash ist es nicht :-(

"..Allerdings sind Winkelberechnungen langsam.."
das hingegen glaube ich nicht. ganz, ganz früher als es noch keine coprozessoren gab waren für eine sinus/cosinus- berechnung 1000 tacke notwendig. heutzutage sind in jedem prozessor mehrere mathe-prozessoren integriert und so eine berechnung kostet auch nur einen einzigen tackt.


so, genug gewitzelt. nun zum praktischen teil:

"..Nach welchem Kriterium kann ich denn die Wände sortieren.."
hab ich was von sortieren gesagt? also du hast so ein hässliches ;-) ballerspiel und willst jetzt wissen, wen du abknallen kannst?

so in der richtung würde ich das mal probieren:
leg über dein spielfeld ein gedachtes schachbrett und trage ein, welche objekte welche felder berühren (mehrfach nennung ist also flicht).
bewegliche objekte tragen sich selbst ein, in welches feld sie gerade gehen.

steht einer auf B2 und sieht nach 12uhr, dann ist zu testen mit allen objekten in A1, B1, C1
steht einer auf B2 uns sieht nach 6uhr, dann ist zu testen mit allen objekten in C1,C2,C3 und eventuell noch D2 (je nach blickweite und je nachdem, wie fein du deine maschen gestrickt hast)

die eintragungen müssen nicht exakt sein, es geht nur darum, die gesamtmenge zu reduzieren.

hinzu kommt. z.b. B1 nach 12uhr: da stehts du immer vor einer wand (es seih denn eine geschlossene welt d.h. wer oben rausfällt, fällt unten wieder rein). sinngemäss wäre in einer tabelle festzulegen, wenn z.b. B2 von B3 durch eine mauer getrennt ist.
hab ich schon verstanden "du willst mit dem kopf durch die wand" und kein karomuster. dann "verzerre" die eckpunkte des schachbrettes auf deine objekte drauf. allerdings hast du damit wieder einen erhöhten rechenaufwand.

[Janoscharlipp]

Hallo,

danke für deine Antwort, auch wenn du den 1. Teil hättest weglassen können.
Wenn ich sage, das es gut funktioniert, dann meine ich das auch so. Die Erkennung eines Baumes hat nichts, aber auch garnichts, mit dem Sichtcheck zu tun.
Die Erkennung einer Geraden z.B. aufgrund von mehreren markanten Punkten schon eher. Und diese funktioniert (ich wiederhole mich) ausgezeichnet. Auch die Erkennung von Kreisen basiert auf solchem geometrischem Herumwurschteln, an dessen Ende alles (selbst für den PC) ganz klar ist.

Was die Winkelfunktionen angeht, dachte ich bisher, dass Flash schlicht nicht auf die prozessorinternen Funktionen zugreift, sondern diese emuliert. (Kompabilität...)
Ich habs aber mal gebencht, und es stellte sich heraus, dass Math.sin schneller als die Funktion function(n){return n*2;} ist, jedoch x = Math.sin(i); langsamer als x = i*2; ist.
Die Sinusfunktion ist also sehr schnell implementiert, sogar schneller als ein normaler Funktionsaufruf.

"hab ich was von sortieren gesagt?"
Du hast nichts davon gesagt, ich aber schon.

"also du hast so ein hässliches ;-) ballerspiel und willst jetzt wissen, wen du abknallen kannst?"
Was du hier ausdrücken willst kann ich beim besten Willen nicht nachvollziehen.

Es geht, wie ich anfangs sagte, darum zu überprüfen, ob der Spieler von Gegnern gesehen wird. (ob ich einen Gegner abschießen kann, ist eine Prüfung, die fällt nicht so ins Gewicht)

Wenn ich z.B. die Wände vom Spieler aus gesehen auf einen Kreis um die ganze map projeziere, habe ich ein Bild, an dem ich leicht ablesen kann von wo aus der Spieler sichtbar ist. Leider geht dabei wie gesagt, die 2. Dimension komplett verloren.
Genauer:
Ich erstelle ein Array, z.B. mit 360 Feldern.
Für jede Wand berechne ich den linken und den rechten Grenzwinkel (vom Spieler aus gesehen) und schreibe in alle Felder des Arrays zwischen diesen beiden Winkeln die Entfernung der Wand auf diesem Winkel zum Gegner.

view = new Array(360);
for(walls)
{
links = //linker Winkel;
rechts = //....;
for(i von links nach rechts)
{
view[i] = // Abstand der Wand bei diesem Winkel;
}
}

Dann müsste ich noch beachten, dass Wände die weiter weg sind, die näheren nicht überschreiben.

Der Sichtcheck ist dann denkbar einfach: Ich berechne den Winkel zu einem Gegner und seinen Abstand zum Spieler, wenn der Abstand der im view-Array unter diesem Winkel steht kleiner als der Gegner-Spieler-Abstand ist, besteht kein Sichtkontakt.

Leider ist das jetzt auch nicht schnell...aber eben vom Prinzip her.


Und zum Raster.
Ich habe einfach mal beide Methoden auf irgendwelche Wände angewendet, und die von den Geraden betroffenen Feldern mit Farbe gefüllt.
Aber irgendwie blick ich jetzt nicht, wie ich das Ergebnis interpretieren soll.
Ist es das Ziel, sowenig wie möglich Felder zu haben?
Oder so wenig wie möglich Fläche mit den Feldern abzudecken?
Bietet das dynamische Raster überhaupt irgendeinen Vorteil?

Ich habe das .fla mal angehängt, man kann dort die einzelnen Ebenen ein und ausblenden (aber das brauche ich wohl nicht zu sagen...)

Egal welches Raster man verwendet, jedenfalls werden die Wände sehr effektiv ausgewählt, das scheint wirklich der Königsweg zu sein.
Aber das Prinzip *schluchz*

EDIT: Anhang wie immer vergessen...

[hgseib]

du sprachst von "Bilderkennung". das ist ein ziemlich eindeutiger begriff.

"..Was die Winkelfunktionen angeht, dachte ich bisher, dass Flash schlicht nicht auf die prozessorinternen Funktionen zugreift, sondern diese emuliert.."
??? also ganz ganz früher hat man einen sinus durch ein polynom n.ten grades genähert = je berechnung 10 multiplikationen und 10 additionen. das ist nun also wirklich prähistorisch. ich kenne natürlich nicht den quellcode von flash. aber alle gehören an die wand gestellt und erschossen, wer heutzutage noch einen sinus per iteration ermittelt.
deine zeitmessung hat nicht unbedingt etwas zu sagen. das ganze "drum herum" braucht gewiss 10.000mal länger als die eigentliche berechnung. ist flash ein interpreter oder ein compiler? wann und wie oft wird zeit verwendet um die grafik zu updaten (das hauptgeschäft von flash) usw.
ich kenne es von anderen problemen her, das man weder mit der stoppuhr noch mit getTime reproduzierbare zeiten erziehlen kann. verändere mal irgendwas und plötzlich ist die zeit viel zu schnell oder viel zu langsam im vergleich zur 1. messung.

methode:
z.b. 3D- render-programme machen genau das, was du machen willst. es gibt zwar kugeln und würfel usw. intern ist aber alles in polygone gewandelt. ein computer (aber das weisst du ja selbst) ist schnell, aber nicht intelligent. der mensch kann ein bild erkennen !!! und daraus nutzen ziehen. der computer erkennt garnichts - er rechnet stur alles durch. unterschiedliche geometriene bedeuten nur programmfehler.

du kannst dich auf 2D beschränken. somit ist alles (auch kreise!!) in linien umzuwandeln. je nach form von deinen wänden/ hindernissen musst du diese durch die randlinien darstellen. jetzt hast du es nur noch mit personen == punkten und hindernisse == linien zu tun.
person A zu person B ist eine linie (die koordianten zählen - ein winkel spielt überhaupt keine geige) und du musst diese linie mit allen anderen linien auf überschneidung testen. gibt es keine überschneidung, dann können die sich sehen.
das ist dein universeller, einfacher algoritmus. sowas kannst du in C++ programmieren. in flash wirst du damit vermutlich keine freude haben?
(und ich gehe einmal davon aus, das du KEINE spiegelnde wände hast ;-)


"..Und zum Raster..."
sorry, da blicke ich auch nicht durch, was das sein soll und was du dir davon versprichst :-(
und wo hast du denn die idee mit der 360 grad projektion her?

[hgseib]

was hällst du den davon?
und die einschränkung mit dem blickwinkel wirst du wohl selbst ergänzen können.

[Janoscharlipp]

zum Sinus...
guck mal in den Flash MX 2004 Ordner, untern en\configuration\actionscript.
Dort findet sich bei mir eine Datei: AsMath.xml
In dieser Datei stehen so Sachen wie:

<actionscript_math>
  <function name="sin">
    <![CDATA[
      set(x, X-int(X/2PI)*2PI);
      set(x3, 1);
      if (X<0) {
        set(x3, -1);
        set(x, -X);
      }
      if (X>PI) {
        set(x3, -X3);
        set(x, X-PI);
      }
      if (X>PI/2) {
        set(x, PI-X);
      }
      set(x2, X*X);
      X3*X*(1-X2*(RF3-X2*(RF5-X2*(RF7-X2*(RF9-X2*RF11)))));
    ]]>
  </function>
  ...

Auch für alle anderen Math-Funktionen gibt es dort solche Nährungsfunktionen...

Mein ergebnis war ja auch gerade, das das Drumherum, nämlich der Funktionsaufruf, länger braucht, als die eigentliche Funktion. Das ist doch ein zufriedenstellendes Ergebnis, oder nicht? Zumal es auch reproduzierbar ist...
Solange Flash in einer Schleife steht gibt es keine anderen Einflüsse wie Bildaufbau und ähnliches...
Trotzdem können sich die Ergebnisse voneinander unterscheiden, aber das Zeitverhältnis zwischen sinus-Funktion und anderer Funktion bleibt fast gleich.


So wie du das alles Beschreibst, habe ich das ja auch schon alles gemacht. Dazu ein paar Auszügewahrscheinlich zerhackts die ganze Formatierung...

	private function lineCrossesCircle(
		x1:Number,y1:Number,
		dx:Number,dy:Number,
		lineLength:Number,
		x:Number,y:Number,
		radius:Number
	):Boolean
	{
		var dx2 = x - x1;
		var dy2 = y - y1;

		var newBaseX:Number = Math.abs(dx * dy2 - dy * dx2) / lineLength;
		var newBaseY:Number = (dx * dx2 + dy * dy2) / lineLength;

		if(newBaseX <= radius)
		{
			if((newBaseY > 0) && (newBaseY < lineLength))
			{
				return true;
			}
		}
		return false;
	}

	private function lineCrossesLine(
		x1:Number,y1:Number,
		x2:Number,y2:Number,
		dx:Number,dy:Number,
		x3:Number,y3:Number,
		x4:Number,y4:Number
	):Boolean
	{
		if(
			((x3 - x1) * dy - (y3 - y1) * dx)*
			((x4 - x1) * dy - (y4 - y1) * dx) < 0)
		{
			dx = x4 - x3;
			dy = y4 - y3;

			if(
				((x2 - x3) * dy - (y2 - y3) * dx)*
				((x1 - x3) * dy - (y1 - y3) * dx) < 0)
			{
				return true;
			}
		}
		return false;
	}

Wie du siehst, möchte ich aber Kreise auch als Kreise behandeln, und nicht irgendwie aus Linien oder Dreiecken zusammenstückeln.
Ebenso werden 4-Ecke mithilfe von ihren Diagonalen geprüft, für alles andere verwende ich Linien.
Abgesehen von der Tatsache, die diese Funktionen für jedes entsprechende Hindernis einmal aufgerufen werden, sind sie schon schnell, nur eben: Die Masse machts.
Und eben das ist mein Problem.

Vielen Dank für dein Flash. Allerdings fehlt dort doch gerade das, worum es mir geht: Das Raster.

Ich werde mal vergleichen, welche Methode schneller ist, deine fLinieLinie oder meine lineCrossesLine. Ifs sind sehr schnell...vermutlich kommt es darauf an, wie lang die Wände sind.
Bei kurzen Strecken fliegen bei deiner Methode fast alle in einem der ersten 4 ifs raus, bei langen Strecken wird öfter die fInnerhalb aufgerufen, was recht langsam sein dürfte.

Nein, keine spiegelnden Wände.. Obwohl?

Das Raster war doch deine Idee!?
Ich wollte überprüfen, ob es sinnvoll ist, das Raster dynamisch anzupassen, oder ob es besser ist, einfach ein regelmäßiges Raster drüber zu legen.
Nur eben weiß ich nicht, wie ich jetzt das Ergebnis deuten soll.

Die Idee mit der Projektion ist auf meinem eigenen Mist gewachsen, wie so viele andere untaugliche Ansätze...

[hgseib]

hin und wieder muss ich ja auch noch ein bisschen arbeiten.
aber sowas lässt einen nicht in ruhe. ist wie eine sucht ;-)

hier mal eine variante mit "optimiertem" wand-tests:
bei so wenig wänden machts natürlich nicht all zu viel sinn
und die bestimmung, welche wände man von einem bereich aus nicht sehen kann muss man wohl per hand (also selbst) vornehmen. es geht ja nur ums prinziep:

im schachbrettmuster "weiss" jeder bereich von welchen wänden er umzäunt ist.
schachbrettmuster ist nicht so eng zu sehen ;-) und kommt auch sehr stark drauf an, wie die wände verteilt sind. bei vielen rechteckigen bereichen kann die zugehörigkeit halt einfach berechnet werden. bei unregelmässigen formen -wie hier angedeutet- ist der bestimmungsaufwand natürlich grösser. hat alles vor und nachteile.

-----------------
"..zum Sinus.."
da hast du aber einen blindgänger ausgegraben :-))) leg das ding mal raus und prüfe, ob flash immer noch sinus berechnet. ich hatte mal versucht, damit die math-classe zu erweitern. so gehts aber nicht.
der set- befehl lässt mich vermuten, dass das im zusammenhang mit einer dialogbox benützt wird. aber wo weiss ich auch nicht.

"..wahrscheinlich zerhackts die ganze Formatierung.."
das bisschen script besagt natürlich garnichts. der schnitt einer linie mit einem kreis ergibt 2 schnittpunkte. die berechnest du nicht. also ist das was du da machst nur eine teillösung, deren zusammenhang in deinem programm ich natürlich nicht beurteilen kann.

"..möchte ich aber Kreise auch als Kreise behandeln.."
jede sonderform: waagrechte/ senkrechte linien, nicht gedrehte rechtecke usw. sind natürlich einzeln besser zu berechnen als schräge linien.
aus erfahrung weiss ich halt, das jede ausnahem auch ihre eigenen fehler in der programmierung mit sich bringt und jede ausnahme muss auch als solche erkannt und behandelt werden. dem computer ist der "einheitsbrei" halt lieber.
und letztendes ist das so flexibler. was machst du z.b. mit ellipsen usw. jede neue form neue programmteile?

"..wie lang die Wände sind.."
die länge ist vollkommen wurscht. ich berechne, ob es einen schnittpunkt gibt zwischen der wandlinie und der linie person0-personN.
die 4 ifs (habe ich in der neuen version auch optimiert, dafür kostet es mehr speicherplatz :-) testen, ob die linien sich überhaupt schneiden können.

".. Das Raster war doch deine Idee!?.."
DAS DA??? nööö. Ich hatte geschrieben mehrere objekte je celle und du hast gemacht mehrere cellen je objekt. ich hoffe, der anhang zeigt es klarer.

"..Idee mit der Projektion.."
was ich nicht verstanden habe ist: was soll das bringen? die figuren bewegen sich laufend. also musst du auch das laufend neu berechnen. es würde etwas bringen, wenn die person (und alle anderen auch) stehen bleibt und sich nur im kreis dreht - dazu kann ich natürlich nichts sagen. ich kenne deine spielregeln nicht.

[Janoscharlipp]

also von Hand wird da nichts gemacht, schließlich ist ja durch die Wände alles festgelegt, also kann man es auch berechnen.

Jep der Sinus in dem XML ist irgendwie verwendungslos, zumindest wird das nicht im Math-Objekt verwendet.
Das zeigt schon allein das Tempo der Math-Methoden.

Die lineCrossesCircle Funktion tut genau das, was ich brauche. Sie gibt zurück, ob das runde Objekt im Sichtstrahl steht, oder nicht.
Du gibst bei deiner lineline-Funktion auch nur true oder false zurück, nicht den Schnittpunkt.

"was machst du z.b. mit ellipsen usw. jede neue form neue programmteile?"
Für Ellipsen vielleicht noch ne Form, wenn es überhaupt Ellipsen gibt, keine Ahnung, wo man die brauchen könnte. Sonst wie gesagt auch Linien. (bis auf 4-Ecke)

Die Länge der Wände spielt schon eine Rolle.
Denn wenn die Wände lang sind, dann "versagen" deine ifs, und du musst wirklich den Schnittpunkt errechnen, und das ist langsam.
Deine Ifs bilden die Box um die Linie, und gucken, ob sich die Boxen der 2 Linien irgendwo berühren. Wenn du aber eine große, am besten noch diagonale Wand hast, dann hat diese eine große Box->die Sichtlinien verlaufen oft in ihr.
Wenn dies der Fall ist, prüfst du auf nen Schnittpunkt, und das nicht grade schnell.

Ok, jetzt verstehe ich, was du mit Raster meintest. Allerdings "bündelst" du deine Wände jetzt per Hand, glaubst du man könnte das automatisieren?

Die Projektion hat den Vorteil bzw. die Eigenschaft, dass nun nicht mehr (Anzahl der Wände) * (Anzahl der Gegner) geprüft werden muss, sondern nur noch (Anzahl der Wände) + (Anzahl der Gegner).
Bzw. es muss nur noch pro Wand ein Vorgang (das geometrische Rumwurschteln) durchgeführt werden, und dann nochmal mit jedem Gegner ein Test gemacht werden.
Du musst bei dir (von der Optimierung abgesehen) für alle Personen jede Wand durchprobieren (bis eine im Weg ist) (Wände * Gegner Prüfungen im schlimmsten Falle).

Zu den Spielregeln:
Alle laufen frei rum.

[hgseib]

"..lineline-Funktion auch nur true oder false zurück, nicht den Schnittpunkt.."
die routinen habe ich von anderen projekten rüberkopiert und zurechtgebogen. ich hatte nicht vor "deine" arbeit zu machen ;-)

"..Allerdings "bündelst" du deine Wände jetzt per Hand.."
irgendwie geht alles. allerdings, man muss "sehen", das man von jedem punkt des bereiches in jede richtung sehen kann - nicht einfach. hierzu fehlt mir auch das wissen wie deine kanten verteilt sind (ich wills garnicht wissen ;-) sind das wenige lange oder viele, viele kurze. wild verstreut oder gibt es da gewisse ordnungen?
wie ist das verhältnis von gesamtspielplan zur "sichtweite". eine auswahl auf die sichtweite beschrängt wäre zwar nicht 100%ig optimal, aber das liese sich auf jeden fall programmieren.
p.s. es kommt noch schlimmer ;-)
die blickrichtung habe ich ja garnicht berücksichtigt. also wird das nicht ein array pro bereich sondern z.b. vier: welche wände sehe ich wenn ich von diesem bereich aus noch oben sehe, nach links, ...
oder wenns ein ereignisreicher bereich ist 8 richtungen oder mehr?

"..Die Projektion hat den Vorteil bzw. die Eigenschaft.."
"meine" bereiche werden (wenn überhaupt) ein einzigstes mal bestimmt und gelten dann unverändert immer. durch die einschränkung durch die bereiche kann man die menge drastisch reduzieren und "alle" wände muss ich nur prüfen, wenn die person sichtbar ist. personen, die zu weit weg sind fallen ja auch sofort raus. also sagen wir mal im durchschnitt muss ich nur die hälte der durch den bereich vorgegebenen wände prüfen.
die rundumprojektion ändert sich mit jeder bewegung der person und muss somit jedesmal neu berechnet werden!? sie hat keinen "wiederverwendungs-wert" - oder?

"..Alle laufen frei rum.."
das dachte ich mir schon ;-) wie die hüner.
sehen die "gegner" immer auf die spielfigur oder müssen die auch "suchen"? (dann bracht jeder von denen auch eine eigene rundumprojektion)

[Janoscharlipp]

das will ich auch auf keinen Fall.
Ich wollte nur sagen, dass man die Schnittpunkte schlicht nicht braucht, warum meinst du dann:
"der schnitt einer linie mit einem kreis ergibt 2 schnittpunkte. die berechnest du nicht. also ist das was du da machst nur eine teillösung, deren zusammenhang...".

"hierzu fehlt mir auch das wissen wie deine kanten verteilt sind (ich wills garnicht wissen ;-)"
Die Wände sind im Level wild verteilt. (da weißt dus :P)
Die Blickrichtungen sind frei.

Aber das kommt wie gesagt alles nicht in Frage, der Levelbauer soll sich nicht auch noch damit rumquälen, die Sichtbereiche richtig zu erstellen, soll er sich lieber um Ablauf und Grafik kümmern.

Ich habe ja schon bekannt, dass dein System mit dem Raster effektiver ist, ich wollte dir nur ein Beispiel geben, wie man die Wände * Gegner Überprüfungen auf Wände + Gegner Überprüfungen reduzieren kann.
Das diese bei meinem Beispiel dafür ziemlich aufwändig sind, ändern am Prinzip nichts: aus n * m mach n + m.
Man muss nur die geeignete Betrachtungsweise und damit geometrische Konstrukton (Projektion oder was auch immer) finden.
Vielleicht gibt es diese Betrachtungsweise bei diesem Problem auch nicht, aber danach suchen kann man ja...

Der Wiederverwendungswert meines gedachten Projektionsarrays war gleich 0. Darum ging es auch nicht.

Die Gegner suchen nicht, sie langweilen sich, oder spazieren rum.

Hier mal der Link zu einer etwas älteren Version, bei den neueren habe ich etwas kaputt gemacht, da ich innendrinn am Umbauen bin.
Beispiel


Ich habe auch mal in deiner 1. Datei das von mir vorgeschlagene Raster eingebaut.
Bei der vorhandenen Anzahl an Wänden ist es langsamer, aber es wird, egal wie viele Wände hinzugefügt werden, nicht mehr wesentlich langsamer werden, da pro Spieler0-SpielerN-Test maximal 2 Wände überprüft werden müssen.
Wenn du im Code die auskommentierten Stellen entkommentierst, siehst du, was gemacht wird.

1. es wird ein Raster über die Map gelegt
2. Wände werden auf allen Feldern, die sie berühren eingetragen
3. Beim Sichtcheck werden nur die Wände geprüft, die sich auf den Feldern zwischen Spieler0 und SpielerN eingetragen haben.

Der größte Performance-Verlust dürfte in der getDir-Funktion zustande kommen.
Diese Funktion ist sowas von schlecht, das hast du wohl noch nie gesehen. Aber ich weiß nicht, wie man an das Problem besser rangeht.
Die Funktion dient dazu, heraus zu finden, welche Felder von einer Strecke berührt werden.
Ich gebe einen Startpunkt vor (ein Endpunkt einer Linie)(der obere) und laufe dann an der Linie entlang, getDir sagt mir immer, zu welchem Feld ich weiterlaufen muss, damit die Strecke am Ende komplett in der von den Feldern belegten Fläche liegt.

Im Anhang die modifizierte Datei.