Wegefinder

[Lulumann6]

hallo
ich hab vor ein Strategie/Bauspiel zu programmieren.
Mein problem ist jetzt, dass ich keine ahnung hab wie meine einheiten den richtigen/kürzesten weg finden sollen, d.h. wenn ich meine einheit grade gegenüber von einen fluss schicke, muss er einen weg finden um an den fluss vorbei zu laufen, z.b. über eine brücke.
ich hab kein problem herauszufinden, dass meine einheit gegen etwas läuft wo es nicht weiter kann.
den gesamten weg sollte die einheit sofort beim klicken ausrechnen, und ein array machen, mit allen punkten zu den die einheit läuft um am ziel anzukommen.

hier hab ich ein beispiel. die schwarzen balken sind die hindernisse. meine figur ist der punkt links und will zu den punkt rechts, dazu hab ich jetzt zwei wegmöglichkeiten angezeichnet (weiß nicht welcher der kürzere ist). die punkte in den pfeilen sollen später die punkte sein die in dem array gespeichert werden sollen.
vielleicht kann mir ja irgendjemand mit einer grundidee weiterhelfen


ps. ich hab schon danach im forum und in google gesucht, aber so wie ich das haben will gibts kein beispiel.

 

[Quaxli]

Da hat doch gerade heute einer gepostet: guck mal hier :###

 

[ice-breaker]

dafür gibt es den A*-Algorithmus
der ist auch relativ simpel umzusetzen und wird oft genutzt

 

[Lulumann6]

okay, das ist doch schon mal ein anfang.
Bei einem Labyrinth oder so könnte man die "Knoten", also die punkte an dem ein weg sich gabelt, recht leicht herausfinden, aber hier hab ich so direkt ja keine knoten. ich kann doch nicht jeden möglichen pixel wo mein mänchen hinlaufen kann zu so einen knoten machen, das wär irrsinnig :autsch:
irgendwie müsste man diese anzahl an knoten deutlich vereinfachen :?:

 

[parabool]

Hi ,

Die Knoten sind in diesem Fall die Eckpunkte deiner Objekte sowie der Start- und der Endpunkt.
Diese Punkte könnten z.B in einer Adjazenzmatrix gespeichert werden(Erreichbarkeit zwischen den Knoten)

Grüsse
p


mmh, habe mir da noch was anderes ausgedacht, funktioniert im Prinzip so:

-Linie von Start zum Zielpunkt durchziehen

-bei 1. hinderniskante "Suche" nach oben/unten bzw links/rechts durchführen um "Umgehung" zu finden
ggf diesen Schritt wiederholen

-von neugefundenen Punkt erneut Linie bis Zielpunkt ziehen usw. usf....

ist nur eine grobe Idee, die Schwierigkeiten stecken im Detail.

 

[Lulumann6]

@parabol die erste idee ist naja... dann müssten alle seiten meiner hindernisse irgendwie zu eckpunkten gemacht werden, weil ich die einheit ja von allen richtungen über mein hinderniss schicken will.

zur zweiten idee. sowas ähnliches hab ich mir auch schon überlegt. erst einmal eine grade linie zum ziel durchziehen und dann die zwei wegemöglichkeiten um das hinderniss suchen. die eine möglichkeit wär dann auf der einen seite meiner graden linie und die andere auf der anderen.
wenn ich diese wegemöglichkeiten rauskriegen könnte wär ich schon einmal einen großen schritt weiter.
vielleicht fällt jemanden von euch eine möglichkeit ein, wie ich das realisieren kann und ich will nicht einfach gegen das hinderniss laufen und dann an dem hinderniss entlang laufen. ???:L

 

[Lulumann6]

ich hab vielleicht eine idee :idea: für mein kleines problem.
also ich müsste die gnaue breite von dem hinderniss kennen, dann könnte ich den mittelpunkt meiner geraden im hinderniss bestimmen und eine neue grade durch den punkt ziehen die auch senkrecht zu der erste grade ist, nun würde ich gucken wo mein hinderniss auf dieser gerade zuende ist und setzt da eine neue gerade hin mit der ich auch das selbe mache, sodass ich dann zwangsläufig irgendwann komplett um mein hinderniss laufen würde.
was halltet ihr von dieser idee?

 

