Wegfinde Algorithmus optimieren

[dreaddy]

Ich hab mal unter Zuhilfenahme von dem was ich in Operations Research gelernt habe einen Wegfindebaumalgorithmus umgesetzt, auf das er den kürzesten Weg zwischen zwei freien Punkten finden möge wenn die belegten Felder als Hindernis gelten.

Allerdings würd ich das Ding gern noch schneller bekommen, da ich den auch gern für mein Spiel benutzen würde, deswegen mal die _Bitte an die Leute die mal Zeit haben sich das Teil anzuschauen und zu verbessern/zu sagen wo man es verbessern könnte und und ob es noch bugs gibt ;).

Zur Zeit ist das Programm zu Übungszwecken in Java(sprich ich mag Java nicht aber ich muss es lernen :p )umgesetzt aber es soll nachher in C++ laufen, weswegen keine Java Spielereien zur Verbesserung eingesetzt werden können.
Naja aber mal abgesehen vom Magenumdrehendem new ohne delete ist der Code eh recht Sprachneutral .

Wichtig für den Algorithmus ist nur was in Pathfinding_life.search(x1,y1,x2,y2) aufgerufen wird, das andere ist Spielfeld berechnen und mit nicht begehbaren Feldern füllen usw.

Das Rote sind die abgearbeiteten Felder, das Orange der kürzeste Weg, das Weisse sind freie Felder auf denen man "gehen" kann und alles andre(glaub blaue) sind Hindernisse

Gute Nacht :p

/**
 * Life Game + list + 
 *
 * @author 
 * @version 1.00 04/11/01
 */

 import java.awt.*;

class Knoten
{
  int x;
  int y;

  Knoten(int x, int y)  	
  {
  	this.x = x;
  	this.y = y;
  }
}

class my_list
{
  private class list_ele
  {
    list_ele(list_ele prev, list_ele next, Knoten value)
    {
      this.next = next;
      this.prev = prev; 
      this.value = value;
    }

    list_ele next;
    list_ele prev;

    Knoten value;	
  }

  // Rückgabe true = tausche, false = tausche nicht
  boolean compare_knoten(Knoten k1, Knoten k2)
  {
    if(k1.x+k1.y < k2.x+k2.y )return false;
    else return true;
  }  

  my_list()
  {
   // list_ele(0,0,inhalt)	

  }

  void bubblesort()
  {

  	boolean again = false;

  	do
  	{
  	  again = false;

  	  list_ele temp = begin;

  	  while(temp.next != null)
  	  {
    	if(compare_knoten(temp.value, temp.next.value))	
     	{
  	  	  Knoten zwischen = temp.next.value;
  	  	  temp.next.value = temp.value;
  	  	  temp.value = zwischen;

  	  	  again = true;

  	    }	
  	    temp=temp.next;	
  	  }
  	}while(again);
  }

  void push_back(Knoten knoten)
  {
    if(last == null)  
    {
      last = new list_ele(null,null, knoten);
      begin = last;
    }
    else
    {
      last = new list_ele(last, null, knoten);
      last.prev.next = last;
    }    	
  }

  boolean delete_last()
  {
  	if(last != null)
  	{
  	  if(begin != last)
  	  {
  	  	last = last.prev;
        last.next = null;
      }
      else
      {
      	begin = null;
      	last = null;
      }

      return true;
  	}
  	return false;
  }

  void delete(int index)
  {
    list_ele temp = get_ele(index);

    if(temp != last)  // nicht das letzte Element?
    {
      if(index != 0)
      {
      	temp.prev.next = temp.next;
        temp.next.prev = temp.prev;
      }
      else
      {
        begin = temp.next;
        begin.prev = null;
      }
    }
    else   // ansonsten ist er der letzte
    {
      delete_last();
    }
  }

  void delete_knoten(Knoten k)
  {
    if(begin == null)return; // nix drin

    list_ele temp = begin;  

    int i = 0;
    while(temp != null)//temp.x != k.x && temp.y != k.y)
    {
      if(temp.value.x == k.x && temp.value.y == k.y)
      {
      	delete(i);
      	break;
      }
      temp = temp.next;
      i++;
    }
    return;
  }  

