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

Show feedback again

patch #3122: Simpler pathfinding

Submitted by:  J Tyne <jamit>
Submitted on:  Sun Feb 5 20:57:14 2012  
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 Feb 23 01:14:32 2013, 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 Feb 22 22:59:18 2013, SVN revision 56375:

Some variable name changes taken from patch #3122.

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

(Browse SVN revision 56375)

J Tyne <jamit>
Project MemberIn charge of this item.
Fri Feb 22 22:11:46 2013, 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 Feb 8 17:01:37 2012, comment #1:

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

Iurii Chernyi <crab>
Project Member
Sun Feb 5 20:57:14 2012, 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):

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.


    Error: not logged in



    Follow 6 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Mon Apr 15 01:59:32 2013jamitOpen/ClosedOpen=>Closed
    Sat Feb 23 01:15:26 2013jamitStatusIn Progress=>Done
    Fri Feb 22 22:11:46 2013jamitAssigned tocrab=>jamit
    Wed Feb 8 17:01:37 2012crabStatusNone=>In Progress
    Mon Feb 6 08:24:25 2012boucmanAssigned toNone=>crab
    Sun Feb 5 20:57:14 2012jamitAttached File-=>Added simpler-paths.diff, #15017
    Show feedback again

    Back to the top

    Powered by Savane 3.1-cleanup