A*+ Pathfinding

by Xirre
A more efficient method of pathfinding.
ID:1951614
 
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.
There's nothing to test...
Fixed. Just a little hub entry issues.
Does it support doors, stairs or teleports?
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.
Looks like the download disappeared again... Weird. I just put it back. Hopefully it stays this time.
Ooooooh yeah, baby. Come to mama... We've been needing a much improved pathfinding algorithm for a while now.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
thank you so much