## 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-----

- Antworten:
  - AW: [ct-bot] Erweiterung Pfadplanung
    - From: Frank Menzel

- Referenzen:
  - AW: [ct-bot] Erweiterung Pfadplanung
    - From: Frank Menzel

- Voriger (Datum): AW: [ct-bot] Erweiterung Pfadplanung, Frank Menzel
- Nächster (Datum): AW: [ct-bot] Erweiterung Pfadplanung, Frank Menzel
- Voriger (Thread): AW: [ct-bot] Erweiterung Pfadplanung, Frank Menzel
- Nächster (Thread): AW: [ct-bot] Erweiterung Pfadplanung, Frank Menzel
- Indizes:
  - Datum
  - Thread