23 replies to this topic

[paul23]

GPathfinding
A generic, cell-based "A*" pathfinding dll for gamemaker


last update: 25/1/2010

What makes this dll exceptional
This dll has the intention to extend the very limited functionality from mp_grids, while keeping it's speed, it especially has support for "cost-based" pathfinding, and to give the user better "time-management" to prevent lagging. Also it allows for a great number of import and export options to insert those "costs" (and extract paths).
The good thing is that it doesn't come with much lag. Creating a 200 * 200 cells room (thus 40 000 cells) where the end is "blocked" by 8 cells, and using 8-directions-based movement. Which is the worst case: it still can perform 85 dll-calls a second. Similar, the same world using mp_grid_path() calls we can perform 100 calls a step.

downloads
(version 1)

The download is a zip file containing 5 files:
GPath.dll - The main dll.
GPF_Tutorial.pdf - An extensive manual about all features of GPathfinding
Gpath7.gmk - an gamemaker 7 example file,
Gpath8.gmk - an gamemaker 8 example file (almost the same as above, only a supporting script is slightly different).
GPathfinding.gmres - A gamemaker 8 resource file, containing all scripts and constants for the heuristic-distance function


updates

• Redone/renamed the entire function list
• added full compatibility for gm8
• build a tutorial
• build an example program
• added a few smaller functions
• fixed a lot of small bugs

