#1 07.09.2005 07:03:20

firlefanz
GodlikeMember
Ort: Olpe in NRW
Registriert: 31.01.2005
Beiträge: 1035
Web-Seite

Pathfinding

Hallo,

ich hatte ja schonmal das Thema Pathfinding angeschnitten. Habe jetzt hierzu ein freies Unit gefunden.

Vielleicht kennt sich jemand mit dem Algo aus, ich verstehe den Source nicht so ganz.

Code: delphi

function tcommandoform.findpath(start,finish: tpoint; wp: tstringlist): boolean;
var
  a : tpoint;
  i,j,k : byte;
  dx,dy : real;
  bound : tbound;
  bsize : integer;

const kk   : array[0..1] of real=(1.42,1);

function findmin: integer;
var i,n: integer;
begin
  n:=1;
  for i:=1 to bsize do
  if map.tiles[bound[n].x,bound[n].y].fval>map.tiles[bound[i].x,bound[i].y].fval
  then n:=i;
  result:=n;
end;

procedure addtobound(point:tpoint);
begin
  if bsize>=maxboundsize then exit;
  bsize:=bsize+1;
  bound[bsize]:=point;
end;

procedure finalizemap(m: tpathmap);
var
x,y,tmp,ncount: integer;
begin
  x:=finish.x;
  y:=finish.y;
  wp.append(ctos(x,y));
  //ncount:=0;
  while (x<>start.x) or (y<>start.y) do begin
    inc(ncount);
    tmp:=x;
    x:=map.tiles[x,y].prev.x;
    y:=map.tiles[tmp,y].prev.y;
    wp.insert(0,ctos(x,y));
  end;
end;

begin // FindPath
  wp.clear;//richtig?
  dx:=start.x-finish.x;
  dy:=start.y-finish.y;
  for i:=0 to map.width-1 do
  for j:=0 to map.height-1 do
  map.tiles[i,j].status:=tsunvisited;
  map.tiles[start.x,start.y].status:=tsbound;
  map.tiles[finish.x,finish.y].status:=tsfinish;
  bsize:=1;
  map.tiles[start.x,start.y].gval:=0;
  map.tiles[start.x,start.y].hval:=hest(start,finish,dx,dy);
  map.tiles[start.x,start.y].fval:=map.tiles[start.x,start.y].gval+map.tiles[start.x,start.y].hval;
  bound[1]:=start;
  result:=false;
  while bsize>0 do
  begin
    k:=findmin;
    i:=bound[k].x;
    j:=bound[k].y;
    map.tiles[bound[k].x,bound[k].y].status:=tspassed;
    bound[k]:=bound[bsize];
    bsize:=bsize-1;
 //bis hier funzt
    for k:=1 to 8 do
    begin
      a.x:=i+courses[k].x;
      a.y:=j+courses[k].y;
      //if (a.x>=0) and (a.x<levelb) and (a.y>=0) and (a.y<levelh)
      //and (i>0) and (i<levelb) and (j>0) and (j<levelh) then
      begin
        if map.terrain[a.x,a.y] then
        case map.tiles[a.x,a.y].status of
          tsunvisited:
          begin
            map.tiles[a.x,a.y].gval:=map.tiles[i,j].gval+map.tiles[a.x,a.y].value*kk[k mod 2];
            map.tiles[a.x,a.y].fval:=map.tiles[a.x,a.y].gval+hest(a,finish,dx,dy);
            map.tiles[a.x,a.y].prev:=point(i,j);
            map.tiles[a.x,a.y].status:=tsbound;
            addtobound(a);
          end;
          tsfinish :
          begin
            map.tiles[a.x,a.y].prev:=point(i,j);
            map.tiles[start.x,start.y].status:=tsstart;
            result:=true;
            finalizemap(map);
            exit;
          end;
        end;
      end;
    end;
  end;
  map.tiles[start.x,start.y].status:=tsstart;
end;

procedure tcommandoform.initpathmap(var pathmap: tpathmap;width, height: integer);
begin
  setlength(pathmap.terrain,width,height);
  setlength(pathmap.tiles,width,height);
  pathmap.width:=width;
  pathmap.height:=height;
end;



[Edit by Coolcat: Hab auch hier den Code-Tag ergänzt! Geb dir bitte mal etwas mehr mühe beim Fragenstellen....thx
Im überingen geht es dir hier doch wohl ganz eindeutig um den Algorithmus, welcher sicher nicht delphi-spezifisch ist... wink[/Edit]


Also das ganze füllt mir eine Stringliste mit jeweils der nächsten Position, auf die ich mich zubewegen möchte.

Das Problem ist hier nur, dass das sich auch diagonal bewegt, das ist in meinem Fall ganz schlecht. Kennt jemand den Algo und kann mir ohne viel Arbeit sagen, was ich ändern muss, damit sich der Pfad bei 1 Schritt nur senkrecht oder waagerecht bewegt und diagonal verboten ist?

Danke,
Firle

Offline

 

#2 07.09.2005 07:27:29

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Pathfinding

Also auf welcher Basis arbeitet das Ding den überhaupt? Graphen? Ein Array mit passierbar/nicht passierbar ?? Das das Ding eine StringList ausgibt, finde ich schonmal sehr merkwürdig...
Sry hab keine Zeit....ich sollte mich mal langsam auf die Klausur am Freitag vorbereiten... :down:

Coolcat


My software never has bugs. It just develops random features.

Offline

 

#3 08.09.2005 15:23:31

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Pathfinding

also ohne etwas mehr infos wird dir da keine helfen können...wäre ja schon mal gut wenn man zumindest den namen das algos hätte...

Coolcat


My software never has bugs. It just develops random features.

Offline

 

#4 08.09.2005 15:49:05

Back in Time
ProMember
Registriert: 08.04.2005
Beiträge: 130

Re: Pathfinding


If we would understand it we wouldn't call it code.

Offline

 

#5 12.09.2005 10:03:36

firlefanz
GodlikeMember
Ort: Olpe in NRW
Registriert: 31.01.2005
Beiträge: 1035
Web-Seite

Re: Pathfinding

Hi!

Konnte mich nicht melden, weil meine DSL Box kaputt ist. Kann daher nur eingeschränkt ins Internet. Danke für den Link, ich schau mal da rein ob mir das hilft.

Firle

Offline

 

#6 12.09.2005 10:45:22

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Pathfinding

Zitat:

meine DSL Box kaputt

*gg da merkt man dann immer wie Internet abhänig man ist...  :mrgreen:


My software never has bugs. It just develops random features.

Offline

 

Brett Fußzeile

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson