[Black Rose]

A* Pathfinding API
Pathfinding API which will (hopefully) find a walkable path between two points. Usable for NPCs without waypoints for every map.


This is highly experimental and should not be used for publically released plugins.
I do encourage that you try it out with the debug mode and help me finding new methods of doing certain checks.

Include (functions)

/** Array:AStar(Float:Start[3], Float:Goal[3], StepSize = 30, Ignore = IGNORE_MONSTERS, IgnoreID = 0, GroundDistance = 35, Heuristic = 50);
 *
 * Finds a path between Start and Goal.
 *
 *
 * Parameters:
 *
 *  Float:Start[3]
 *    Starting position.
 *
 *  Float:Goal[3]
 *    Hopefully the end position.
 *
 *  (Optional) StepSize = 30
 *    Defines how far between each step to take in a pattern of -X + X in all three dimensions. This means that diagonally, the step will be longer.
 *
 *  (Optional) Ignore = IGNORE_MONSTERS
 *    Flags for the traceline check.
 *
 *  (Optional) IgnoreID = 0
 *    id of the calling player if IGNORE_MONSTERS is not set. Again, this is for the traceline.
 *
 *  (Optional) GroundDistance = 35
 *    Set the maximum distance from the ground for the point to be accepted as valid. If set to 0 this check is disabled, meaning pathfinding for flying entities.
 *
 *  (Optional) Heuristic = 50
 *    Optimization parameter. Decides how much importance the distance from the target has.
 *    Higher values might result in a faster execution but may also result in a suboptimal path.
 *
 * Returns a handle to a dynamic array that will contain each step between start and goal.
 * On failure it will return Invalid_Array.
**/
native Array:AStar(Float:Start[3], Float:Goal[3], StepSize = 30, Ignore = IGNORE_MONSTERS, IgnoreID = 0, GroundDistance = 35, Heuristic = 50, ...);

/** AStarThreaded(Float:Start[3], Float:Goal[3], Handler[], StepSize = 30, Ignore = IGNORE_MONSTERS, IgnoreID = 0, GroundDistance = 35, Heuristic = 50);
 *
 * Finds a path between Start and Goal.
 *
 *
 * Parameters:
 *
 *  Float:Start[3]
 *    Starting position.
 *
 *  Float:Goal[3]
 *    Hopefully the end position.
 *
 *  Handler[]
 *    The function that will be called once the pathfinding is done.
 *    The format of the handler function should be as such:
 *      public PathDone(Index, Array:hPath, Float:Distance, NodesAdded, NodesValidated, NodesCleared)
 *
 *  (Optional) StepSize = 30
 *    Defines how far between each step to take in a pattern of -X + X in all three dimensions. This means that diagonally, the step will be longer.
 *
 *  (Optional) Ignore = IGNORE_MONSTERS
 *    Flags for the traceline check.
 *
 *  (Optional) IgnoreID = 0
 *    id of the calling player if IGNORE_MONSTERS is not set. Again, this is for the traceline.
 *
 *  (Optional) GroundDistance = 35
 *    Set the maximum distance from the ground for the point to be accepted as valid. If set to 0 this check is disabled, meaning pathfinding for flying entities.
 *
 *  (Optional) Heuristic = 50
 *    Optimization parameter. Decides how much importance the distance from the target has.
 *    Higher values might result in a faster execution but may also result in a suboptimal path.
 *
 * Returns a que index that can be used in the handler to identify which path is complete.
 * On failure it will return -1.
**/
native AStarThreaded(Float:Start[3], Float:Goal[3], Handler[], StepSize = 30, Ignore = IGNORE_MONSTERS, IgnoreID = 0, GroundDistance = 35, Heuristic = 50, ...);



// The following functions are only used with the AStar() function, not AStarThreaded().

/**
 * AStar_GetDistance()
 *
 * Returns the distance of the last non-threaded path.
**/
native Float:AStar_GetDistance();

/**
 * AStar_GetNodesAdded()
 *
 * Returns the ammount of nodes that were created from the last non-threaded path.
**/
native AStar_GetNodesAdded();