  Knoten get_smallest_c(Stone[][] s)
  {

    if(begin == null)return null; // nix drin
    list_ele temp = begin;  
    int c = 999999999;

    Knoten retval = null;
    while(temp != null)//temp.x != k.x && temp.y != k.y)
    {
      if(s[temp.value.x][temp.value.y].c < c)
      {
      	c = s[temp.value.x][temp.value.y].c;
      	retval = temp.value;
      }
      temp = temp.next;
    }
    return retval;
  }    

  Knoten get_a_star(Stone[][] s, Knoten ziel)
  {

    if(begin == null)return null; // nix drin
    list_ele temp = begin;  

    Knoten retval = begin.value;//get_smallest_c(s);
    while(temp != null)//temp.x != k.x && temp.y != k.y)
    {

      int x_adv_new = Math.abs(temp.value.x - ziel.x);
      int y_adv_new = Math.abs(temp.value.y - ziel.y);
      int x_adv_old = Math.abs(retval.x - ziel.x);
      int y_adv_old = Math.abs(retval.y - ziel.y);

      int x_adv_new_ges = x_adv_new + y_adv_new; 
      int x_adv_old_ges = x_adv_old + y_adv_old;

      if(x_adv_new_ges < x_adv_old_ges)retval = temp.value;      

      temp = temp.next;
    }
    return retval;
  }    

  Knoten get_confused_way(Stone[][] s, Knoten ziel)
  {

    if(begin == null)return null; // nix drin
    list_ele temp = begin;  

    Knoten retval = begin.value;//get_smallest_c(s);
    while(temp != null)//temp.x != k.x && temp.y != k.y)
    {

      if(Math.abs(retval.x - ziel.x) < Math.abs(retval.y - ziel.y)) // x ist näher
      {
        if(temp.value.x > retval.x &&
        temp.value.x > ziel.x)retval = temp.value;
        else if(temp.value.x < retval.x &&
        temp.value.x < ziel.x)retval = temp.value;
      }
      else // y ist näher
      {

        if(temp.value.y > retval.y &&
        temp.value.y > ziel.y)retval = temp.value;
        else if(temp.value.y < retval.y &&
        temp.value.y < ziel.y)retval = temp.value;
      }

    //  System.out.println("x"+retval.x+" y"+retval.y);
      /*
      if(temp.value.x < k.x && temp.value.y < k.y)
      {
      	c = s[temp.value.x][temp.value.y].c;
      	retval = temp.value;
      }*/
      temp = temp.next;
    }
    return retval;
  }    

  Knoten search_Knoten(int x, int y)
  {
    if(begin == null)return null; // nix drin
    list_ele temp = begin;  

    Knoten retval = null;
    while(temp != null)//temp.x != k.x && temp.y != k.y)
    {
      if(temp.value.x == x && temp.value.y == y)
      {
        return temp.value;	
      }
      temp = temp.next;
    }
    return null;
  }    

  public Knoten get(int index)
  {
  	return get_ele(index).value;
  }

  private list_ele get_ele(int index)
  {
  	list_ele temp = begin;
   	for(int i = 0; i < index && temp.next != null; i++)temp = temp.next;

   	return temp;
  }

  Knoten get_first()
  {
  	return begin.value;
  }

  Knoten get_last()
  {
    return last.value;
  }

  public boolean is_empty()
  {
    return (begin == null);
  }  

  list_ele begin;  
  list_ele last;
}

class Stone
{
  Stone()
  {
  	status = false;
  	status_old = false;

  	c = 99999; // für Wegfindung
  	ux1 = 0;
  	uy1 = 0;

  	found_start = false;

  	its_the_way = false;
  }

  boolean status_old;
  boolean status;
  boolean its_the_way;
  Color color;
  int width;
  int height;
  int left;
  int top;

  int c; // weglänge

  int ux1; // vorgänger
  int uy1; // vorgänger  

  boolean found_start;

  boolean abgearbeitet;
}

class Life extends Frame
{
  Image bufImage;
  Graphics bufG;

  int old_w = -1;
  int old_h = -1;

