{"action":"created","comment":{"url":"https://api.github.com/repos/OpenRA/OpenRA/pulls/comments/25000456","id":25000456,"diff_hunk":"@@ -1,4 +1,4 @@\n-<?xml version=\"1.0\" encoding=\"utf-8\"?>\n+﻿<?xml version=\"1.0\" encoding=\"utf-8\"?>","path":"OpenRA.Game/OpenRA.Game.csproj","position":2,"original_position":2,"commit_id":"6079421f3bb18f0024dc0f7c1f9b18a11b5564b6","original_commit_id":"0dad56a95752d872ac272c6ef0bada1210d2fc52","user":{"login":"Rydra","id":5826108,"avatar_url":"https://avatars.githubusercontent.com/u/5826108?v=3","gravatar_id":"","url":"https://api.github.com/users/Rydra","html_url":"https://github.com/Rydra","followers_url":"https://api.github.com/users/Rydra/followers","following_url":"https://api.github.com/users/Rydra/following{/other_user}","gists_url":"https://api.github.com/users/Rydra/gists{/gist_id}","starred_url":"https://api.github.com/users/Rydra/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Rydra/subscriptions","organizations_url":"https://api.github.com/users/Rydra/orgs","repos_url":"https://api.github.com/users/Rydra/repos","events_url":"https://api.github.com/users/Rydra/events{/privacy}","received_events_url":"https://api.github.com/users/Rydra/received_events","type":"User","site_admin":false},"body":"Can't really see what's wrong with the project xml.","created_at":"2015-02-19T16:20:48Z","updated_at":"2015-02-19T16:20:48Z","html_url":"https://github.com/OpenRA/OpenRA/pull/7430#discussion_r25000456","pull_request_url":"https://api.github.com/repos/OpenRA/OpenRA/pulls/7430","_links":{"self":{"href":"https://api.github.com/repos/OpenRA/OpenRA/pulls/comments/25000456"},"html":{"href":"https://github.com/OpenRA/OpenRA/pull/7430#discussion_r25000456"},"pull_request":{"href":"https://api.github.com/repos/OpenRA/OpenRA/pulls/7430"}}},"pull_request":{"url":"https://api.github.com/repos/OpenRA/OpenRA/pulls/7430","id":28711414,"html_url":"https://github.com/OpenRA/OpenRA/pull/7430","diff_url":"https://github.com/OpenRA/OpenRA/pull/7430.diff","patch_url":"https://github.com/OpenRA/OpenRA/pull/7430.patch","issue_url":"https://api.github.com/repos/OpenRA/OpenRA/issues/7430","number":7430,"state":"open","locked":false,"title":"[Discussion PR] Complete refactor of Pathfinder","user":{"login":"Rydra","id":5826108,"avatar_url":"https://avatars.githubusercontent.com/u/5826108?v=3","gravatar_id":"","url":"https://api.github.com/users/Rydra","html_url":"https://github.com/Rydra","followers_url":"https://api.github.com/users/Rydra/followers","following_url":"https://api.github.com/users/Rydra/following{/other_user}","gists_url":"https://api.github.com/users/Rydra/gists{/gist_id}","starred_url":"https://api.github.com/users/Rydra/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Rydra/subscriptions","organizations_url":"https://api.github.com/users/Rydra/orgs","repos_url":"https://api.github.com/users/Rydra/repos","events_url":"https://api.github.com/users/Rydra/events{/privacy}","received_events_url":"https://api.github.com/users/Rydra/received_events","type":"User","site_admin":false},"body":"The whole intent of this pull request is basically to review and discuss the changes I introduced in the pathfinder architecture and algorithm, find better solutions and guide the development to a better version. According to unit test benchmarks and some playtests I've thrown in, I've achieved approximately a 20% increased performance in the pathfinder. However, I need some help in order to implement integration tests to make some real and better pathfinding benchmarking as it seems quite complex to create Map, Actor and World instances and I'm not fully aware of how it works.\r\n\r\nIf someone wants to test in-game differences between legacy pathfinder and the new pathfinder, he or she should simply go to the file OpenRA.Mods.Common\\Traits\\World\\Pathfinder\\PathFinderInfo.cs and change the line \"return new PathFinderCacheDecorator(new PathFinder(init.World), new PathCacheStorage(init.World));\" to \"return new PathFinderCacheDecorator(new LegacyPathFinder(init.World), new PathCacheStorage(init.World));\". This is one of the advantages of the changes I introduced, it's rather easy to switch implementation strategies.\r\n\r\nThe next steps after re-architecting the pathfinder should be to improve the A* algorithm. The 0 A.D. (another great opensource RTS game) provides some interesting documentation and strategies they use for their pathfinder: https://github.com/0ad/0ad/blob/master/docs/pathfinder.tex\r\n\r\nI made a complete refactor of the Pathfinder trait, based upon PR #7358. The goals of these changes are:\r\n\r\n- Isolate the dependencies (by extracting interfaces of classes like\r\n  Actor, Map and World) of the pathfinder trait and A* algorithm and\r\n  allow testability\r\n\r\n- Follow software engineering design patterns and best practices (SOLID\r\n  design principles) to create smaller, focused and isolated classes and\r\n  methods to allow to easily swap, create and benchmark different implementations\r\n  (through dependency injection), extend functionality and follow the SRP\r\n  principle and, of course, easier to read and understand.\r\n\r\n- Detect redundant calculations and unfitted data structures for several\r\n  problems\r\n\r\n- Ultimately, performance improvements\r\n\r\nIn detail, the changes introduced in this commit are the following:\r\n\r\n- The changes in PR #7358 (fragmented methods from the Expand algorithm,\r\n  fragmented the caching capabilities from the PathFinder class,\r\n  introduced interfaces to Actor, Map, and World classes, enabled unit\r\n  testability.\r\n\r\n- Fragmented the whole code which regards to pathfinding into several\r\n  files, placed inside its own folder \"Pathfinder\".\r\n\r\n- Improved the path cache (PathCacheStorage class) to work with a\r\n  Dictionary structure instead of a list for faster lookups and removals\r\n\r\n- Modified the CellLayer class to work with the Prototype design pattern,\r\n  and encapsulated this functionality in the class instead of making the\r\n  PathSearch class responsible for it.\r\n\r\n- Code which lookup up for \"PathFinder\" trait now looks for the\r\n  \"IPathFinder\" trait.\r\n\r\n- Extracted interface in the PriorityQueue class to be able to work with\r\n  both the former implementation or with a .Net SortedSet data structure.\r\n  Using one implementation or the other should be dependant on benchmarks\r\n  and use cases (Insertions in SorterSet are O(log n), removals and\r\n  Min lookups are O(1) while insertions in PriorityQueue are O(1) but Pops\r\n  are O(n log n)).\r\n\r\n- Extracted interface for the PathSearch class so we can provide different\r\n  implementations for the A* algorithm. 2 implementations for PathSearch\r\n  and Pathfinder are provided\r\n  currently: LegacyPathFinder and LegacyPathSearch (which contains the\r\n  same implementation as the former PathSearch class, only adapted to work\r\n  with interfaces, which has negligible penalty cost) and PathFinder and\r\n  PathSearch, which contains tweaked modifications of the A*, mobileinfo\r\n  and different data structures which are better fit with their usage.\r\n  This last implementation should be faster.\r\n\r\n- Provided more unit tests for benchmarking.","created_at":"2015-02-05T09:56:34Z","updated_at":"2015-02-19T16:20:48Z","closed_at":null,"merged_at":null,"merge_commit_sha":"981826e5e624cce60edfe38d088ae90a73f6915f","assignee":null,"milestone":{"url":"https://api.github.com/repos/OpenRA/OpenRA/milestones/12","labels_url":"https://api.github.com/repos/OpenRA/OpenRA/milestones/12/labels","id":844833,"number":12,"title":"Next release","description":"","creator":{"login":"obrakmann","id":4331210,"avatar_url":"https://avatars.githubusercontent.com/u/4331210?v=3","gravatar_id":"","url":"https://api.github.com/users/obrakmann","html_url":"https://github.com/obrakmann","followers_url":"https://api.github.com/users/obrakmann/followers","following_url":"https://api.github.com/users/obrakmann/following{/other_user}","gists_url":"https://api.github.com/users/obrakmann/gists{/gist_id}","starred_url":"https://api.github.com/users/obrakmann/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/obrakmann/subscriptions","organizations_url":"https://api.github.com/users/obrakmann/orgs","repos_url":"https://api.github.com/users/obrakmann/repos","events_url":"https://api.github.com/users/obrakmann/events{/privacy}","received_events_url":"https://api.github.com/users/obrakmann/received_events","type":"User","site_admin":false},"open_issues":6,"closed_issues":29,"state":"open","created_at":"2014-10-29T09:04:03Z","updated_at":"2015-02-19T16:00:27Z","due_on":null,"closed_at":null},"commits_url":"https://api.github.com/repos/OpenRA/OpenRA/pulls/7430/commits","review_comments_url":"https://api.github.com/repos/OpenRA/OpenRA/pulls/7430/comments","review_comment_url":"https://api.github.com/repos/OpenRA/OpenRA/pulls/comments/{number}","comments_url":"https://api.github.com/repos/OpenRA/OpenRA/issues/7430/comments","statuses_url":"https://api.github.com/repos/OpenRA/OpenRA/statuses/6079421f3bb18f0024dc0f7c1f9b18a11b5564b6","head":{"label":"Rydra:upstream/pf-optimized","ref":"upstream/pf-optimized","sha":"6079421f3bb18f0024dc0f7c1f9b18a11b5564b6","user":{"login":"Rydra","id":5826108,"avatar_url":"https://avatars.githubusercontent.com/u/5826108?v=3","gravatar_id":"","url":"https://api.github.com/users/Rydra","html_url":"https://github.com/Rydra","followers_url":"https://api.github.com/users/Rydra/followers","following_url":"https://api.github.com/users/Rydra/following{/other_user}","gists_url":"https://api.github.com/users/Rydra/gists{/gist_id}","starred_url":"https://api.github.com/users/Rydra/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Rydra/subscriptions","organizations_url":"https://api.github.com/users/Rydra/orgs","repos_url":"https://api.github.com/users/Rydra/repos","events_url":"https://api.github.com/users/Rydra/events{/privacy}","received_events_url":"https://api.github.com/users/Rydra/received_events","type":"User","site_admin":false},"repo":{"id":19907485,"name":"OpenRA","full_name":"Rydra/OpenRA","owner":{"login":"Rydra","id":5826108,"avatar_url":"https://avatars.githubusercontent.com/u/5826108?v=3","gravatar_id":"","url":"https://api.github.com/users/Rydra","html_url":"https://github.com/Rydra","followers_url":"https://api.github.com/users/Rydra/followers","following_url":"https://api.github.com/users/Rydra/following{/other_user}","gists_url":"https://api.github.com/users/Rydra/gists{/gist_id}","starred_url":"https://api.github.com/users/Rydra/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Rydra/subscriptions","organizations_url":"https://api.github.com/users/Rydra/orgs","repos_url":"https://api.github.com/users/Rydra/repos","events_url":"https://api.github.com/users/Rydra/events{/privacy}","received_events_url":"https://api.github.com/users/Rydra/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/Rydra/OpenRA","description":"An open-source implementation of the Red Alert engine using .NET/mono and OpenGL. Runs on Windows, Linux and Mac OS X.","fork":true,"url":"https://api.github.com/repos/Rydra/OpenRA","forks_url":"https://api.github.com/repos/Rydra/OpenRA/forks","keys_url":"https://api.github.com/repos/Rydra/OpenRA/keys{/key_id}","collaborators_url":"https://api.github.com/repos/Rydra/OpenRA/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/Rydra/OpenRA/teams","hooks_url":"https://api.github.com/repos/Rydra/OpenRA/hooks","issue_events_url":"https://api.github.com/repos/Rydra/OpenRA/issues/events{/number}","events_url":"https://api.github.com/repos/Rydra/OpenRA/events","assignees_url":"https://api.github.com/repos/Rydra/OpenRA/assignees{/user}","branches_url":"https://api.github.com/repos/Rydra/OpenRA/branches{/branch}","tags_url":"https://api.github.com/repos/Rydra/OpenRA/tags","blobs_url":"https://api.github.com/repos/Rydra/OpenRA/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/Rydra/OpenRA/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/Rydra/OpenRA/git/refs{/sha}","trees_url":"https://api.github.com/repos/Rydra/OpenRA/git/trees{/sha}","statuses_url":"https://api.github.com/repos/Rydra/OpenRA/statuses/{sha}","languages_url":"https://api.github.com/repos/Rydra/OpenRA/languages","stargazers_url":"https://api.github.com/repos/Rydra/OpenRA/stargazers","contributors_url":"https://api.github.com/repos/Rydra/OpenRA/contributors","subscribers_url":"https://api.github.com/repos/Rydra/OpenRA/subscribers","subscription_url":"https://api.github.com/repos/Rydra/OpenRA/subscription","commits_url":"https://api.github.com/repos/Rydra/OpenRA/commits{/sha}","git_commits_url":"https://api.github.com/repos/Rydra/OpenRA/git/commits{/sha}","comments_url":"https://api.github.com/repos/Rydra/OpenRA/comments{/number}","issue_comment_url":"https://api.github.com/repos/Rydra/OpenRA/issues/comments/{number}","contents_url":"https://api.github.com/repos/Rydra/OpenRA/contents/{+path}","compare_url":"https://api.github.com/repos/Rydra/OpenRA/compare/{base}...{head}","merges_url":"https://api.github.com/repos/Rydra/OpenRA/merges","archive_url":"https://api.github.com/repos/Rydra/OpenRA/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/Rydra/OpenRA/downloads","issues_url":"https://api.github.com/repos/Rydra/OpenRA/issues{/number}","pulls_url":"https://api.github.com/repos/Rydra/OpenRA/pulls{/number}","milestones_url":"https://api.github.com/repos/Rydra/OpenRA/milestones{/number}","notifications_url":"https://api.github.com/repos/Rydra/OpenRA/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/Rydra/OpenRA/labels{/name}","releases_url":"https://api.github.com/repos/Rydra/OpenRA/releases{/id}","created_at":"2014-05-18T09:46:30Z","updated_at":"2015-02-17T19:29:43Z","pushed_at":"2015-02-19T16:15:25Z","git_url":"git://github.com/Rydra/OpenRA.git","ssh_url":"git@github.com:Rydra/OpenRA.git","clone_url":"https://github.com/Rydra/OpenRA.git","svn_url":"https://github.com/Rydra/OpenRA","homepage":"http://open-ra.org","size":83885,"stargazers_count":3,"watchers_count":3,"language":"C#","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":3,"default_branch":"bleed"}},"base":{"label":"OpenRA:bleed","ref":"bleed","sha":"e2da1f11cb98efae0f43c93e87d994d23db18b1a","user":{"login":"OpenRA","id":409046,"avatar_url":"https://avatars.githubusercontent.com/u/409046?v=3","gravatar_id":"","url":"https://api.github.com/users/OpenRA","html_url":"https://github.com/OpenRA","followers_url":"https://api.github.com/users/OpenRA/followers","following_url":"https://api.github.com/users/OpenRA/following{/other_user}","gists_url":"https://api.github.com/users/OpenRA/gists{/gist_id}","starred_url":"https://api.github.com/users/OpenRA/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/OpenRA/subscriptions","organizations_url":"https://api.github.com/users/OpenRA/orgs","repos_url":"https://api.github.com/users/OpenRA/repos","events_url":"https://api.github.com/users/OpenRA/events{/privacy}","received_events_url":"https://api.github.com/users/OpenRA/received_events","type":"Organization","site_admin":false},"repo":{"id":959908,"name":"OpenRA","full_name":"OpenRA/OpenRA","owner":{"login":"OpenRA","id":409046,"avatar_url":"https://avatars.githubusercontent.com/u/409046?v=3","gravatar_id":"","url":"https://api.github.com/users/OpenRA","html_url":"https://github.com/OpenRA","followers_url":"https://api.github.com/users/OpenRA/followers","following_url":"https://api.github.com/users/OpenRA/following{/other_user}","gists_url":"https://api.github.com/users/OpenRA/gists{/gist_id}","starred_url":"https://api.github.com/users/OpenRA/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/OpenRA/subscriptions","organizations_url":"https://api.github.com/users/OpenRA/orgs","repos_url":"https://api.github.com/users/OpenRA/repos","events_url":"https://api.github.com/users/OpenRA/events{/privacy}","received_events_url":"https://api.github.com/users/OpenRA/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/OpenRA/OpenRA","description":"An open-source implementation of the Command & Conquer: Red Alert engine using .NET/Mono and OpenGL. Runs on Windows, Linux and Mac OS X.","fork":false,"url":"https://api.github.com/repos/OpenRA/OpenRA","forks_url":"https://api.github.com/repos/OpenRA/OpenRA/forks","keys_url":"https://api.github.com/repos/OpenRA/OpenRA/keys{/key_id}","collaborators_url":"https://api.github.com/repos/OpenRA/OpenRA/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/OpenRA/OpenRA/teams","hooks_url":"https://api.github.com/repos/OpenRA/OpenRA/hooks","issue_events_url":"https://api.github.com/repos/OpenRA/OpenRA/issues/events{/number}","events_url":"https://api.github.com/repos/OpenRA/OpenRA/events","assignees_url":"https://api.github.com/repos/OpenRA/OpenRA/assignees{/user}","branches_url":"https://api.github.com/repos/OpenRA/OpenRA/branches{/branch}","tags_url":"https://api.github.com/repos/OpenRA/OpenRA/tags","blobs_url":"https://api.github.com/repos/OpenRA/OpenRA/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/OpenRA/OpenRA/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/OpenRA/OpenRA/git/refs{/sha}","trees_url":"https://api.github.com/repos/OpenRA/OpenRA/git/trees{/sha}","statuses_url":"https://api.github.com/repos/OpenRA/OpenRA/statuses/{sha}","languages_url":"https://api.github.com/repos/OpenRA/OpenRA/languages","stargazers_url":"https://api.github.com/repos/OpenRA/OpenRA/stargazers","contributors_url":"https://api.github.com/repos/OpenRA/OpenRA/contributors","subscribers_url":"https://api.github.com/repos/OpenRA/OpenRA/subscribers","subscription_url":"https://api.github.com/repos/OpenRA/OpenRA/subscription","commits_url":"https://api.github.com/repos/OpenRA/OpenRA/commits{/sha}","git_commits_url":"https://api.github.com/repos/OpenRA/OpenRA/git/commits{/sha}","comments_url":"https://api.github.com/repos/OpenRA/OpenRA/comments{/number}","issue_comment_url":"https://api.github.com/repos/OpenRA/OpenRA/issues/comments/{number}","contents_url":"https://api.github.com/repos/OpenRA/OpenRA/contents/{+path}","compare_url":"https://api.github.com/repos/OpenRA/OpenRA/compare/{base}...{head}","merges_url":"https://api.github.com/repos/OpenRA/OpenRA/merges","archive_url":"https://api.github.com/repos/OpenRA/OpenRA/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/OpenRA/OpenRA/downloads","issues_url":"https://api.github.com/repos/OpenRA/OpenRA/issues{/number}","pulls_url":"https://api.github.com/repos/OpenRA/OpenRA/pulls{/number}","milestones_url":"https://api.github.com/repos/OpenRA/OpenRA/milestones{/number}","notifications_url":"https://api.github.com/repos/OpenRA/OpenRA/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/OpenRA/OpenRA/labels{/name}","releases_url":"https://api.github.com/repos/OpenRA/OpenRA/releases{/id}","created_at":"2010-10-04T07:38:05Z","updated_at":"2015-02-19T14:34:36Z","pushed_at":"2015-02-18T22:40:59Z","git_url":"git://github.com/OpenRA/OpenRA.git","ssh_url":"git@github.com:OpenRA/OpenRA.git","clone_url":"https://github.com/OpenRA/OpenRA.git","svn_url":"https://github.com/OpenRA/OpenRA","homepage":"http://www.openra.net","size":157828,"stargazers_count":1738,"watchers_count":1738,"language":"C#","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":607,"mirror_url":null,"open_issues_count":697,"forks":607,"open_issues":697,"watchers":1738,"default_branch":"bleed"}},"_links":{"self":{"href":"https://api.github.com/repos/OpenRA/OpenRA/pulls/7430"},"html":{"href":"https://github.com/OpenRA/OpenRA/pull/7430"},"issue":{"href":"https://api.github.com/repos/OpenRA/OpenRA/issues/7430"},"comments":{"href":"https://api.github.com/repos/OpenRA/OpenRA/issues/7430/comments"},"review_comments":{"href":"https://api.github.com/repos/OpenRA/OpenRA/pulls/7430/comments"},"review_comment":{"href":"https://api.github.com/repos/OpenRA/OpenRA/pulls/comments/{number}"},"commits":{"href":"https://api.github.com/repos/OpenRA/OpenRA/pulls/7430/commits"},"statuses":{"href":"https://api.github.com/repos/OpenRA/OpenRA/statuses/6079421f3bb18f0024dc0f7c1f9b18a11b5564b6"}}}}