code34 248 Posted January 16, 2016 OO_PATHFINDING - shortest route between two positions Lastest version : 0.4 by Code34 Download from : Dropbox Download from : Armaholic Like to donate ? with Paypal GitHub : https://github.com/code34/oo_pathfinding.altis Pathfinding or pathing is the plotting, by a computer application, of the shortest route between two points. It is a more practical variant on solving mazes. This field of research is based heavily on Dijkstra's algorithm for finding a shortest path on a weighted graph (Source wikipedia) OO_PATH gives the opportunity to recover a set of positions that form a path between point A and point B. Several algorithm are avalaible to check the path.OO_PATH uses a virtual grid which replaces the map, and allows you to improve the precision on a well-defined area. The A* algorithm can use a weight function call back that permits to give weight depending of obstacles, objects, etc found on the sector. You must know that the condition of pathfinding is not optimized (it is not part of the object), that's why it takes time. Here the goal is to deliver an object ready for use for all types of use and not specifically for GPS. If you want to improve performance, precalculate prerequisites.Applications Pathfinding for units/vehicles AI improvements GPS Features GreedyBestFirst Algorithm Dijkstra Algorithm A* Algorithm, with dynamic call back weight function entrie Use a virtual Grid (OO_GRID) Licence Under Gpl, you can share, modify, distribute this script but don't remove the licence and the name of the original author Documentation Quote /* Author: code34 nicolas_boiteux@yahoo.fr Copyright © 2016 Nicolas BOITEUX CLASS OO_PATHFIND - PATHFINDING CLASS This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see <http://www.gnu.org/licenses/>. */ -------------------------------------------------------------------------------------------------------------- Function: _path = ["new", _grid] call OO_PATHFINDING; Create a new path object OO_PATHFINDING requiere several class: OO_GRID, OO_HASHMAP, OO_QUEUE Parameters: code - grid object -------------------------------------------------------------------------------------------------------------- Function: ["setWeightFunction", _yourweightfunction] call _path; For : getPath_A algorythm, set the weight function wich will be call to evaluate the weight of each sectors Your function must return a scalar. 0 if you want to ignore the sector, 1 if your want a high priority, >1 for lowest priority Parameters: code - yourweightfunction Return : nothing -------------------------------------------------------------------------------------------------------------- Function: ["getPath_GreedyBestFirst", [_startpos, _endpos]] call _path; Find a way of positions between start and end using the Greedybestfirst algorythm Return : array - positions -------------------------------------------------------------------------------------------------------------- Function: ["getPath_Dijkstra", [_startpos, _endpos]] call _path; Find a way of positions between start and end using the Dijkstra algorythm Return : array - positions -------------------------------------------------------------------------------------------------------------- Function: ["getPath_A", [_startpos, _endpos]] call _path; Find a way of positions between start and end using the A* algorythm Return : array - positions Example with A* Algorithm Quote call compilefinal preprocessFileLineNumbers "oo_grid.sqf"; call compilefinal preprocessFileLineNumbers "oo_queue.sqf"; call compilefinal preprocessFileLineNumbers "oo_hashmap.sqf"; call compilefinal preprocessFileLineNumbers "oo_pathfinding.sqf"; // Initialize a virtual grid over the map _grid = ["new", [0,0,31000,31000,100,100]] call OO_GRID; _path = ["new", _grid] call OO_PATHFINDING; // Weight function example to evaluate each sector _weightfunction = { private ["_position", "_size", "_average", "_cost"]; _position = _this select 0; _size = _this select 1; _average = 0; _cost = 0; _list = _position nearRoads _size; if(count _list > 0) then { _bbr = boundingBoxReal (_list select 0); _br0 = _bbr select 0; _br1 = _bbr select 1; _maxwidth = abs ((_br1 select 0) - (_br0 select 0)); _maxlength = abs ((_br1 select 1) - (_br0 select 1)); _average = floor (_maxwidth * _maxlength); if(_average > 200) then { _cost = 1; } else { _cost = 2; }; }; _cost; }; ["setWeightFunction", _weightfunction] call _path; _start = getmarkerpos "start"; _end = getmarkerpos "end"; _time1 = time; _waypoints = ["getPath_A", [_start, _end]] call _path; _time2 = time; hintc format ["Waypoints: %1 Time: %2", count _waypoints, _time2 - _time1]; Readme Quote /* Author: code34 nicolas_boiteux@yahoo.fr Copyright (C) 2016-2018 Nicolas BOITEUX CLASS OO_PATHFIND - PATHFINDING CLASS This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see <http://www.gnu.org/licenses/>. */ Retrieve the way before A and B point according the weightfunction Usage: put the "oo_grid.sqf" and the "oop.h" files in your mission directory put the "oo_hashmap.sqf" in your mission directory put the "oo_pathfinding.sqf" in your mission directory put the "oo_queue.sqf" in your mission directory put this code into your mission init.sqf call compile preprocessFileLineNumbers "oo_grid.sqf"; call compile preprocessFileLineNumbers "oo_queue.sqf"; call compile preprocessFileLineNumbers "oo_hashmap.sqf"; call compile preprocessFileLineNumbers "oo_pathfinding.sqf"; See example mission in directory: init.sqf Licence: You can share, modify, distribute this script but don't remove the licence and the name of the original author logs: 0.4 - add new oo_queue 0.3 - add new grid/hashmap/queue object 0.2 - improve performance with last upgrade 0.1 - OO PATHFINDING - first release 1 Share this post Link to post Share on other sites
whiztler 137 Posted January 16, 2016 Will give this a go. Perhaps add some information what your findings are compared to BIS pathfinding. Share this post Link to post Share on other sites
genesis92x 810 Posted January 17, 2016 This seems very interesting. Do you mind if I play around with it in my AI mod? Share this post Link to post Share on other sites
code34 248 Posted January 17, 2016 This seems very interesting. Do you mind if I play around with it in my AI mod? No probs :) It was done for this. Share this post Link to post Share on other sites
code34 248 Posted January 17, 2016 Will give this a go. Perhaps add some information what your findings are compared to BIS pathfinding. It s not a OO_PATH vs BIS built in functions :) BIS functions will be always faster (and i hope better), but you can not use them directly. It s an additional purpose that permit to uses thoses kind of features directly in sqf. I add somes informations in the main thread, don't know if it s more clear :) Share this post Link to post Share on other sites
Guest Posted January 17, 2016 Release frontpaged on the Armaholic homepage. OO PATHFINDING v0.1 ** Armaholic now supports authors with donation button/links. When you have any donation/support links please contact me! Share this post Link to post Share on other sites
code34 248 Posted January 17, 2016 Release frontpaged on the Armaholic homepage. OO PATHFINDING v0.1 ** Armaholic now supports authors with donation button/links. When you have any donation/support links please contact me! Hi Foxhound ! Thanks you for your support, i m going to update my post with Armaholic ! Share this post Link to post Share on other sites
cybercoco 16 Posted January 17, 2016 How nice is that ! Good work, I was looking for a Dijkstra Algorithm for Arma ! Share this post Link to post Share on other sites
Netarion 2 Posted January 19, 2016 Je pourrais avoir les droit d'admins sur le TS? Share this post Link to post Share on other sites
Netarion 2 Posted January 19, 2016 C'est quand qu'on joue à combat assault? Share this post Link to post Share on other sites
Netarion 2 Posted January 19, 2016 Je suis sur tu dis ça parce que Bernard t'a mis un couteau sous la gorge.. Share this post Link to post Share on other sites
whiztler 137 Posted January 19, 2016 English please! Share this post Link to post Share on other sites
code34 248 Posted October 24, 2017 hi :) just release a new version 0.2 - upgrade OO_PATHFINDING with performance improvement with native array - upgrade with upgrade of : priority queue, hashmap, grid objects 1 Share this post Link to post Share on other sites
code34 248 Posted January 19, 2018 hi just release a new version 0.4 - upgrade with last version of oo_queue :) Share this post Link to post Share on other sites
Guest Posted January 21, 2018 The Armaholic mirror has been updated with the new version: OO PATHFINDING v0.4 Share this post Link to post Share on other sites
code34 248 Posted January 21, 2018 Thanks Foxhound :) Share this post Link to post Share on other sites
