c't

c't-Projekte - Mailinglisten


[Voriger (Datum)] [Nächster (Datum)] [Voriger (Thread)] [Nächster (Thread)]
[Nach Datum][Nach Thread]

Re: [ct-bot] Erweiterung Pfadplanung

Absender: Timo Sandmann
Datum: Mo, 06.04.2009 12:56:39
In-reply-to: <000001c9b527$68a781d0$0200a8c0@mexpnew>
References: <000001c9b527$68a781d0$0200a8c0@mexpnew>


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi Frank,

was ich meinte ist Folgendes: Wenn ich bei deinem Code

 /*!
+ * Map-Umfeldpruefung ob ein bestimmter Wert compare ab einer Position xy mit Radius r nicht unterschritten wird
+ * @param x			Map-Koordinate
+ * @param y			Map-Koordinate
+ * @param radius	Radius des Umfeldes
+ * @param compare	Vergleichswert, der nicht unterschritten werden darf
+ * @return True wenn alle Felder wenigstens den Vergleichswert haben, False wenn mindestens 1 Feld kleiner dem Wergleichswert ist
+ */
+uint8_t check_value_field_circle(uint16_t x, uint16_t y, int8_t radius, int8_t compare) {
+	int8_t dX, dY;
+	int16_t h = muls8(radius, radius);
+	for (dX=-radius; dX<=radius; dX++) {
+		int16_t dX2 = muls8(dX, dX);
+		for (dY=-radius; dY<=radius; dY++) {
+			if (dX2 + muls8(dY, dY) <= h) {
+				// nur innerhalb des Umkreises
+				if (access_field(x + dX, y + dY, 0, 0) < compare)
+					return False;
+			}
+		}
+	}
+	return True;
+}
+
+/*!
+ * prueft ob innerhalb eines Radius-Umfeldes kein Feld den Vergleichswert unterschreitet; Falls doch sofortiges Ende der Routine;
+ * Hindernis wird mit MAP_RADIUS_FIELDS eingetragen
+ * @param x		Welt-X-Koordinate
+ * @param y		Welt-Y-Koordinate
+ * @param compare	Vergleichswert, der nicht unterschritten werden darf
+ * @return True wenn alle Felder wenigstens den Vergleichswert haben, False wenn mindestens 1 Feld kleiner dem Wergleichswert ist
+ */
+uint8_t check_value_circle(int16_t x, int16_t y, int8_t compare) {
+	uint8_t r;
+	// in Map mit dem Radius um x/y eintragen
+	for (r=1; r<=MAP_RADIUS_FIELDS; r++) {
+ if (!check_value_field_circle(world_to_map(x), world_to_map(y), r, compare))
+		  return False;
+	}
+	return True;
+}

die Funktion check_value_circle() aufrufe, werden die meisten Bereiche des Kreises doppelt und dreifach auf Hindernisse geprüft. Wenn dort im ersten Schleifendurchlauf kein Hindernis war, wird das im zweiten, dritten, vierten, ... Durchlauf aber auch nicht der Fall sein. Wenn man Zahlen in die Schleifen einsetzt, sieht man schnell, dass der Code für einen Kreis mit einem Radius von 6 Pixel 91*pi Vergleiche (und access_field()-Aufrufe) durchführt mit Koordinaten innerhalb dieses Kreises. Solch ein Kreis besitzt aber insgesamt nur 36*pi Pixel => völlig unnötiger Overhead. Dort wo du den Code vermutlich her hast, hat er eine ganz andere Aufgabe: Er ist dazu gedacht, in einem Kreis Hinderniswahrscheinlichkeiten anhand einer (angenäherten) Normalverteilung einzutragen. Für die Auswertung von Map-Daten (zu einem festen Zeitpunkt) ist das Vorgehen aber unsinnig.

Grüße,
Timo

Am 04.04.2009 um 15:15 schrieb Frank Menzel:
Hallo Timo,
die Idee ist, neben dem Ersetzen der fehlerhaften avg-Routine, zu
erkennen ob innerhalb eines gewissen Umkreises zu einem Punkt ein
Hindernis in der Map eingetragen ist und dann sofort abzubrechen und
keinen weiteren Mapzugriff stattfinden zu lassen.
Was Du wiederum  meinst, verstehe ich nicht-hatte die Routine
abgekupfert aus den Zeilen höher.
Gruß, Frank

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Darwin)

iEYEARECAAYFAknZ3+UACgkQDH/BX4067fLkXACfbYBg5hJAJS+Xt5klA6gldpuU
xuMAn2ONBP0J6K28z+3FBkj9f6pw+Jt9
=10g8
-----END PGP SIGNATURE-----