Compiled PHP

[DV8]

The game I'm working on has a rather slow A* path finding algorithm that I've been optimising gradually since I wrote it, but it's still not fast enough for my liking. I've been looking at this near-mythical compiled PHP, like phc, but I'm loathe to implement it because it seems like an awful lot of work. Does anyone have any experience with this type of thing?

[CygnusX]

I did some work on A* heuristics many years ago.  Unfortunately, I did it in Java and not PHP.  On the 450Mhz CPU I was running back in those days, it heuristic ran fairly fast (and this was with giving real time graphical displays of the path choosing logic). 

Is your game turn based, or Real Time?  If real time, you I can see why you're having performance issues.

[DV8]

No, it's turn-based. One of the tile-maps I'm using is 58x34 big, with various walls, obstacles, etc. I've got ten enemies whose paths all need to be calculated and it probably takes about 0.2-0.5 seconds per step the character takes, and then I've already limited each of the enemies to search any more than 200 tiles for their target. It seems awfully long to me. Here's the path-finding code. (You can ignore the LineOfSight().) A sample of the $arrTiles array can be found below.

I was kind of hoping that the execution time of the Path() class would go up if compiled.

Code: [Select]

<?php
  /********************************************************************************************************/
  /* __construct
  /* __destruct
  /* ClearObject
  /* CompareCost
  /* getPath
  /* getStep
  /* FindPath
  /* AddNode
  /* MakePath
  /* LineOfSight
  /********************************************************************************************************/

  class Path {
    var $strErrorMsg = "";
    var $strDebugInfo = "";
    var $arrTiles = array();
    var $arrQueue = array();
    var $arrPath = array();
    var $blnFound = FALSE;
    var $intSourceX;
    var $intSourceY;
    var $intTargetX;
    var $intTargetY;
    var $intTimeTotal = 0;

    var $intMax = 200;
    var $intCount = 0;

    /********************************************************************************************************/
    /* Name         : __construct()
    /* Type         : Public
    /* Parameters   : $arrTiles, Array, a collection of tiles that make up the map.
    /* Return Type  : None
    /* Description  : Class initialisation
    /********************************************************************************************************/

    public function __construct( $arrTiles ) {
      try {
        $this->intTimeTotal = microtime(true);
        $this->arrTiles = $arrTiles;
      }
      catch( Exception $e ) {
        $this->strErrorMsg = $e->getMessage();
      }
    }

    /********************************************************************************************************/
    /* Name         : __destruct()
    /* Type         : Public
    /* Parameters   : None
    /* Return Type  : None
    /* Description  : Class destructor.
    /********************************************************************************************************/

    public function __destruct() {
      //echo "Path: Execution time: " . round( microtime( true ) - $this->intTimeTotal, 3 ) . "s<br>\n";
    }

    /********************************************************************************************************/
    /* Name         : __destruct()
    /* Type         : Public
    /* Parameters   : None
    /* Return Type  : None
    /* Description  : Class destructor.
    /********************************************************************************************************/

    public function ClearObject() {
      try {
        $intReturn = 1;

        $this->intSourceX = NULL;
        $this->intSourceY = NULL;
        $this->intTargetX = NULL;
        $this->intTargetY = NULL;
        unset( $this->arrQueue );
        unset( $this->arrPath );
        $this->arrQueue = array();
        $this->arrPath = array();
        $this->blnFound = FALSE;
        $this->intCount = 0;
      }
      catch( Exception $e ) {
        $this->strErrorMsg = $e->getMessage();
        $intReturn = -1;
      }

      return $intReturn;
    }

    /********************************************************************************************************/
    /* Name         : CompareCost()
    /* Type         : Public
    /* Parameters   : $x, Array, the array with primary tile information.
    /* Return Type  : $y, Array, the array with secondary tile information
    /* Description  : This compares the cost (distance to target) of the two tiles and sees which one is
    /*              : lower in order to use it to sort the queue.
    /********************************************************************************************************/

    private function CompareCost( $x, $y ) {
      if ( $x["cost"] == $y["cost"] ) {
        return 0;
      }
      elseif ( $x["cost"] < $y["cost"] ) {
        return -1;
      }
      else {
        return 1;
      }
    }

    /********************************************************************************************************/
    /* Name         : getPath()
    /* Type         : Public
    /* Parameters   : $intSourceX, Integer, the x-coordinate for the source tile on the map.
    /*              : $intSourceY, Integer, the y-coordinate for the source tile on the map.
    /*              : $intTargetX, Integer, the y-coordinate for the target tile on the map.
    /*              : $intTargetY, Integer, the y-coordinate for the target tile on the map.
    /* Return Type  : Integer.
    /* Description  : This is the main method of this class, which is called and determines the path from
    /*              : source to target.
    /********************************************************************************************************/

    public function getPath( $intSourceX, $intSourceY, $intTargetX, $intTargetY ) {
      try {
        $intReturn = 1;
        //$strOutput = "";
        $this->intSourceX = $intSourceX;
        $this->intSourceY = $intSourceY;
        $this->intTargetX = $intTargetX;
        $this->intTargetY = $intTargetY;

        if ( $this->AddNode( NULL, NULL, $intSourceX, $intSourceY ) < 1 ) {
          throw new Exception( $this->strErrorMsg );
        }

        if ( $this->FindPath( $intSourceX, $intSourceY ) < 1 ) {
          throw new Exception( $this->strErrorMsg );
        }

        if ( $this->blnFound ) {
          //$strOutput .= "Found!<br>\n";

          if ( $this->MakePath() < 1 ) {
            //$strOutput .= $this->strErrorMsg;
            throw new Exception( $this->strErrorMsg );
          }
        }
        else {
          //$strOutput .= "Not found!<br>\n";
        }
      }
      catch( Exception $e ) {
        $this->strErrorMsg = $e->getMessage();
        //$strOutput = $this->strErrorMsg;
        $intReturn = -1;
      }

      //return $strOutput;
      return $intReturn;
    }

    /********************************************************************************************************/
    /* Name         : getStep()
    /* Type         : Public
    /* Parameters   : $intX, Integer (byRef)
    /*              : $intY, Integer (byRef)
    /* Return Type  : Integer.
    /* Description  :
    /********************************************************************************************************/

    public function getStep( &$intX, &$intY ) {
      try {
        $intReturn = 1;

        if ( count( $this->arrPath ) < 1 ) {
          throw new Warning( "No elements in path." );
        }

        //$arrStep = array_pop( $this->arrPath );
        $arrStep = array_pop( $this->arrPath );
        $intX = $arrStep["x"];
        $intY = $arrStep["y"];
      }
      catch( Warning $e ) {
        $this->strErrorMsg = $e->getMessage();
        $intReturn = 0;
      }
      catch( Exception $e ) {
        $this->strErrorMsg = $e->getMessage();
        $intReturn = -1;
      }

      return $intReturn;
    }

    /********************************************************************************************************/
    /* Name         : FindPath()
    /* Type         : Private
    /* Parameters   : $intX, Integer
    /*              : $intY, Integer
    /* Return Type  : Integer.
    /* Description  :
    /********************************************************************************************************/

    private function FindPath( $intX, $intY ) {
      try {
        // Initialise variables.
        $intReturn = 1;

        if ( $this->AddNode( $intX, $intY, $intX - 1, $intY - 1 ) < 1 ) {
          throw new Exception( $this->strErrorMsg );
        }

        if ( $this->AddNode( $intX, $intY, $intX + 0, $intY - 1 ) < 1 ) {
          throw new Exception( $this->strErrorMsg );
        }

        if ( $this->AddNode( $intX, $intY, $intX + 1, $intY - 1 ) < 1 ) {
          throw new Exception( $this->strErrorMsg );
        }

        if ( $this->AddNode( $intX, $intY, $intX - 1, $intY + 0 ) < 1 ) {
          throw new Exception( $this->strErrorMsg );
        }

        if ( $this->AddNode( $intX, $intY, $intX + 1, $intY + 0 ) < 1 ) {
          throw new Exception( $this->strErrorMsg );
        }

        if ( $this->AddNode( $intX, $intY, $intX - 1, $intY + 1 ) < 1 ) {
          throw new Exception( $this->strErrorMsg );
        }

        if ( $this->AddNode( $intX, $intY, $intX + 0, $intY + 1 ) < 1 ) {
          throw new Exception( $this->strErrorMsg );
        }

        if ( $this->AddNode( $intX, $intY, $intX + 1, $intY + 1 ) < 1 ) {
          throw new Exception( $this->strErrorMsg );
        }

        // Sort
        uasort( $this->arrQueue, array( $this, "CompareCost" ) );

        foreach( $this->arrQueue as $arrTileCheck ) {
          $this->intCount++;

          if ( $this->intCount > $this->intMax ) {
            break;
          }

          if ( !$this->blnFound ) {
            if ( !$arrTileCheck["checked"] ) {
              if ( $arrTileCheck["x"] == $this->intTargetX && $arrTileCheck["y"] == $this->intTargetY ) {
                $this->blnFound = TRUE;
                break;
              }
              else {
                $this->arrQueue[$arrTileCheck["x"] . "x" . $arrTileCheck["y"]]["checked"] = TRUE;

                if ( $this->FindPath( $arrTileCheck["x"], $arrTileCheck["y"] ) < 1 ) {
                  throw new Exception( $this->strErrorMsg );
                }
              }
            }
          }
        }
      }
      catch( Exception $e ) {
        $this->strErrorMsg = $e->getMessage();
        $intReturn = -1;
      }

      return $intReturn;
    }

    /********************************************************************************************************/
    /* Name         : AddNode()
    /* Type         : Private
    /* Parameters   : $intParX, Integer
    /*              : $intParX, Integer
    /*              : $intX, Integer
    /*              : $intY, Integer
    /* Return Type  : Integer.
    /* Description  :
    /********************************************************************************************************/

    private function AddNode( $intParX, $intParY, $intX, $intY ) {
      try {
        // Initialise variables.
        $intReturn = 1;

        $strKey = $intX . "x" . $intY;

        if ( $intX > 0 && $intY > 0 ) {
          if ( !array_key_exists( $strKey, $this->arrQueue ) ) {
            if ( $this->arrTiles[$strKey]["block"] == 0 ) {
              $this->arrQueue[$strKey] = array( "parx" => $intParX, "pary" => $intParY, "x" => $intX, "y" => $intY, "checked" => FALSE, "cost" => abs( $this->intTargetX - $intX ) + abs( $this->intTargetY - $intY ) );
            }
          }
        }
      }
      catch( Exception $e ) {
        $this->strErrorMsg = $e->getMessage();
        $intReturn = -1;
      }

      return $intReturn;
    }

    /********************************************************************************************************/
    /* Name         : MakePath()
    /* Type         : Private
    /* Parameters   : None.
    /* Return Type  : Integer.
    /* Description  :
    /********************************************************************************************************/

    private function MakePath() {
      try {
        // Initialise variables.
        $intReturn = 1;

        $arrTile = $this->arrQueue[$this->intTargetX . "x" . $this->intTargetY];

        while( !is_null( $arrTile["x"] ) && !is_null( $arrTile["y"] ) ) {
          $this->arrPath[$arrTile["x"] . "x" . $arrTile["y"]] = array( "x" => $arrTile["x"], "y" => $arrTile["y"] );

          $arrTile = $this->arrQueue[$arrTile["parx"] . "x" . $arrTile["pary"]];
        }
      }
      catch( Exception $e ) {
        $this->strErrorMsg = $e->getMessage();
        $intReturn = -1;
      }

      return $intReturn;
    }

    /********************************************************************************************************/
    /* Name         : LineOfSight()
    /* Type         : Public
    /* Parameters   : $intSourceX, Integer, the x-coordinate for the source tile on the map.
    /*              : $intSourceY, Integer, the y-coordinate for the source tile on the map.
    /*              : $intTargetX, Integer, the y-coordinate for the target tile on the map.
    /*              : $intTargetY, Integer, the y-coordinate for the target tile on the map.
    /*              : $blnLineOfSight, Boolean, By Reference, whether the target tile can be seen (and
    /*              : targeted) from the source tile.
    /* Return Type  : Integer.
    /* Description  :
    /* Date edited  : 2011-01-05
    /* Reason       : In the case of a slope ( so the else statement ) then the increment should always be
    /*              : 0.25, and it shouldn't matter if the intDiffY == 0, since that can never happen there.
    /* Date edited  : 2011-01-06
    /* Reason       : It turns out in case of a slope, we always followed it along the x-axis, which can cause
    /*              : huge jumps along the y-axis if delta-x is smaller than delta-y, skipping potentially
    /*              : blocking tiles. Now we first check if delta-x is bigger than delta-y and then deciding
    /*              : to follow the path along the x-axis or the y-axis. This is much more accurate.
    /********************************************************************************************************/

    public function LineOfSight( $intSourceX, $intSourceY, $intTargetX, $intTargetY, &$blnLineOfSight ) {
      try {
        // Initialise variables.
        $intReturn = 1;
        $blnFound = false;

        // Determine equation.
        $intDiffX = $intTargetX - $intSourceX;
        $intDiffY = $intTargetY - $intSourceY;

        if ( $intDiffX == 0 ) {
          $intTileStart = ( $intDiffY < 0 ) ? $intTargetY : $intSourceY;
          $intTileEnd   = ( $intDiffY < 0 ) ? $intSourceY : $intTargetY;

          for ( $intCount = $intTileStart; $intCount <= $intTileEnd; $intCount++ ) {
            if ( !array_key_exists( $intSourceX . "x" . $intCount, $this->arrTiles ) ) {
              $blnLineOfSight = false;
              break;
            }

            if ( $this->arrTiles[$intSourceX . "x" . $intCount]["block"] == 1 ) {
              $blnLineOfSight = false;
              break;
            }
          }
        }
        elseif ( $intDiffY == 0 ) {
          $intTileStart = ( $intDiffX < 0 ) ? $intTargetX : $intSourceX;
          $intTileEnd   = ( $intDiffX < 0 ) ? $intSourceX : $intTargetX;

          for ( $intCount = $intTileStart; $intCount <= $intTileEnd; $intCount++ ) {
            if ( !array_key_exists( $intCount . "x" . $intSourceY, $this->arrTiles ) ) {
              $blnLineOfSight = false;
              break;
            }

            if ( $this->arrTiles[$intCount . "x" . $intSourceY]["block"] == 1 ) {
              $blnLineOfSight = false;
              break;
            }
          }
        }
        else {
          if ( abs( $intDiffX ) > abs( $intDiffY ) ) {
            $dblSlope = $intDiffY / $intDiffX;
            $dblIntercept = $intSourceY - ( $dblSlope * $intSourceX );
            $dblIncrement = 0.25;

            $intTileStart = ( $intDiffX < 0 ) ? $intTargetX : $intSourceX;
            $intTileEnd   = ( $intDiffX < 0 ) ? $intSourceX : $intTargetX;

            for ( $dblCount = $intTileStart; $dblCount <= $intTileEnd; $dblCount += $dblIncrement ) {
              $intTileX = floor( $dblCount );
              $intTileY = floor( ( $dblCount * $dblSlope ) + $dblIntercept );

              //$this->strDebugInfo .= "Count: " . $dblCount . ", Slope: " . $dblSlope . ", Intercept: " . $dblIntercept . ", [" . $intTileX . "x" . $intTileY . "]: " . $this->arrTiles[$intTileX . "x" . $intTileY]["block"] . "<br>";

              if ( !array_key_exists( $intTileX . "x" . $intTileY, $this->arrTiles ) ) {
                $blnLineOfSight = false;
                break;
              }

              if ( $this->arrTiles[$intTileX . "x" . $intTileY]["block"] == 1 ) {
                $blnLineOfSight = false;
                break;
              }
            }
          }
          else {
            $dblSlope = $intDiffX / $intDiffY;
            $dblIntercept = $intSourceX - ( $dblSlope * $intSourceY );
            $dblIncrement = 0.25;

            $intTileStart = ( $intDiffY < 0 ) ? $intTargetY : $intSourceY;
            $intTileEnd   = ( $intDiffY < 0 ) ? $intSourceY : $intTargetY;

            for ( $dblCount = $intTileStart; $dblCount <= $intTileEnd; $dblCount += $dblIncrement ) {
              $intTileY = floor( $dblCount );
              $intTileX = floor( ( $dblCount * $dblSlope ) + $dblIntercept );

              //$this->strDebugInfo .= "Count: " . $dblCount . ", Slope: " . $dblSlope . ", Intercept: " . $dblIntercept . ", [" . $intTileX . "x" . $intTileY . "]: " . $this->arrTiles[$intTileX . "x" . $intTileY]["block"] . "<br>";

              if ( !array_key_exists( $intTileX . "x" . $intTileY, $this->arrTiles ) ) {
                $blnLineOfSight = false;
                break;
              }

              if ( $this->arrTiles[$intTileX . "x" . $intTileY]["block"] == 1 ) {
                $blnLineOfSight = false;
                break;
              }
            }
          }
        }
      }
      catch( Exception $e ) {
        $this->strErrorMsg = $e->getMessage();
        $intReturn = -1;
      }

      return $intReturn;
    }
  }
