Algorithmus gesucht

Sweeper · 23. März 2015, 19:13

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:

HappyTiger · 23. März 2015, 19:24

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

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

ctrl · 23. März 2015, 19:25

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

(nicht zum melden) · 23. März 2015, 19:26

Die Entfernung zwischen zwei Feldern AB und XY ist sqrt(|A-X|²+|B-Y|²).

HappyTiger · 23. März 2015, 19:30

Den Betrag braucht man beim Quadrieren nicht wirklich.

Sunslayer · 23. März 2015, 19:35

Funktioniert auch ganz gut als Klammer :fine:

Sweeper · 23. März 2015, 20:06

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

float R;
Vector2 start;
//+-1 wegen abschneiden der nachkommastellen
int xa = (int)(start.x - R - 1);
int xe = (int)(start.x + R + 1);
int ya = (int)(start.y - R - 1);
int ye = (int)(start.y + R + 1);
// < 0 && > Spielfeld muss hier noch abgefangen werden
for(int nx = xa ; nx < xe ; nx++ ) {
for(int ny = ya ; ny < ye ; ny++ ) {
Vector2 tile = new Vector2(nx+0.5,ny+0.5);
if(Vector2.Distance(start,tile) <= R){
//was auch immer ich tun will.
}
}
}

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.

Coruscant · 23. März 2015, 20:46

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

Sweeper · 23. März 2015, 21:57

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

float R;
Vector2 start;
int df = (int)(R + 1);
int x = (int)start.x;
int y = (int)start.y;
AddHeat(x,y);
for(int i = 1 ; i <= df ; i++){
//Hauptachsen
Vector2 tile = new Vector2((x+i+0.5),y);
if(Vector2.Distance(start,tile) <= R){
AddHeat(x-i,y)
AddHeat(x+i,y)
}
tile = new Vector2(x,(y+i+0.5));
if(Vector2.Distance(start,tile) <= R){
AddHeat(x,y+1)
AddHeat(x,y-1)
}
//Ecken
for(int j = 1 ; j <= df ; j++){
tile.x = (x+j+0.5)
if(Vector2.Distance(start,tile) <= R){
AddHeat(x+i,y+j)
AddHeat(x+i,y-j)
AddHeat(x-i,y+j)
AddHeat(x-i,y-j)
}
}
}

Alles anzeigen

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

Coruscant · 23. März 2015, 23:05

Quellcode

float R;
Vector2 start;
df = (int)(R + 1)
x = (int)start.x
y = (int)start.y
int i = 1 //Kann auch 0 sein, nicht ganz sicher
int j = 1 //Kann auch 0 sein, nicht ganz sicher
Do{ //Durchlaufen der Kacheln in X-Richtung
Vector2 tile = new Vector2((x+i+0.5),y + j +0.5);
if(Vector2.Distance(start,tile) <= R){
AddHeat(x+i,y+j)
AddHeat(x+i,y-j)
AddHeat(x-i,y-j)
AddHeat(x-i,y+j)
//Alternativ an Addheat alle 4 Variablen auf einmal übergeben (x,y,i,j) und die Spielfeldüberprüfung
// wieder mit Schleifen alle 4 Punkte durchlaufen, beginnend mit (x-i,y-j)
i = i+1
// für Kacheln auf den Koordinatenachsen wird
// das Ergebnis zwei mal erzeugt. Da du bis jetzt nur check
// willst ob die Kachel im Spielfeld liegt bekommst du das
// Ergebnis zweimal. Event. noch ne IF dafür einbauen
}
else{
//Sobald die erste Kachel außerhalb des Radius erreicht wurde,
//wird die nächst höhere Zeile von Anfang überprüft
i = 1
j = j + 1
}
}
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

Sweeper · 25. März 2015, 21:56

Dann kommen wir jetzt mal zu was etwas schwierigerem

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)

Spoiler anzeigen

Und der Code:

Spoiler anzeigen

Java-Quellcode

