rechteckige Spirale durchlaufen

[DGL-luke]

Hallo,
für Pathfinding will ich mich spiralförmig um einen gegebenen Punkt herum bewegen.
Nach viel Denkarbeit habe ich bereits rausgefunden, dass ich mich an "Eckpunkten" festhalten kann, die eine ganzzahlige Quadratwurzel haben.

Delphi-Quellcode:

function GetSpiralPoint(origin: TPoint; index: Integer):TPoint;
var i,corner:integer;
p:TPoint;
begin
// we're assuming origin to be 0|0 here, translation will be added afterwards
// additionally we assume the spiral to go counter-clockwise and start at -1|0

  corner := ceil(sqrt(index));
  i := sqr(corner);
  
  if (Odd(corner)) then
    begin
      corner := -((corner -1) div 2);
      p.X := corner;
      p.Y := corner;
    end
  else
    begin
      p.Y := corner div 2;
      p.X := p.Y -1;
    end;
end;

Ich berechne hier immer einen Eckpunkt, der vor dem gesuchten Punkt liegt, und will dann weiter rundrum, bis ich zum gesuchten Punkt komme. Wenn der Eckpunkt oben links ist, muss ich noch eins nach links, und dann nach unten, und evtl. dann irgendwann auch wieder nach rechts.
Wenn er unten rechts liegt, noch eins nach rechts und dann entsprechend nach oben usw. usf.

Gibt es da irgendetwas mathematisch elegantes? ich wäre auch zufrieden, wenn ich mir eine Punktliste generieren könnte.

[ichbins]

Delphi-Quellcode:

function spirale(abstand,count,startstep:integer;startpunkt:tpoint;drehsinnnachrechts:boolean):array of tpoint;
var
  richtung,i,step:integer;
  actpos:tpoint;
begin
  richtung:=1;
  actpos:=startpunkt;
  setlength(result,1);
  result[1]:=actpos;
  step:=startstep;
  for i:=2 to count do begin
    case richtung of
      1: actpos.x:=actpos.x+step;
      2: actpos.y:=actpos.y+step;
      3: actpos.x:=actpos.x-step;
      4: actpos.y:=actpos.y-step;
    end;
    step:=step+abstand;
    if drehsinnnachrechts then
    begin
      richtung:=richtung+1;
      if richtung=5 then richtung:=1;
    end else begin
      richtung:=richtung-1;
      if richtung=0 then richtung:=4;
    end;
    setlength(result,length(result)+1);
    result[length(result-1)]:=actpos;
  end;
end;

[DGL-luke]

DANKE! das ist großartig!
ok.... hab das ganze ein wenig umgeschrieben, und es funktioniert.

Delphi-Quellcode:

type PArray = array of TPoint;

function spirale(abstand,count,startstep:integer;startpunkt:tpoint;drehsinnnachrechts:boolean):PArray;
var
  richtung,i,step:integer;
  actpos:tpoint;
begin
  setlength(result,count);
  richtung:=1;
  actpos:=startpunkt;
  result[1]:=actpos;
  step:=startstep;
  for i:=1 to count-1 do begin
    case richtung of
      1: actpos.x:=actpos.x+step;
      2: actpos.y:=actpos.y+step;
      3: actpos.x:=actpos.x-step;
      4: actpos.y:=actpos.y-step;
    end;
    step:=step+abstand;
    if drehsinnnachrechts then
    begin
      richtung:=richtung+1;
      if richtung=5 then richtung:=1;
    end else begin
      richtung:=richtung-1;
      if richtung=0 then richtung:=4;
    end;
    result[i]:=actpos;
  end;
end;
end;

Aber müsste das nicht überlaufen, siehe Kommentare?

EDIT: habe den code jetzt nochmal angepasst.

[ichbins]

ich habe ja for i:=2 to count gemacht, damit es weniger Elemente werden, da das 1. Element ja der Startpunkt ist. Du kannst ja das Element [count-1] verwenden.

Ein dynamisches Array fängt immer bei 0 an und hört bei count-1 auf.


==>

• mach am Anfang result[0]:=actpos
• dann for i:=2 to count
• und dann result[i-1]:=actpos

[DGL-luke]

sodele, funzt jetzt immer noch ;)
Ich weiss ja, dass es bis count-1 geht, aber genau das verletze ich ja und es funzt trotzdem...

werde das gleich mal für die codelib vorschlagen.

ach ja: wenn man das setlength gleich am anfang macht, sollte es schneller gehen.

[ichbins]

mach doch noch die oben vorgeschlagenen Veränderungen. Sone vllt-Zugriffsverletztung is nie gut. Der schreibt eben dann in einen nicht-zugewiesenen RAM-Bereich, und wenn da jetzt eine Variable drinn ist...

Bei mir funzt auch folgendes:

Delphi-Quellcode:

var
  a:array[1..10,1..10] of integer;
begin
  a[87]:=7;
  --> a[8,7]=7
end;

aber es ist immer eine Fehlerquelle.

[DGL-luke]

schon passiert, hab einfach for i:=1 to count-1 gemacht.

EDIT: weitere anmerkungen zur funktion bitte gleich in die codlib-section: http://www.delphipraxis.net/viewtopi...=473530#473530