161 reputation
14
bio website
location
age 18
visits member for 2 years, 8 months
seen Aug 30 '13 at 15:51

Interests: Computing, Programming, Linux, Technology, Music, Drumming, Climbing.
Programming and/or scripting languages: Java, PHP, JavaScript, SQL (MySQL), (X)HTML (5), CSS (3)
OS: Arch Linux


Jul
2
awarded  Notable Question
May
24
awarded  Popular Question
Mar
26
awarded  Nice Question
Nov
30
comment A* navigational mesh path finding
Furthermore, even if I did a full breadth-first search in both of these cases it would still find the same path due to the nature of the polygon mesh. So after smoothing (or even without) I would still be left walking the long way around the obstacle. So basically I REQUIRE the true shortest found using inadmissible A* preferably using a navigational mesh rather than visibility graph and then I will care about optimising later! (Anyway I though "premature optimization is the root of all evil"?)
Nov
30
comment A* navigational mesh path finding
@JonathanDickinson I know I don't need a path that will be 100% accurate to the last pixel, and I know I can use A* to produce paths that will be at most p admissible. The thing is going the long way round an obstacle so clearly, as in my previous question on stack overflow or in gamedev.stackexchange.com/questions/8087/… is simply too much. I can't let my AI walk that way around an obstacle!
Nov
30
comment A* navigational mesh path finding
@JonathanDickinson I know, hence my point.
Nov
30
awarded  Editor
Nov
30
revised A* navigational mesh path finding
Made links inline (now that I have finally had my new user restrictions removed!)
Nov
30
comment A* navigational mesh path finding
Actually, I just read the article in gamedev.stackexchange.com/questions/8087/… and it seems to work by finding a route with A*, then calculating it's true cost with a modified funnel algorithm and then finding another route and calculating it's true cost again and seeing if it is any shorter than the other one. It repeats until it knows it's found the shortest route. This does indeed solve my problem, however, this seems like it will be quite slow as you are repeating both the straightening and the path finding, which would be quite costly.
Nov
30
comment A* navigational mesh path finding
I want to have a nav mesh where A* will always find the path that once straightened is the shortest, regardless of the cost of traveling via vertices/midpoints. I appreciate that this can be done with visibility graph's but I want to use a navmesh because it has a lot of other benefits and because the complexity of a visibility graph can grow very quickly: theory.stanford.edu/~amitp/GameProgramming/…
Nov
30
comment A* navigational mesh path finding
I'm not really concerned about how to actually go about the path straightening atm, what I am concerned about is what you say: "You should observe that it will only straighten the path within the bounds of the polygons found during the A* search. As such, if that doesn't not find the tightest path around an obstacle, you will not get a tight path after running that algorithm either."
Nov
30
comment A* navigational mesh path finding
I've just had a brief read of this, but I understand you should never use the square of the distance (or not square root it) for A*: theory.stanford.edu/~amitp/GameProgramming/…
Nov
30
comment A* navigational mesh path finding
Yes, in the second link you can see my primary concern, the A* algorithm would give the path round the bottom as being the shortest using edge midpoints but the path round the top of the obstacle is actually the shortest. I want to know how I can get A* to give me the path round the top which I will then straighten (by a funnel algorithm for example) to get the true shortest path, where as if it gives me the one around the bottom then even if I straighten it it is still taking a detour.
Nov
29
awarded  Student
Nov
29
comment A* navigational mesh path finding
thanks for adding the links :)
Nov
29
asked A* navigational mesh path finding