A* PATHFINDING EXTENSION
Hello everyone! I made an A* pathfinding .dll in C++ and put it into an extension.
You can use this freely without credit, even in commercial applications. However, I would greatly appreciate credit and you posting here if you found it useful.
Someone requested a GML only version of this. It will probably be a decent amount slower. However, it lets you use the features of this pathfinding on platforms other than windows.
Check the downloads for the .zip containing the .gmk. You'd need to add the AStarPathfinding folders under Scripts and Objects into your own game, but other than that it should use the same syntax as the C++ extension.
If it causes too much lag when pathing it could be modified to compute the path over multiple frames rather than all at once -- if you can't figure out how to do it and you want to then let me know.
Neither of the influence map functions are currently implemented in the GML only version.
Also, I found a bug (only in the C++ version now) where if you try to create a path with unitwidth > 1 it can crash when it tries to path near the bottom or right edges of the map. As long as the edges of the map are impassible and you don't explicity try to path the top left of the object to a place too close to the edge where it wouldn't fit (there is no reason to do this anyway) then it should be fine. If this is a big deal to anyone I can upload a fixed version.
astar GML ONLY VERSION.zip
FEATURES: (vs. mp_grid)
Fast, especially for paths with few obstacles, even on huge maps. Uses arrays to mark open/closed tiles to avoid searching; uses binary heap to keep track of lowest cost.
Terrain can be given different costs (eg. you move slower in a forest than on a road).
Objects can be 2x2, 3x3, etc. tiles in size. Passages that allow a 1x1 object to pass through may not let larger objects pass through.
as_map_create(width,height,value); // Returns a new grid to do pathfinding on with width * height squares. All squares are initialized with value (cost to move into it, negative for unwalkable). // It's important to make open ground a value of 1 in most situations. Having values between 0 and 1 will produce paths that aren't necessarily the best paths. // Values larger than 1 will cause the pathfinding to be slower. as_map_destroy(map); // Frees memory used by map. as_map_getcell(map,x,y); // Returns the cost of tile with given x and y (negative number for impassible). as_map_setcell(map,x,y,value); // Sets the cost of tile with given x and y to value (negative number for impassible). as_map_setrectangle(map,x,y,width,height,value); // Sets the cost of tiles in rectangle with given x, y, width, and height to given value (negative number for impassible). as_path_create(map,xstart,ystart,xgoal,ygoal,unitwidth,diag,maxdepth); // Returns a new path from xstart and ystart to xgoal and ygoal (the pathfinding is done when you call this function). // The path will have length of 0 if no path can be found. // unitwidth says how many tiles an object takes up (all objects are square, so an object with width 3 takes up 9 tiles in a square). // The x and y values refer to the top left tile of this object. // maxdepth is number of items in open list that will be examined before quitting and saying path can't be found. // Set negative to make this infinite (will always find a path if availble, but may take too long on huge maps). // if diag is 0 then the path will have no diagonal moves. If diag is 1 then diagonals will be allowed even if they cut corners. // If diag is 2 then diagonals will be allowed only if they don't cut corners. // This means that it is valid to move from A to B in the given picture (with X as wall) only if diag is 1: // AX // XB // mp_grid doesn't allow the cutting of corners. as_path_destroy(path); // Frees memory used by path. as_path_nodex(path,index); // Returns x position of node that has given index in given path (0 is first, as_path_length-1 is last). as_path_nodey(path,index); // Returns y position of node that has given index in given path (0 is first, as_path_length-1 is last). as_path_length(path); // Returns number of nodes in path. as_path_removefirst(path); // Removes first node from a path (second item in path is now first and at index 0). Make sure path has a node. as_inf_create(map,x,y,width,height,group,value); // Creates an influence map. Adds value to all walkable tiles in map in rectangle given by x, y, width, and height. // This provides an easy way to temporarily modify the cost of tiles on the map (eg. to avoid other moving objects or an ambush). // If value is negative it won't be subtracted... all tiles will be marked temporarily as unwalkable. // Is given an integer to denote its group to allow easy removal of all influence maps in the same group (don't use -1, see below). as_inf_destroygroup(map,group); // Destroys and frees memory used by all influence maps that have the given group (-1 to destroy all groups). // Reverses operation done by influence map (subtracts values, makes tiles that were walkable and then turned unwalkable walkable again). // BE CAREFUL: If you add a value with an infmap, then make the tile unwalkable with another infmap, and then delete the first infmap the operation won't be reverted.
All times measured using the high resolution timer extension, and are obviously based on the power of my computer. What is more important is the comparison to mp_grid, game maker's built in A* pathfinding. A larger and more thorough test likely should be done.
Computing a very simple path, such as a few tiles in a straight line with no obstacles takes ~0.03 milliseconds compared to ~1.2 milliseconds by mp_grid.
Computing a long path (1000 squares in a 1000 by 1000 map) with no obstacles takes ~1.4 milliseconds compared to ~250 milliseconds.
Computing a moderate path with obstacles ~0.3 milliseconds compared to ~1.2 milliseconds.
Computing a winding path that requires a lot of backtracking in general direction of start is slower: ~6 milliseconds compared to ~3 milliseconds.
If you need any help, don't be afraid to ask!
Edited by Jake Armstrong, 31 August 2015 - 09:22 PM.