  public void update(Graphics g)
  {

    Dimension dim = getSize(); // Breite und Höhe des Fensters feststellen 
    int w = dim.width;
    int h = dim.height;

    if(old_w != w || old_h != h) // Größe wurde geändert, daher muss neue Surface mti neuer Größe her
    {
      bufImage = createImage(w,h);   // Neue Surface erstellen
      bufG = bufImage.getGraphics(); // Grafikkontext des Bildes
    }

    old_w = w; // benötigt um Größenveränderungen festzustellen
    old_h = h;

    bufG.setColor(getBackground()); // liefert die eigentliche Hintergrundfarbe des Fensters(also meist weiss)
    bufG.fillRect(0,0,w,h); // Bildschirm löschen

    bufG.setColor(getForeground()); // und StandardVordergrundfarbe wieder zuweisen

    paint(bufG); //paint methode aufrufen, die als Besonderheit diesmal nicht direkt auf this malt sondern auf der erstellten Surface(kann man ja im Parameter angeben)

    g.drawImage(bufImage,0,0,this); // erst jetzt wo das zeichnen abgeschlossen ist das fertige Bild so rüberkopieren das es sichtbar wird

  }

  boolean noresize;

  int size_x = 0, size_y = 0;

  public void recalc_stonesizes()
  {

    Insets ins = getInsets();
    Dimension dim = getSize();	 

	float winwidth = dim.width - ins.left - ins.right;
	float winheight = dim.height - ins.top - ins.bottom;

	float stdwidth = winwidth/x_ist;
	float stdheight = winheight/y_ist; 	 

	float uebertragx = 0;	
	float uebertragy = 0;	 	 

	float lasttop = ins.top;
	float lastleft = ins.left;

	for(int y = 0; y < y_ist; y++)
	{

	  uebertragy += stdheight%1;

	  for(int x = 0; x < x_ist; x++)
	  {
	     uebertragx += stdwidth%1; 

	     s[x][y].width  = (int)((int)stdwidth + uebertragx);
	     s[x][y].height = (int)((int)stdheight + uebertragy); 
	     s[x][y].left  = (int)lastleft;
	     s[x][y].top = (int)lasttop;    

	     lastleft += s[x][y].width;

	     uebertragx = uebertragx%1; 
	  }

	  lasttop += s[0][y].height;
	  lastleft = ins.left; 

	  uebertragx  = 0;	 
	  uebertragy = uebertragy%1;          
	}
  }

   public void paint(Graphics g)
   {
   	 recalc_stonesizes();

   	 for(int y = 0; y < y_ist; y++)
   	 {
   	   for(int x = 0; x < x_ist; x++)
   	   {
         g.setColor( s[x][y].color );

   	 	 if(!is_kreis)
   	 	 {
   	 	   if(!s[x][y].status)
   	 	   {
             if(s[x][y].found_start)
             {
               g.setColor( Color.red );   	 	   	
   	 	       g.fillRect(s[x][y].left, s[x][y].top, s[x][y].width, s[x][y].height);
             }

             if(s[x][y].its_the_way)
             {
               g.setColor( Color.orange );   	 	   	
   	 	       g.fillRect(s[x][y].left, s[x][y].top, s[x][y].width, s[x][y].height);
             }                              
   	 	   }
   	 	   else
   	 	   {
             g.setColor( s[x][y].color );   	 	   	
   	 	     g.fillRect(s[x][y].left, s[x][y].top, s[x][y].width, s[x][y].height);
   	 	   }

   	 	   g.setColor(Color.black);
   	 	   g.drawRect(s[x][y].left, s[x][y].top, s[x][y].width, s[x][y].height);
   	 	 }
   	 	 else
   	 	 {
   	 	   if(!s[x][y].status)
   	 	   {
   	 	     g.setColor(Color.black);
   	 	     g.drawOval(s[x][y].left, s[x][y].top, s[x][y].width, s[x][y].height);
   	 	   }
   	 	   else
   	 	   {
   	 	     g.fillOval(s[x][y].left, s[x][y].top, s[x][y].width, s[x][y].height);
   	 	     g.setColor(Color.black);
   	 	     g.drawOval(s[x][y].left, s[x][y].top, s[x][y].width, s[x][y].height);
   	 	   }   	 	  	
   	 	 }	
	   }
   	 }
   }    

  Stone s[][];

  Insets ins = getInsets();

  Life(boolean is_kreis)
  {
    this(20,20, is_kreis);
  }

  boolean is_kreis;

