A*+ Pathfinding

by Xirre
A more efficient method of pathfinding. [More]
To download this library for your Linux/Mac installation, enter this on your command line:

DreamDownload byond://Xirre.Pathfinding##version=1

Emulator users, in the BYOND pager go to File | Open Location and enter this URL:

byond://Xirre.Pathfinding##version=1

194 downloads
Version 1.0
Date added: Sep 29 2015
Last updated: Oct 1 2015
2 fans
A more efficient method of pathfinding. This should be better than step/walk_to since they seem to be CPU intensive.

- Currently tested in a 5,3,1 map producing ~0.000 CPU with every procedure on a 3.4GHz processor.
                               Profile results (total time)
Proc Name                                  Self CPU    Total CPU    Real Time        Calls
--------------------------------------    ---------    ---------    ---------    ---------
/mob/verb/WalkToEndPoint                      0.000        0.001        3.937            1
/mob/proc/WalkTo                              0.000        0.001        3.937            1
/Pathfinder/New                               0.000        0.001        0.000            1
/Point/New                                    0.000        0.000        0.000           50
/Vector2/New                                  0.000        0.000        0.000            6
/mob/proc/SimplifyVectors                     0.000        0.000        0.000            1
/Pathfinder/proc/Heuristic                    0.000        0.000        0.000           28
/Pathfinder/proc/ResetSearchNodes             0.000        0.000        0.000            1
/Pathfinder/proc/FindBestNode                 0.000        0.000        0.000           12
/Pathfinder/proc/FindFinalPath                0.000        0.000        0.000            1
/Pathfinder/proc/FindPath                     0.000        0.000        0.000            1
/Pathfinder/proc/InitializeSearchNodes        0.001        0.001        0.000            1
                                              0.000        0.000        0.000            1


If you would like to contribute your results, post your processor speed, map-size, and results from the profiler.

Comments

Paulmontecillocabral: (Mar 20 2020, 3:27 am)
thank you so much
Xirre: (Oct 20 2015, 3:52 am)
I just came across this post again and remembered something. This pathing does not take bounds in to account. But, you can definitely have it use pixel movement. That is easy.
Xirre: (Oct 16 2015, 10:24 pm)
FKI wrote:
I was hoping this worked with pixel movement, but I guess this is more encouragement for me to design my own solution.

Nonetheless, interesting library.

Feel free to contribute to it. I'm hoping somehow we get to a point where we have a good system to use for all purposes. I'd be more than happy to explain the current system if you need me to. I just don't have the time to work on it myself since I committed myself to a partnership on a 3D project.
FKI: (Oct 16 2015, 12:24 pm)
I was hoping this worked with pixel movement, but I guess this is more encouragement for me to design my own solution.

Nonetheless, interesting library.
Xirre: (Sep 30 2015, 2:33 pm)
AERProductions wrote:
That would allow players to move through the door as well, though.

The best bet would be to do a simple density check and put in another if/for check that declares whether it is a door/staircase/etc or not and provide the proper procedure for the AI to manipulate such objects.

So if it finds density = 1, it would search if it is a staircase or a door and execute the proc that opens or utilizes it.

I could make it so that it checks if each tile has an "interactable" variable set to true. If it does, then it calls obj:Interact() on it. Meaning, any object that has the interactable variable set to true MUST have an Interact() proc on it.

As for adding nodes to them, I'd need a bit more thinking on that.

In addition, I can also make it so teleporters can link to each other so they are neighbors.