Timeline for A* navigational mesh path finding
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 9, 2018 at 21:32 | history | edited | user1430 | edited tags | |
| Nov 16, 2017 at 21:56 | review | Suggested edits | |||
| Nov 17, 2017 at 0:52 | |||||
| May 23, 2017 at 12:37 | history | edited | CommunityBot | replaced http://stackoverflow.com/ with https://stackoverflow.com/ | |
| Nov 30, 2011 at 15:36 | comment | added | angrydust | 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, 2011 at 15:33 | comment | added | angrydust | @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, 2011 at 13:28 | comment | added | Jonathan Dickinson | Polygon storage: only store the visible polygons - or associate a tag with each polygon (remember each polygon will need to be a circular list of vertices); similarly with nodes you can store the ID of the polygon that they originate from - but I shouldn't need to tell you this: it's elementary data storage. Finally why do you care about the true shortest path? Your game can run dog slow or you can have slightly incorrect paths: choose one. Obtaining the true shortest path REQUIRES a full breadth-first search (at least over a node graph). | |
| Nov 30, 2011 at 11:58 | history | edited | angrydust | CC BY-SA 3.0 | Made links inline (now that I have finally had my new user restrictions removed!) |
| Nov 30, 2011 at 11:47 | comment | added | angrydust | 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, 2011 at 11:17 | comment | added | angrydust | 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, 2011 at 23:23 | answer | added | U62 | timeline score: 15 | |
| Nov 29, 2011 at 23:21 | history | tweeted | twitter.com/#!/StackGameDev/status/141658143594774528 | ||
| Nov 29, 2011 at 21:22 | comment | added | Ali1S232 | I'm not sure but these links may help: gamedev.stackexchange.com/questions/1327/… gamedev.stackexchange.com/questions/8087/… also there was another question about path-finding that I can't find right now, which got a bounty and had a very good answer. | |
| Nov 29, 2011 at 20:24 | history | edited | user1430 | CC BY-SA 3.0 | deleted 90 characters in body |
| S Nov 29, 2011 at 20:23 | history | suggested | Jimmy | CC BY-SA 3.0 | added links |
| Nov 29, 2011 at 20:11 | review | Suggested edits | |||
| S Nov 29, 2011 at 20:23 | |||||
| Nov 29, 2011 at 20:05 | history | asked | angrydust | CC BY-SA 3.0 |