Important features
These are a few of the features currently in the dll. (If the feature is followed by {GMX} there is a number it means it's only for X version of gamemaker)

• cells can have different costs (or -1 meaning "infinite")
• 4, or 8 way development
• Not-infinite pathfinding calls. (You can define the maximum depth a call should make, and at a later call continue the search)
• Handles correctly bigger objects (objects which are larger than 1 cell)
• setting of multiple nodes at once
• setting while inputting 'real world' rectangles or ellipses
• Importing objects as "obstacles" with a cost
• Importing ds_girds
• Export to paths, lists, queues and stacks
• Multiple pathfinding systems at the same time
• Custom (in gamemaker written) heuristic functions

Basic help
The pdf tutorial inside the zip-package should be considered vital for anyone, and as quick reference you can use the in-script comments.
But it all comes down to simply those 5 steps:

• Load the dll: GPF_Init(dllname)
• create a pathfinding system: pid = GPF_Create(xstart,ystart, xend,yend, gridwidth,gridheight, cellwidth,cellheight, xoffset,yoffset)
• Add obstacles to the system-grid: GPF_Set(pid,x,y,value)
• Calculate the path: GPF_Calculate(pid,-1,false)
• Export the path: GPF_ExportPath(pid,gmpath)

Function list
There are at the moment of writing about 70 scripts which you can use, here is a quick overview.

GPF_Create(xstart,ystart,xend,yend,w,h, xoffset,yoffset,cellw,cellh)GPF_CopySystem(pid)GPF_Release(pid)GPF_ReleaseAll()GPF_Resize(pid,w,h)GPF_SetDimensions(pid,w,h,xoffset,yoffset,cellw,cellh)GPF_SetNumdir(pid,numdir)GPF_SetDistancefunc(pid,disfunc)GPF_SetCutcorners(pid,cutcorners)GPF_SetPathfindingoptions(pid,numdir,disfunc,cutcorners)GPF_SetMover(pid,width,height)GPF_GetWidth(pid)GPF_GetHeight(pid)GPF_GetCellWidth(pid)GPF_GetCellHeight(pid)GPF_GetXoffset(pid)GPF_GetYoffset(pid)GPF_Set(pid,x,y,v)GPF_SetArea(pid,x,y,x2,y2,v)GPF_Add(pid,x,y,v)GPF_AddArea(pid,x,y,x2,y2,v)GPF_Rem(pid,x,y,v)GPF_RemArea(pid,x,y,x2,y2,v)GPF_SetRectangle(pid,x,y,x2,y2,v)GPF_SetCircle(pid,x,y,r,v)GPF_SetEllipse(pid,x,y,x2,y2,v)GPF_AddRectangle(pid,x,y,x2,y2,v)GPF_AddCircle(pid,x,y,r,v)GPF_AddEllipse(pid,x,y,x2,y2,v)GPF_RemRectangle(pid,x,y,x2,y2,v)GPF_RemCircle(pid,x,y,r,v)GPF_RemEllipse(pid,x,y,x2,y2,v)GPF_SetObjectRect(pid,objid,v)GPF_AddObjectRect(pid,objid,v)GPF_RemObjectRect(pid,objid,v)GPF_SetObjectEllip(pid,objid,v)GPF_AddObjectEllip(pid,objid,v)GPF_RemObjectEllip(pid,objid,v)GPF_ImportGmGrid(pid,grid)GPF_SetGmGrid(pid,grid)GPF_AddGmGrid(pid,grid)GPF_Fill(pid,v)GPF_SetStart(pid,x,y)GPF_SetEnd(pid,x,y)GPF_GetStartX(pid)GPF_GetStartY(pid)GPF_GetStart(pid)GPF_GetEndX(pid)GPF_GetEndY(pid)GPF_GetEnd(pid)GPF_GetCost(pid,x,y)GPF_CalculatePath(pid,steps,update)GPF_GetState(pid)GPF_GetCalc(pid)GPF_GetFound(pid)GPF_Cleanup(pid)GPF_PathNumPoints(pid)GPF_PathLength(pid)GPF_PathCost(pid)GPF_PathPointX(pid,num)GPF_PathPointY(pid,num)GPF_PathPoint(pid,num)GPF_ExportPath(pid,gmpath)GPF_ExportPathExt(pid,gmpath)GPF_ExportList(pid,list)GPF_ExportStack(pid,stack)GPF_ExportQueue(pid,queue)GPF_DebugDraw(pid,maxv)

Planned updates
The gm7 version should be considered "finished": I will only fix possible bugs, and add functions which are necessary for the dll to work completely. - But new features will be added to the gm8 version (and if they work for gm7, that's a nice extra). But what I like to add:
The way objects are added with GPF_SetObject... I don't find satisfying (basically the fact that it is an object is ignored after the adding). What I like to make is that the dll remembers the objects added, and their value. That should allow for easier removal, and could possibly combined with motion prediction.. (To create paths who work correctly with moving objects).
Another item of interest is to add the possibility for "wierd" ends: where the end-point is not a simple item but instead a list of points - or possibly a polygon.
Different pathfinding-algorithms are also in my to-do list.. (Some other algorithms have specific uses).
Also I'm open for any other suggestions!

Thanks, and have fun enhancing the AI of your game with these dlls,
Paul Weijtens

Edited by paul23, 10 February 2010 - 12:14 PM.

[Krisando]

Marvelous, this is capable of doing real-time path-finding is it not? This has been a major problem in the other A* path finding dll, the creator at the time just couldn't get it to do so and ended up moving through objects which had recently blocked the set path.

[InCreator[EST]]

How does it work?
I see some path and rectangle/etc drawing functions here, but could not get a single path drawn on screen (v8).
A few lines explaining usage would be nice...

Also, startx seems to be -1 all the time unless LMB is held down???

Edited by InCreator[EST], 25 January 2010 - 04:00 PM.

[paul23]

Marvelous, this is capable of doing real-time path-finding is it not? This has been a major problem in the other A* path finding dll, the creator at the time just couldn't get it to do so and ended up moving through objects which had recently blocked the set path.

uhm well not really.. What you describe is one of the most difficult problems to overcome for pathfinding...

On the other hand if you do a "non infinite" pathfinding call, and then the next step changes something (in a part that haven't been discovered yet), it will indeed take into account this object (and even an end-change would work). However for already "found" parts of the path, it won't update correctly..


I am thinking about using the "parenting" map (when debug drawing, it are all the small black arrows) to help making "future" calls to a similar environment (only small changes) faster..

@increator:

Well the problem with gm8 - version is that it simply doesn't have the export options, nor the good exporting options (to export the "calculated" path into an "gm" path).

That rectangle/ellipse drawing you see is a "test" to generate "costs" (the startx, starty means the position where you started to click, they don't have anything to do with the path).
With the right-mouse-button one could set the start (and while holding control) the end..

This means you manually have to get all paths points, using GPF_PathPointX, GPF_PathPointY (one could create script): I didn't do this yet since somewhere this week GMAPI for gamemaker 8 should come out I believe.. And it's a bit of a waste of time to create a script then..

OW I noticed a missing function:
GPF_PathLength() - you obviously need that function for creating your own "export" method - give me a few minutes to recompile/upload everything



EDIT: UPDATE! (see first post)

Edited by paul23, 25 January 2010 - 05:08 PM.

[Krisando]

The movement debugging would be awesome. Also re-acquiring its path every cell you move into would be sufficient for carefully planned movement engines. Would avoid any such obstacles entirely.

[paul23]

Well collision avoidance is a subject completely of its own.. In most professional games the path is simply calculated first, and then while walking it is capable of handling such "irregular" problems.. (mostly done by raycasting).
The main problem with any such an update to A* is that it makes it more specific to a certain type of game. - There is no "one size fits all" answer for the "changeable worlds" (other than to recalculate everything all over again). - For example if the changes are predictable ahead of time (or we can make good guesses where they are), it calls for a "time variable" to go inside the pathfinding system: and we can avoid the objects while calculating the paths easy. (though it won't be 100% perfect, for example the pathfinding system won't consider "standing at the spot")..
Another method uses the "on obstacle recalculate" pathfinding algorithm: once it meets an object it will recalculate its way around it (back to the original path).. This is "fast", however can produce very bad paths. (the original AoE used something like this: and it let to very strange results when you for example suddenly build a long wall before an enemy).

Another, exceptional good, "generic" method is to use Lifelong planning A* (LPA*).This system uses the previous pathfinding data to calculate future paths faster, so it can very well comprehend to small changes in the map. However LPA* that has the problem that all pathfinding data is stored. And thus for each instance you would need to have a new pathfinding system. - Even though memory is cheap, doing this for possibly 100-200 units like RTS games have reaches into the megabytes of extra memory used. (but if your game uses only 4-5 AI's, this might be interesting).

Also there exist the always nice Hierarchy pathfinding A*: this creates layers from the world and then first calculates the path on the "top level" (which consist of very large cells) and then goes down to the smaller level(s).. This method can very well incorporate small changes to the map (it just has to update the lower level layers, it can asume the higher (bigger tiles) layers aren't really changed. The problem with this method is that it won't always give optimal paths.. And it performs very,very badly in maze like environments.. (might return "no path possible" while there is a path possible).

A complete other approach would be to use "nav-meshes", in open maps using these things would make pathfinding 2-4 times as fast (probably even more), and in indoor/maze environments it shouldn't have a big strain on the speed..
Problem however is how to create the mesh: indoor/maze like environments have total different needs for meshes as outdoor maps (outdoor have generally more open space than non-accessible area, indoor it's the opposite). Also updating the map might become time consuming (and thus it's even worse with changeable maps than standard pathfinding methods). - On the other hand, small changes to the maps CAN be ignored, and it ties very well with HPA*.
Also, calculates with "width", and such are not easy, and for large objects these nav-meshes might be a bigger problem than I can foresee now.


Basically I am just wondering what the needs here are (it also the main reason I am posting this): I WILL improve this DLL for the needs of the people here.. (In the future I will probably create different dlls, for different types).
Currently I am still ironing out the basic A* dll (I just updated the internal scripts so 4-directional movements don't have the penalty of the capability of 8 directional movement).

[icuurd12b42]

One limited fn I find in GM is the resulting movement, like yours, is 8 or 4 direction. I think it would be cool to add a feature to find the path that is most direct. eg you do the a* then strip away the cells that forces it to move in a robotic 8 directional way.

Picture


Lime line.

[paul23]

One limited fn I find in GM is the resulting movement, like yours, is 8 or 4 direction. I think it would be cool to add a feature to find the path that is most direct. eg you do the a* then strip away the cells that forces it to move in a robotic 8 directional way.

Picture


Lime line.

Lol that was indeed a good suggestion.. However it turned out harder than it seemed.

Basically it's the combination of other "freedom" things which make this very difficult to calculate.
-the object can be bigger than 1 cell (so a line-based calculation can't be made)
-cells can have "non infinite/zero" cost. - So I don't only have to check IF the object moves over a certain cell, but also how much.
For the last few days I've been trying to find a formula for that question (calculating for a cell how much of the cell was covered during the movement from a - .. However I couldn't solve it.. Also I would like to create a good way to morph the grid into "navmeshes" - which might speed up pathfinding. But on the same note might create much better "smoothed" paths.

[icuurd12b42]

One limited fn I find in GM is the resulting movement, like yours, is 8 or 4 direction. I think it would be cool to add a feature to find the path that is most direct. eg you do the a* then strip away the cells that forces it to move in a robotic 8 directional way.

Picture


Lime line.

Lol that was indeed a good suggestion.. However it turned out harder than it seemed.

Basically it's the combination of other "freedom" things which make this very difficult to calculate.
-the object can be bigger than 1 cell (so a line-based calculation can't be made)
-cells can have "non infinite/zero" cost. - So I don't only have to check IF the object moves over a certain cell, but also how much.
For the last few days I've been trying to find a formula for that question (calculating for a cell how much of the cell was covered during the movement from a - .. However I couldn't solve it.. Also I would like to create a good way to morph the grid into "navmeshes" - which might speed up pathfinding. But on the same note might create much better "smoothed" paths.

I can do it in GM after the path is calculated I guess

if(num point>1)
{
i = 0;
last x,y = get point x,y (i)
add last x,y to list
repeat( num points)
{
i+=1;
x,y = get point x,y (i)
if(collision_line(x,y to last x,y))
{
add get point x,y (i-1) to list
add x,y to list
last x,y = x,y
}
}

Edited by icuurd12b42, 01 February 2010 - 02:46 AM.

[Maverick22]

Hi Paul,

Can you explain what GPF_SetMovingObject does. Does that allow you to have non-stationary objects in your grid that the a*star algorithm is aware of, or is this your player object which will be going from point A to point B?

Thanks.

Looks like a great DLL.

[paul23]

Hi Paul,

Can you explain what GPF_SetMovingObject does. Does that allow you to have non-stationary objects in your grid that the a*star algorithm is aware of, or is this your player object which will be going from point A to point B?

Thanks.

Looks like a great DLL.

It's a "partially" done feature (didn't have time to test it thoroughly/ write an explanation).. However it's just a script so you can set the "movers" size, with that I mean the "object" which is used for calculations and such..

So you can move for example a 32*32 object correctly through a 16*16 grid (by creating a grid with 16*16 cell width/height - and then calling GPF_SetMovingObject(pid,2,2)...


Expect an update on the help-file (as well as quite a few fixes/minor speed improvements) in the days to come..

[paul23]

A small bump for a HUGE update:

updates

• Redone/renamed the entire function list
• added full compatibility for gm8
• build a tutorial
• build an example program
• added a few smaller functions
• fixed a lot of small bugs

Version 1 is out now!

[icuurd12b42]

Nice.. But the demo should clear everything, or have a clear button... it hard yo see the new paths from the old ones.

Good documentation in the pdf. it's good to see people go the extra mile.

[MatrixQuare]

The good thing is that it doesn't come with much lag. Creating a 200 * 200 cells room (thus 40 000 cells) where the end is "blocked" by 8 cells, and using 8-directions-based movement. Which is the worst case: it still can perform 85 dll-calls a second. Similar, the same world using mp_grid_path() calls we can perform 100 calls a step.

Am I correct in assuming that what this DLL trades off in terms of speed, it gains in extra features? However, 15% slower is quite the slowdown, compared to the built-in mp_grid_path() function (which is already slow as it is). I'm just wondering what would be the advantage of using your dll instead of GM's built-in functions if I do not need your extra features (such as cell cost calculation)?

Also, what did you mean by: "Custom (in gamemaker written) heuristic functions"?

The movement debugging would be awesome. Also re-acquiring its path every cell you move into would be sufficient for carefully planned movement engines. Would avoid any such obstacles entirely.

Another method uses the "on obstacle recalculate" pathfinding algorithm: once it meets an object it will recalculate its way around it (back to the original path).. This is "fast", however can produce very bad paths. (the original AoE used something like this: and it let to very strange results when you for example suddenly build a long wall before an enemy).

Actually, regarding the AoE path finding, what they improved on with AoE2 was to add a value-based movement system where a unit with higher value takes priority, and a unit with lower value will simply stop and wait for the higher value unit to move out of the and then continue on its normal path--Of course, if you build a wall in front of the AI, then there is only one thing the AI can do: Re-calculate a new path since the path is now permanently blocked. There's not much you can do to avoid this, other than to not implement a wall-type object that can permanently change the map while units are moving about.

[Schyler]

You should add some arc maths into the dll, so it generates arcs between each point (ofcourse, can be disabled). That way, the movement will look really smooth. It would be good for usage in 3D, as its mostly here that you can notice robot-like behavior, rather than in 2D games.

[Robert3DG+]

These is really nice. I'm impressed. Any chance a GEX will come of this?

[ze1]

I have a problem.
I managed to understand and use many of this dll's functions. But I have a problem with GPF_PathLength()

GPF_SetStart(G_pfgrid, _x/24, _y/24);
GPF_SetEnd(G_pfgrid, playerid.x/24, playerid.y/24);
GPF_CalculatePath(G_pfgrid,-1,false);
show_message(string(GPF_PathLength(G_pfgrid)));

GPF_PathLength(G_pfgrid) always returns 0, eventhough the destination is reachable. Why is that? None of the coordinates are zero nor they overlap.

Never mind. I've figured it out.

Great script, btw! =)

Edited by ze1, 21 April 2010 - 05:01 PM.

[newedge]

Great work! This is best pathfinding DLL for GM! Solve my huge problem, but I find a little bug in pathfinding algorithm. The 8-directional path cut north-east corner of blocked cell.

Edited by newedge, 18 March 2011 - 10:18 AM.

[Docopoper]

Would you be able to update it to 8.1? Please?

(and add a feature to export all of the costs to a grid)

[paul23]

Would you be able to update it to 8.1? Please?

(and add a feature to export all of the costs to a grid)

Well there are some problems with that, first of all this project is a good example of "feature creep", so a lot of trimming, and focussing will be done if I update it. (So it's back to the core) - maybe I release different builds for different purposes later then again..

But secondly, this project depends a LOT on gmapi.. And untill that is compatible -or there's some native gm system- I see no real point in making it for gm 8.1 yet.

Though if gmapi takes too long I'll find a way around it.

Edited by paul23, 16 May 2011 - 07:38 PM.