Pathing

[Hooker]

This is just a quick questions about map-pathing for game i'm considering making for my local games club so don't stress yourselves too much if its alot of trouble :

 

Anyway, i have a map made in php that at the moment is 10x10 squares, each square has a record in mysql. I wanted to know if there was a way to generate a "path" accross the map from one point to another bearing in mind that some squares would be impassable.

 

I could do this in C or VB fairly easily but i don't use PHP alot so any assistance is greatly appreciated.

 

P.S - Just incase the above isn't very clear, my intention is to give people a character and allow them to move from say 1,1 to 10,9 and the path be marked out on the map.

[JasonLewis]

What like some sort of path finding algorithm?

[Hooker]

basicaly, sorry for the poor wording, its been a late night

[JasonLewis]

Okay, can be simple to quite complex.

I've heard of A* Pathfinding, not sure if it will be of any relevance to you and I am not very familiar with it (I've only heard of it).

 

Who knows, it may help you.

 

[Hooker]

Thanks, i'm fairly familiar with A* pathing, i'm just working out the best way to implement it.

[JasonLewis]

Ah well you have 1 up on me. I'm interested now, so I'm going to sit down in a minute and see if I can figure out something with A*.

[Hooker]

im my usual method i've broken it down into seperate sections of code and going at it randomly, right now i'm up to this:

 

//set start/finnish coordiantes to help calculate the G value
$x_start = "1";
$y_start = "1";

$x_finnish = "10";
$y_finnish = "10";

$x_axis_current = "1";
$y_axis_current = "2";

//Select the "open" list for the current block being processed
$result = mysql_query("SELECT * FROM map WHERE X_axis > $x_axis_current-1 AND X_axis < $x_axis_current+1 AND Y_axis > $y_axis_current-1 AND Y_axis < $y_axis_current+1");

while($row = mysql_fetch_array($result))
  {

//calculate next block to enter

  }

mysql_close($con);

 

as far as i can find, not alot of people have done this in php which got me intrested to start with

[Hooker]

calculating the "H" value would be something like this in php presumably..

$h = ($x_finnish - $x_axis_current) + ($y_finnish - $x_axis_current) * 10;

 

[Hooker]

//detecting if it's a diagnal movement or not and assigning the movement cost "G":
If (($row['x_axis'] !=  $x_axis_current) && ($row['y_axis'] !=  $y_axis_current)){
  $G = "14";
} else {
  $G = "10"
}

 

So calculating the "F" value:

$F = $G + $H;

[Hooker]

Okay, so say the layout for the "map" table is something like this:

- x_axis

- y_axis

- movable

   

i'd have something along the lines of this so far:

 

//set start/finnish coordiantes to help calculate the G value
$x_start = "1";
$y_start = "1";

$x_finnish = "10";
$y_finnish = "10";

$x_axis_current = $x_start;
$y_axis_current = $y_start;

while(($x_axis_current != $x_finnish)&&($y_axis_current != $y_finnish)){
//set initial score.
$score = "999999999";

//Select the "open" list for the current block being processed
$result = mysql_query("SELECT * FROM map WHERE X_axis > $x_axis_current-1 AND X_axis < $x_axis_current+1 AND Y_axis > $y_axis_current-1 AND Y_axis < $y_axis_current+1 AND movable = '1'");

  while($row = mysql_fetch_array($result))
  {
    //calculating the "H" value
    $h = ($x_finnish - $x_axis_current) + ($y_finnish - $x_axis_current) * 10;
    //detecting if it's a diagnal movement or not and assigning the movement cost "G":
    IF(($row['x_axis'] !=  $x_axis_current) && ($row['y_axis'] !=  $y_axis_current)){
      $G = "14";
    } else {
      $G = "10"
    }

    //calculating the "F" value:
    $F = $G + $H;

  //If the square being checked has an F score lower than the previous, set as the next square to move to
    IF($F < $score){
      $score = $F;
      $x_axis_current = $row['x_axis'];
      $y_axis_current = $row['y_axis'];
    }
  }
}
mysql_close($con);

all untested + veyr messey and could be complete rubbish, like i said i don't use PHP much but apart from some syntax errors which there are all over the place presumably, in theorey it should work..

 

[blinky001]

Afraid I've never tried to do this in PHP, but I did have a go starting from someone elses script once in JS, sadly my Zelda clone was too boring to work on for very long...

 

//pathFinder.js

