A simple PHP pathfinder class

May 25, 2010 at 22:55

I recently shared a simple PHP and jQuery animated pathfinding tech-demo through my Twitter account and promised to share the simple pathfinding class used for pathfinding calculations. The example shared in Twitter is still available here.

This example has a few limits, that is you can easily confuse it by clicking on two tile locations in a row. But in general it works and what I will be using this for will be something a bit different, so this limitation was of no concern to me. However the entire pathfinding calculation takes place on PHP backend. Each map is essentially a square (currently a limitation of pathfinder, but can easily be tweaked) and stored as an associative array, every tile in that array like this:

$map['1x1']['weight']=1.0;

The first key is the coordinate of the single map tile and the weight key is used to store weight of this map tile for calculations. Nothing else is needed (and an example is provided in the files below). For actual game purposes or whatnot you can store additional information on that very map as long as the coordinate and weight are assigned as shown in the example. For example, in my own tech-demo I also store the graphic tile used in the map array.

Finding the actual path is just as simple:

$map=getMap();
require(‘class.pathfinder.php’);
$path=new PathFinder();
//Create new pathfinder object
$path->setOrigin(1,1);
//Set the start location
$path->setDestination(20,20);
//Set the destination
$path->setMap($map);
//Assign the map to use for calculations
$result=$path->returnPath();
//Returns an array of all the walked steps

Working example, as well as commented pathfinder class is available below:

Download the class and example file here

Please note that this is not a definitive pathfinder. It only takes into account one square ahead and on very large maps I am sure there are more ideal solutions. But for your basic browser based game this is a good starting point and I learned a lot by creating it. This is also easy to expand based on your needs.

If you have any other questions, let me know.

The code is shared entirely free for personal or commercial use.

Cheers!


Tags: ,

7 Responses to “A simple PHP pathfinder class”

  • Streak says:

    Unfortunately, the example page (http://waher.net/pathfinder/) is not available :( Otherwise, a very fine thing.

    Cheese and best greet:=)

  • Kristo Vaher says:

    My mistake, the website was compromised not too long ago and it seems the jquery file was incomplete. It should work now.

    Thanks for pointing it out!

  • Ralf says:

    Hi Kristo,

    the class ist cool, But unfortunately I do not understand how the demo works.
    I have tried everything possible to move any figure on my map, but unfortunately all in vain. Maybe you can help me, because you have solved it so wonderfully

    Best regards, Ralf

  • Kristo Vaher says:

    Well it requires a bit more knowledge to implement the pathfinder class, pathfinder class is mainly intended for only finding the shortest path. This example includes an entire user interface which uses that. But if you’re interested, I have it uploaded here:

    http://waher.net/pathfinder/pathfinder.rar

    It’s not documented and explained though, since it was not meant for public release, but perhaps it helps.

  • David c says:

    Hi there, I’ve recently been looking around on Google to find a pathfinder that I can incorporate into my website. The reason I’m looking to do this is for a game that I play more so for the purpose of learning new programming techniques, well anyway, the game has a 2d map and I am trying to get from point A on the map to point B, in each node of the map there are 4 possible directions that you can go, North, South, East and West.

    http://i55.tinypic.com/213okkk.jpg

    That is an example of what a piece of the map looks like, I added lines to show each room individually. I can’t quite grasp how your solution works, the map array that it creates, are there 4 different ways that you can move on it? That’s kind of what I don’t understand about your ‘weight’ part of the class.

    Any information on this would be greatly appreciated! Your example is the most simplistic I’ve found as yet and I would love to figure it out to work for my needs :)

    Thanks, Dave.

  • Kristo Vaher says:

    Hey there!

    The working example that runs in http://waher.net/pathfinder can be downloaded from here: http://waher.net/pathfinder.rar

    In my implementation of pathfinder the movement can be not just in four directions but in eight directions (also diagonally). Every ‘square’ on a map has weight, aka how easy this tile is to be passed, so on a more complicated map you could have plains and forests and the solution would prefer to use the plains, rather than forests.

    If you look at my example, then I generate a map there with getMap() function in functions.php

    It is entirely hardcoded in getMap() functon, in reality this should be called from database for example. The snippet I used to randomly generate that map is also there, commented out.

    So the entire map is an array, consisting of tile graphic (which is only used for rendering), modifier (which I planned to use for other purposes, but didn’t) and weight (during pathfinding the system will always prefer tiles with lower weights, so if you want to make a tile unpassable, just give it a very high weight).

    If you have further problems, let me know. I’ll gladly help get this solution of yours working (I am at work right now though, so apologies if I am unable to respond right away).

    -K

Leave a Reply

You must be logged in to post a comment.