fast node path algorithm

[PhantOS]

im trying to make some ai node path stuff with port's node tool. whats a good algorithm i should use to efficiently find the best path from one node to a really far away node through multiple connections

i'd assume A* or dikstra's but i want to aim for speed as best as possible

[Ad Bot]

[mctwist]

It all depends on what you have at the start. Dijkstra's could be an alternative if you're handling weights, distances and graphs.

If you can precalculate the paths, that is a static map, then you could use JPS+ and Goal Bounding.
Video
Git

It could be doable for a map, unless you change it. Then it needs to precalculate the paths once again.

[PhantOS]

this is more or less what i'm trying to do. the red box is the start point and the blue is the end. normally i'd use dijisktra's for it but the problem is that on the first major branch about two nodes down it would take the left path first since it's the shortest known path, and would waste time without using heuristics.

the best available path would probably be generated for each bot every 10 seconds as it changes targets, but if its more efficient i could have it save best available paths so it will default to a saved path instead of generating it every time

[Conan]

a*? why not use heuristics? just have the only heuristic be distance of target node from destination.

saving paths can get hairy fast since theres no good list system in torque, and sometimes things could obstruct paths that originally existed.

a* is the fastest out there thats not adapted to specific situations/using precalculated paths. in fact it probably technically covers anything not dijkstra's since the heuristic used is unspecified

edit: mctwists jps+ goal bounding reference is a nice source but assumes a grid with equal weights nodes so its probably not optimal/not possible to use.

[PhantOS]

yeah im using a* and essentially having the bot's starting node be the closest node to it, while the final destination is the closest node to the target

[mctwist]

If the speed you're looking for is about "not boggling down the server", then I suggest that you split it up in parts. That is, start a search and do a couple of nodes, then schedule an another round and continue. The bots may move within this time. When it has reached the goal, then it's done.

However, if a brick is modified, it will then check if that is a node(I'm not sure how you're placing nodes, so do your thing here to move/replace it), and then do the A* again. I assume that in a heavy match with many AI's, this should reduce the lag on the server. You may also make so the bots wont move until a valid path has been found.

There is also this thing that you may split the graph up into smaller sections and connect them with their own graph. This may of course be a bit complicated, but it could make the A* to guess in beforehand what path is faster, and then do smaller A* searches each time they search.
That is, first do a fast A* on the overview graph. Then do A* on the section the bot is within right now.

Mix together both of the suggestions and you will have something solid enough.

I believe this technique was used in Rail Tycoon.

No-edit: Man, now you got me hyped to make this myself...

Edit: I made an image to maybe make it a bit easier. The orange circles is the sections and the yellow lines are connections between them. This might look like it's complicated to make, but actually, just bundle together a couple of neighbors that are closest to each other and mark their section connections.



This could also give room to optimizations between sections to have a predefined path while just going through sections.

Sectioning like this can be done within itself as well. Sectionception!

[phflack]

if you're saving the graph as a variable on the bot, it may make more sense to use D* if the paths can be blocked

[PhantOS]

honestly i'm not that good at coding so tackling something of this weight is kind of a challenge. mctwist if you want you can always work on this thing, i managed to make a very simple path detection but it doesn't prioritize shortest path first correctly, simply because it visits a node crossway and moves that into the visited pile, but when a shorter path meets that same crossway it cuts off because that node has been visited

im really bad at this stuff

[Conan]

mctwist your sectioning of the pathing can lead to bot self-looping as it finds optimal nodes within its own network but does not lead to the optimal path. it can also lead to looping if the sub-network it connects to has no way other than backtracking to go to the target node.

[mctwist]

mctwist your sectioning of the pathing can lead to bot self-looping as it finds optimal nodes within its own network but does not lead to the optimal path. it can also lead to looping if the sub-network it connects to has no way other than backtracking to go to the target node.

That is indeed true and I didn't think about that. Of course it could be solved partly with weights. Like, take all nodes and take the mean value of them and then the weight of the neighboring section weight. I'm not sure if a looping would occur though. Would you care to explain more?