function pathFinder(grid)
{
    this.grid    = grid;
    this.cols    = grid[0].length;
    this.rows    = grid.length;
    this.limit   = this.cols * this.rows;
}

pathFinder.prototype = {

    // Variables ---------------------------------------------------------
    grid:    new Array(),
    start:    new Array(),
    end:    new Array(),
    cols:    0,
    rows:    0,
    limit:    0,

    
    // Returns boolean value (Grid cell is available and open)
    inGrid: function(x, y)
    {
        return this.grid[y][x] === 1;
    },


    // Node function, returns a new object with Node properties
    node: function(parent, point)
    {
        return {
            parent: parent,
            value:    point.x + (point.y * this.cols),
            x:        point.x,
            y:        point.y,
            f:        0,
            g:        0
        };
    },


    calculatePath: function(start, end)
    {
        this.start    = start;
        this.end    = end;

        var    startNode        = this.node(null, {x:this.start[0], y:this.start[1]}),
            endNode            = this.node(null, {x:this.end[0], y:this.end[1]}),
            AStar            = new Array(this.limit),    
            openArray        = [startNode], 
            closedArray        = [], 
            resultArray        = [],
            successorNodes, 
            currentNode, 
            pathNodes, 
            length, 
            max, 
            min, 
            i, 
            j;    

        while(length = openArray.length)
        {
            max = this.limit;
            min = -1;

            for(i = 0; i < length; i++)
            {
                if(openArray[i].f < max)
                {
                    max = openArray[i].f;
                    min = i;
                }
            }

            currentNode = openArray.splice(min, 1)[0];

            if(currentNode.value === endNode.value)
            {
                pathNodes = closedArray[closedArray.push(pathNodes) - 1];

                do
                {
                    resultArray.push([pathNodes.x, pathNodes.y]);
                }
                while(pathNodes = pathNodes.parent);

                AStar = closedArray = openArray = [];

                resultArray.reverse();
            }
            else
            {
                successorNodes = this.successors(currentNode.x, currentNode.y);

                for(i = 0, j = successorNodes.length; i < j; i++)
                {
                    pathNodes = this.node(currentNode, successorNodes[i]);

                    if(!AStar[pathNodes.value])
                    {
                        pathNodes.g = currentNode.g + this.manhattan(successorNodes[i], currentNode);
                        pathNodes.f = pathNodes.g + this.manhattan(successorNodes[i], endNode);

                        openArray.push(pathNodes);

                        AStar[pathNodes.value] = true;
                    }
                }

                closedArray.push(currentNode);
            }
        }

        return resultArray;
    },


    // Find adjacent available cells - returns every available North, South, East or West cell
    successors: function(x, y)
    {
        var    N = y - 1,
            S = y + 1,
            E = x + 1,
            W = x - 1,
            $N = N > -1 && this.inGrid(x, N),
            $S = S < this.rows && this.inGrid(x, S),
            $E = E < this.cols && this.inGrid(E, y),
            $W = W > -1 && this.inGrid(W, y),
            result = [];

        if($N)
        {
            result.push({x:x, y:N});
        }

        if($E)
        {
            result.push({x:E, y:y});
        }

        if($S)
        {
            result.push({x:x, y:S});
        }

        if($W)
        {
            result.push({x:W, y:y});
        }

        //this.diagonalSuccessors($N, $S, $E, $W, N, S, E, W, result);

        return result;
    },
    

    diagonalSuccessors: function($N, $S, $E, $W, N, S, E, W, result)
    {
        if($N)
        {
            if($E && this.inGrid(E, N))
            {
                result.push({x:E, y:N});
            }

            if($W && this.inGrid(W, N))
            {
                result.push({x:W, y:N});
            }
        }

        if($S)
        {
            if($E && this.inGrid(E, S))
            {
                result.push({x:E, y:S});
            }

            if($W && this.inGrid(W, S))
            {
                result.push({x:W, y:S});
            }
        }
    },


    diagonalSuccessors$: function($N, $S, $E, $W, N, S, E, W, result)
    {
        $N = N > -1;
        $S = S < this.rows;
        $E = E < this.cols;
        $W = W > -1;

        if($E)
        {
            if($N && this.inGrid(E, N))
            {
                result.push({x:E, y:N});
            }

            if($S && this.inGrid(E, S))
            {
                result.push({x:E, y:S});
            }
        }

        if($W)
        {
            if($N && this.inGrid(W, N))
            {
                result.push({x:W, y:N});
            }

            if($S && this.inGrid(W, S))
            {
                result.push({x:W, y:S});
            }
        }
    },


    // Distance functions, returns ideal distance from 2 points

    diagonal: function(point, end)
    {
        // diagonal movement
        return Math.max(Math.abs(Point.x - end.x), Math.abs(Point.y - end.y));
    },
    

    euclidean: function(point, end)
    {
        // diagonal movement using Euclide (AC = sqrt(AB^2 + BC^2))
        //    where AB = x2 - x1 and BC = y2 - y1 and AC will be [x3, y3]
        return Math.sqrt(Math.pow(point.x - end.x, 2) + Math.pow(point.y - end.y, 2));
    },
    

    manhattan: function(point, end)
    {
        // linear movement
        return Math.abs(point.x - end.x) + Math.abs(point.y - end.y);
    }

}

 