  Life(int x, int y, boolean is_kreis)
  {
    super("Life");	

	this.is_kreis = is_kreis;

	x_ist = x;
	y_ist = y;

	init_array();

	setSize(500,500);

	setVisible(true);       

	recalc_stonesizes();
  }

  private int x_ist;
  private int y_ist;

  void init_array()
  {

    s = new Stone[x_ist][y_ist];

	for(int y = 0; y < y_ist; y++)
	{
	  for(int x = 0; x < x_ist; x++)
	  {
	    s[x][y] = new Stone();

	    s[x][y].color = new Color(255,0,0);//r.nextInt(256),r.nextInt(256),r.nextInt(256));
	    s[x][y].status = java.lang.Math.random() >= 0.5;

	  }
	} 	 	 

	size_y = s[0].length-1;
	size_x = s.length-1;
  }

  protected int next_x(int x)
  {
    if(x < size_x)return x+1;
    return 0;
  }

  protected int prev_x(int x)
  {
    if(x != 0)return x-1;
    return size_x;
  }

  protected int next_y(int y)
  {
    if(y < size_y)return y + 1;
    return 0;
  }

  protected int prev_y(int y)
  {
    if(y != 0)return y-1;
    return size_y;
  }

  public int get_nachbarn(int x, int y)
  {

    my_list retval = new my_list();

  	int anzahl = 0;
   	if(s[x][next_y(y)].status_old)anzahl++;
   	if(s[x]        [prev_y(y)].status_old)anzahl++;
   	if(s[next_x(x)][y].status_old)anzahl++;
   	if(s[prev_x(x)][y].status_old)anzahl++;
   	if(s[next_x(x)][next_y(y)].status_old)anzahl++;
   	if(s[prev_x(x)][prev_y(y)].status_old)anzahl++;
    if(s[next_x(x)][prev_y(y)].status_old)anzahl++; 
   	if(s[prev_x(x)][next_y(y)].status_old)anzahl++;   	   	    	  

   	return anzahl; 
  }