using UnityEngine;
using System.Collections;
using System.Collections.Generic;
using Priority_Queue;
namespace RTS{
public class Pathfinding : MonoBehaviour {
private static HeapPriorityQueue<Node> open = new HeapPriorityQueue<Node>((RTS.Ground.chunkCount*RTS.Ground.chunkSize)*(RTS.Ground.chunkCount*RTS.Ground.chunkSize));
private static List<Node> closed = new List<Node>();
private static Node[,] nodes;
private static Node start;
private static Node end;
private static Vector2 boundary = new Vector2(RTS.Ground.chunkCount*RTS.Ground.chunkSize,RTS.Ground.chunkCount*RTS.Ground.chunkSize);
private static float p = (float)(1.0 + (10/1000));
public static Stack<Node> FindPath(Vector3 position, Vector3 target){
//clear Lists
closed.Clear();
open.Clear();
nodes = new Node[RTS.Ground.chunkCount*RTS.Ground.chunkSize+1,RTS.Ground.chunkCount*RTS.Ground.chunkSize+1];
// Starting Point
int x = (int)position.x;
int y = (int)position.y;
float g = 0;
float h = 0;
start = new Node(x,y,g,h,null);
// Starting Point not Valid (shouldn't be possible)
if(!RTS.Ground.Walkable(x,y)) return null;
// End Point
x = (int)target.x;
y = (int)target.y;
g = 0;
h = 0;
end = new Node(x,y,g,h,null);
// End Point not Valid --> currently Out
// TODO: Find nearest Valid Position?
if(!RTS.Ground.Walkable(x,y)) return null;
//Add Starting Point to Closed List
AddNode(start);
closed.Add (start);
//Add Neighbours
AddNeighbours(start);
//Check Open List
while(open.Count > 0) {
//Get Next Node
//and Add it to Closed List
Node node = open.Dequeue ();
closed.Add (node);
//reached End, Path found
if(node.x == end.x && node.y == end.y){
end = node;
return SelectPath();
}
//Add Neighbours
AddNeighbours(node);
}
//no Path found
return null;
}
private static Stack<Node> SelectPath(){
Stack<Node> path = new Stack<Node>();
Node current = end;
//Select Nodes From End-Node backwards to Start
while(!current.Equals(start)){
path.Push(current);
current = current.parent;
}
return path;
}
//Checks all Neighbours
private static void AddNeighbours(Node node){
int x = node.x;
int y = node.y;
//Loop all Neighbours
for(int nx = (x-1);nx <= (x+1); nx++){
for(int ny = (y-1);ny <= (y+1); ny++){
//This Node --> Out
if(nx == x && ny == y) continue;
//Neighbour out of Map --> Out
if(nx < 0 || ny < 0 || nx > boundary.x || ny > boundary.y) continue;
//Get Node (if it already exists)
Node current = nodes[nx,ny];
//Node already in closed List or not walkable --> Out
if(closed.Contains(current) || !RTS.Ground.Walkable(nx,ny)) continue;
//Node doesn't exist --> Create and Add to Open List
if(current == null){
//Calculate Costs from Start
float g = node.g;
if(nx == x || ny == y) g += 10;
else g += 14;
//Calculate Costs to End
float h = ((Mathf.Abs(nx - end.x)+Mathf.Abs (ny - end.y))*10);
//"Breaking Ties"
h *= p;
//Create + Add Node
Node newNode = new Node(nx,ny,g,h,node);
AddNode(newNode);
open.Enqueue (newNode,(g+h));
continue;
}
//Node in Open --> Validate parent
if(open.Contains(current)) {
//Calculate new costs from Start (with this node as parent)
float newG = node.g;
if(nx == x || ny == y) newG += 10;
else newG += 14;
//if lower than old costs change parent to this
if(newG < current.g){
current.g = newG;
current.parent = node;
}
}
}
}
}
//Adds Node to Array
private static void AddNode(Node node){
int x = node.x;
int y = node.y;
nodes[x,y]=node;
}
}
}

Alles anzeigen

Die PriorityQueue hab ich von BlueRaja

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

lubold · 26. März 2015, 00:26

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

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.

Sweeper · 26. März 2015, 19:43

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.

Aufjedenfall, dickes Dankeschön! :love:

ctrl · 26. März 2015, 20:23

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

Sweeper · 26. März 2015, 20:52

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)

Algorithmus gesucht

Algorithmus gesucht

Quellcode

Beitrag von (nicht zum melden) (23. März 2015, 19:41)

Quellcode

Quellcode

Quellcode

Java-Quellcode

Beitrag von Stefanovic (25. März 2015, 21:59)

Quellcode

Sweeper schrieb:

Benutzer online 1