and usage test:

 

//pathFinderDemo.js

window.onload = function()
{
    var movementMap = 
    [
        [1, 1, 0, 1, 1, 1],
        [1, 1, 0, 1, 0, 1],
        [1, 1, 0, 1, 0, 1],
        [1, 1, 0, 1, 0, 1],
        [1, 1, 1, 1, 0, 1],
    ];

    for(y = 0; y < movementMap.length; y++)
    {
        // Loop Width
        for(x = 0; x < movementMap[0].length; x++)
        {
            var element = document.createElement('div');

            element.style.position    = 'absolute';
            element.style.left        = (x * 32) + 'px';
            element.style.top        = (y * 32) + 'px';
            element.style.width        = 32 + 'px';
            element.style.height    = 32 + 'px';
            element.id                = x + '_' + y;

            if(movementMap[y][x] == 1)
            {
                element.style.backgroundColor = 'blue';
            }
            else
            {
                element.style.backgroundColor = 'red';
            }

            document.getElementById('map').appendChild(element);
        }
    }

    var startPoint    = [0, 2];
    var endPoint    = [5, 4];

    if(path = new pathFinder(movementMap))
    {
        result = path.calculatePath(startPoint, endPoint, 'Manhattan');
    
        if(result.length == 0)
        {
            alert('damn');
        }
        else
        {
            for(var i = 0; i < result.length; i++)
            {
                x = result[i][0];
                y = result[i][1];

                var element = document.createElement('div');

                element.style.position    = 'absolute';
                element.style.left        = (x * 32) + 'px';
                element.style.top        = (y * 32) + 'px';
                element.style.width        = 32 + 'px';
                element.style.height    = 32 + 'px';
                element.id                = 'p_' + x + '_' + y;

                element.style.backgroundColor = 'green';

                element.style.textAlign    = 'center';

                element.innerHTML = i + 1;

                document.getElementById('map').appendChild(element);
            }
        }
    }

}

 

and the basic html to let you see it:

 

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">

<head>

    <title> Pathfinder Demo </title>

    <meta name="author" content="" />
    <meta name="keywords" content="" />
    <meta name="description" content="" />

    <script src="pathFinder.js" type="text/javascript"></script>
    <script src="pathFinderDemo.js" type="text/javascript"></script>

</head>

<body>
    
    <div id="map"></div>

</body>

</html>

[Hooker]

i don't use java so i could be off the mark but my very quickly thrown together code seems to be along the same tracks in alot of areas (obvious changes because of languages/the fact im using a DB aside) which is atleast encouraging for an hours playing.

 

the only part i don't account for is the removal of squares that have already been occupied from the "available movements" list, it's a little redundent to me since i can't see the F value of those squares being any lower than a square nearer the final destination while im just using the manhattan method.

 

ie. you're a square closer, the previous square gets +10 to its F value so even if you're moving in a diagnol and encouring the +4 penalty the difference would still be 6

[JasonLewis]

Ah pathfinding is confusing. It's interesting, yet so confusing.

[Hooker]

the basic idea is to loop through all the ajacent squares to the current square you're in assigning them values based on the distance away from the final square (without using diagnol movements) and the difficulty to move into the next square.

 

in the case diagnols are valued at a 14 difficulty and horizontal/verticle movements are valued at 10 so a horizontal/verticle movement will always get priority unless that square is further away from the final target square than the diagnol o.o

 

anyway, i think i have the basics down in my above post, i just need someone a little more php-savvy to check the syntax

 

i can give better comments on what i'm actualy trying to acheive at each point of the query if that helps.

[Hooker]

This is what i have so far:

<?php
mysql_connect("localhost", "username", "password") or die(mysql_error());
mysql_select_db("database") or die(mysql_error());

