News for hackers. Stuff that matters.
Re:Pathfinding Demystified by Kiro on Friday May 16, 2014 @07:15AM (#7754881)
Maybe I misunderstand how this works but I want to find a pathfinding algorithm that is super fast and only calculates the first few steps toward a target. The target is moving and the calculation needs to happen several times every second so calculating the whole path is not feasible. It doesn't really matter if it gets stuck or doesn't find the optimal path, just that it looks like it's trying to move closer to the target.

Any ideas?

Re:Pathfinding Demystified by Negitivefrags on Friday May 16, 2014 @08:49AM (#7755153)
More context would be useful to know exactly what kind of algorithm you need.

In our game we use a bounding ellipse to limit the A* traversal with the actors current position and the target position as the focal points.

If a pathfind fails, we still move towards the closest square that we found to the goal.

When the two points are far away from each other the ellipse is long and thin which causes the paths to be very direct. As the current position and target position get closer the ellipse turns in to more of a circle meaning that the pathfinder will discover more indirect routes should they be needed to get to the final goal.

So this means that entities will tend to move in direct paths when they are far away (even if they don't actually know if they will be able to complete the path yet) and then discover an actual route around blocking obsticals as they get closer.

Because long and thin ellipses tend to really constrain the number of nodes that will be considered, it works pretty well to speed up the A* searches.

Re:Pathfinding Demystified by gradstudent on Friday May 16, 2014 @10:42AM (#7755740)
Do you have time to preprocess the map? Do you have some spare memory? If so, check out Compressed path databases.

They're a type of oracle that does exactly what you want: given a start and target position, the oracle returns the next step on the optimal path to the target. You can extract one step, a few steps or the entire path. Extracting a single step is very fast since it requires little more than a memory lookup. Needless to say this approach has significant advantages if you need to constantly replan your path.

Re:Pathfinding Demystified by ggambetta on Friday May 16, 2014 @08:14AM (#7755039)
If "trying to move closer" is enough, maybe you don't even need a pathfinding algorithm - if the target is to the right move one step to the right, if the target is above move one step up, and so on?
Re:Pathfinding Demystified by Kiro on Saturday May 17, 2014 @08:34AM (#7759956)
That's basically what I have with the addition of a small collision check. If there is a collision tile between the seeker and the target it tries to move sideways but this has the effect that it only takes three adjacent tiles to stop the seeker from reaching the target. I would like something smarter than that but still preserve the efficiency.
Re:Pathfinding Demystified by datashaman on Friday May 16, 2014 @08:42AM (#7755131)
What if there are obstacles in the path? You'll need a more complex algorithm to deal with the possibility of getting stuck in corners.
Re:Pathfinding Demystified by ggambetta on Friday May 16, 2014 @09:05AM (#7755212)
Well, he did say "It doesn't really matter if it gets stuck".
Re:Pathfinding Demystified by datashaman on Friday May 16, 2014 @09:25AM (#7755315)
puts glasses on ah. :-$
Re:Pathfinding Demystified by conjectures on Friday May 16, 2014 @07:20AM (#7754896)
Guesses more than ideas but. Have the distance estimation function take time as an argument? Actually move along the current best n-step path then start again?