A* Pathfinding API
Pathfinding API based on the A* method.
Functions:
A new example so you can test in game
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.
And here's an example image of a path between two points that has objects, corners and height differences.
It was hard taking a good picture since the beams disappear really fast. You get the point.
Changelog:
Additional notes:
Use this file however you want. Credit not required.
The best would probably be to make it a module. Feel free to do so (I'm not good enough). You have my permission to use any of this code in that project.
I'm always open to suggestions, feedback and criticism. I aim to add as much support as possible. Please share your thoughts.
Pathfinding API based on the A* method.
Functions:
Code:
/** 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();
A new example so you can test in game
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.
Code:
#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)); } }
And here's an example image of a path between two points that has objects, corners and height differences.
Spoiler
It was hard taking a good picture since the beams disappear really fast. You get the point.
Changelog:
Code:
Version 1.0
* Initial release.
Version 1.1
* Added possibility of running the pathfinding as "threaded". (Thinking entity, not actually threaded.)
Use this file however you want. Credit not required.
The best would probably be to make it a module. Feel free to do so (I'm not good enough). You have my permission to use any of this code in that project.
I'm always open to suggestions, feedback and criticism. I aim to add as much support as possible. Please share your thoughts.
0 nhận xét:
Post a Comment