{"action":"created","issue":{"url":"https://api.github.com/repos/TeamPorcupine/ProjectPorcupine/issues/1560","repository_url":"https://api.github.com/repos/TeamPorcupine/ProjectPorcupine","labels_url":"https://api.github.com/repos/TeamPorcupine/ProjectPorcupine/issues/1560/labels{/name}","comments_url":"https://api.github.com/repos/TeamPorcupine/ProjectPorcupine/issues/1560/comments","events_url":"https://api.github.com/repos/TeamPorcupine/ProjectPorcupine/issues/1560/events","html_url":"https://github.com/TeamPorcupine/ProjectPorcupine/issues/1560","id":184032210,"number":1560,"title":"Pathfinding Improvements [Discussion]","user":{"login":"Geoffrotism","id":5430964,"avatar_url":"https://avatars.githubusercontent.com/u/5430964?v=3","gravatar_id":"","url":"https://api.github.com/users/Geoffrotism","html_url":"https://github.com/Geoffrotism","followers_url":"https://api.github.com/users/Geoffrotism/followers","following_url":"https://api.github.com/users/Geoffrotism/following{/other_user}","gists_url":"https://api.github.com/users/Geoffrotism/gists{/gist_id}","starred_url":"https://api.github.com/users/Geoffrotism/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Geoffrotism/subscriptions","organizations_url":"https://api.github.com/users/Geoffrotism/orgs","repos_url":"https://api.github.com/users/Geoffrotism/repos","events_url":"https://api.github.com/users/Geoffrotism/events{/privacy}","received_events_url":"https://api.github.com/users/Geoffrotism/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":7,"created_at":"2016-10-19T17:58:41Z","updated_at":"2016-10-19T21:59:59Z","closed_at":null,"body":"# Problem\r\n\r\nThe current pathfinding system often takes a long time to find a valid path if the distance between starting and ending locations are large.\r\n\r\n# Suggested Solution\r\n\r\nI would suggest switching to JPS (jump-point system) to do all exterior pathfinding. This method has a substantial decrease in evaluation time compared to A* and Dijkstra. One thing to note is that JPS requires uniform movement cost across tiles which is why @vogonistic suggested to use it for tiles in space. We would use A* for tiles inside to make use of the movement cost modifiers. \r\n\r\nJPS was originally used for 2D tile graphs that allowed diagonal movement. (you can read a good summary here: \r\n[http://zerowidth.com/2013/05/05/jump-point-search-explained.html](url)\r\n\r\nThe problem with this is that we have a 3D map and do not allow diagonal tile movement. I propose that instead of expanding diagonally until finding a forced neighbor, we expand along the X coords and expand along the Y and Z axis when looking for forced neighbors. \r\n\r\nMy reasoning has a little bit to do with the psychology of the mind. I believe most people are likely to build their space station, it will be more wide than tall. Most players in factorio build their bases spanning horizontally. Disney World in Florida was designed knowing that most people will enter the park and then turn right instead of staying straight (which is why the bridge to futureland is wider than that of the other bridges.)\r\n\r\nThis will help in the case that the distance (as the crow flies) to reach the X coord of the end point is larger than the distances to either the Y or Z coords.\r\n\r\n# Task List\r\n\r\n-[] Implement base design.\r\n-[] Split pathfinding between inside and outside.\r\n-[] Try bi-directional searching.\r\n-[] Add handling for cases where there is no valid path."},"comment":{"url":"https://api.github.com/repos/TeamPorcupine/ProjectPorcupine/issues/comments/254953608","html_url":"https://github.com/TeamPorcupine/ProjectPorcupine/issues/1560#issuecomment-254953608","issue_url":"https://api.github.com/repos/TeamPorcupine/ProjectPorcupine/issues/1560","id":254953608,"user":{"login":"koosemose","id":6334643,"avatar_url":"https://avatars.githubusercontent.com/u/6334643?v=3","gravatar_id":"","url":"https://api.github.com/users/koosemose","html_url":"https://github.com/koosemose","followers_url":"https://api.github.com/users/koosemose/followers","following_url":"https://api.github.com/users/koosemose/following{/other_user}","gists_url":"https://api.github.com/users/koosemose/gists{/gist_id}","starred_url":"https://api.github.com/users/koosemose/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/koosemose/subscriptions","organizations_url":"https://api.github.com/users/koosemose/orgs","repos_url":"https://api.github.com/users/koosemose/repos","events_url":"https://api.github.com/users/koosemose/events{/privacy}","received_events_url":"https://api.github.com/users/koosemose/received_events","type":"User","site_admin":false},"created_at":"2016-10-19T21:59:59Z","updated_at":"2016-10-19T21:59:59Z","body":"@vogonistic As much as I could understand of that sounds good. \r\n\r\nAnd I definitely think in the case of pathfinding we can accept not absolutely optimal solutions. Which includes the whole thing I remember you talking about with some folks about... non admissable heuristics... And actually watching quill play rimworld I noticed some of the paths generated seemed to show evidence of just that, like going diagonal for a bit and then another diagonal where optimally it could have just gone straight in the first place, and I don't think I'd have noticed it had I not just before the video been looking up exactly what that does to pathfinding."}}
{"actor":{"display_login":"koosemose"}}