Bos Wars - Patches: patch #7141, Speed up pathfinder by caching...
You are not allowed to post comments on this tracker with your current authentication level.
patch #7141: Speed up pathfinder by caching islands
Submitter: | Kalle Olavi Niemitalo <kon> | ||
Submitted: | Sat 27 Mar 2010 07:30:37 PM UTC | ||
Open/Closed: | Closed | Status: | Wont Do |
Assigned to: | None |
Jump to the original submission
Thu 08 Jul 2010 01:51:22 PM UTC, comment #13: |
Kalle Olavi Niemitalo <kon> |
Sat 22 May 2010 12:58:43 PM UTC, comment #12: In comment #8, I mentioned a scenario that the island cache might not handle correctly. That indeed is the case. I'm attaching a map that demonstrates the problem. First apply PATCHv9 (file #20591), uncomment #define VERIFY_ISLAND_CACHE, and build the debug configuration. Start a game in this map, select all the units and tell them to move to the camera.
|
Kalle Olavi Niemitalo <kon> |
Sat 22 May 2010 12:48:18 PM UTC, comment #11: Fixed the out-of-range CostMoveTo call; PATCHv9 (for 2.6.0) attached. |
Kalle Olavi Niemitalo <kon> |
Sun 16 May 2010 12:07:21 AM UTC, comment #10: There is a bug in v7; it can call CostMoveTo with coordinates that are outside the map. It's trivial to fix but anyway I'm noting the bug here before I forget. |
Kalle Olavi Niemitalo <kon> |
Thu 13 May 2010 03:08:44 PM UTC, comment #9: The random variation in the call counts shown by gprof was caused by the SDL sound mixer thread:
|
Kalle Olavi Niemitalo <kon> |
Tue 04 May 2010 05:34:12 AM UTC, comment #8: Version 7 of the island-cache patch, for boswars-2.6 r9725. This seems to be the fastest version so far.
|
Kalle Olavi Niemitalo <kon> |
Mon 12 Apr 2010 04:36:30 AM UTC, comment #7: Attached the hack I tried to use for unattended profiling of different variants of the pathfinder. I left this running overnight and in the morning I saw v3 and v4 had failed with SIGABRT.
|
Kalle Olavi Niemitalo <kon> |
Mon 12 Apr 2010 04:19:25 AM UTC, comment #6: Version 4 of the island-cache patch, for boswars-2.6 r9725. This version tries to let other units benefit from the cache built for one unit.
|
Kalle Olavi Niemitalo <kon> |
Sun 11 Apr 2010 07:35:10 AM UTC, comment #5: Marking as postponed so feb won't apply this one yet. |
Kalle Olavi Niemitalo <kon> |
Tue 06 Apr 2010 10:06:41 PM UTC, comment #4: Here's one problematic scenario. This does NOT currently trigger a bug but might do so later.
|
Kalle Olavi Niemitalo <kon> |
Tue 06 Apr 2010 09:49:12 PM UTC, comment #3: Version 3 of the island-cache patch, for trunk r9708.
|
Kalle Olavi Niemitalo <kon> |
Sat 03 Apr 2010 08:34:59 AM UTC, comment #2: Version 2 of the island-cache patch.
|
Kalle Olavi Niemitalo <kon> |
Sun 28 Mar 2010 08:17:46 AM UTC, comment #1: I tested file #20052 on trunk r9695 by uncommenting #define VERIFY_ISLAND_CACHE and replaying file #20005 from bug #29303 until game cycle 40139. (The last command in the log is at game cycle 36203.) There were no assertion failures, which means all goals that were unreachable according to the island cache were also unreachable according to AStarFindPath.
|
Kalle Olavi Niemitalo <kon> |
Sat 27 Mar 2010 07:30:37 PM UTC, original submission:
When AStarFindPath decides that the goal is unreachable, it has already done a flood fill from the source position to all reachable tiles. Save the filled island in a cache. Then, if another unit in that island wants to move out of it, consider the goal unreachable right away.
|
Kalle Olavi Niemitalo <kon> |
Depends on the following items: None found
Items that depend on this one: None found
Follow 14 latest changes.
Date | Changed by | Updated Field | Previous Value | => | Replaced by |
---|---|---|---|---|---|
2010-07-08 | kon | Open/Closed | Open | Closed | |
Status | Postponed | Wont Do | |||
2010-05-22 | kon | Attached File | - | Added presentation.smp, #20592 | |
Attached File | - | Added setup.sms, #20593 | |||
2010-05-22 | kon | Attached File | - | Added 0001-Speed-up-pathfinder-by-caching-islands.patch, #20591 | |
2010-05-04 | kon | Attached File | - | Added 0001-Speed-up-pathfinder-by-caching-islands.patch, #20417 | |
2010-04-12 | kon | Attached File | - | Added log_of_stratagus_0-4on4-assert-failed.log, #20200 | |
2010-04-12 | kon | Attached File | - | Added 0001-Add-r-for-profiling-the-pathfinder-with-a-log.patch, #20199 | |
2010-04-12 | kon | Attached File | - | Added profile, #20198 | |
2010-04-12 | kon | Attached File | - | Added 0001-Speed-up-pathfinder-by-caching-islands.patch, #20197 | |
2010-04-11 | kon | Status | None | Postponed | |
2010-04-06 | kon | Attached File | - | Added 0001-Speed-up-pathfinder-by-caching-islands.patch, #20141 | |
2010-04-03 | kon | Attached File | - | Added 0001-Speed-up-pathfinder-by-caching-islands.patch, #20096 | |
2010-03-27 | kon | Attached File | - | Added 0001-Speed-up-pathfinder-by-caching-islands.patch, #20052 |
Powered by Savane 3.13-bb6a.
Corresponding source code
Now that jsalmon3 has fixed bug #29766, I think this patch will not be needed. Thus closing; let's reopen later if the game turns out to be too slow still.