The problem with this idea NytzovNee is that it may have been the case that the path between nodes n+1 and n+3 was more optimal than the path between nodes n and n+2. If you had deleted node n+1, you would now never observe the optimality of n+1 -> n+3.
Timkin
A* on a quad-tree
Author
Using the sides has reduced the overestimation. Is there any way to completely remove the overestimation? Even if I have to calculate the distance each node (worst case) what options do I have?
To visualize the problem I am thinking of having a chain of points each on the border of a quad-tree block. They are all connected by a string connect the dots style. I want to tighten the string by moving the dots up and down their borders until I have the best (shortest) possible string (path).
I was thinking of having generations of path smoothing where each time I go through the list I move the points a little in the direction they need to go (n, n+2, move n+1 a bit). After the movement stops (or slows enough) the path will be the best it can be. Am I making sense? Are there easier ways to do this?
To visualize the problem I am thinking of having a chain of points each on the border of a quad-tree block. They are all connected by a string connect the dots style. I want to tighten the string by moving the dots up and down their borders until I have the best (shortest) possible string (path).
I was thinking of having generations of path smoothing where each time I go through the list I move the points a little in the direction they need to go (n, n+2, move n+1 a bit). After the movement stops (or slows enough) the path will be the best it can be. Am I making sense? Are there easier ways to do this?
GregK, there is tonnes of literature on such problems available, even online. You really should be reading that to work out your problem. Essentially you have an optimisation problem subject to constraints. You might want to look up mixed integer linear programming, or other linear constraint satisfaction algorithms.
Cheers,
Timkin
Cheers,
Timkin
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
