Pathfinding Algorithm

by Crazy Star


Posted on July 05, 2005 at 4:00 AM



Second version is out. I should have released this a long time ago but I wanted to do two tied pathfinding or whatsitcalled. Oh well, it'll be in next version probably.

This is a pathfinding algorithm similar to those found preinstalled in gamemaker only these works in a different way and supports things as terrain penalties isometric and hexagonal (and more) grids, and the thing I mentioned for next version.

Don't mind the screenshots my computer is very slow. Have a look for yourself before deciding to use the (bad) inbuild functions.

reference article:
http://www.policyalmanac.org/games/aStarTutorial.htm
<big>EDIT:</big>
No, no new version yet but I'm working on it right now. Just wanted to let everyone know that the next version is going to show you several uses for this example.

PLANNED FOR NEXT/FUTURE VERSIONS:
<ul>
<li>Two and three tiered pathfing both isometric and square. Will probably be made so you can have endless amounts of sizes (tieres? heh...) (which I'm working on right now actually)</li>
<li>Variations on square and isometric. Like, 4 and 8 directional, cut corners / don't cut corners, ...</li>
<li>Several variations of the same example. Like, one that shows a graphical presentation of what it does, one that tests speed (and possibly compares the speed to the other examples (not in next version)), maybe more if I can think of more...</li>
<li>Simple games using the scripts that shows you how to implement it to your own game</li>
<li>Second last and also least: actually move to the target after finding the path</li>
<li>Better comments :)</li>
</ul>



Alpha Man commented October 29, 2005 at 5:12 AM
I think this is extremly good. I might just use this! For a FE style hex based game! Hmm... *writes some things down*
matthewjumps commented December 02, 2005 at 2:35 AM
Damn this looks good. CAnt wait for new version

thanks dude
Crazy Star commented April 29, 2006 at 3:22 PM
2nd version out
neonut99 commented May 16, 2006 at 10:50 PM
top score 11356 hahahah its easy. just walk side ways and shoot forwards, back, forward back. This is great example too [:P]
DFortun81 commented August 10, 2006 at 9:41 PM
nice man.
Jesper commented September 02, 2006 at 8:12 PM
It's good but not very usefull. GameMaker has a script for this already.
Crazy Star commented September 03, 2006 at 11:02 AM
It's good but not very usefull. GameMaker has a script for this already
Quote
Only the inbuild one sucks, and has less possibilities.
mesenberg commented November 14, 2006 at 11:26 PM
this is sweet.
Flea1991 commented December 08, 2006 at 4:23 PM
Cool.

-Flea
Ph0x commented April 09, 2007 at 9:03 PM
the hex on is cool
Zac1790 commented December 02, 2007 at 7:49 PM
Terrain penalties? wow I really need to keep this for the rest of my life. Downloaded and archived.
Shrooblord commented October 20, 2009 at 11:45 AM
Hey, SpectreNectar.

I was just posting this because I noticed that my Game Maker doesn't support the ds_grid_ functions. I own GM6 PRO and my Game Maker keeps coming up with an error message that the function ds_grid_create in script init_iso. Probably it doesn't support any of the other ds_grid_ functions either, so I came here to ask what I should do. I have noticed that the last post was since 2007, and I'm sorry for reviving such an old thread, but I need a little help here.
Glen commented March 31, 2012 at 8:19 PM
Necro'd, but I'd like to know if you have a way to make the original block move along the path. I'm working with the isometric version.
hel commented March 31, 2012 at 8:32 PM
oh wow i love how the hex finding one works, i want to code something like it just to see if i can lol
Alert Games commented March 31, 2012 at 9:04 PM
its only been 7 years since he has posted this. guess i could try it out now
Crazy Star commented March 31, 2012 at 9:18 PM
Oh lol this old thing - I thought for sure someone else had uploaded an example like this when I saw it in the feed =)
Cool though, the trick to move along the path is to save the path list as well as the index (node) you're currently at.
So what you do is you move towards the next position, delete it when you reach it, then go for the next. Obviously. Here's a code example:

[step event]
{
if(!ds_list_empty(list_path)) {
    var journey;
    journey = 20.0;
    while(journey>0 && !ds_list_empty(list_path)) {
        var node;
        node = ds_list_find_value(list_path, ds_list_size(list_path)-1);
        
        var tx, ty;
        tx = ds_grid_get(grid_state, node, CELL_X);
        ty = ds_grid_get(grid_state, node, CELL_Y);
        
        var pdis, pdir;
        pdis = point_distance(x, y, tx, ty);
        pdir = point_direction(x, y, tx, ty);
        
        if(pdis<=journey) {
            x = tx;
            y = ty;
            ds_list_delete(list_path, ds_list_size(list_path)-1);
            journey-=pdis;
        } else {
            x+=lengthdir_x(journey, pdir);
            y+=lengthdir_y(journey, pdir);
            journey=-1.0;
        }
    }
    snaptogrid_iso();
}
}

Cheers Hel
Glen commented April 01, 2012 at 5:10 AM
That code seemed to work pretty well, but the moving object disappeared once it reached the last point.
-edit-

it seems to be snapping to the grid under the white blocks every one in awhile.
Crazy Star commented April 01, 2012 at 11:16 AM
Well what I did was insert the code in the c_pathfind_iso object after the mouse script and change the sprite of obstacle to the smallest isometric one. Like in the second screenshot. I couldn't mimic the behavior you mention. What did you do exactly?
Glen commented April 01, 2012 at 9:44 PM
It doesn't follow the green blocks exactly. A lot of times it moves "next" to them and seems to always stop on the block right next to the point you click. http://64digits.com/download.php?id=30731&dir=0
Moikle commented April 01, 2012 at 10:19 PM
@activity feed: WITCHCRAFT

edit Wait, wat
"I'm pregnant" had a game icon and switched places with this in the feed, I clicked on what I thought was a game called "I'm pregnant" thinking Tha fuq is this? and it sent me to this