{"action":"created","issue":{"url":"https://api.github.com/repos/OpenRCT2/OpenRCT2/issues/6440","repository_url":"https://api.github.com/repos/OpenRCT2/OpenRCT2","labels_url":"https://api.github.com/repos/OpenRCT2/OpenRCT2/issues/6440/labels{/name}","comments_url":"https://api.github.com/repos/OpenRCT2/OpenRCT2/issues/6440/comments","events_url":"https://api.github.com/repos/OpenRCT2/OpenRCT2/issues/6440/events","html_url":"https://github.com/OpenRCT2/OpenRCT2/pull/6440","id":264718728,"node_id":"MDExOlB1bGxSZXF1ZXN0MTQ2MDQ4ODUz","number":6440,"title":"Initial prototype of A* for the heuristic search.","user":{"login":"zaxcav","id":20344978,"node_id":"MDQ6VXNlcjIwMzQ0OTc4","avatar_url":"https://avatars0.githubusercontent.com/u/20344978?v=4","gravatar_id":"","url":"https://api.github.com/users/zaxcav","html_url":"https://github.com/zaxcav","followers_url":"https://api.github.com/users/zaxcav/followers","following_url":"https://api.github.com/users/zaxcav/following{/other_user}","gists_url":"https://api.github.com/users/zaxcav/gists{/gist_id}","starred_url":"https://api.github.com/users/zaxcav/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/zaxcav/subscriptions","organizations_url":"https://api.github.com/users/zaxcav/orgs","repos_url":"https://api.github.com/users/zaxcav/repos","events_url":"https://api.github.com/users/zaxcav/events{/privacy}","received_events_url":"https://api.github.com/users/zaxcav/received_events","type":"User","site_admin":false},"labels":[{"id":281304053,"node_id":"MDU6TGFiZWwyODEzMDQwNTM=","url":"https://api.github.com/repos/OpenRCT2/OpenRCT2/labels/on%20hold","name":"on hold","color":"e11d21","default":false}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":28,"created_at":"2017-10-11T20:06:48Z","updated_at":"2018-06-12T21:20:22Z","closed_at":null,"author_association":"CONTRIBUTOR","pull_request":{"url":"https://api.github.com/repos/OpenRCT2/OpenRCT2/pulls/6440","html_url":"https://github.com/OpenRCT2/OpenRCT2/pull/6440","diff_url":"https://github.com/OpenRCT2/OpenRCT2/pull/6440.diff","patch_url":"https://github.com/OpenRCT2/OpenRCT2/pull/6440.patch"},"body":"First signs of life from the A* heuristic search I've been working on.\r\n\r\nThe A* code can either be enabled for all peeps (with significant performance degradation in parks with lots of peeps) or only for selected peeps.\r\n\r\nIn Peep.cpp the variable gAStarEnableAll (shortly after the #includes at the top of the file) controls this.\r\nThe A* code is currently enabled for all peeps be default.\r\n\r\nWhen the A* code is enabled for only selected peeps, peeps are selected as follows:\r\n- guests use A* when they are being tracked;\r\n- mechanics use A* when they are named \"Mechanic Star\".\r\n\r\nThe A* code is substantially simpler than the existing heuristic search despite implementing similar specific handling of overlaid paths (zero clearance) to cater for really creative builders.\r\n\r\nI've done rudimentary testing using save games for all of the path finding issues I've fixed over the last months, and the A* code works at least as well as the existing heuristic and lots better where the wide paths are causing \"unnatural\" behavior in the existing heuristic.\r\n\r\nThe various A* lists (open, closed,etc) are currently a hack with O(n) performance for search operations, so replacing these is absolutely necessary before this can even be remotely considered for merging.\r\n\r\nNext steps:\r\n- ~~rebase to the current development branch~~ done\r\n- refactor/clean up the current A* logic\r\n- implement a more efficient data structure for the A* lists\r\n- start experimenting with fun & interesting stuff like using transport rides, letting the search leave paths (no more catastrophic path finding failures from disconnected ride entrances/exits, no more need for separate \"surface finding\" vs \"path finding\" vs all other \"* finding\")\r\n- tuning: appropriate search limits?\r\n- optimisation, incl. save state.\r\n"},"comment":{"url":"https://api.github.com/repos/OpenRCT2/OpenRCT2/issues/comments/396737790","html_url":"https://github.com/OpenRCT2/OpenRCT2/pull/6440#issuecomment-396737790","issue_url":"https://api.github.com/repos/OpenRCT2/OpenRCT2/issues/6440","id":396737790,"node_id":"MDEyOklzc3VlQ29tbWVudDM5NjczNzc5MA==","user":{"login":"IntelOrca","id":1482259,"node_id":"MDQ6VXNlcjE0ODIyNTk=","avatar_url":"https://avatars3.githubusercontent.com/u/1482259?v=4","gravatar_id":"","url":"https://api.github.com/users/IntelOrca","html_url":"https://github.com/IntelOrca","followers_url":"https://api.github.com/users/IntelOrca/followers","following_url":"https://api.github.com/users/IntelOrca/following{/other_user}","gists_url":"https://api.github.com/users/IntelOrca/gists{/gist_id}","starred_url":"https://api.github.com/users/IntelOrca/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/IntelOrca/subscriptions","organizations_url":"https://api.github.com/users/IntelOrca/orgs","repos_url":"https://api.github.com/users/IntelOrca/repos","events_url":"https://api.github.com/users/IntelOrca/events{/privacy}","received_events_url":"https://api.github.com/users/IntelOrca/received_events","type":"User","site_admin":false},"created_at":"2018-06-12T21:20:22Z","updated_at":"2018-06-12T21:20:22Z","author_association":"CONTRIBUTOR","body":"@zaxcav This looks like a good start on a more sophisticated path finding algorithm, however we are currently trying to close all our PRs so we can perform a code base re-format which will most likely cause all PRs to have nasty conflicts.\r\n\r\nWe welcome you to continue working on this if you have time. We recommend abstracting the peep AI in such a way that the game can switch between your new AI logic and the original logic. This should be done with interfaces so that the switch can be done at runtime rather than #if #else or even conventional if else blocks. That way your new code is isolated in a new source file and it is then much easier to integrate without fear of high code maintenance. Feel free to talk to us in gitter as I do have some of my own ideas for how path finding could be improved."}}
{"actor":{"display_login":"IntelOrca"}}