//set start/finnish coordiantes to help calculate the G value
$x_start = "2";
$y_start = "2";
$x_finnish = "10";
$y_finnish = "10";

//check if there is a "current" square, if not, set it as the start square
if((!isset($x_axis_current))||(!isset($y_axis_curren))){
  $x_axis_current = $x_start;
  $y_axis_current = $y_start;
}

//Check whether the current square being checked is the "finnish" square and stop if it is
while(($x_axis_current != $x_finnish)&&($y_axis_current != $y_finnish)){

//Select the "open" list for the current square being processed
$result = mysql_query("SELECT * FROM map WHERE 
(x_axis = $x_axis_current-1 OR x_axis = $x_axis_current+1 OR x_axis = $x_axis_current)
AND (y_axis = $y_axis_current-1 OR y_axis = $y_axis_current+1 OR y_axis = $y_axis_current)
AND CONCAT(y_axis, ',', x_axis) != $y_axis_current
AND movable = '1'") or die(mysql_error());

  while($row = mysql_fetch_array($result))
  {
    //calculating the "H" value
    $h = ($x_finnish - $x_axis_current) + ($y_finnish - $x_axis_current) * 10;

    //detecting if it's a diagnal movement or not and assigning the movement cost "G"
    IF(($row['x_axis'] !=  $x_axis_current) && ($row['y_axis'] !=  $y_axis_current)){
      $G = "14";
     } else {
      $G = "10";
    }

    //calculating the "F" value:
    $F = $G + $H;

    //set a default "score" if this is the first square being checked
    if(!isset($score)){
    $score = "99999";
    }

    //If the square being checked has an F score lower than the previous, set as the next square to move to
    if($F < $score){
      $score = $F;
      //Set the next square to be used (this will probably be changed several times as it checks all available squares but by the end of the while loop it should be the square with the lowest "F" value)
      $x_axis_current = $row['x_axis'];
      $y_axis_current = $row['y_axis'];
    }

  }

    echo $x_axis_current.",".$y_axis_current."<br>";

}

?>

 

i just seem to get spammed with "1,3" when i run it, im sure this is a syntax issue, any ideas?

[JasonLewis]

Um, didn't look. Sorry. I've been working on mine for a while now. It seems to work, actually. But it screws up a bit at the end, with the open and closed lists.

 

I'll take a look later, when (if) I finish mine.

 

It's challenging, which is good.

[JasonLewis]

Okay I successfully made a path finder that sometimes finds the right path. It needs more work, and optimizations and recoding in many spots. I don't want to release the source yet, but I've made a live version.

You can change the blocked tile, the start and the end tile. I wouldn't recommend boxing the end tile in either. Bad things happen.

 

Check it out here.

 

What a challenge it was!

 

Oh and it's pretty slow, due to the fact that I did it pretty bad. It could do with a lot of optimization. But I'll worry about that later.

[Hooker]

looks good, does it use a db?

[JasonLewis]

No, I didn't put a database behind it. It's just using sessions to store your X/Y positions etc. Wouldn't be hard to implement a DB though. I've already spotted a few errors. But all-in-all it seems to work okay.

 

It's pretty dodge actually, ran a few more tests. It's so stupid sometimes. I'll look at it later though.

[Hooker]

cool, well it looks good

[Hooker]

As you can see in my attempt erlier in this thread the plan was to:

 

- Have the user assign the start and the finnish variables (x&y split into two variables for each)

- Assign a variable for the current coordinate the script is processing (again split into x&y)

- Start the loop to check if the current variable is the same as the finnish variable (obviously, if its done. stop.)

- Pull each coordinate within 1 of the current coordinate out of the mysql table

- Start a loop to calculate each squares F value 1 by 1, if the F value is smaller than the previous, assign its coordinates to the "current coordinates" variables

- Once the loop is finnished and the coordinates the the lowest F value is assigned, pass them on to the parent loop and check if it's at the end or not.

 

on the spot i can't see a fault in the logic, perhaps someone could make suggestions to the logic or look at the code i posted erlier in this thread and point out any flaws?

 

thanks

[ugly]

I am new to PHP. I have XAMPP on my system. I am trying to run a simple PHP, hello world file. when I put on the browser " 127.0.0.1/helo.php it does not work and error message comes like page can not be found. On my XAMPP status, mySQL, PHP,SSL, CGI, SSI, SMTP, and FTP all are activated and running. please help.

Thanks

[JasonLewis]

Start a new topic mate. This is a bit old.