/**
 * AStar_GetNodesValidated()
 *
 * Returns the ammount of nodes that were validated from the last non-threaded path.
**/
native AStar_GetNodesValidated();

/**
 * AStar_GetNodesValidated()
 *
 * Returns the ammount of nodes that were cleared from the last non-threaded path.
**/
native AStar_GetNodesCleared();

Example code

This time it's based on 2 points that you create using the commands astar_pos1 and astar_pos2 instead of distance by aim. This allows you to test much bigger paths.
Run the pathfinding by using astar_run for "threaded" or astar_run2 for non-threaded.
The execution time is pretty similar, the non-threaded being slightly faster but will freeze the server while working.

#include <amxmodx>
#include <fakemeta>
#include <astar>
#include <xs>

/*
new hTimer = TimerStart();
// ...
TimerStop(hTimer);
server_print("Timer: %d days, %d hours, %d minutes, %d seconds and %d milliseconds.", TimerDays(hTimer), TimerHours(hTimer), TimerMinutes(hTimer), TimerSeconds(hTimer), TimerMilliseconds(hTimer));
*/
#define TimerStart()            tickcount()
#define TimerMid(%0)            ( tickcount() - %0 )
#define TimerStop(%0)         ( %0 = tickcount() - %0 )
#define TimerDays(%0)         ( %0 / 86400000 )
#define TimerHours(%0)      ( %0 % 86400000 / 3600000 )
#define TimerMinutes(%0)        ( %0 % 3600000 / 60000 )
#define TimerSeconds(%0)        ( %0 % 60000 / 1000 )
#define TimerMilliseconds(%0)   ( %0 % 1000 )

#define RGB(%0,%1,%2) ( ( ( %0 & 255 ) << 16 ) | ( ( %1 & 255 ) << 8 ) | ( %2 & 255 ) )

new Float:gPos[2][3];
new gLastStep[11][3];
new Array:gPath[11];
new gTimer[10];

new Colors[] = {
    RGB(0, 0, 255),
    RGB(0, 255, 0),
    RGB(0, 255, 255),
    RGB(255, 0, 0),
    RGB(255, 0, 255),
    RGB(255, 255, 0),
    RGB(255, 255, 255)
}

public plugin_init() {
    register_plugin("A* Sample code", "2.0", "[ --{-@ ]");

    register_clcmd("astar_run", "run");
    register_clcmd("astar_run2", "run2");
    register_clcmd("astar_pos1", "pos1");
    register_clcmd("astar_pos2", "pos2");
}

new g_sprite;

public plugin_precache()
    g_sprite = precache_model("sprites/laserbeam.spr")

stock beam(origin1[3], origin2[3], Float:seconds, rgb) {
    message_begin(MSG_BROADCAST ,SVC_TEMPENTITY)
    write_byte(TE_BEAMPOINTS)
    write_coord(origin1[0]) // start position
    write_coord(origin1[1])
    write_coord(origin1[2])
    write_coord(origin2[0]) // end position
    write_coord(origin2[1])
    write_coord(origin2[2])
    write_short(g_sprite)   // sprite index
    write_byte(0)   // starting frame
    write_byte(10)  // frame rate in 0.1's
    write_byte(floatround(seconds*10))  // life in 0.1's
    write_byte(10)  // line width in 0.1's
    write_byte(1)   // noise amplitude in 0.01's
    write_byte(( rgb >> 16 ) & 255) // Red
    write_byte(( rgb >> 8 ) & 255)  // Green
    write_byte(rgb & 255)   // Blue
    write_byte(127) // brightness
    write_byte(10)  // scroll speed in 0.1's
    message_end()
}

public pos1(id)
    SavePos(id, 0);

public pos2(id)
    SavePos(id, 1);

SavePos(id, pos) {

    new Float:Origin[3];
    new Float:End[3];
    new hTrace;

    pev(id, pev_origin, Origin);
    
    xs_vec_copy(Origin, End);
    End[2] -= 1000
    
    engfunc(EngFunc_TraceLine, Origin, End, IGNORE_MONSTERS, id, hTrace);
    get_tr2(hTrace, TR_vecEndPos, Origin);
    free_tr2(hTrace);
    
    Origin[2] += 10;

    xs_vec_copy(Origin, gPos[pos]);
}