  public void recalc()
  {

    for(int y = 0; y < y_ist; y++)
 	{
 	  for(int x = 0; x < x_ist; x++)
 	  {
        s[x][y].status_old = s[x][y].status; 	 	   	
 	  }
 	}

 	for(int y = 0; y < y_ist; y++)
 	{
 	  for(int x = 0; x < x_ist; x++)
 	  {
 	    s[x][y].color = s[x][y].color.darker();

 	    int nachbarn = get_nachbarn(x,y);

 	    if(nachbarn < 2 || nachbarn > 3)s[x][y].status = false;

 	    if(nachbarn == 3)
 	    {
 	      if(!s[x][y].status)s[x][y].color =  new Color(0,200,0);//r.nextInt(256),r.nextInt(256),r.nextInt(256));
 	      s[x][y].status = true;
	    }
	  }
    }	   

    noresize = true;
    repaint(); // neu zeichnen  
    noresize = false;
  }	 
}

 class Pathfinding_Life extends Life
 {

   // pseudo enum
   int start = 1;
   int end = 2;

   Pathfinding_Life(int x, int y)
   {
   	 super(x,y,false);
   }

   void check_push(int x, int y, Knoten prev, my_list discovered, int pos)  // wenn Knoten weiss dann rauspushen und als benutzt markieren
   {
   	 if(!s[x][y].status)
   	 {
       if(!s[x][y].found_start && pos == start)
       {
         discovered.push_back(new Knoten(x,y));

         s[x][y].c = s[prev.x][prev.y].c;
         s[x][y].ux1 = prev.x; 	
         s[x][y].uy1 = prev.y;

         s[x][y].found_start = true;
       }
   	 }
   }

   public int search_new_fields(Knoten knoten, my_list discovered, int pos)
   {

     int x = knoten.x;
     int y = knoten.y;

  	 int anzahl = 0;

   	 int x_zw;
   	 int y_zw;

   	 if(y != size_y)
   	 {      	 
   	   x_zw = x;
   	   y_zw = next_y(y);   	 
   	   check_push(x_zw,y_zw,knoten, discovered, pos);
   	 }

   	 if(y != 0)
   	 {   	 
   	   x_zw = x;
   	   y_zw = prev_y(y);
   	   check_push(x_zw,y_zw,knoten, discovered, pos);
   	 }

   	 if(x != size_x)
   	 {
   	   x_zw = next_x(x);
   	   y_zw = y;
   	   check_push(x_zw,y_zw,knoten, discovered, pos);
   	 }

   	 if(x != 0)
   	 {
   	   x_zw = prev_x(x);
   	   y_zw = y;
   	   check_push(x_zw,y_zw,knoten, discovered, pos);
   	 }

   	 return anzahl; 
   }

   void search(Knoten start, Knoten end)
   {
     int starttime = (int) System.currentTimeMillis();

     Knoten akt_knoten;
     my_list done_top = new my_list(); // liste mit abgearbeiteten Knoten
     my_list discovered_start = new my_list();   	 
     akt_knoten = start;
   	 s[start.x][start.y].c = 0;
	 discovered_start.push_back(start);

   	 do
   	 {
  	   if(!discovered_start.is_empty())
  	   {

   	     akt_knoten = discovered_start.get_a_star(s, end);     // verwende A*: wert "menschlich" schätzen, also wenn ziel rechts ist schaue rechts usw
         //akt_knoten = discovered_start.get_smallest_c(s);   // verwende Dijkstra: wert mit kleinstem c finden und zuweisen

   	     search_new_fields(akt_knoten, discovered_start, this.start); // neue Felder suchen und auch gleich c und u setzen

  	     done_top.push_back(akt_knoten);

   	     discovered_start.delete_knoten(akt_knoten); // der aktuelle fliegt raus weil er ja nicht mehr unbearbeitet ist

         if(akt_knoten.x == end.x && akt_knoten.y==end.y)break;
   	   }	

   	 }while(!discovered_start.is_empty());

     System.out.println("asdfasdfasdf");

     if(akt_knoten.x == end.x && akt_knoten.y==end.y)
     {

       while(akt_knoten != start)
       {
         akt_knoten = done_top.search_Knoten( s[akt_knoten.x][akt_knoten.y].ux1, s[akt_knoten.x][akt_knoten.y].uy1 );
         s[akt_knoten.x][akt_knoten.y].its_the_way = true;
       }
     }
     else System.out.println("hier gibt es keinen Weg");

     int endtime = (int) System.currentTimeMillis();

     int time = endtime - starttime;     
     System.out.println("Zeit: " + time + "ms");  
   }
 }

class pflifegame3astern
{ 
  public static void main(String[] args) 
  {

    // Array mit Hindernissen füllen
  	Pathfinding_Life fields = new Pathfinding_Life(100,100);
    for(int i = 0; i < 15; i++)fields.recalc(); 

    // weg suchen
    fields.search( new Knoten(5,5), new Knoten(90,90) );
    fields.repaint();

    for(;;)fields.repaint();
  }
}

[otze]

nicht dass ich mir alles angesehen hätte, aber wieso benutzt du den langsamsten sortier alghorithmus den es gibt?(bubblesort)

//edit ich bezweifle auch, dass sich hier irgendjemand da durchliest, die Formatierung ist überwältigend

[Miq (Gast)]