[RoliMG]

ich habe eine library im netz gefunden, und auch schon selber in einem programm implementiert. die bibliothek unterstützt die algorithmen bfs(bestensuche), a*, und dijkstra.
www.robotacid.com/PBeta/AILibrary/Pathfinder/index.html
leider ist die library nicht ordentlich objekt-orientiert ausprogramiert, dieses problem habe ich aber selber gelöst. und die javadoc habe ich auch eingefügt.
wenn jemand meine version brauch, bitte melden.

 

[ice-breaker]

wo ist denn das Problem? der A*-Stern Algorithmus berechnet recht simpel und schnell den kürzesten Weg zwischen 2 Punkten mit Hindernissen, die ganze Map unterteilst du eben in kleine Vierecke, wobei du definierst das man entlang der Linien laufen kann oder quer über ein Kästchen, das noch in A* implementiert, wozu es sehr viele Beispiele gibt, und fertig...

 

[Lulumann6]

ok, danke
ich seh mir erst mal die ganzen links genauer und guck mal ob es bei mir funzt, wenn ich noch fragen hab werde ich mich wieder melden :bae:

 

[Lulumann6]

So ich hab jetzt erst mal wieder ein paar fragen.
in dem link von RoliMG steht, dass ich "listen" machen muss, wie kann ich die am besten verwirklichen. als array ist klar scheiße, weil sich die liste erweitern muss, also besser sowas wie ein arraylist oder vector, oder doch noch vielleicht etwas anderes...?
aufjedenfall wollte ich wissen ob es sowas wie einen 2 dimensionalen vector gibt? oder ob ich das mit vielen vectoren realisieren muss?
außerdem hab ich ausprobiert ein array in einen vector zu tun, aber wenn ich dann mit den werten ein wenig arbeite und set ung get und so anwende ändern sich die werte auf ganz merkwürdige weise um (vielleicht passiert das auch nur in meiner fantasie, oder ich hab da was falsch gemacht^^) vielleicht kann mir jemand sagen warum.

 

[RoliMG]

So ich hab jetzt erst mal wieder ein paar fragen.
in dem link von RoliMG steht, dass ich "listen" machen muss, wie kann ich die am besten verwirklichen. als array ist klar scheiße, weil sich die liste erweitern muss, also besser sowas wie ein arraylist oder vector, oder doch noch vielleicht etwas anderes...?

willst du dir deine eigene wegfindung programmieren?

aufjedenfall wollte ich wissen ob es sowas wie einen 2 dimensionalen vector gibt? oder ob ich das mit vielen vectoren realisieren muss?

du könntest einen vector in einen vector einfügen, dadurch hättest du 2 dimensionen. ich empfehle jedoch 2 dimensionale arrays, da diese wesentlich schneller sind.

 

[Lulumann6]

ja ich will alles selber programmieren :wink:
es geht mir letztenendlich nicht um das programm, sonder um die erfahrungen die ich dadurch mache.

2 dimensionale arrays würde ich ja auch am liebsten nehmen, aber da in den listen gespeichert wird welche felder "durchsucht" wurden varriiert die anzahl natürlich erheblich und in den meisten fällen würden sich dann warscheinlich sogar vectoren eher lohnen, da die größe des arrays sehr sehr groß gemacht werden müsste.

ist nur eine kombination aus zwei vectoren möglich?
es wär auch in ordnung, dass die eine dimension seine größe nicht verändert.
somit wär mir eine kombination aus vektor und array am liebsten, aber wie schon gesagt, irgendetwas stimmte da bei mir nicht.

 

[RoliMG]

ja ich will alles selber programmieren :wink:
es geht mir letztenendlich nicht um das programm, sonder um die erfahrungen die ich dadurch mache.

vor dieser aufgabe habe ich kapituliert (war mir zu langwierig. warum das rad neu erfinden?).

ist nur eine kombination aus zwei vectoren möglich?

wenn alles voll dynamisch sein soll musst du collections verwenden.