public run(id) {
    client_print(0, print_chat, "Start: %.0f, %.0f, %.0f. End: %.0f, %.0f, %.0f. Distance: %.0f units.", gPos[0][0], gPos[0][1], gPos[0][2], gPos[1][0], gPos[1][1], gPos[1][2], get_distance_f(gPos[0], gPos[1]));
    
    new Index = AStarThreaded(gPos[0], gPos[1], "PathDone", 30, IGNORE_MONSTERS, id, 35, 50);

    if ( Index == -1 ) {
        client_print(id, print_chat, "All pathfinding slots are busy.")
        return;
    }
    gTimer[Index] = TimerStart();

}

public run2(id) {
    client_print(0, print_chat, "Start: %.0f, %.0f, %.0f. End: %.0f, %.0f, %.0f. Distance: %.0f units.", gPos[0][0], gPos[0][1], gPos[0][2], gPos[1][0], gPos[1][1], gPos[1][2], get_distance_f(gPos[0], gPos[1]));
    
    new hTimer = TimerStart();
    new Array:hPath = AStar(gPos[0], gPos[1], 30, IGNORE_MONSTERS, id, 35, 50);
    TimerStop(hTimer);

    new Timer[32];
    TimerFormat(hTimer, Timer, charsmax(Timer), 2);

    client_print(0, print_chat, "Execution time: %s (%d nodes, %d validated, %d successful)", Timer, AStar_GetNodesAdded(), AStar_GetNodesValidated(), AStar_GetNodesCleared());
    
    if ( hPath == Invalid_Array ) {
        client_print(0, print_chat, "Pathfinding failed.");
        return;
    }

    client_print(0, print_chat, "Distance of path: %.0f units, %d steps.", AStar_GetDistance(), ArraySize(hPath) - 1);

    if ( gPath[10] != Invalid_Array )
        ArrayDestroy(gPath[10]);

    if ( task_exists(10) )
        remove_task(10);
    
    arrayset(gLastStep[10], 0, sizeof gLastStep[]);
    gPath[10] = hPath;
    set_task(0.2, "ShowPath", 10, . flags = "a", . repeat = ArraySize(hPath));

}

public PathDone(Index, Array:hPath, Float:Distance, NodesAdded, NodesValidated, NodesCleared) {

    TimerStop(gTimer[Index]);

    new Timer[32];
    TimerFormat(gTimer[Index], Timer, charsmax(Timer), 2);

    client_print(0, print_chat, "Execution time: %s (%d nodes, %d validated, %d successful)", Timer, NodesAdded, NodesValidated, NodesCleared);
    
    if ( hPath == Invalid_Array ) {
        client_print(0, print_chat, "Pathfinding failed.");
        return;
    }

    client_print(0, print_chat, "Distance of path: %.0f units, %d steps.", Distance, ArraySize(hPath) - 1);

    if ( gPath[Index] != Invalid_Array )
        ArrayDestroy(gPath[Index]);

    if ( task_exists(Index) )
        remove_task(Index);
    
    arrayset(gLastStep[Index], 0, sizeof gLastStep[]);
    gPath[Index] = hPath;
    set_task(0.2, "ShowPath", Index, . flags = "a", . repeat = ArraySize(hPath));
}

public ShowPath(Index) {

    static curStep[3];

    ArrayGetArray(gPath[Index], 0, curStep);
    ArrayDeleteItem(gPath[Index], 0);

    if ( gLastStep[Index][0] && gLastStep[Index][1] && gLastStep[Index][2] )
        beam(gLastStep[Index], curStep, 4.0, Colors[Index % sizeof Colors]);

    gLastStep[Index][0] = curStep[0];
    gLastStep[Index][1] = curStep[1];
    gLastStep[Index][2] = curStep[2];
}