?>


Code: [Select]

<?php
  $this->arrTiles["0x1"] = array( "block" => 1, "y" => 1, "x" => 0, "name" => "wall_vertical_3" );
  $this->arrTiles["1x1"] = array( "block" => 0, "y" => 1, "x" => 1, "name" => "ground_dark_2" );
  $this->arrTiles["2x1"] = array( "block" => 0, "y" => 1, "x" => 2, "name" => "ground_dark_2" );
  $this->arrTiles["3x1"] = array( "block" => 0, "y" => 1, "x" => 3, "name" => "ground_dark_5" );
  $this->arrTiles["4x1"] = array( "block" => 0, "y" => 1, "x" => 4, "name" => "ground_dark_5" );
  $this->arrTiles["5x1"] = array( "block" => 0, "y" => 1, "x" => 5, "name" => "ground_dark_4" );
  $this->arrTiles["6x1"] = array( "block" => 1, "y" => 1, "x" => 6, "name" => "wall_vertical_4" );
  $this->arrTiles["7x1"] = array( "block" => 1, "y" => 1, "x" => 7, "name" => "wall_vertical_7" );
  $this->arrTiles["8x1"] = array( "block" => 0, "y" => 1, "x" => 8, "name" => "ground_dark_4" );
  $this->arrTiles["9x1"] = array( "block" => 0, "y" => 1, "x" => 9, "name" => "ground_dark_3" );
