Easy AStar

by Geldonyetich
A simple-to-use A* Pathing implementation
ID:115001
 
Want some effective but easy-to-use pathing in your game? Give this a spin.

Features & Functionality:

  • This library utilizes turf.Enter() to determine if a turf is passable. If your game requires special rules, simply override turf.Enter() as you normally would. (e.g. "don't count a mob obstructing the path here if I can't see them.")
  • This library requires you create a new proc: turf.GetMovementCost(var/atom/movable). This is used to weigh the most efficient movement for a given atom. However, if your game does not use variable movement costs, simply have GetMovementCost() return a value greater than 0 (recommended: 1). See the included demo code for an example.
  • To utilize A* pathing, request a list of turfs making up the path via the GetAStarPath() proc:
    var/list/turf/whateverPathVariableName = GetAStarPath(movableAtomDoingTheMoving,destinationToGoTo)

    // Alternate method using atom/movable.GetAStarPathTo on a /mob/player variable initialized as playerMob

    var/list/turf/whateverPathVariableName = playerMob.GetAStarPathTo(destinationToGoTo)
    These simply return a list of turfs representing steps from movable/atom to arrive at a (non-area) atom destination on the same map. This allows allowing for easy implementation for any project.

    For an even easier implementation, you can simply use this proc:
    // Method involving simply using step_towards_astar_Path() with the same example of a /mob/player initialized as playerMob.

    step_towards_astar_path(playerMob,destinationToGoTo)

    That functions identically to the BYOND step_towards() function except it uses the AStar pathing. It will automatically store pathing information on the movable atoms as required.
  • GetAStarPath and GetAStarPathTo can take an additional numeric argument after the destination representing a minimum distance from the destination space. (Default: 0) This is useful if you want to stop pathing at a certain distance away from the goal. Setting this too high will likely result in significant slowdown.
  • GM Verbs for pathing debugging are included. By default, this code is removed in order to improve efficiency. To enable it, add the following line before the first //BEGIN in the main .dme file:
    #DEFINE PATHING_DEBUG
    
    Then, just add the debugging verbs to any players who should have appropriate access. See the debugging code files for details as to what those verbs are.
  • Tweakable global variables allow for further refinement of how pathing occurs and whether or not diagonal movement is allowed (including a definable multiple of increased movement cost for diagonal movement). These are set to typical default values and need not be changed unless your game calls for it.

Warning: Cannot path between multiple maps. This is because there are many possible implementations you can have that would use multiple maps. To work around this, just use Easy AStar to path on the same maps, and then use alternate pathing methods to facilitate movement between maps.

Release Notes:

7/7/11 - Several versions released today.

v1.6

Made the step_towards_astar_path pathing data list into a variable of type tmp so it will not save on your mobs.

Fixed bug in step_towards_astar_path() related to paths of length one being unable to reach destinations 2 distance away if they were not able to be reached via a standard step_towards.

Made demo more robust with a larger interface and runtime compile toggled methods of pathing.

v1.5

Added support for two more functions:

atom/movable.GetAStarPathTo() works identically to GetAStarPath but does not require the movable atom is passed as the first arg.

Global function step_towards_astar_path() works identically to step_towards except it utilizes astar pathing. The list of turfs is managed automatically.

v1.4

For improved efficiency, all pathing debug code is now removed at compile time unless you #DEFINE PATHING_DEBUG in your .dme file before the first //BEGIN.

v1.3

Changed implementation of maximum distance from destination mechanic to utilize a whole list of turfs to check against for pathing success instead of simply attempting to path to the nearest enterable turf from the start.

4/6/10 - v1.2 released. Changed GM debugging command to include less machine-intensive version. Made granting/removing GM verbs easier by moving them to a global proc list. Set pathing process to background to prevent from timing out on extremely long pathing assignments.

3/13/10 - v1.1 released. Commented out some unnecessary variable checks and optimized list handling for even more efficiency.

3/13/10 - v1.0 released. Improved in terms of efficiency, correct pathing accuracy, and features.

To give some credit where it was due: procs from AbyssDragon's Basic Math were utilized to boost efficiency.
This is a great library but, there are a few things I would like to see changed.


1) I don't like how the debug stuff is so tightly interwoven with the rest of the lib. It should instead be a optional, modular component.

2) The ability to disregard dense objects occupying a tile while obeying tile density itself.
Thanks very much for the feedback on this, sorry for taking so long to get back to you about that.

I agree that there needs to be a boost to the general efficiency of the code. Currently, the debug calls are put behind extremely quick "if (debug_flag)" statements, but even those can stack up when you're doing the necessary thousands of iterations required to perform effective A* pathing. Ideally, I'd like to put the debug code behind stuff that is removed at compile time, I should really look into his the #IF statements work in BYOND.

As for the ability to disregard dense objects, my initial plan on this was that the user would redefine turf.Enter() as required to provide special treatment (such as cases where dense objects would return true). However, I could potentially change this, for example I could provide a special version of the A* pathing that uses turf.density instead of turf.Enter, or an argument provided that would change the method of pathing.

Easy AStar works in terms of providing easy to use pathing that rides the existing turf.Enter() rules, but there's certainly quite a bit I could do in terms of improving the overall implementation. This is a library a few years old now, and I'm a little better at coding now. For example, I should really consider leaving old pathing data laying around, that would *massively* boost efficiency of execution, although it would bloat memory use a bit.
Geldonyetich wrote:
I should really consider leaving old pathing data laying around, that would *massively* boost efficiency of execution, although it would bloat memory use a bit.

The extra memory used is definitely worth the processing power you save. I tried piecing together a system were if the target mobile atom moved it would update the very end of the path rather than recalculating the whole thing. It sped things up a little, but it didn't really make much of a difference in the big picture since the process itself was already quite taxing on my CPU.

In an MMO for example, it would make sense to have creatures share pathing data rather than constantly calculating new ones.
Removing the debug code at compile time by rigging it up to a #DEFINE flag turned out to be a lot easier than I thought it would be. v1.3 now removes all that code at compile time unless you have defined it.

I'll have to put some thought into how to go about leaving around old pathing data. There's a few big problems with that:

1) Pathing data that suits one mob won't suit another. I could differentiate the data on mob.type, but it could be that this too could change - for example, a mob of the same type may have a jet pack.

2) Mutable terrain could make previously derived paths obsolete. E.g. a wall is put up in the middle of a previously working path, possibly a long wall that requires a radical recalculation. Conversely, a wall could go down, making old pathing information that goes around it much longer than it need be. I'm not sure what you could do about this short of removing *all* pathing information on that map whenever change occurs.

3) Movement cost could differ between different units. For example, some could be better at crossing rough terrain than others. Thus, if those units reuse each other's pathing information, one of those units may end up moving in a less speedy manner than it can.

Because the differences will be on the side of the game that implements the library, I would advise code that saves old pathing data go there. As EasyAStar just returns a list of turfs, you could use it in any manner you see fit, such as saving those paths to a datum and re-testing those paths before committing to them.
I just put in some other major enhancements today. A couple more functions to ease use of the library and a better implementation of how it checks for maximum distance to the target when one is specified.