Such' mal nach Leiterplatten-Routingalgorithmen. Da gibt's einiges, und ist nicht schwer zu implementieren (http://www.google.de/search?hl=de&q=lee+autorouting+algorithmus+&btnG=Suche&meta=lr%3Dlang_de)

Mit freundlichem Gruß

Miq

[TGGC|-|work]

Wieviel Geld bezahlst du?

Bye, TGGC (Wähle deine Helden)

[dreaddy]

Alles was ich dadurch verdiene?

Ich will ja nicht das den jemand komplett umschreibt, sondern nur das sich das mal jemand der grad Lust hat (solls ja geben, gibt ja sogar Leute die ihre Zeit damit verbringen sinnfreie Posts in Foren schreiben) anschaut der vielleicht ein wenig mehr Ahnung hat und sagt wo man da noch was optimieren könnte da meine Kommulitonen da irgendwie mit überfordert sind(klingt prollig, ist aber leider so Öö ) habich den Eindruck =[.
Es geht ja wiegesagt nur um die search methode und die 4 die von dem aufgerufen werden, der Rest ist nur das der kram optisch toll dargestellt wird.

Den bubblesort kann man übrigens getrost ignorieren, den musste ich nur für eine Java Übung vonner FH aus einbauen (die List Klasse war mal Übungsaufgabe und nein das hier ist keine Ü-aufgabe sondern selbstgewolltes Elend :p).

Das Prinzip von dem geht so das der sich immer das angrenzende Feld x mit der geringsten Entfernung zum Start raussuche, von diesem dann die unbelegten angrenzenden Felder nehme und da die Entfernung auf x+1 setze sowie mir den Vorgänger merke.
Quasi ein von mir etwas optimierter Dijkstra Algorithmus(der ist ja für bewertete Graphen, sprich von Feld zu feld ist es unterschiedlich weit, man kann manchmal nur hin und nicht zurück usw, da muss man ein paar Sachen logischerweise komplexer machen).

Naja ich werd das Teil nochmal neu formatieren(war gestern etwas spät ) und dann reineditieren.
Vielleicht findet sich ja wer, sonst muss der da so rein in mein Spiel an dem ich seit einigen Jahren progge und was ich KOSTENLOS für alle bis auf tggc ins Netz stellen werde.
Und ihr heult dann rum das die Wegfindung so langsam ist ich seh das schon kommen tztz -_-a

[TGGC...work]

A* etc. ist tausendfach im Netz erklärt, und weil du zu faul bist sollen wir uns in deinen Source einlesen?

Bye, TGGC (Wähle deine Helden)

[dreaddy]

so hab den mal richtig formatiert Öö
Und das ist der A*? hm gut zu wissen, dachte der geht anders ^^

Aber ich sagte ja, er LÄUFT (hoffentlich) fehlerfrei und ich weiss auch genau wie er geht weswegen ich keine dieser "tausendfachen Erklärungen" benötige.
Was soll ich da nachlesen? Wie etwas was ich schon programmiert habe funktioniert?
Ja ne is klar, man programmiert ja auch Sachen die man nicht versteht problemlos mal eben hin.

Alles worum ich bitte ist das sich jemand der Lust hat mal meine Implementierung anschaut und sagt ob man da noch was verbessern kann und optimalerweise auch was Öö.
Und auch wenn ich mich wiederhole, der relevante Teil sind keine 250 Zeilen, es geht nur um das was im search() abläuft und aufgerufen wird, das sollte doch eigentlich möglich sein.
Der Rest ist Spielfeldanzeige etc, ich kann den wichtigen Teil auch noch rausschneiden aber dann läuft das Programm halt nicht .

[dreaddy]

so, hab nochmal den A* als Alternativalgorithmus zum nächsten Knoten suchen eingebaut ( das vorher war der Dijkstra Algorithmus und der heisst auch so @ dggc Öö ).

Jetzt schaff ich es in nem 100*100 array von 5,5 nach 90,90 in 16 statt ca 100 ms einen Weg zu finden, keine Ahnung ob das gut ist, aber es ist schonmal besser und jetzt denkich auch brauchbar .
Wär zwar immernoch heldenhaft wenn jemand ein paar Optimierungsideen hat, aber ich werd das Gefühl nicht los das das zu viel Quellcode ist damit sich das mal jemand anschaut =[
Und reduzieren geht auch schlecht... naja.

[TGGC_work]

dreaddy schrieb:

das vorher war der Dijkstra Algorithmus und der heisst auch so @ dggc

Habe nichts Anderes behauptet. Aber schön, das du es ensiehst.

Bye, TGGC (Wähle deine Helden)

[Walli]

otze schrieb:

nicht dass ich mir alles angesehen hätte, aber wieso benutzt du den langsamsten sortier alghorithmus den es gibt?(bubblesort)

Stimmt nicht! Es gibt langsamere . Snailsort hat jemand das Ding glaube ich mal genannt.

[Gast]

ROFL. Und wie arbeitet der? Wirft der die Elemente so lange zufällig durcheinander, bis es passt??

[TGGC]

Nein, das nennt man bogus sort oder bogosort. Dann gibt noch bozo sort, der tauscht immer nur zwei zufällige Elemente.

Bye, TGGC (Keine Macht den Dummen)

[Sgt. Nukem]

Wurde der nicht in einem Command & Conquer Teil benutzt?!?

So lange einen zufälligen Pfad auswählen bis sich die Erntesammler am meisten verheddern...