bestway.php

Go to the documentation of this file.

<?php
/***************************************************************************
 This program is free software; you can redistribute it and/or
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 2
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 ***************************************************************************/

// this is used by two classes
$aHashCache = array();

Class BestWay
{
    var $aHashCache = array();      
    var $dblMinAufwand;             
    var $aTerrainPoints = array();  

    function BestWay ( &$aTerrainPoints )
    {
        global $aHashCache;
        $this->aTerrainPoints =& $aTerrainPoints;
        $this->aHashCache =& $aHashCache;
        $this->dblMinAufwand = 4 / 1.3;
    }

    function calcWay( $sx, $sy, $ex, $ey, $mapdata, $booDebug=false )
    {
        // hilfsarray zur einfachen nachbar bestimmung
        $nachbarn = array();
        for ( $i =- 1; $i < 2; $i++ )
        {
            for ( $j = -1; $j < 2; $j++ )
            {
                if ( ( $i != 0 ) || ( $j != 0 ) )
                {
                    $nachbarn[] = array( $i, $j );
                }
            }
        }
        $result = array();
        // liste der offenen und geschlossenen knoten
        $aOpen   = array();
        $aClosed = array();
        // wurzel anlegen und in die open liste
        $actKey = $this->getHashKey ( $sx, $sy );
        $aOpen[$actKey] = new Node( $sx, $sy, 0, $this->getEST($sx, $sy, $ex, $ey), $sx, $sy );
        // solange nicht der zielknoten erreicht wurde
        while ( $aOpen[$actKey]->est > 0 )
        {
            // akt. knoten aus open loeschen und nach closed schieben
            $aClosed[$actKey] =& $aOpen[$actKey];
            unset( $aOpen[$actKey] );
            // alle nachbarn berechnen
            for ( $i = 0; $i < 8; $i++ )
            {
                $tx = $aClosed[$actKey]->x + $nachbarn[$i][0];
                $ty = $aClosed[$actKey]->y + $nachbarn[$i][1];
                $nextKey = $this->getHashKey( $tx, $ty );
                // akt. aufwand um an dieses feld zu gelangen
                if ( isset ( $mapdata[$tx][$ty]['terrain'] ) )
                {
                    $effort = $this->aTerrainPoints[$mapdata[$tx][$ty]['terrain']];
                    // falls eine strasse dabei ist, 30% weniger aufwand
                    if ( $mapdata[$tx][$ty]['street'] > 0 )
                    {
                        $effort /= 1.3;
                    }
                }
                else
                {
                    // falls keine daten vorhanden, nehmen wir an es ist etwas besser
                    // als wasser
                    $effort = 90;
                }
                // vorherigen aufwand dazu addieren
                $effort += $aClosed[$actKey]->effort;
                if ( isset( $aOpen[$nextKey] ) )
                {
                    // knoten existiert schon in der open list
                    // wenn aufwand besser, dann werte und vorgaenger anpassen
                    if ( $effort < $aOpen[$nextKey]->effort )
                    {
                        $aOpen[$nextKey]->effort= $effort;
                        $aOpen[$nextKey]->calc();
                        $aOpen[$nextKey]->prevKey= $actKey;
                    }
                }
                elseif ( isset ( $aClosed[$nextKey] ) )
                {
                    // knoten ist bereits geschlossen
                    // wenn aufwand besser, dann werte und vorgaenger anpassen
                    // und zurueck nach open schieben
                    if ( $effort < $aClosed[$nextKey]->effort )
                    {
                        $aOpen[$nextKey] = $aClosed[$nextKey];
                        unset( $aClosed[$nextKey] );
                        $aOpen[$nextKey]->effort = $effort;
                        $aOpen[$nextKey]->calc();
                        $aOpen[$nextKey]->prevKey = $actKey;
                    }
                }
                else
                {
                    // neuen Knoten anlegen
                    $aOpen[$nextKey] = new Node( $tx, $ty, $effort,
                                                $this->getEST( $tx, $ty, $ex, $ey ) - ( ( $nachbarn[$i][0] == 0 || $nachbarn[$i][1] == 0 ) ? 0.001 : 0),
                                                $aClosed[$actKey]->x, $aClosed[$actKey]->y );
                }
                if ( $booDebug )
                {
                    echo $tx.'/'.$ty.'='.$effort.' est='.$this->getEST($tx,$ty,$ex,$ey).'<br />';
                }
            }
            $minVal = 99999;
            // besten knoten aus open liste suchen
            foreach( $aOpen as $oNode )
            {
                if ( $oNode->sum < $minVal )
                {
                    $minVal = $oNode->sum;
                    $actKey = $oNode->hashKey;
                }
            }
            if ( $booDebug )
            {
                $aOpen[$actKey]->dump();
                echo '<br />';
            }
        }
        // letzten key nach closed
        $aClosed[$actKey] = $aOpen[$actKey];
        $effort = $aClosed[$actKey]->effort;
        $text = $actKey;
        // vom endpunkt zurueck zum startpunk und ins result schreiben.
        while ( $aClosed[$actKey]->x != $sx || $aClosed[$actKey]->y != $sy )
        {
            //$aClosed[$actKey]->dump();
            $result[$aClosed[$actKey]->x][$aClosed[$actKey]->y] = 1;
            $actKey = $aClosed[$actKey]->prevKey;
            $text = $actKey.",".$text;
        }
        $text = $this->getWdsWayScript($text);
        return ( array($result,$effort,$text) );
    }

    function getHashKey( $x, $y )
    {
        if ( !isset($this->aHashCache[$x][$y] ) )
        {
            $this->aHashCache[$x][$y] = sprintf ( "%4d/%4d", $x, $y );
        }
        return( $this->aHashCache[$x][$y] );
    }

    function getEST( $intStartX, $intStartY, $intEndX, $intEndY )
    {
        // x und y abstand
        $intXDif = abs( $intStartX - $intEndX );
        $intYDif = abs( $intStartY - $intEndY );
        return ( $this->dblMinAufwand * max ( $intXDif, $intYDif ) );
    }

    function getWdsWayScript ( $strText )
    {
        //Mapping   (X)(Y) Change
        $aWaymapping [0][0]   = '';
        $aWaymapping [-1][1]  = 1;
        $aWaymapping [0][1]   = 2;
        $aWaymapping [1][1]   = 3;
        $aWaymapping [1][0]   = 6;
        $aWaymapping [1][-1]  = 9;
        $aWaymapping [0][-1]  = 8;
        $aWaymapping [-1][-1] = 7;
        $aWaymapping [-1][0]  = 4;

        $strWay = '';
        $aCoordlist = explode ( ',', $strText );

        //First Coordinate
        $aPrevCoord = explode ( '/', $aCoordlist[0] );
        $aPrevCoord[1] = trim ( $aPrevCoord[1] );

        //Begin with Second Coord for Way creation
        for ( $i = 1; $i < count($aCoordlist); $i++ )
        {
            //Load Coordinate
            $aCoord = explode ( '/', $aCoordlist[$i] );
            $aCoord[1] = trim ( $aCoord[1] );

            //Get Change of Coordinate
            $intXDiff = $aCoord[0] - $aPrevCoord[0];
            $intYDiff = $aCoord[1] - $aPrevCoord[1];

            //Add To Way
            $strWay .= $aWaymapping[$intXDiff][$intYDiff];

            //Set current Coordinate as Previous
            $aPrevCoord = $aCoord;
        }

        return $strWay;
    }
}

class Node
{
    var $hashKey;   
    var $prevKey;   
    var $x, $y;
    var $effort;    
    var $est;       
    var $sum;       
    var $aHashCache;

    function Node( $x, $y, $effort, $est, $px, $py )
    {
        global $aHashCache;
        $this->aHashCache =& $aHashCache;
        $this->hashKey = $this->getHashKey( $x, $y);
        $this->prevKey = $this->getHashKey( $px, $py);
        $this->x = $x;
        $this->y = $y;
        $this->effort = $effort;
        $this->est = $est;
        $this->calc();
    }

    function calc()
    {
        $this->sum = $this->effort + $this->est;
    }

    function dump()
    {
        printf( " Node: '%s' Prev: '%s' effort=%4.4f EST=%4.4f sum= %4.4f<br /> ", $this->hashKey, $this->prevKey, $this->effort, $this->est, $this->sum );
    }

    function getHashKey( $x, $y )
    {
        if ( !isset($this->aHashCache[$x][$y] ) )
        {
            $this->aHashCache[$x][$y] = sprintf ( "%4d/%4d", $x, $y );
        }
        return( $this->aHashCache[$x][$y] );
    }
}

---