Algorithmus gesucht

    Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

    • Algorithmus gesucht

      bin vermutlich grad ziemlich doof, aber

      ich hab ne karte, 2D Tile based (Schachbrett), die Felder sind 1x1 groß. Einheiten können immer nur mittig auf den Feldern stehen. Wenn ich jetzt ne Einheit habe und eine Schussreichweite R, wie bekomme ich alle Felder die die Einheit "beschießen" kann. Also alle Felder wo der Mittelpunkt des Feldes innerhalb des Kreises (mit dem Radius R) um die Einheit ist?

      Ich brauche wirklich eine Liste aller Felder bzw. muss alle Felder durchlaufen. Es geht mir nicht ums tatsächliche schießen / Zielauswahl.


      Hat da jemand nen Tipp? :huh:
    • Willst du R wirklich als normale variable float angeben?
      Also z.b. 5,5 und dann berechnen welche Feldermittelpunkte alle in diesem Radius sind, sodass die Einheit angegriffen werden kann?
      Haben die Einheiten ein Collisionradius, oder muss genau die Mitte getroffen werden können?

      Spontanes Brainstorming:

      Berechne den Abstand des mittelpunkts eines Feldes zu deinem mittelpunkt.
      Das musst natürlich für jedes Feld machen.

      Pseudocode:

      Quellcode

      1. float distance = sqrt( (y2 - y1)^2 + (x2 - x1)^2 )
      2. if ( distance < R )
      3. {
      4. feld[x2][y2].CanAttack = true;
      5. }
      6. else
      7. feld[x2][y2].CanAttack = false;

      Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von HappyTiger ()

    • schreib dir ne hilfsfunktion die die distanz zwischen zwei feldern (zwischen ihren mittelpunkten) berechnet. sqrt((x1-x2)^2 + (y1-y2)^2) oder so.
      dann geh per schleife alle felder durch und check ob die distanz <= R ist.
      du kannst ein bisschen arbeit sparen indem du nur die felder überprüfst deren x oder y koordinate sich um maximal R vom wert deiner position unterscheidet

      WE GON TAKE OVER THE WORLD
      WHILE THESE HATERS GETTIN MAD

      Beitrag von (nicht zum melden) ()

      Dieser Beitrag wurde gelöscht, Informationen über den Löschvorgang sind nicht verfügbar.
    • Danke, das hat schon gereicht. Manchmal steht man einfach aufm Schlauch. Gibt sogar ne hauseigene Methode in Unity dafür.

      Allerdings durchlaufe ich damit auch Teile die nicht dazu gehören, also falls wer noch was besseres hat, immer her damit :)

      Quellcode

      1. float R;
      2. Vector2 start;
      3. //+-1 wegen abschneiden der nachkommastellen
      4. int xa = (int)(start.x - R - 1);
      5. int xe = (int)(start.x + R + 1);
      6. int ya = (int)(start.y - R - 1);
      7. int ye = (int)(start.y + R + 1);
      8. // < 0 && > Spielfeld muss hier noch abgefangen werden
      9. for(int nx = xa ; nx < xe ; nx++ ) {
      10. for(int ny = ya ; ny < ye ; ny++ ) {
      11. Vector2 tile = new Vector2(nx+0.5,ny+0.5);
      12. if(Vector2.Distance(start,tile) <= R){
      13. //was auch immer ich tun will.
      14. }
      15. }
      16. }
      Alles anzeigen

      Zur Verständnis vielleicht noch, z.B. das Feld mit dem Index [1|1] geht von den Koordinaten (1|1) bis (2|2) und hat den Mittelpunkt (1.5|1.5).


      @HappyTiger:
      Die Einheiten ermittel ich über einen kreisförmigen Raycast ("also einen kreisförmigen Laser der immer größer wird bis radius R und alle getroffenen Objekte zurückliefert") beim Boden geht das aber nicht, da er aus performancegründen in Chunks gerendert wird und ich somit nur die Chunks zurückbekommen würde.


      @Einsatzgebiet:
      Ich will eine Heatmap der "Gefahrenbereiche" erzeugen, welche dann beim Pathfinding bzw. der Auswahl der Angriffsstrategie von der KI beachtet wird.

      Dieser Beitrag wurde bereits 5 mal editiert, zuletzt von Sweeper ()

    • Also den Satz des Pythagoras sollte man schon kennen :)))

      Aber Spaß bei Seite:

      So wie du es im Moment gelöst hast, funktioniert es. Aber je größer der Radius, desto mehr Felder werden untersucht, bzw. die Schleifendurchläufe steigen.

      Was mir in den Sinn kommt, wäre nur den ersten Quadranten zu untersuchen und die Ergebnisse auf die Kacheln der anderen Quadranten anzuwenden (dazu die Vorzeichen von x und y anpassen)

      Also angenommen die Kachel (2 | 3) liegt im Radius, dann gilt das auch für die Kacheln:

      (2 | -3)
      (-2 | -3)
      (-2 | 3)

      Vllt bringt dir das ja was.

      mfg
      Coruscant
      Kommentar zur Krise xyz:
      Ich hatte mich schon gefragt welche nächste Sau durch's Dorf getrieben
      wird. Was wohl als nächstes kommt. Klimawandel oder vielleicht doch
      wieder Terrorismus ...

      Das der Mond auf die Erde stützt, DASS wäre mal was wirlich neues und
      sicher auch extrem verheerend. Alternativ tut es auch ein großer
      Meteorit.

      Ich kann es mir in Gedanken schon vorstellen. An Schweinegrippe
      erkrankt und vom Meteoriten erschlagen als der Kofferbomber gerade
      einen Block entfernt war ...

      Ja, das sind wahrhaft düstere Zeiten. Ich mach erst mal ein Bier auf ... Das ewige Leben wird sowieso keiner haben.

      Hier gehts lang zu Rätseln der gehobenen Schwierigkeitsklasse!
    • Danke,

      AddHeat() hier jetzt als Platzhalter für die Methode zum hinzufügen der "Hitze". In AddHeat folgt dann auch die Überprüfung ob das Feld innerhalb des Spielfeldes ist.

      Sieht schon besser aus, wobei ich nicht glaube, dass es viel schneller ist, weil ich jetzt häufiger überprüfen muss ob das Feld innerhalb des Spielfeldes ist. Aber passt erstmal so.

      Quellcode

      1. float R;
      2. Vector2 start;
      3. int df = (int)(R + 1);
      4. int x = (int)start.x;
      5. int y = (int)start.y;
      6. AddHeat(x,y);
      7. for(int i = 1 ; i <= df ; i++){
      8. //Hauptachsen
      9. Vector2 tile = new Vector2((x+i+0.5),y);
      10. if(Vector2.Distance(start,tile) <= R){
      11. AddHeat(x-i,y)
      12. AddHeat(x+i,y)
      13. }
      14. tile = new Vector2(x,(y+i+0.5));
      15. if(Vector2.Distance(start,tile) <= R){
      16. AddHeat(x,y+1)
      17. AddHeat(x,y-1)
      18. }
      19. //Ecken
      20. for(int j = 1 ; j <= df ; j++){
      21. tile.x = (x+j+0.5)
      22. if(Vector2.Distance(start,tile) <= R){
      23. AddHeat(x+i,y+j)
      24. AddHeat(x+i,y-j)
      25. AddHeat(x-i,y+j)
      26. AddHeat(x-i,y-j)
      27. }
      28. }
      29. }
      Alles anzeigen


      Muss morgen aber noch testen ob ich da nicht irgendwo durcheinandergekommen bin.

      Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von Sweeper ()

    • Quellcode

      1. float R;
      2. Vector2 start;
      3. df = (int)(R + 1)
      4. x = (int)start.x
      5. y = (int)start.y
      6. int i = 1 //Kann auch 0 sein, nicht ganz sicher
      7. int j = 1 //Kann auch 0 sein, nicht ganz sicher
      8. Do{ //Durchlaufen der Kacheln in X-Richtung
      9. Vector2 tile = new Vector2((x+i+0.5),y + j +0.5);
      10. if(Vector2.Distance(start,tile) <= R){
      11. AddHeat(x+i,y+j)
      12. AddHeat(x+i,y-j)
      13. AddHeat(x-i,y-j)
      14. AddHeat(x-i,y+j)
      15. //Alternativ an Addheat alle 4 Variablen auf einmal übergeben (x,y,i,j) und die Spielfeldüberprüfung
      16. // wieder mit Schleifen alle 4 Punkte durchlaufen, beginnend mit (x-i,y-j)
      17. i = i+1
      18. // für Kacheln auf den Koordinatenachsen wird
      19. // das Ergebnis zwei mal erzeugt. Da du bis jetzt nur check
      20. // willst ob die Kachel im Spielfeld liegt bekommst du das
      21. // Ergebnis zweimal. Event. noch ne IF dafür einbauen
      22. }
      23. else{
      24. //Sobald die erste Kachel außerhalb des Radius erreicht wurde,
      25. //wird die nächst höhere Zeile von Anfang überprüft
      26. i = 1
      27. j = j + 1
      28. }
      29. }
      30. While (j<= df)
      Alles anzeigen


      Aus schmerzlicher Erfahrung: gewöhn die Annotations im Quellcode an. Wenn du in 2 Wochen auf diesen Quellcode schaust wirst du sonst einige Zeit mehr zum nachvollziehen brauchen.
      Des Weiterenn, kein PLan ob du es schon machst: Bei jeglichen Schleifen diese mit Beispielwerten und Print-Outs auf Vollständigkeit überprüfen, oft ist es ein +1 oder -1 der Zählvariable was wichtige Ergebnisse fehlen lässt.

      mfg
      Coruscant
      Kommentar zur Krise xyz:
      Ich hatte mich schon gefragt welche nächste Sau durch's Dorf getrieben
      wird. Was wohl als nächstes kommt. Klimawandel oder vielleicht doch
      wieder Terrorismus ...

      Das der Mond auf die Erde stützt, DASS wäre mal was wirlich neues und
      sicher auch extrem verheerend. Alternativ tut es auch ein großer
      Meteorit.

      Ich kann es mir in Gedanken schon vorstellen. An Schweinegrippe
      erkrankt und vom Meteoriten erschlagen als der Kofferbomber gerade
      einen Block entfernt war ...

      Ja, das sind wahrhaft düstere Zeiten. Ich mach erst mal ein Bier auf ... Das ewige Leben wird sowieso keiner haben.

      Hier gehts lang zu Rätseln der gehobenen Schwierigkeitsklasse!
    • Dann kommen wir jetzt mal zu was etwas schwierigerem :D

      zur Erinnerung: 2D-Tile-Based RTS (Schachbrett, Diagonale Bewegung ist erlaubt.)

      Ich hab Pathfinding mit nem A* Algorithmus implementiert, funktioniert soweit auch.

      Jetzt hab ich mal bisschen "Worst-Cases" ausprobiert und er ist leider etwas zu langsam. Für den Hinweg braucht er so 3-4 Sekunden, da er den grauen Bereich komplett durchsucht. Für den Rückweg braucht er 0,5 - 1 Sekunde. Ich denke "Breaking-Ties" könnte noch einiges verbessern. Krieg es aber nicht so wirklich hin, ändert zumindest nichts an dem Problemfall (s.u.). Grundsätzlich soll man nicht den Optimalsten Weg suchen (was meiner im Moment macht), sondern lieber auf Schnelligkeit setzen, weiss aber nicht wirklich wie man das hinbekommt.

      Falls da jemand Erfahrungen hat, wären Tipps nett. Lese mich auch gerne ein, falls wer gute Guides hat.

      Bei der heuristik-Funktion (z.Z. Manhatten) werde ich auf jedenfall noch Chebyshev ausprobieren. Falls jemand Erfahrungen mit anderen Heuristiken hat, natürlich auch gerne her damit. Und andere Performance-Verbesserung sind natürlich auch gern gesehen :)

      Problemfall: (Achtung: Unfassbar gute Paint Skills)


      Und der Code:
      Spoiler anzeigen

      Java-Quellcode

      1. using UnityEngine;
      2. using System.Collections;
      3. using System.Collections.Generic;
      4. using Priority_Queue;
      5. namespace RTS{
      6. public class Pathfinding : MonoBehaviour {
      7. private static HeapPriorityQueue<Node> open = new HeapPriorityQueue<Node>((RTS.Ground.chunkCount*RTS.Ground.chunkSize)*(RTS.Ground.chunkCount*RTS.Ground.chunkSize));
      8. private static List<Node> closed = new List<Node>();
      9. private static Node[,] nodes;
      10. private static Node start;
      11. private static Node end;
      12. private static Vector2 boundary = new Vector2(RTS.Ground.chunkCount*RTS.Ground.chunkSize,RTS.Ground.chunkCount*RTS.Ground.chunkSize);
      13. private static float p = (float)(1.0 + (10/1000));
      14. public static Stack<Node> FindPath(Vector3 position, Vector3 target){
      15. //clear Lists
      16. closed.Clear();
      17. open.Clear();
      18. nodes = new Node[RTS.Ground.chunkCount*RTS.Ground.chunkSize+1,RTS.Ground.chunkCount*RTS.Ground.chunkSize+1];
      19. // Starting Point
      20. int x = (int)position.x;
      21. int y = (int)position.y;
      22. float g = 0;
      23. float h = 0;
      24. start = new Node(x,y,g,h,null);
      25. // Starting Point not Valid (shouldn't be possible)
      26. if(!RTS.Ground.Walkable(x,y)) return null;
      27. // End Point
      28. x = (int)target.x;
      29. y = (int)target.y;
      30. g = 0;
      31. h = 0;
      32. end = new Node(x,y,g,h,null);
      33. // End Point not Valid --> currently Out
      34. // TODO: Find nearest Valid Position?
      35. if(!RTS.Ground.Walkable(x,y)) return null;
      36. //Add Starting Point to Closed List
      37. AddNode(start);
      38. closed.Add (start);
      39. //Add Neighbours
      40. AddNeighbours(start);
      41. //Check Open List
      42. while(open.Count > 0) {
      43. //Get Next Node
      44. //and Add it to Closed List
      45. Node node = open.Dequeue ();
      46. closed.Add (node);
      47. //reached End, Path found
      48. if(node.x == end.x && node.y == end.y){
      49. end = node;
      50. return SelectPath();
      51. }
      52. //Add Neighbours
      53. AddNeighbours(node);
      54. }
      55. //no Path found
      56. return null;
      57. }
      58. private static Stack<Node> SelectPath(){
      59. Stack<Node> path = new Stack<Node>();
      60. Node current = end;
      61. //Select Nodes From End-Node backwards to Start
      62. while(!current.Equals(start)){
      63. path.Push(current);
      64. current = current.parent;
      65. }
      66. return path;
      67. }
      68. //Checks all Neighbours
      69. private static void AddNeighbours(Node node){
      70. int x = node.x;
      71. int y = node.y;
      72. //Loop all Neighbours
      73. for(int nx = (x-1);nx <= (x+1); nx++){
      74. for(int ny = (y-1);ny <= (y+1); ny++){
      75. //This Node --> Out
      76. if(nx == x && ny == y) continue;
      77. //Neighbour out of Map --> Out
      78. if(nx < 0 || ny < 0 || nx > boundary.x || ny > boundary.y) continue;
      79. //Get Node (if it already exists)
      80. Node current = nodes[nx,ny];
      81. //Node already in closed List or not walkable --> Out
      82. if(closed.Contains(current) || !RTS.Ground.Walkable(nx,ny)) continue;
      83. //Node doesn't exist --> Create and Add to Open List
      84. if(current == null){
      85. //Calculate Costs from Start
      86. float g = node.g;
      87. if(nx == x || ny == y) g += 10;
      88. else g += 14;
      89. //Calculate Costs to End
      90. float h = ((Mathf.Abs(nx - end.x)+Mathf.Abs (ny - end.y))*10);
      91. //"Breaking Ties"
      92. h *= p;
      93. //Create + Add Node
      94. Node newNode = new Node(nx,ny,g,h,node);
      95. AddNode(newNode);
      96. open.Enqueue (newNode,(g+h));
      97. continue;
      98. }
      99. //Node in Open --> Validate parent
      100. if(open.Contains(current)) {
      101. //Calculate new costs from Start (with this node as parent)
      102. float newG = node.g;
      103. if(nx == x || ny == y) newG += 10;
      104. else newG += 14;
      105. //if lower than old costs change parent to this
      106. if(newG < current.g){
      107. current.g = newG;
      108. current.parent = node;
      109. }
      110. }
      111. }
      112. }
      113. }
      114. //Adds Node to Array
      115. private static void AddNode(Node node){
      116. int x = node.x;
      117. int y = node.y;
      118. nodes[x,y]=node;
      119. }
      120. }
      121. }
      Alles anzeigen


      Die PriorityQueue hab ich von BlueRaja


      Edit by ramius: Code-BBCode durch Java.BBCode ersetzt für Code Highlighting.

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von Sweeper ()

      Beitrag von Stefanovic ()

      Dieser Beitrag wurde gelöscht, Informationen über den Löschvorgang sind nicht verfügbar.
    • Bei so einem kleinen Feld sollte das auch ohne irgendwelche Heuristiken in ein paar Millisekunden durchlaufen, würde da eher am bestehenden Code optimieren als irgendwas neues einzubauen.

      Hab mich mal grob durch den Code gewälzt, dabei sind mir ein paar Sachen aufgefallen:

      Quellcode

      1. private static float p = (float) (1.0 + (10 / 1000));

      Da kommt für p = 1.0 raus, weil 10 / 1000 in integern gerechnet wird und somit 0 rauskommt, damit ist vermutlich auch die ganze (mir unbekannte) Heuristik im Eimer. Mach doch einfach float p = 1.01 draus.

      Generell ist dieses ganze Node-Objekte kreieren, speichern etc. ziemlich lahm. Beispielsweise speichert ihr "closed" nodes in einer Liste ab und überprüft dann immer, ob eine Node darin enthalten ist. Das dauert bei einer Liste, wenn die voller wird, extrem lang. Für Felder, die nicht all zu groß sind, (<1 mrd felder oder so), kann man das ganze ziemlich gut einfach als boolean-Array abspeichern. boolean[][] isClosed = boolean[breite des feldes][höhe des feldes], dort ist dann nach dem Initialisieren überall false drin und sobald ein Feld "closed" ist, setzt du das Feld mit den entsprechenden Koordinaten auf true. Dann kannst du, statt immer die Node aus einer Liste zu suchen, einfach mit isClosed[x][y] nachschauen, was quasi instant ist.

      Generell würde ich diese ganze Node-Geschichte aber noch mal überlegen, weil's einfach unnötig lahmer overhead ist. Für so kleine Felder würde ich spontan einfach ein int[][]-Array anlegen, in dem zu jedem Feld die Entfernung zum Target-Feld eingetragen wird. Initialisieren tust du einfach jedes Feld mit 99999 (oder int max, irgendeine übergroße Zahl halt) und das Targetfeld mit 0. Wenn ein Feld nicht walkable ist, kannst du -1 eintragen und das im code dann dementsprechend berücksichtigen. Dann fängst du von da aus an und trägst in jedem angrenzenden Feld die Entfernung ein, also hier z.B. 10 in den angrenzenden und 14 in den diagonal angrenzenden. Alle Felder, die du geändert hast, knallst du in deine PriorityQueue und machst dann von denen aus weiter, in der Reihenfolge der Entfernung (die Felder mit der kleinsten Entfernung zuerst). In dem neuen Feld machst du dann genau das gleiche. Wenn du das Feld verlässt, kannst du es auf closed setzen und musst es dann in Zukunft nicht weiter betrachten. Es muss bereits der kürzeste Weg sein, da du Felder ja in der Reihenfolge der Entfernung abarbeitest und somit die anderen Felder bereits eine gleich große oder größere Entfernung haben (und es keine negativen Entfernungen gibt).
      Wenn du dann irgendwann "zufällig" am Startfeld ankommst, kannst du von da aus den Weg rückwärts rekonstruieren, indem du einfach immer das angrenzende Feld mit der kleinsten Zahl entlang läufst.
      So ein 140x140 Feld (also knapp 20000 Felder) sollte damit auch komplett ohne Heuristik eigentlich kaum länger als einen Augenblick dauern.

      Gehe jetzt ins Betti, kann morgen noch mal was dazu schreiben, hoffe ich hab hier jetzt auch keinen groben Fehler eingebaut, sollte aber alles Sinn ergeben :wacko:

      Die Wikipedia-Erläuterung ist wohl ausführlicher und besser: de.wikipedia.org/wiki/Dijkstra-Algorithmus
      Mehr braucht man für den Problemumfang eigentlich nicht, A* kann man machen, wenn dann aber ordentlich umgesetzt, sonst hat man den Salat.

      Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von lubold ()




      eventually there comes a point where it's like the true test for your team - will he cast a spell or will he not
      - Artour Babaev

      Und wenn beide dann nicht mehr stacken und der einer 6k Boi, der vorher 4k war, mit einem anderen 4k Boi spielt, dann ist er nicht mehr 6k, weil er reverse trägert, oder?
      - User des Monats
    • closed Liste durch Array ersetzt.

      Laufzeit Vorher:
      00:00:04.9133502

      Laufzeit Nachher:
      00:00:00.0230145

      :love:

      "Breaking Ties" hab ich erstmal wieder entfernt. Hat keinen Unterschied gemacht.

      Wie ich die Node Geschichte ganz weglasse weiss ich nicht, da die PriorityQueue Nodes benötigt. Und eine eigene PriorityQueue mit guter Performance zu schreiben kann ich glaub ich vergessen. Werde mal Recherchieren ob ich da noch ne Lösung finde, will aber schon am A* Algorithmus festhalten.

      Problem bei mir ist halt, dass ich beruflich mit ner Programmiersprache arbeite, die keine Objekte, keine Datentypen, keine Listen(, keine Performanceprobleme) hat. Als ich deinen Post gelesen hab, hätte ich meinen Kopf am liebsten gegen die Wand geschlagen, weils halt echt schon ziemlich offensichtlich ist (vorallem da der Algorithmus immer an der Stelle steckte wenn ich ihn pausiert hab >.<). Aber von alleine nehm ich sowelche Sachen einfach nicht wahr, weil ich nicht gewohnt bin darauf zu achten. :S

      Aufjedenfall, dickes Dankeschön! :love:
    • Sweeper schrieb:

      Problem bei mir ist halt, dass ich beruflich mit ner Programmiersprache arbeite, die keine Objekte, keine Datentypen, keine Listen(, keine Performanceprobleme) hat.

      schreibst du assemblercode oder was? oder programmierst du fpgas mit vhdl oder so?
      selbst funktionale sprachen wie haskell haben datentypen und listen

      WE GON TAKE OVER THE WORLD
      WHILE THESE HATERS GETTIN MAD
    • en.wikipedia.org/wiki/MUMPS

      ziemlich alte Sprache, aber ziemlich cool zum Programmieren, weil man sich auf die Funktionen konzentrieren kann und sich nicht mit "Nebensachen" aufhalten muss. Hat aber auch große Nachteile ^^

      Die Datenablage in der Datenbank ist schlüsselbasiert und erfüllt damit ähnliche Funktionieren wie eine Liste. Wir arbeiten aber auch direkt auf der Datenbank und benutzen dann Tabellen die "Temporär" sind und bei jedem Serverneustart (vom Programm) gelöscht werden. Daher haben wir auch i.d.R. keinen Bedarf für Arrays, Listen, etc (im herkömmlichen Sinn).

      Da es nur einen Datentyp gibt, gehen da halt so dinge wie:

      SET ZAHL = 0.5
      SET SATZ = "Hallo Welt!"
      SET SATZ = ZAHL + SATZ
      (SATZ ist danach 0.5, weil SATZ als 0 gewertet wird)
    • Benutzer online 1

      1 Besucher