Timeline for How can I make A* finish faster when the destination is impassable?
Current License: CC BY-SA 3.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 7, 2015 at 10:13 | comment | added | o0'. | @mklingen in that situation it makes sense, here… not as much. | |
| Jan 6, 2015 at 20:24 | comment | added | mklingen | @Lohoris I strongly disagree. If your goal is to avoid the user waiting around for the program to finish, it's reasonable to have a limit on time, since that's directly what you're trying to avoid. I come from a robotics background, where what matters is the amount of time between now and when you have to make a control decision, or else your robot breaks something. All of our planners have hard time limits for this reason. | |
| Jan 6, 2015 at 20:08 | comment | added | AturSams | @Desty It doesn't precisely have a name. I described it's implementation in an edit to my answer bellow. | |
| Jan 4, 2015 at 22:21 | comment | added | Desty | @Zehelvion Do you know the name of the algorithm which can calculate the longest distance of an undirected graph in linear time (to the number of nodes)? I've searched for this and can't find anything that seems relevant. Are you sure this can be done? | |
| Jan 3, 2015 at 16:51 | comment | added | o0'. | I'm tempted to just remove the third option. It's just terrible, for the reasons already explained (while the other two are quite good). | |
| Jan 3, 2015 at 14:51 | comment | added | AturSams | @MSalters Well, yeah, you can compute the maximum distance but that is not the longest path problem. And the longest path program isn't NP in "path length" and not node count... NP is not like O(). NP is simply a group of all problems that cannot be computed in polynomial time so saying NP in nodes or path length is incorrect. | |
| Jan 3, 2015 at 14:42 | comment | added | MSalters | @Zehelvion: details, really, the point is that you establish an upper bound which allows you to prune A* searches, allowing a quicker result in particular for cases when no path exists (but also for long paths near the max length) | |
| Jan 3, 2015 at 14:38 | comment | added | MSalters | @Desty: That's NP in path length, not node count, which is why I explicitly wrote O(nodes) instead of just O(n). | |
| Jan 3, 2015 at 14:29 | comment | added | AturSams | @Desty You can't, it's not directed and it's not acyclic. I've never played a game where you couldn't walk back and could never go in circles. The O(n) comment was just wrong. The correct thing is that the longest distance! Not path, DISTANCE, can be computed in O(n) so if you see the shortest, (again not longest), is longer than the longest distance, than the shortest path doesn't exist. | |
| Jan 2, 2015 at 23:17 | comment | added | Desty | @MooingDuck: True, but I don't think we can treat this as a DAG? | |
| Jan 2, 2015 at 22:26 | comment | added | Mooing Duck | @Desty: Two sentences after that: "However, it has a linear time solution for directed acyclic graphs" | |
| Jan 2, 2015 at 21:28 | comment | added | Desty | According to Wikipedia, the longest path problem is NP-hard, unfortunately. | |
| Jan 2, 2015 at 18:19 | comment | added | Steven | @MSalters How do you do this in O(n)? And what is 'reasonably efficient'? If this is only for pairs of nodes are you not just duplicating work? | |
| Jan 2, 2015 at 17:25 | comment | added | MSalters | Note that you can determine (reasonably efficient, O(nodes)) for a given graph the maximum distance between two nodes. This is the longest path problem, and it provides you with a correct upper bound for the number of nodes to check. | |
| Jan 2, 2015 at 14:43 | history | edited | mklingen | CC BY-SA 3.0 |
added 134 characters in body
|
| Jan 2, 2015 at 14:41 | comment | added | mklingen | @Philipp. Modified the answer to reflect this. | |
| Jan 2, 2015 at 9:49 | comment | added | Philipp | I would like to point out that changing the mechanics of your game depending on the CPU speed (yes, route finding is a game mechanic) might turn out to be a bad idea because it can make the game quite unpredictable and in some cases even unplayable on computers 10 years from now. So I would rather recommend to limit A* by capping the open set than by CPU time. | |
| Jan 1, 2015 at 18:30 | history | edited | Anko | CC BY-SA 3.0 |
Changed numbers to bullets to make it clearer they're not an interrelated sequence. Some grammar and clarity tweaks.
|
| Jan 1, 2015 at 15:44 | history | answered | mklingen | CC BY-SA 3.0 |