?>


[CygnusX]

Your map is not that big.  I don't see any reasons you should have performance issues.  Pacman, the 80's videogame, had A* heuristic algorithm on all (maybe all but 1) of the ghost.  And it was a similar sized map.  So, I see no reason why this should take .5 seconds per NPC.  I would expect it to be more in the range of .05 to .09.  

It will take me some time to break down and analyze your code.  It looks pretty well written though... gj on that.


Edit:  I'm adding notes here as I read through your code:

This may not matter.... but why are you using:

$Array[3x1]

and not

$Array[3][1]

?

[DV8]

The reason for the array being designed that way...I can't really say. It's been a while since I came up with that. Just one of those design decisions, I suppose.

Also, it doesn't take .5 per NPC, it takes about .5 for 10 NPCs. So every step the character takes, it takes about .8 seconds for the AJAX call to update the map, about .5 of which, I'm guessing is path finding related.

[CygnusX]

I'm going to retract my comment on the speed.  My experiences are based on technology from 10 years ago...

Beyond the way you've coded your array, your code looks fairly solid.  However, I'm having difficulty understanding the path search algorithm you've created.  Conceptually, what is it doing?

[DV8]

Essentially, it starts out at the source coordinates, adding all the surrounding tiles that aren't blocked to a queue. This happens in FindPath(). Once it's done that, it sorts the tiles in the queue based on their cost. The cost of each tile is derived from how close their are, in an absolute sense, to the target tile. For each of the tiles in the queue, it checks if it's the target tile, if not, it adds all the surrounding tiles to the queue, sorts them again on the basis of their cost and takes the top one, checking weather it's the target, if not, it adds all the surrounding tiles to the queue, etc.

