Pathfinding für eine x:y Karte

Deadbone · 27.04.2010, 15:23

Moin,

ich habe derzeit ein Problem bei der Realisierung eines Pathfinding Algorithmuses.

Mein Ziel ist es, in einer x:y Karte einen kurzen und am besten auch "good looking"-Weg von a nach b zu finden und mir jedes Feld das dabei überquert wird in einem Array zurück zu geben.

Die Felder können unterschiedlich sein. Also eines schnell zu überqueren, ein anderes langsamer. Anbieten würde sich hier ein A*-Algorithmus.
Ich habe mir auch bereits einige gut erklärte Links durchgelesen (bsp: A* Pathfinding for Beginners) allerdings find ich keinen Anfang und auch das Verständnis der Open und Closed Lsiten etc. hält sich in Grenzen.

Meine Frage wäre also, hat jemand schoneinmal einen solchen Pathfinding Algorithmus geschrieben (Dijkstra's Algorithmus is leider nicht das was ich suche) der aus einem Array in Form von $arr[x][y] = überquerungswertigkeit; einen schnellen und am besten gutaussehenden weg findet? Oder kann mir helfen das Verständnis für einen aufzubringen damit ich ihn selber schreiben kann ?

Ich hoffe mir kann geholfen werden...

Gruß,
Deadbone

nikosch · 27.04.2010, 15:24

[MOD: verschoben]

cetalian · 27.04.2010, 17:19

Einfacher als in dem Link gehts ja kaum. Ich nehme an das Angebot ist unbezahlt?

Deadbone · 27.04.2010, 18:29

Oh, ich wusste nicht das man hier für Hilfe eventuell bezahlen müsste.
Ja das Angebot wäre unbezahlt, ich hoffe aber wenn es so leicht ist das es jemanden gibt der das umsonst machen würde ?

Ich sitze selber grade dran, falls ich auf ein Ergebnis komme poste ich es auch, aber wenn es jemanden gibt der sich da mit dran setzt wär ich sehr dankbar.

splasch · 27.04.2010, 19:21

Naja es gibt da schon auch ein fertiges Script. Das ist eine Facharbeit von jemanden.

Den Download findest du unter:
http://www.php-einfach.de/download.p...Facharbeit.zip

Mfg Splasch

nikosch · 27.04.2010, 19:26

Zitat:

Ich sitze selber grade dran, nur wie gesagt ich bin immo stressbedingt etwas konfus und kriegs einfach nicht gescheit hin.

Wenn ich sowas imnmer lese, denke ich: „Dann bastel Papierflieger und programmiere weiter, wenn Du wieder klar denken kannst“. Wem nützen solche Aussagen?

Deadbone · 27.04.2010, 19:33

Jeglicher privater schnickschnack wurde entfernt.

Aber danke für die Facharbeit, sieht schonmal gut aus !

nikosch · 27.04.2010, 19:39

Splasch, kannst Du vielleicht noch den Autor ergänzen (Link oder so). Finde das ein bissel unfair, das so als zip-Direktload anzubieten.

[edit] Ach ich sehe gerade, da ist ein pdf dabei..

splasch · 27.04.2010, 21:10

Der Autor steht in allen Php datein sowie auch in der Pdf datei. Ich denke das sollte ausreichen.
Es handelt sich dabei um den Besitzer der Webseite.
http://php-einfach.de/nav_impressum.php

Er hat das Script selbt dort zum Download angeboten.

Mfg Splasch

Deadbone · 01.05.2010, 16:28

So ich hab das ganze nun selbst in einer hoffentlich guten Umsetzung geschafft.
Fals wer noch nen Verbesserungsvorschlag hat würd ich mich drüber freuen.

Zur Handhabung:

Als Karte brauch der Algorithmus einen Array in Form von:
$array[(x-Koordinate)][(y-Koordinate)]['value'] = (Überquerungskosten)

Als Rückgabe erhält man einen Array mit den Punkten die bei dem kürzesten Pfad überquert werden und die Kosten für den jeweiligen Punkt (Hab ich so eingebaut da ich die Kosten zur Zeit Berechnung brauche)

Und hier die Klasse:

PHP-Code:

  <?php

class AStar {
    private $map;
    private $openList;
    private $closedList;
    private $maxFieldValue     = 0;
    private $endField         = array();
    private $startField     = array();
    private $result         = array();

    
    function __construct($map, $maxFieldValue) {
        $this->map                 = $map;
        $this->maxFieldValue     = $maxFieldValue;    
    }
    
    public function getPath($startY, $startX, $endX, $endY) {
        unset($this->openList);
        unset($this->closedList);
        
        if($startY == $endX && $startX == $endY)
            return false;
            
        $this->endField['x']     = $endY;
        $this->endField['y']     = $endX;
        $this->startField['x']     = $startX;
        $this->startField['y']     = $startY;
        
        $this->addOpenListField(null, null, $startX, $startY);
        $this->addClosedListField($startX, $startY);
        $this->loadAdjacentFields($startX,$startY);
        
        while(count($this->openList) > 0) {
            $newField = $this->getLowestOpenField();
            $this->addClosedListField($newField['x'], $newField['y']);
            
            if($newField['x'] == $this->endField['x'] && $newField['y'] == $this->endField['y']) {
                $this->backwalkPath($this->endField['x'],$this->endField['y']);
                return $this->result;
            }
            $this->loadAdjacentFields($newField['x'], $newField['y']);
        }
        return false;    
    }
    
    private function getLowestOpenField() {
        asort($this->openList);
        return $this->getCoordinates(key($this->openList));
    }
    
    private function backwalkPath($x = false, $y = false) {
        if($this->map[$x][$y]['mx'] == null && $this->map[$x][$y]['my'] == null) {
            $this->addFinalPathField($x, $y);
            $this->result = array_reverse($this->result);
        } else {
            $this->addFinalPathField($x, $y);
            $this->backwalkPath($this->map[$x][$y]['mx'], $this->map[$x][$y]['my']);    
        }
    }
    
    private function addFinalPathField($x, $y) {
        $t['x']         = $x;
        $t['y']             = $y;
        $t['cost']         = $this->map[$x][$y]['g'];
        $this->result[] = $t;
    }

    protected function loadAdjacentFields($x, $y) {
        if($this->checkAdjacentField($x-1,$y-1))
            $this->addOpenListField($x, $y, $x-1, $y-1,true);
        if($this->checkAdjacentField($x,$y-1))
            $this->addOpenListField($x, $y, $x, $y-1);
        if($this->checkAdjacentField($x+1,$y-1))
            $this->addOpenListField($x, $y, $x+1, $y-1, true);
        if($this->checkAdjacentField($x-1,$y))
            $this->addOpenListField($x, $y, $x-1, $y);
        if($this->checkAdjacentField($x+1,$y))
            $this->addOpenListField($x, $y, $x+1, $y);
        if($this->checkAdjacentField($x-1,$y+1))
            $this->addOpenListField($x, $y, $x-1, $y+1, true);
        if($this->checkAdjacentField($x,$y+1))
            $this->addOpenListField($x, $y, $x, $y+1);
        if($this->checkAdjacentField($x+1,$y+1))
            $this->addOpenListField($x, $y, $x+1, $y+1, true);
    }
    
    private function checkAdjacentField($x, $y) {
        if(isset($this->map[$x][$y]['value']) && $this->map[$x][$y]['value'] < $this->maxFieldValue)
            return true;
        else
            return false;
    }
    
    private function addOpenListField($masterX, $masterY, $childX, $childY, $diag = false) {
        if(!isset($this->closedList[$childX.'_'.$childY])) {
            if(!isset($this->openList[$childX.'_'.$childY])) 
                $this->setNewFieldData($childX, $childY, $this->calculateMovementCost($masterX, $masterY, $childX, $childY, $diag), $masterX, $masterY);
            else
                if(($cost = $this->calculateMovementCost($masterX, $masterY, $childX, $childY, $diag)) < $this->map[$childX][$childY]['g'])
                    $this->setNewFieldData($childX, $childY, $cost, $masterX, $masterY);
        }
    }
    
    private function setNewFieldData($x, $y, $g, $mx, $my) {
        $this->map[$x][$y]['h']     = $this->calculateHeuristic($x, $y);
        $this->map[$x][$y]['g']     = $g;
        $this->map[$x][$y]['mx']     = $mx;
        $this->map[$x][$y]['my']     = $my;
        $this->openList[$x.'_'.$y]     = $this->map[$x][$y]['h'] + $this->map[$x][$y]['g'];
    }
    
    private function getCoordinates($key) {
        $s         = explode('_',$key);
        $r['x'] = $s[0];
        $r['y'] = $s[1];
        return $r;
    }
    
    private function addClosedListField($x, $y) {
        $this->closedList[$x.'_'.$y] = $this->openList[$x.'_'.$y];
        unset($this->openList[$x.'_'.$y]);
    }
    
    private function calculateHeuristic($x, $y) {
        return (abs($this->endField['x'] - $x) + abs($this->endField['y'] - $y)) * 10;
    }
    
    private function calculateMovementCost($mx, $my, $x, $y, $diag = false) {
        if($mx == null && $my == null)
            $mcost = $this->map[$this->startField['x']][$this->startField['y']]['value'];
        else
            $mcost = $this->map[$mx][$my]['g'];
            
        if($diag)
            $ccost = round(sqrt(pow($this->map[$x][$y]['value'],2) + pow($this->map[$mx][$my]['value'],2)));
        else
            $ccost = $this->map[$x][$y]['value'];
            
        return ($ccost + $mcost);
    }
}
?>

Hoffe ich konnte einigen helfen die für ihr Browserspiel einen Pfandfindungsalgorithmus brauchen.
Nochmal danke an die netten Hilfen.

Deadbone

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Thema bewerten
Thema bewerten:

Ähnliche Themen
Thema	Autor	Forum	Antworten	Letzter Beitrag
[Erledigt] Browsergame : Objekte auf einer Karte	BlackScorp	Software-Design	10	01.04.2010 09:59
wie erstellt man eine Karte?	SteiniKeule	Off-Topic Diskussionen	7	27.03.2010 16:27
[Erledigt] Marker werden nicht auf Google Maps Karte gezeigt ?!	Blade	PHP Tipps 2009	3	15.11.2009 22:57
Deutschlandkarte: Menge an Punkten farblich darstellen	noreux	Off-Topic Diskussionen	1	06.09.2009 14:29
Karte in PHP	michi*1	PHP Tipps 2009	5	19.07.2009 01:24
Zweidimensionale Karte	Griffith	Datenbanken	19	02.07.2008 16:51
Pathfinding Algorithmus optimieren? (Algorith. von Dijkstra)	Martin13	PHP Tipps 2007	19	04.09.2007 19:20
User karte ( x , y Kordinaten )	Mondschein	PHP Tipps 2007	1	20.11.2005 12:30
Karte funktioniert nicht ganz richtig ( koardinaten system )		PHP Tipps 2005-2	7	15.06.2005 16:48
Broadcom Wireless Karte	suter	Server, Hosting und Workstations	0	18.05.2005 08:23
Fernsehen mit Satelliten Karte		Off-Topic Diskussionen	1	05.09.2004 16:45
Karte		Beitragsarchiv	13	02.09.2004 17:30
[Erledigt] WAs stimmt da nicht?		PHP Tipps 2004	32	25.08.2004 14:05

27.04.2010, 15:23
Deadbone Neuer Benutzer Registriert seit: 27.04.2010 Beiträge: 6 PHP-Kenntnisse: Fortgeschritten	Pathfinding für eine x:y Karte Moin, ich habe derzeit ein Problem bei der Realisierung eines Pathfinding Algorithmuses. Mein Ziel ist es, in einer x:y Karte einen kurzen und am besten auch "good looking"-Weg von a nach b zu finden und mir jedes Feld das dabei überquert wird in einem Array zurück zu geben. Die Felder können unterschiedlich sein. Also eines schnell zu überqueren, ein anderes langsamer. Anbieten würde sich hier ein A-Algorithmus. Ich habe mir auch bereits einige gut erklärte Links durchgelesen (bsp: A Pathfinding for Beginners) allerdings find ich keinen Anfang und auch das Verständnis der Open und Closed Lsiten etc. hält sich in Grenzen. Meine Frage wäre also, hat jemand schoneinmal einen solchen Pathfinding Algorithmus geschrieben (Dijkstra's Algorithmus is leider nicht das was ich suche) der aus einem Array in Form von $arr[x][y] = überquerungswertigkeit; einen schnellen und am besten gutaussehenden weg findet? Oder kann mir helfen das Verständnis für einen aufzubringen damit ich ihn selber schreiben kann ? Ich hoffe mir kann geholfen werden... Gruß, Deadbone Geändert von Deadbone (27.04.2010 um 19:33 Uhr).


Mister Ad PHP Code Flüsterer Registriert seit: 21.08.2005 Beiträge: 4682 PHP-Kenntnisse: Fortgeschritten

27.04.2010, 15:24
nikosch moderatives Dielektrikum Registriert seit: 21.05.2008 Beiträge: 35.994 PHP-Kenntnisse: Fortgeschritten	[MOD: verschoben] __________________ -- One pixel is still too big. Please make it smaller. ASAP. Initiative Mittelstand. Die wichtigste Gestaltungsregel im Screendesign ist Pi mal Daumen des Arbeitgebers. --

27.04.2010, 17:19
cetalian Erfahrener Benutzer Registriert seit: 27.06.2009 Beiträge: 498 PHP-Kenntnisse: Anfänger	Einfacher als in dem Link gehts ja kaum. Ich nehme an das Angebot ist unbezahlt?

27.04.2010, 18:29
Deadbone Neuer Benutzer Registriert seit: 27.04.2010 Beiträge: 6 PHP-Kenntnisse: Fortgeschritten	Oh, ich wusste nicht das man hier für Hilfe eventuell bezahlen müsste. Ja das Angebot wäre unbezahlt, ich hoffe aber wenn es so leicht ist das es jemanden gibt der das umsonst machen würde ? Ich sitze selber grade dran, falls ich auf ein Ergebnis komme poste ich es auch, aber wenn es jemanden gibt der sich da mit dran setzt wär ich sehr dankbar. Geändert von Deadbone (27.04.2010 um 19:32 Uhr).

27.04.2010, 19:21
splasch Erfahrener Benutzer Registriert seit: 05.01.2009 Beiträge: 474 PHP-Kenntnisse: Fortgeschritten	Naja es gibt da schon auch ein fertiges Script. Das ist eine Facharbeit von jemanden. Den Download findest du unter: http://www.php-einfach.de/download.p...Facharbeit.zip Mfg Splasch

27.04.2010, 19:33
Deadbone Neuer Benutzer Registriert seit: 27.04.2010 Beiträge: 6 PHP-Kenntnisse: Fortgeschritten	Jeglicher privater schnickschnack wurde entfernt. Aber danke für die Facharbeit, sieht schonmal gut aus ! Geändert von Deadbone (27.04.2010 um 19:39 Uhr).

27.04.2010, 19:39
nikosch moderatives Dielektrikum Registriert seit: 21.05.2008 Beiträge: 35.994 PHP-Kenntnisse: Fortgeschritten	Splasch, kannst Du vielleicht noch den Autor ergänzen (Link oder so). Finde das ein bissel unfair, das so als zip-Direktload anzubieten. [edit] Ach ich sehe gerade, da ist ein pdf dabei.. __________________ -- One pixel is still too big. Please make it smaller. ASAP. Initiative Mittelstand. Die wichtigste Gestaltungsregel im Screendesign ist Pi mal Daumen des Arbeitgebers. --

27.04.2010, 21:10
splasch Erfahrener Benutzer Registriert seit: 05.01.2009 Beiträge: 474 PHP-Kenntnisse: Fortgeschritten	Der Autor steht in allen Php datein sowie auch in der Pdf datei. Ich denke das sollte ausreichen. Es handelt sich dabei um den Besitzer der Webseite. http://php-einfach.de/nav_impressum.php Er hat das Script selbt dort zum Download angeboten. Mfg Splasch Geändert von splasch (27.04.2010 um 21:16 Uhr).

01.05.2010, 16:28
Deadbone Neuer Benutzer Registriert seit: 27.04.2010 Beiträge: 6 PHP-Kenntnisse: Fortgeschritten	So ich hab das ganze nun selbst in einer hoffentlich guten Umsetzung geschafft. Fals wer noch nen Verbesserungsvorschlag hat würd ich mich drüber freuen. Zur Handhabung: Als Karte brauch der Algorithmus einen Array in Form von: $array[(x-Koordinate)][(y-Koordinate)]['value'] = (Überquerungskosten) Als Rückgabe erhält man einen Array mit den Punkten die bei dem kürzesten Pfad überquert werden und die Kosten für den jeweiligen Punkt (Hab ich so eingebaut da ich die Kosten zur Zeit Berechnung brauche) Und hier die Klasse: PHP-Code: <?php class AStar { private $map; private $openList; private $closedList; private $maxFieldValue = 0; private $endField = array(); private $startField = array(); private $result = array(); function __construct($map, $maxFieldValue) { $this->map = $map; $this->maxFieldValue = $maxFieldValue; } public function getPath($startY, $startX, $endX, $endY) { unset($this->openList); unset($this->closedList); if($startY == $endX && $startX == $endY) return false; $this->endField['x'] = $endY; $this->endField['y'] = $endX; $this->startField['x'] = $startX; $this->startField['y'] = $startY; $this->addOpenListField(null, null, $startX, $startY); $this->addClosedListField($startX, $startY); $this->loadAdjacentFields($startX,$startY); while(count($this->openList) > 0) { $newField = $this->getLowestOpenField(); $this->addClosedListField($newField['x'], $newField['y']); if($newField['x'] == $this->endField['x'] && $newField['y'] == $this->endField['y']) { $this->backwalkPath($this->endField['x'],$this->endField['y']); return $this->result; } $this->loadAdjacentFields($newField['x'], $newField['y']); } return false; } private function getLowestOpenField() { asort($this->openList); return $this->getCoordinates(key($this->openList)); } private function backwalkPath($x = false, $y = false) { if($this->map[$x][$y]['mx'] == null && $this->map[$x][$y]['my'] == null) { $this->addFinalPathField($x, $y); $this->result = array_reverse($this->result); } else { $this->addFinalPathField($x, $y); $this->backwalkPath($this->map[$x][$y]['mx'], $this->map[$x][$y]['my']); } } private function addFinalPathField($x, $y) { $t['x'] = $x; $t['y'] = $y; $t['cost'] = $this->map[$x][$y]['g']; $this->result[] = $t; } protected function loadAdjacentFields($x, $y) { if($this->checkAdjacentField($x-1,$y-1)) $this->addOpenListField($x, $y, $x-1, $y-1,true); if($this->checkAdjacentField($x,$y-1)) $this->addOpenListField($x, $y, $x, $y-1); if($this->checkAdjacentField($x+1,$y-1)) $this->addOpenListField($x, $y, $x+1, $y-1, true); if($this->checkAdjacentField($x-1,$y)) $this->addOpenListField($x, $y, $x-1, $y); if($this->checkAdjacentField($x+1,$y)) $this->addOpenListField($x, $y, $x+1, $y); if($this->checkAdjacentField($x-1,$y+1)) $this->addOpenListField($x, $y, $x-1, $y+1, true); if($this->checkAdjacentField($x,$y+1)) $this->addOpenListField($x, $y, $x, $y+1); if($this->checkAdjacentField($x+1,$y+1)) $this->addOpenListField($x, $y, $x+1, $y+1, true); } private function checkAdjacentField($x, $y) { if(isset($this->map[$x][$y]['value']) && $this->map[$x][$y]['value'] < $this->maxFieldValue) return true; else return false; } private function addOpenListField($masterX, $masterY, $childX, $childY, $diag = false) { if(!isset($this->closedList[$childX.'_'.$childY])) { if(!isset($this->openList[$childX.'_'.$childY])) $this->setNewFieldData($childX, $childY, $this->calculateMovementCost($masterX, $masterY, $childX, $childY, $diag), $masterX, $masterY); else if(($cost = $this->calculateMovementCost($masterX, $masterY, $childX, $childY, $diag)) < $this->map[$childX][$childY]['g']) $this->setNewFieldData($childX, $childY, $cost, $masterX, $masterY); } } private function setNewFieldData($x, $y, $g, $mx, $my) { $this->map[$x][$y]['h'] = $this->calculateHeuristic($x, $y); $this->map[$x][$y]['g'] = $g; $this->map[$x][$y]['mx'] = $mx; $this->map[$x][$y]['my'] = $my; $this->openList[$x.'_'.$y] = $this->map[$x][$y]['h'] + $this->map[$x][$y]['g']; } private function getCoordinates($key) { $s = explode('_',$key); $r['x'] = $s[0]; $r['y'] = $s[1]; return $r; } private function addClosedListField($x, $y) { $this->closedList[$x.'_'.$y] = $this->openList[$x.'_'.$y]; unset($this->openList[$x.'_'.$y]); } private function calculateHeuristic($x, $y) { return (abs($this->endField['x'] - $x) + abs($this->endField['y'] - $y)) * 10; } private function calculateMovementCost($mx, $my, $x, $y, $diag = false) { if($mx == null && $my == null) $mcost = $this->map[$this->startField['x']][$this->startField['y']]['value']; else $mcost = $this->map[$mx][$my]['g']; if($diag) $ccost = round(sqrt(pow($this->map[$x][$y]['value'],2) + pow($this->map[$mx][$my]['value'],2))); else $ccost = $this->map[$x][$y]['value']; return ($ccost + $mcost); } } ?> Hoffe ich konnte einigen helfen die für ihr Browserspiel einen Pfandfindungsalgorithmus brauchen. Nochmal danke an die netten Hilfen. Deadbone