Jump to content
code34

OO_PATHFINDING - shortest route between two positions

Recommended Posts

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

 

  • Like 1

Share this post


Link to post
Share on other sites

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

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

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

Release frontpaged on the Armaholic homepage.

news_download_a3_3.png

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

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

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

 

  • Like 1

Share this post


Link to post
Share on other sites

hi :don14:

 

just release a new version 0.4

- upgrade with last version of oo_queue :)

Share this post


Link to post
Share on other sites

Please sign in to comment

You will be able to leave a comment after signing in



Sign In Now

×