patchBattle for Wesnoth - Patches: patch #3122, Simpler pathfinding

 
 
Show feedback again

patch #3122: Simpler pathfinding

Submitted by:  J Tyne <jamit>
Submitted on:  Sun 05 Feb 2012 08:57:14 PM UTC  
 
Priority: 5 - NormalStatus: Done
Privacy: PublicAssigned to: J Tyne <jamit>
Open/Closed: Closed

Add a New Comment (Rich MarkupRich Markup):
   

You are not logged in

Please log in, so followups can be emailed to you.

 

Sat 23 Feb 2013 01:14:32 AM UTC, SVN revision 56379:

More efficient version of find_routes().

This removes some overhead that accommodated edge-weights (which is
not needed since Wesnoth maps bear vertex weights). Testing indicates
a reduction in execution times on the order of 1%-4%. Not much, but
this function is called fairly often.

This is an updated version of (my) patch #3122.

(Browse SVN revision 56379)

J Tyne <jamit>
Project MemberIn charge of this item.
Fri 22 Feb 2013 10:59:18 PM UTC, SVN revision 56375:

Some variable name changes taken from patch #3122.

Splitting these from the logic changes should make it easier to check
them.

(Browse SVN revision 56375)

J Tyne <jamit>
Project MemberIn charge of this item.
Fri 22 Feb 2013 10:11:46 PM UTC, comment #2:

I finally got around to some speed tests. When timing batches of 10,000 calls to find_routes() -- for total execution times on the order of hundreds of milliseconds -- I am seeing execution times typically being reduced between 1% and 4%, probably averaging at least 2%. (Those times included the construction and destruction of the vector that receives the results, so the actual gain might be greater.)

So this looks like a good thing for me to update and commit.

J Tyne <jamit>
Project MemberIn charge of this item.
Wed 08 Feb 2012 05:01:37 PM UTC, comment #1:

yes, you're right, it is called fairly often. I'll take a look.

Iurii Chernyi <crab>
Project Member
Sun 05 Feb 2012 08:57:14 PM UTC, original submission:

I was looking around the codebase, orienting myself, when I noticed that the path generation in find_routes(), pathfind.cpp, was a bit more complicated than necessary. It appears to be based on Dijkstra's algorithm, which solves graphs with edge-weights. Since Wesnoth movement has vertex-weights instead, a simpler greedy algorithm can be used (as someone had already noted in the comments). I do not know how much of a savings this would be, but it does eliminate a temporary variable created for each hex evaluated for being in range. Since it looks like this function is called fairly often, this optimization might be useful.

While I was at it, I converted some names to be more meaningful and threw in some comments explaining how things work.

Anyway, it seems to work correctly and in theory should be faster (I didn't do any profiling though), so I am submitting it here for consideration for the official game.

J Tyne <jamit>
Project MemberIn charge of this item.

 

(Note: upload size limit is set to 1024 kB, after insertion of the required escape characters.)

Attach File(s):
   
   
Comment:
   

Attached Files
file #15017:  simpler-paths.diff added by jamit (12kB - text/x-patch - Revised find_routes() and associated structs)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by crab (Posted a comment)
  • -unavailable- added by boucman (Updated the item)
  • -unavailable- added by jamit (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 6 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Mon 15 Apr 2013 01:59:32 AM UTCjamitOpen/ClosedOpen=>Closed
    Sat 23 Feb 2013 01:15:26 AM UTCjamitStatusIn Progress=>Done
    Fri 22 Feb 2013 10:11:46 PM UTCjamitAssigned tocrab=>jamit
    Wed 08 Feb 2012 05:01:37 PM UTCcrabStatusNone=>In Progress
    Mon 06 Feb 2012 08:24:25 AM UTCboucmanAssigned toNone=>crab
    Sun 05 Feb 2012 08:57:14 PM UTCjamitAttached File-=>Added simpler-paths.diff, #15017
    Show feedback again

    Back to the top


    Powered by Savane 3.1-cleanup