Once it's found the target tile, it tries to create a path with MakePath() from the target tile back to the source tile. Each tile has a parent tile -- the tile that lead to it -- except for the source tile, so once we trace the path all the way back to the source tile we've got the final and shortest path. We then also know which step to take from the source tile.

Does that make any sense?

[DV8]

I've got a small demo up and running at: http://www.wiredreflexes.com/dev/path/index.php I set that up to do some testing when I was getting some PHP memory issues when I was still running at 8Mb (now 32Mb.)

The green tiles are the path it finds, and the red tiles are tiles that were considered in the queue. I set the limit to the amount of tiles it checks to 2000, instead of 200.

[CygnusX]

Edit:  Edited multiple times.... your logical approach is spot on.

I believe, then, that the root of your problem must lie with general performance issues with PHP.  And i am not familiar with phc.

[codestryke]

I've used APC in the past and had some very good results in some areas. I wasn't running a path finding system but I was running a pretty complex battle simulation which used a lot of looping. The performance gain I had was minimal in that area.

There are a couple of discussions going on right now about performance with the back end (ie the ajax polling questions) and this one. There are a lot of emerging technologies out there that have been mentioned and I'm sure they work very well. My problem with them is I have a limit time for R&D and I have a vision for a game and that game just needs to work. This is when you start having to think outside the box and maybe rethink design based on both the technology you know right now. Things can always change and be re-written later!