es wär auch in ordnung, dass die eine dimension seine größe nicht verändert.
somit wär mir eine kombination aus vektor und array am liebsten, aber wie schon gesagt, irgendetwas stimmte da bei mir nicht.

ein codebeispiel wäre aufschlussreich.

 

[Lulumann6]

ups, das geht ja doch ein array mit vector zu verbinden^^ beim letzten mal als ich es versucht hab stand da "incompatible typs" und da wusste ich noch nicht so richtig damit umzugehen.
also hat sich meine frage erst mal geklärt

 

[Lulumann6]

kann mir jemand das erklären? normalerweise müsste test[4] doch gleich bleiben.

  System.out.println("erst: " + test[4]);
   offeneWerte[4] = test[4] + 14;
   System.out.println("danach: " + test[4]);

erst: 0
danach: 14

ich hab keinen zweiten threat der test[4] ändert.

 

[Marco13]

Das kommt, wenn 'test' und 'offeneWerte' Referenzen auf dasselbe Array sind:

int test[] = { 1, 2, 3, 4, 5};

int offeneWerte[] = test; 
// Jetzt ist 'offeneWerte' nur "ein anderer Name für" 'test' - jede Änderung an
// 'offeneWerte' ändert auch 'test' (weil ja beides dasselbe Array ist)

System.out.println("erst: " + test[4]); // Ausgabe: 5
offeneWerte[4] = test[4] + 14;
System.out.println("danach: " + test[4]); // Ausgabe: 19

Stattdessen muß man eine Kopie machen, oder ein neues Array anlegen

int test[] = { 1, 2, 3, 4, 5};

int offeneWerte[] = test.clone(); 
// Jetzt ist 'offeneWerte' eine KOPIE von 'test'. Die Inhalte sind am Anfang
// gleich, aber eine Änderung an 'offeneWerte' ändert NICHTS an 'test'

System.out.println("erst: " + test[4]);  // Ausgabe: 5
offeneWerte[4] = test[4] + 14;
System.out.println("danach: " + test[4]);  // Ausgabe: 5

Und ...
ups, das geht ja doch ein array mit vector zu verbinden^^ beim letzten mal als ich es versucht hab stand da "incompatible typs" und da wusste ich noch nicht so richtig damit umzugehen.
Wenn du das genauer beschreibst, kann man es vielleicht auch (er)klären...

 

[Lulumann6]

danke, lag tatsächlich daran :applaus:

Wenn du das genauer beschreibst, kann man es vielleicht auch (er)klären...

das verstehe ich auch schon selbst, das ist nur eine kleinigkeit die ich früher nicht verstanden hab.

int test = beispiel.elementAt(5);

auf der einen seite hat man ein int und auf der anderen seite object, das passt natürlich nicht, daher muss aus dem object erst noch ein int gemacht werden.

int test = (int)beispiel.elementAt(5);

 

[Marco13]

Hm. Seit Java 1.5 wird sowas eigentlich durch Autoboxing / Autounboxing geregelt. Ansonsten kann man nämlich auch kein Object in einen int casten....

 

[Lulumann6]

direkt in ein int casten geht nicht, dass stimmt ich meinte damit eigentlich auch Integer, wobei ich den unterschied von int und Integer nicht verstehe. ich dachte immer int wär einfach nur ne abkürzung für Integer
hier ein beispiel:

import java.io.*;
import java.util.*;

public class Beispiel{
 private Vector vector = new Vector();

 public static void main(String[] args){
  Beispiel bsp = new Beispiel();
 }
 
 public Beispiel(){
  int zahl = 5;
  vector.addElement(zahl);

  int test = (Integer)vector.elementAt(0); //wenn ich hier das (Integer) weglasse gehts nicht mehr
  System.out.println(test);
 }
}

wenn ich nun das (Integer) in zeile 15 weglasse geht es bei mir nicht mehr.

 

[merlin2]

int ist ein ein primitiver Datentyp, Integer die entsprechende Wrapper-Klasse.

 

[RoliMG]

ich würde collections immer typisieren(funktioniert ab java 1.5)!
außer du möchtest beliebige objekte zu deinem vector hinzufügen.

Vector<Integer> v = new Vector<Integer>();