A*+ Pathfinding

by Xirre
A more efficient method of pathfinding.

About A*+ Pathfinding

ID:1951614
 
Sep 29 2015, 10:00 pm
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.
Sep 30 2015, 12:22 am
There's nothing to test...
Sep 30 2015, 12:36 am
Fixed. Just a little hub entry issues.
Sep 30 2015, 12:47 am
Does it support doors, stairs or teleports?
Sep 30 2015, 1:04 am
In response to Zecronious
Zecronious wrote:
Does it support doors, stairs or teleports?

It's basically walk_to but dumbed down in such a way that it uses less CPU.
Sep 30 2015, 3:06 am
Looks like the download disappeared again... Weird. I just put it back. Hopefully it stays this time.
Sep 30 2015, 7:20 am
Ooooooh yeah, baby. Come to mama... We've been needing a much improved pathfinding algorithm for a while now.
Sep 30 2015, 7:36 am
In response to Xirre
Is it possible to add any of those features? I've always run into issues where sure I have pathfinding but my map is made of doors and other connecting objects which my AI always fails to make use of, usually resulting in very silly behaviour.
Sep 30 2015, 8:37 am (Edited on Sep 30 2015, 9:35 am)
In response to Zecronious
There are existing pathfinding libraries that let you do that. If they ask for a proc that gives adjacent tiles, then you give it one that returns nearby tiles + if the center tile is a staircase or ladder, return the destination tile (because it's a tile you can get to from the center tile, aka adjacent).

A* pathfinding is like a guided flood-fill. You can get a path from one point to another if both points are in the same flood-filled region. You just have to make sure that other floors are part of the same region by telling it that stairs and ladders go to other floors.

After a quick look at Xirre's pathfinding, it doesn't seem like a straightforward change. His pathfinding system gets 4 neighbors in the cardinal directions by itself. It doesn't seem to accept a dynamic list of neighbors.
Sep 30 2015, 8:37 am
In response to Zecronious
Absolutely there is a way to add it.

Either you can modify it yourself or convince Xirre here to implement it into this, which only makes sense because it is a pathfinding demo and if it can't find a path through a door it isn't of much use for the majority!

There would have to be some kind of trigger for doors and other objects that have temporary density, otherwise the pathseeker will simply ignore that dense object.
Sep 30 2015, 11:24 am
In response to Zecronious
Zecronious wrote:
Is it possible to add any of those features? I've always run into issues where sure I have pathfinding but my map is made of doors and other connecting objects which my AI always fails to make use of, usually resulting in very silly behaviour.

Couldn't you just... y'know... Set the density on the door to 0 and then change its Enter() procedure so when they bump in to the door they walk right through it? Same thing with stairs. I'm not saying that this would be your final output. But, the general though of using Enter() or Bump() would work with any pathfinding system.

If that doesn't solve your problems, then I'll try and make some changes on my end.
Sep 30 2015, 11:27 am
In response to Xirre
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.
Sep 30 2015, 12:18 pm
By the way, "doors, stairs, ladders, teleports" refer to objects on the map that you might step onto that teleport you to a different position on the map, possibly on a different z-level. A* is good for this because all it needs to know is "where can I go from here?" for every position it considers.

If you're on a teleporter, then your neighboring points aren't just the points to your north, south, east, and west; you also have a point that is the teleporter's destination.
Sep 30 2015, 1:39 pm (Edited on Oct 16 2015, 1:26 pm)
I think an easy method for custom collision detection would be to add a variable under atom that makes it "legally" dense. This could be useful for tiles that aren't necessarily dense but still want to be avoided by the pathfinding, such as pits or other floor hazards. That would require like 3 lines of code, fortunately. Lol.
Sep 30 2015, 3:33 pm
In response to AERProductions
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.
Oct 16 2015, 1: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.
Oct 16 2015, 11:24 pm
In response to FKI
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.
Oct 20 2015, 4: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.
Mar 20 2020, 4:27 am
thank you so much