With your specific problem you could stick with only running the path finding system when you are coming upon a certain distance with an enemy (I'm assuming this is what your game is doing, finding a target). This will cut down the number of loops you have to run which is the performance killer. You could drop the path finding and do something like a fight or flight system again when a certain proximity is met. These are all things you could test pretty easily and with some creative thinking and tinkering get a faster system that works just as well

[DV8]

As it stands, the system works, it just doesn't work as fast as I want it to, but I am not willing to give up on it just yet. I've considered pre-processed paths, but with multiple enemies trying to find their way to the player, it's going to be difficult not to have them get stuck when they're tripping over one another. I'll have to tinker with it some more because I think that upon reviewing it once again, I think there's some optimisation possible, but for now I'll concentrate on getting the rest of the game up and running.

Thank you for your time.

[Chris]

A* is slow because it is A* Do you really need such sophisticated pathfinding algorithm? Do you have variable terrain cost? Do you have portals? If not maybe use something simplier like floodfill? Or maybe first try raytracing a straight line and only if it fails attempt heavier algorithms?

And above all, drop it on client side. Server side pathfinding for thousands of players... I don't see it working without crashing the server

[CygnusX]

The only other technique you could consider is reducing your map to a series of nodes (macro approach) . You'd place a node at each intersection paths (ie, hallway + door, crossing hallways, etc), and create a map that that describes the quickest route between these node points.  You could also set up barriers, which describe the entrance to a room with no outlet.  In most A* routines, where dead ends and other corridors eat up a lot of your time, these points could prevent your algorithm from doing a lot of unnecessary searching.  I have never seen this done before, but I think it could work.