/* TimerFormat(hTimer, output[], maxlen, mode = 1, bool:full = 0)
* Formats the result of a timer handle into a string.
*
* Parameters:
*
* hTimer
*    Timer Handle
*
* output[]
*    The output string
*
* maxlen
*    Maximum size of the output string
*
* mode
*    1: 00:00:00:00.000
*    2: 0d 0h 0m 0s 0ms
*
* bool:full
*    If full is set to true it will print all fields, even those which contains no value.
*    If full is set to false and mode is set to 1, it will print the first field that contains a value and everything after that point. For example: 03:00:00.295
*    If full is set to false and mode is set to 2, it will print only the fields that contains a value. For example: 3h 295ms
*/
stock TimerFormat(hTimer, output[], maxlen, mode = 1, bool:full = false) {
    new len, bool:started;
    
    if ( full || TimerDays(hTimer) ) {
        if ( mode == 1 )
            len = formatex(output, maxlen, "%02d:", TimerDays(hTimer));
        else
            len = formatex(output, maxlen, "%dd ", TimerDays(hTimer));
        started = true;
    }
    if ( full || ( started && mode == 1 ) || TimerHours(hTimer) ) {
        if ( mode == 1 )
            len += formatex(output[len], maxlen - len, "%02d:", TimerHours(hTimer));
        else
            len += formatex(output[len], maxlen - len, "%dh ", TimerHours(hTimer));
        started = true;
    }
    if ( full || ( started && mode == 1 ) || TimerMinutes(hTimer) ) {
        if ( mode == 1 )
            len += formatex(output[len], maxlen - len, "%02d:", TimerMinutes(hTimer));
        else
            len += formatex(output[len], maxlen - len, "%dm ", TimerMinutes(hTimer));
        started = true;
    }
    if ( full || ( started && mode == 1 ) || TimerSeconds(hTimer) ) {
        if ( mode == 1 )
            len += formatex(output[len], maxlen - len, "%02d.", TimerSeconds(hTimer));
        else
            len += formatex(output[len], maxlen - len, "%ds ", TimerSeconds(hTimer));
        started = true;
    }
    if ( full || ( started && mode == 1 ) || TimerMilliseconds(hTimer) ) {
        if ( mode == 1 )
            len += formatex(output[len], maxlen - len, "%03d", TimerMilliseconds(hTimer));
        else
            len += formatex(output[len], maxlen - len, "%dms", TimerMilliseconds(hTimer));
    }
}

Changelog

Version 1.0
* Initial release.

Version 1.1
* Added possibility of running the pathfinding as "threaded". (Thinking entity, not actually threaded.)

Version 1.2
* Added a debug mode so you could easily see where the search fails. To enable it, edit the line at the top saying:
//#define DEBUG
to:
#define DEBUG

Here's a short explanation:
Yellow beam: Not enough distance to the ground.
Teal beam: Could not connect to parent node.
Purple beam: The same as teal but with 5 added to the Z axis.
White beam: Successfully connected to parent node.

Additional notes:
The best would probably be to make it a module. Feel free to do so (I can't write code in C). You have my permission to use any of this code in that project.
I'm always open to suggestions, feedback and criticism. Please share your thoughts.

[GuskiS]

I don't quite understand what it does. Doest it look for suitable movement path? If so, this could be amazing for NPC's making them walk around the map just by giving coords :O

[Black Rose]

Yes, that is what it does.

[UchihaMadara]

It's cool, where did you take it?
And this one should be posted in Code Snippets/Tutorials

[Black Rose]

I didn't take it. I made it.
Mostly from psuedocode on the Wikipedia page on A*. The rest is my work.

[Backstabnoob]

Originally Posted by UchihaMadara It's cool, where did you take it? And this one should be posted in Code Snippets/Tutorials

No it shouldn't. It's a plugin like any other, this one is an API so it might not be suited for you, but it's suited for others.

[<VeCo>]

Wow, awesome, will definitely try this out!

[Phant]

Very interesting.
It would be nice to see how this algorithm calculate long path, for example, from T spawn on de_aztec to CT spawn.
Or on some big Half-Life map, for example, "bounce".

[hleV]

This seems pretty neat, good job.

[4554]

very cool!